Precomputation-based Load Balancing

Böhm, Max and Speckenmeyer, Ewald (1997) Precomputation-based Load Balancing.
Published In: Proceedings of the 4th Workshop on Parallel Systems & Algorithms, PASA '96 : Research Center Jülich, Germany, 10 - 12 April 1996 World Scientific 1997, pp. 177-194.


An algorithm, called PLB is introduced, which redistributes workload in a processor network N in order to supply every processor of N with (about) the same amount of workload. PLB is defined in its basic form for trees, but can be extended to other topologies. The redistribution is done locally on the basis of information of over- or underload in subnetworks of N. We show, that PLB performs O(d) steps, only, where d denotes the diameter of N, and in the average case at most four times as many workload has to be migrated in complete binary trees compared to clique networks, the best possible networks. We describe an implementation of PLB and present experimental results when solving the Boolean satisfiability problem, demonstrating that PLB performs very well in practice.

Download: [img] Postscript - Preprinted Version
Download (243kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-219
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:46