Universität zu Köln

Böhm, Max and Speckenmeyer, Ewald (1997). Precomputation-based Load Balancing. World Scientific. ["eprint_fieldopt_monograph_type_preprint" not defined].

Preview

PDF zpr96-219.pdf Download (238kB) | Preview

Abstract

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.

Item Type:	Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:	Creators Email ORCID ORCID Put Code Böhm, Max UNSPECIFIED UNSPECIFIED UNSPECIFIED Speckenmeyer, Ewald UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-547066
Page Range:	pp. 177-194
Date:	1997
Publisher:	World Scientific
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54706