An efficient dynamic load balancing using the dimension exchange method for balancing of quantized loads on hypercube multiprocessors

Abstract

Dynamic load balancing on hypercube multiprocessors is considered with emphasis on quantized loads. Quantized loads are divisible only in a fixed size. First, we show that a direct application of the well-known Dimension Exchange Method (DEM) to quantized loads may result in difference in assigned loads to processors as large as log N units after balancing for a hypercube of size N. Then we propose a new method which reduces the maximum difference by half to [1/2 log N]. The claim is proved both by analysis of possible cases incrementing the difference on each phase of balancing and by enumerating all possible combination of load for hypercubes of limited sizes using a computer. To estimate the accumulated effect of balancing instances under real-world parallel processing environment, a simulation for hypercube multiprocessors using SLAM II tool is performed. The result shows about 30% improvement in speedup which results from reduced processing time, which in turn results from reduced nonuniformity.