An asynchronous algorithm for balancing unpredictable workload on distributed-memory machines

It is challenging to parallelize problems with irregular computation and co mmunication. In this paper, we propose an asynchronous algorithm for balanc ing unpredictable workload on distributed-memory machines. By using an init ial workload estimate, we first partition the computations such that the wo rkload is distributed evenly across the processors. In addition, we perform task migrations dynamically for adapting to the evolving workload. To demo nstrate the usefulness of our load balancing strategy, we conducted experim ents on an IBM SP2 and a Gray 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 machine s.