 |
|
|||
| Authors: | Stefan Bischof, Ralf Ebner, Thomas Erlebach |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | Load Balancing for Problems with Good Bisectors, and Applications in Finite Element Simulations |
| Year: | 1998 |
| Pub-Key: | BEE98 |
| Book Titel: | Lecture Notes in Computer Science. 4th International Euro-Par Conference on Parallel Processing (EURO-PAR 98) |
| Volume: | 1470 |
| Pages: | 383-389 |
| Keywords: | load balancing |
| Publisher: | Springer-Verlag |
| Abstract: | This paper studies load balancing issues for classes of problems with certain bisection properties. A class of problems has alpha-bisectors if every problem in the class can be subdivided into two subproblems whose weight is not smaller than an alpha-fraction of the original problem. It is shown that the maximum weight of a subproblem produced by Algorithm HF, which partitions a given problem into N subproblems by always subdividing the problem with maximum weight, is at most a factor of floor(1/alpha)*(1-alpha)floor(1/alpha)-2 greater than the theoretical optimum (uniform partition). This bound is proved to be asymptotically tight. Two strategies to use Algorithm HF for load balancing distributed hierarchical finite element simulations and experimental results are presented. For this purpose, a certain class of weighted binary trees representing the load of such applications is shown to have 1/4-bisectors. This establishes a performance guarantee of 9/4 for load balancing in this case. |
| Location: | Southampton, UK |
| Resources: | [BibTeX] |
