KIT | KIT-Bibliothek | Impressum
Open Access Logo
URN: urn:nbn:de:swb:90-AAA87946

Analysis of random polling dynamic load balancing

Sanders, Peter


Dynamic load balancing is crucial for the performance of many
parallel algorithms. Random Polling, a simple randomized
algorithm,has proved to be very efficient in practice for
applications like parallel depth first search. This paper derives
tight bounds for the scalability of Random Polling which are for
the first time able to explain its superior performance
analytically. In some cases, Random Polling even turns out to be
optimal. The analysis is based on a fairly general model of the
application and the parallel machine. Some of the proof-techniques
used might also turn out be useful for the analysis of other
parallel algorithms. Finally, a simple initialization scheme is
presented which vastly improves the algorithm's performance during
the startup phase.

Zugehörige Institution(en) am KIT Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.)
Publikationstyp Buch
Jahr 1994
Sprache Englisch
Identifikator URN: urn:nbn:de:swb:90-AAA87946
KITopen ID: 8794
Erscheinungsvermerk Karlsruhe 1994. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1994,12.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page