Dynamic load balancing of SAMR applications on distributed systems

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%-46% as compared to using parallel DLB scheme which does not consider the heterogeneous and dynamic features of distributed systems.

REFERENCES

• 1: Dennis B. Gannon , Michael L. Norman , Nikos P. Chrisochoides , Scott B. Baden, Structured Adaptive Mesh Refinement (Samr) Grid Methods, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 2: M. J. Berger , P. Colella, Local adaptive mesh refinement for shock hydrodynamics, Journal of Computational Physics, v.82 n.1, p.64-84, May 1989 [doi>10.1016/0021-9991(89)90035-1]
• 3: Greg L. Bryan, Fluids in the universe: adaptive mesh refinement in cosmology, Computing in Science and Engineering, v.1 n.2, p.46-53, March-April 1999 [doi>10.1109/5992.753046]
• 4: Jian Chen , Valerie E. Taylor, Mesh partitioning for distributed systems, 1999
• 5: J. Chen and V. Taylor. ParaPART: Parallel Mesh Partitioning Tool for Distributed Systems. In Concurrency: Practice and Experience, 12:111-123, 2000.
• 6: Jian Chen , Valerie E. Taylor, Mesh Partitioning for Efficient Use of Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.67-79, January 2002 [doi>10.1109/71.980027]
• 7: G. Cybenko, Dynamic load balancing for distributed memory multiprocessors, Journal of Parallel and Distributed Computing, v.7 n.2, p.279-301, October 1989 [doi>10.1016/0743-7315(89)90021-X]
• 8: K. Dragon and J. Gustafson. A low-cost hypercube load balance algorithm. In Proc. Fourth Conf. Hypercubes, Concurrent Comput. and Appl., pages 583-590, 1989.
• 9: Robert Elsässer , Burkhard Monien , Robert Preis, Diffusive load balancing schemes on heterogeneous networks, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.30-38, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341805]
• 10: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 11: Globus Project Team. Globus Project. World Wide Web, http://www.globus.org, 1996.
• 12: Andrew S. Grimshaw , Wm. A. Wulf , CORPORATE The Legion Team, The Legion vision of a worldwide virtual computer, Communications of the ACM, v.40 n.1, p.39-45, Jan. 1997 [doi>10.1145/242857.242867]
• 13: W. Johnston, D. Gannon, and B. Nitzberg. Grids as Production Computing Environments: The Engineering Aspects of NASA's Information Power Grid. IEEE Computer Society Press, 1999.
• 14: The KeLP Programming System. World Wide Web, http://www-cse.ucsd.edu/groups/hpcl/scg/kelp.html.
• 15: Zhiling Lan , Valerie E. Taylor , Greg Bryan, Dynamic Load Balancing for Structured Adaptive Mesh Refinement Applications, Proceedings of the 2001 International Conference on Parallel Processing, p.571-579, September 03-07, 2001
• 16: Z. Lan, V. Taylor, and G. Bryan. Dynamic Load Balancing For Adaptive Mesh Refinement Applications: Improvements and Sensitivity Analysis. In Proc. of IASTED PDCS'2001, Anaheim, CA, 2001.
• 17: Frank C. H. Lin , Robert M. Keller, The gradient model load balancing method, IEEE Transactions on Software Engineering, v.13 n.1, p.32-38, Jan. 1987 [doi>10.1109/TSE.1987.232563]
• 18: MPICH Project Team. World Wide Web, http://www.niu.edu/mpi/.
• 19: Henry Joel Neeman , Michael Heath , Michael Norman, Autonomous hierarchical adaptive mesh refinement for multiscale simulations, 1996
• 20: M. Norman and G. Bryan. Cosmological adaptive mesh refinement. In Computational Astrophysics, 1998.
• 21: L. Oliker and R. Biswas. PLUM:parallel load balancing for adaptive refined meshes. In Journal of Parallel and Distributed Computing, 47(2):109-124, 1997.
• 22: Kirk Schloegel , George Karypis , Vipin Kumar, Multilevel diffusion schemes for repartitioning of adaptive meshes, Journal of Parallel and Distributed Computing, v.47 n.2, p.109-124, Dec. 15, 1997 [doi>10.1006/jpdc.1997.1410]
• 23: Shweta Sinha , Manish Parashar, Adaptive Runtime Partitioning of AMR Applications on Heterogeneous Clusters, Proceedings of the 3rd IEEE International Conference on Cluster Computing, p.435, October 08-11, 2001
• 24: A. Sohn and H. Simon. Jove: A dynamic load balancing framework for adaptive computations on an sp-2 distributed multiprocessor. In NJIT CIS Technical Report, New Jersey, 1994.
• 25: Rick Stevens , Paul Woodward , Tom DeFanti , Charlie Catlett, From the I-WAY to the National Technology Grid, Communications of the ACM, v.40 n.11, p.50-60, Nov. 1997 [doi>10.1145/265684.265692]
• 26: C. Walshaw. Jostle:partitioning of unstructured meshes for massively parallel machines. In Proc. Parallel CFD'94, 1994.
• 27: M. H. Willebeek-LeMair , A. P. Reeves, Strategies for Dynamic Load Balancing on Highly Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.979-993, September 1993 [doi>10.1109/71.243526]
• 28: R. Wolski. Dynamically Forcasting Network Performance using the Network Weather Service. Technical Report CS-96-494, U.C. San Diego, 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance

Keywords:
adaptive mesh refinement, distributed systems, dynamic load balancing, dynamic network loads, heterogeneity