On the convergence of SID and DASUD load-balancing algorithms

A.Cortés, A. Ripoll, M.A. Senar, F.Cedó and E. Luque

Abstract. Dynamic load balancing is essential for the efficient use of highly parallel systems when solving problems with unpredictable load estimates. We present a new fully distributed dynamic load-balancing algorithm for load balancing among the processors of an arbitrary interconnected network of processors. This algorithm called DASUD (Diffusion Algorithm Searching Unbalanced Domains) has been proposed to remedy the shortcoming experienced by other techniques when applied to non-divisible tasks. Since DASUD is iterative and runs in an asynchronous and distributed way, a mathematical model that describes DASUD behaviour has been proposed and has been used to prove DASUD’s convergence.

Key words. Dynamic load balancing, diffusion algorithms, nearest-neighbours algorithms, algorithm convergence, load balancing model.

Registration: PIRDI-8/98, October 1998.


Retrieve postScript document (pirdi8.ps: 896104 bytes)
Copyright © 1998 by Computer Science Department. UAB