Dynamic topology aware load balancing algorithms for molecular dynamics applications

ABSTRACT

Molecular Dynamics applications enhance our understanding of biological phenomena through bio-molecular simulations. Large-scale parallelization of MD simulations is challenging because of the small number of atoms and small time scales involved. Load balancing in parallel MD programs is crucial for good performance on large parallel machines. This paper discusses load balancing algorithms deployed in a MD code called NAMD. It focuses on new schemes deployed in the load balancers and provides an analysis of the performance benefits achieved. Specifically, the paper presents the technique of topology-aware mapping on 3D mesh and torus architectures, used to improve scalability and performance. These techniques have a wide applicability for latency intolerant applications.

REFERENCES

• 1: Laxmikant Kalé , Robert Skeel , Milind Bhandarkar , Robert Brunner , Attila Gursoy , Neal Krawetz , James Phillips , Artiomo Shinozaki , Krishnan Varadarajan , Klaus Schulten, NAMD2: greater scalability for parallel molecular dynamics, Journal of Computational Physics, v.151 n.1, p.283-312, May 1, 1999 [doi>10.1006/jcph.1999.6201]
• 2: Kevin J. Bowers , Edmond Chow , Huafeng Xu , Ron O. Dror , Michael P. Eastwood , Brent A. Gregersen , John L. Klepeis , Istvan Kolossvary , Mark A. Moraes , Federico D. Sacerdoti , John K. Salmon , Yibing Shan , David E. Shaw, Scalable algorithms for molecular dynamics simulations on commodity clusters, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188544]
• 3: Blake G. Fitch , Aleksandr Rayshubskiy , Maria Eleftheriou , T. J. Christopher Ward , Mark Giampapa , Michael C. Pitman , Robert S. Germain, Blue matter: approaching the limits of concurrency for classical molecular dynamics, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188547]
• 4: S. J. Plimpton and B. A. Hendrickson. A new parallel method for molecular-dynamics simulation of macromolecular systems. J Comp Chem, 17:326--337, 1996.
• 5: James C. Phillips , Gengbin Zheng , Sameer Kumar , Laxmikant V. Kalé, NAMD: biomolecular simulation on thousands of processors, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-18, November 16, 2002, Baltimore, Maryland
• 6: Abhinav Bhatele, Sameer Kumar, Chao Mei, James C. Phillips, Gengbin Zheng, and Laxmikant V. Kale. Overcoming Scaling Challenges in Biomolecular Simulations across Multiple Platforms. In Proceedings of IEEE International Parallel and Distributed Processing Symposium 2008, April 2008.
• 7: Laxmikant V. Kale , Sanjeev Krishnan, CHARM++: a portable concurrent object oriented system based on C++, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.91-108, September 26-October 01, 1993, Washington, D.C., United States
• 8: Laxmikant V. Kalé , Milind A. Bhandarkar , Robert Brunner, Load Balancing in Parallel Molecular Dynamics, Proceedings of the 5th International Symposium on Solving Irregularly Structured Problems in Parallel, p.251-261, August 09-11, 1998
• 9: T. P. Straatsma , J. A. McCammon, Load balancing of molecular dynamics simulation with NWChem, IBM Systems Journal, v.40 n.2, p.328-341, February 2001
• 10: S. H. Bokhari, On the Mapping Problem, IEEE Transactions on Computers, v.30 n.3, p.207-214, March 1981 [doi>10.1109/TC.1981.1675756]
• 11: P. Sadayappan , F. Ercal, Nearest-neighbor mapping of finite element graphs onto processor meshes, IEEE Transactions on Computers, v.36 n.12, p.1408-1424, Dec. 1987 [doi>10.1109/TC.1987.5009494]
• 12: Francois Gygi , Erik W. Draeger , Martin Schulz , Bronis R. de Supinski , John A. Gunnels , Vernon Austel , James C. Sexton , Franz Franchetti , Stefan Kral , Christoph W. Ueberhuber , Juergen Lorenz, Large-scale electronic structure calculations of high-Z metals on the BlueGene/L platform, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188502]
• 13: Hideaki Kikuchi, Bijaya B. Karki, and Subhash Saini. Topology-aware parallel molecular dynamics simulation algorithm. In PDPTA, pages 1083--1088, 2006.
• 14: Abhinav Bhatelé and Laxmikant V. Kalé. Benefits of Topology Aware Mapping for Mesh Interconnects. Parallel Processing Letters (Special issue on Large-Scale Parallel Processing), 18(4):549--566, 2008.
• 15: Peter L. Freddolino, Anton S. Arkhipov, Steven B. Larson, Alexander McPherson, and Klaus Schulten. Molecular dynamics simulations of the complete satellite tobacco mosaic virus. 14:437--449, 2006.
• 16: Abhinav Bhatele and Laxmikant V. Kale. An Evaluation of the Effect of Interconnect Topologies on Message Latencies in Large Supercomputers. In Proceedings of Workshop on Large-Scale Parallel Processing (IPDPS '09), May 2009.
• 17: S. Kumar , C. Huang , G. Zheng , E. Bohm , A. Bhatele , J. C. Phillips , H. Yu , L. V. Kalé, Scalable molecular dynamics with NAMD on the IBM Blue Gene/L system, IBM Journal of Research and Development, v.52 n.1/2, p.177-188, January 2008
• 18: Gengbin Zheng , Laxmikant V. Kale, Achieving high performance on extremely large parallel machines: performance prediction and load balancing, University of Illinois at Urbana-Champaign, Champaign, IL, 2005

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Algorithms, Performance

Keywords:
load balancing, mapping, mesh, topology, torus