Title

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

Authors

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