| Abstract |
|---|
| 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. 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 greater than the theoretical optimum by at most a small factor depending only on alpha. This bound is tight. Two strategies to use Algorithm HF for load balancing distributed hierarchical FE simulations are presented. The class of weighted binary trees representing the load of such applications has (1/4)-bisectors, giving a performance guarantee of 9/4 for load balancing. |
| Contact |
| Stefan Bischof Institut fuer Informatik, Technische Universitaet Muenchen, 80290 Muenchen, Germany, bischof@informatik.tu-muenchen.de |