On the convergence of distributed load balancing algorithms with integer
F. Cedó, A. Ripoll, A.Cortés, M.A. Senar and E. Luque
Abstract. There are several kinds of parallel programs for which
static mapping strategies are never going to be entirely satisfactory.
For example, a program may be strongly data-dependent, or it may exhibit
time varying patterns of activity. In this cases run time load-balancing
(called dynamic load-balancing) may produce an even distribution of the
tasks among the processors and reduce the execution time of the programs.
There have been several descriptions of distributed load-balancing algorithms
reported in the literature. They are based on the local evaluation of the
load on each processor, followed more or less by independents load movements.
By exploiting the fact that these load-balancing algorithms can be analytically
modeled, several theoretical works have been developed for their study
treating load as a continuos variable whereas in practice it has to be
moved in discrete units. In this paper we prove that partially asynchronous,
distributed, load-balancing algorithms with integer load are finite and
they conclude in a distribution of the load such that the difference between
the load of any two processors is upper-bounded by the diameter of the
Key words: Parallel processing, dynamic load-balancing model,
analysis of algorithms, convergence analysis.
Registration: PIRDI-2/00, February 2000.
Retrieve PostScript document (pirdi13.ps: 591872
Copyright © 2000 by Computer Science Department. UAB