Load Balancing for Problems with Good Bisectors, and Applications in Finite Element Simulations: Worst-case Analysis and Practical Results

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.     «

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...     »