Open AccessAn Asynchronous Algorithm for Balancing Unpredictable Workload on Distributed‐Memory Machines
Author(s) -
Chung Yongwha,
Park JinWon,
Yoon SukHan
Publication year - 1998
Publication title -
etri journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.295
H-Index - 46
eISSN - 2233-7326
pISSN - 1225-6463
DOI - 10.4218/etrij.98.0198.0403
Subject(s) - workload , computer science , asynchronous communication , partition (number theory) , load balancing (electrical power) , parallel computing , distributed computing , computation , ibm , task (project management) , distributed memory , shared memory , operating system , algorithm , computer network , engineering , materials science , geometry , mathematics , systems engineering , combinatorics , nanotechnology , grid
It is challenging to parallelize problems with irregular computation and communication. In this paper, we propose an asynchronous algorithm for balancing unpredictable workload on distributed‐memory machines. By using an initial workload estimate, we first partition the computations such that the workload is distributed evenly across the processors. In addition, we perform task migrations dynamically for adapting to the evolving workload. To demonstrate the usefulness of our load balancing strategy, we conducted experiments on an IBM SP2 and a Cray T3D. Experimental results show that our task migration strategy can balance unpredictable workload with little overhead. Our code using C and MPI is portable onto other distributed‐memory machines.