Can I read A Simple Reduction of Non-uniformity in Dynamic Load Balancing of Quantized Loads on Hypercube Multiprocessors and Hiding Balancing Overheads on EtoBox?

A Simple Reduction of Non-uniformity in Dynamic Load Balancing of Quantized Loads on Hypercube Multiprocessors and Hiding Balancing Overheads by Hwakyung Rim; Ju-wook Jang; Sungchun Kim is a Computer Science article available to read on EtoBox.

What is A Simple Reduction of Non-uniformity in Dynamic Load Balancing of Quantized Loads on Hypercube Multiprocessors and Hiding Balancing Overheads about?

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 log N 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 J 1 2 log Nn: 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 c

Who reads A Simple Reduction of Non-uniformity in Dynamic Load Balancing of Quantized Loads on Hypercube Multiprocessors and Hiding Balancing Overheads?

Author

Hwakyung Rim; Ju-wook Jang; Sungchun Kim

Publisher

Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0022-0000)

Published

2003

Language

EN

Field

Computer Science (Physical Sciences)