Parallel Load Balancing for Problems with Good Bisectors

✍ Scribed by Stefan Bischof; Ralf Ebner; Thomas Erlebach

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 264 KB
• Volume: 60
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2000.1647

✦ Synopsis

Parallel load balancing is studied for problems with certain bisection properties. A class of problems has :-bisectors if every problem p of weight w( p) in the class can be subdivided into two subproblems whose weight (load) is at least an :-fraction of the original problem. A problem p is to be split into N subproblems such that the maximum weight among them is as close to w( p)ÂN as possible. It was previously known that good load balancing can be achieved for such classes of problems using Algorithm HF, a sequential algorithm that repeatedly bisects the subproblem with maximum weight. Several parallel variants of Algorithm HF are introduced and analyzed with respect to worst-case load imbalance, running-time, and communication overhead. For fixed :, all variants have running-time O(log N) and provide constant upper bounds on the worst-case load imbalance. Results of simulation experiments regarding the load balance achieved in the average case are presented.