A simple reduction of non-uniformity in dynamic load balancing of quantized loads on hypercube multiprocessors and hiding balancing overheads

摘要

We reconsider the dimension exchange method (DEM), a known dynamic load balancing scheme on hypercube multiprocessors, for its inefficiency when the load is not divisible in arbitrary sizes but divisible only in a fixed size. We show that a direct application of the DEM to this kind of load may result in nonuniformity (the maximum difference in assigned units of load among the processors after balancing) as large as logN for a hypercube of size N. Since the processing time after the balancing depends on the processor with the maximum number of units, it is desirable to reduce the nonuniformity as small as possible. In this paper, we propose a new simple method, odd even method (OEM), which reduces the nonuniformity to no more than ⌈12logN⌉. The claim is proved and confirmed by enumerating all possible combinations of load for hypercubes of limited sizes using a computer. To estimate the accumulated effect of our balancing method 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 in overall processing. In addition, we introduce new techniques for hiding communication overheads involved in balancing. The basic idea is coalescing some phases of balancing to overlap or pipeline the transmission of load whenever possible. They proved effective in making links busy transmitting load as soon as possible, thus reducing the transmission time. It is shown via simulation that pipelining is powerful even in the presence of severe unevenness of initial load distribution. Combined together, proposed techniques reduce (hide) communication overheads by 15–50% depending on initial load distribution.