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