Parallel load balancing for problems with good bisectors

Parallel load balancing is studied for problems with certain bisection prop erties. A class of problems has cc-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 a-fraction of the original problem. A problem p is to be sp lit 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. Sever al parallel variants of Algorithm HF are introduced and analyzed with respe ct to worst-case load imbalance, running-time, and communication overhead. For fixed alpha, all variants have running-time O(log N) and provide consta nt upper bounds on the worst-case load imbalance. Results of simulation exp eriments regarding the load balance achieved in the average case are presen ted. (C) 2000 Academic Press.