On the convergence of distributed load balancing algorithms with integer
load.
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 datadependent, or it may exhibit
time varying patterns of activity. In this cases run time loadbalancing
(called dynamic loadbalancing) 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 loadbalancing 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 loadbalancing 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, loadbalancing 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 upperbounded by the diameter of the
topology.
Key words: Parallel processing, dynamic loadbalancing model,
analysis of algorithms, convergence analysis.
Registration: PIRDI2/00, February 2000.

Retrieve PostScript document (pirdi13.ps: 591872
bytes)

Copyright © 2000 by Computer Science Department. UAB