 |
|
|||
| Authors: | Stefan Bischof, Ralf Ebner, Thomas Erlebach |
| Group: | Theory of Communication Networks |
| Type: | Article |
| Title: | Parallel Load Balancing for Problems with Good Bisectors |
| Year: | 2000 |
| Month: | September |
| Pub-Key: | BEE00 |
| Journal: | Journal of Parallel and Distributed Computing |
| Volume: | 60 |
| Number: | 9 |
| Pages: | 1047-1073 |
| Abstract: | Parallel load balancing is studied for problems with certain bisection properties. A class of problems has alpha-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 alpha-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 alpha, 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. |
| Resources: | [BibTeX] |
