An asynchronous and iterative load balancing algorithm for discrete load model

Research output: Contribution to journalArticleResearchpeer-review

30 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)1729-1746
JournalJournal of Parallel and Distributed Computing
Volume62
DOIs
Publication statusPublished - 1 Dec 2002

Fingerprint Dive into the research topics of 'An asynchronous and iterative load balancing algorithm for discrete load model'. Together they form a unique fingerprint.

Cite this