Dynamic Load Balancing In Very Large Shared-Nothing Hypercube Database-Computers

    Authors

    K. A. Hua;J. X. W. Su

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    IEEE Trans. Comput.

    Keywords

    Database Machines; Hypercube; Load Balancing; Parallel Join; Relational; Database; System; Computer Science, Hardware & Architecture; Engineering, Electrical &; Electronic

    Abstract

    A consensus on parallel architecture for database management has emerged. This architecture is based on a shared-nothing (message passing) hardware organization. Various network topologies can be used to implement this structure. Among them, hypercube is widely used for many commercial highly parallel systems such as Intel iPSC/2 and nCUBE nCUBE/2. The availability of these machines has spurred a great interest in developing database management systems for this structure. Recently, two relational join strategies, Broadcast-Based Join and Bucket-Based Join, have been proposed specifically for the hypercube interconnection topology. The first strategy, however, incurs many unnecessary comparisons of pairs of tuples of the two relations. Although the second technique compares only tuples of the relevant buckets, it may suffer from potential load imbalance which is most critical to the performance of a shared-nothing system. This paper deals with these issues. In particular, we propose a novel join algorithm, for hypercube computers, which includes dynamic load balancing capabilities to minimize the effect of skewness in tuple distribution. Our simulation results indicate that the proposed scheme provides significant improvement over the Bucket-Based Join strategy. It is also interesting to observe that our technique is consistently superior even when the skew condition is very mild.

    Journal Title

    Ieee Transactions on Computers

    Volume

    42

    Issue/Number

    12

    Publication Date

    1-1-1993

    Document Type

    Article

    Language

    English

    First Page

    1425

    Last Page

    1439

    WOS Identifier

    WOS:A1993MP62800002

    ISSN

    0018-9340

    Share

    COinS