An asynchronous and iterative load balancing algorithm for discrete load model

Producció científica: Contribució a una revistaArticleRecercaAvaluat per experts

31 Cites (Scopus)

Resum

Diffusion algorithms are some of the most popular algorithms for dynamic load balancing in which loads move from heavily loaded processors to lightly loaded neighbor processors. To achieve a global load balance in a parallel computer, the algorithm is iterated until the load difference between any two processors is smaller than a specified value. Therefore, one fundamental property to be studied is algorithm convergence. Several analytical works on the convergence of different diffusion load balancing algorithms have been carried out, but they treat loads as non-negative real quantities. In this paper, we describe the Diffusion Algorithm Searching Unbalanced Domains (DASUD) algorithm, which uses loads as non-negative integer values and, unlike existing algorithms, reaches a local balance situation where the maximum load difference between any two processor in the set of neighbor processors for each processor is one load unit. The convergence property of an asynchronous implementation of DASUD using integer loads is proven theoretically. © 2002 Elsevier Science (USA). All rights reserved.
Idioma originalEnglish
Pàgines (de-a)1729-1746
RevistaJournal of Parallel and Distributed Computing
Volum62
DOIs
Estat de la publicacióPublicada - 1 de des. 2002

Fingerprint

Navegar pels temes de recerca de 'An asynchronous and iterative load balancing algorithm for discrete load model'. Junts formen un fingerprint únic.

Com citar-ho