Affiliations: Department of Computer Science, Illinois Institute of
Technology, Chicago, IL 60616, USA. E-mail: lan@iit.edu | Department of Electrical and Computer Engineering,
Northwestern University, Evanston, IL 60208, USA. E-mail:
taylor@ece.nwu.edu | Nuclear and Astrophysics Laboratory, Oxford
University, Oxford, OX13RH, UK. E-mail: gbryan@astro.ox.ac.uk
Abstract: Dynamic load balancing(DLB) for parallel systems has been studied
extensively; however, DLB for distributed systems is relatively new. To
efficiently utilize computing resources provided by distributed systems, an
underlying DLB scheme must address both heterogeneous and dynamic features of
distributed systems. In this paper, we propose a DLB scheme for Structured
Adaptive Mesh Refinement(SAMR) applications on distributed systems. While the
proposed scheme can take into consideration (1) the heterogeneity of processors
and (2) the heterogeneity and dynamic load of the networks, the focus of this
paper is on the latter. The load-balancing processes are divided into two
phases: global load balancing and local load balancing. We also
provide a heuristic method to evaluate the computational gain and
redistribution cost for global redistribution. Experiments show that by using
our distributed DLB scheme, the execution time can be reduced by 9%- to using
parallel DLB scheme which does not consider the heterogeneous and dynamic
features of distributed systems.
