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 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 topology.

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 bytes)
Copyright © 2000 by Computer Science Department. UAB