Scalable algorithms for molecular dynamics simulations on commodity clusters

ABSTRACT

Although molecular dynamics (MD) simulations of biomolecular systems often run for days to months, many events of great scientific interest and pharmaceutical relevance occur on long time scales that remain beyond reach. We present several new algorithms and implementation techniques that significantly accelerate parallel MD simulations compared with current state-of-the-art codes. These include a novel parallel decomposition method and message-passing techniques that reduce communication requirements, as well as novel communication primitives that further reduce communication time. We have also developed numerical techniques that maintain high accuracy while using single precision computation in order to exploit processor-level vector instructions. These methods are embodied in a newly developed MD code called Desmond that achieves unprecedented simulation throughput and parallel scalability on commodity clusters. Our results suggest that Desmond's parallel performance substantially surpasses that of any previously described code. For example, on a standard benchmark, Desmond's performance on a conventional Opteron cluster with 2K processors slightly exceeded the reported performance of IBM's Blue Gene/L machine with 32K processors running its Blue Matter MD code.

REFERENCES

• 1: G. Almasi, C. Archer, J. G. Castanos, et al., Design and Implementation of Message-Passing Services for the Blue Gene/L Supercomputer, IBM J. Res. & Dev., 49(2-3): 393--406, 2005.
• 2: I. T. Arkin, H. Xu, K. J. Bowers, et al., Mechanism of a Na+/H+ Antiporter, submitted, 2006.
• 3: K. J. Bowers, Speed Optimal Implementation of a Fully Relativistic 3D Particle Push with a Charge Conserving Current Accumulate on Modern Processors, presented at 18th International Conference on the Numerical Simulation of Plasmas, Cape Cod, MA, 2003.
• 4: K. J. Bowers, R. O. Dror, and D. E. Shaw, Overview of Neutral Territory Methods for the Parallel Evaluation of Pairwise Particle Interactions, J. Phys. Conf. Ser., 16: 300--304, 2005.
• 5: K. J. Bowers, R. O. Dror, and D. E. Shaw, The Midpoint Method for Parallelization of Particle Simulations, J. Chem. Phys., 124: 184109, 2006.
• 6: K. J. Bowers, R. O. Dror, and D. E. Shaw, Zonal Methods for the Parallel Execution of Range-Limited N-Body Problems, in press, J. Comput. Phys., 2006.
• 7: B. R. Brooks, R. E. Bruccoleri, B. D. Olafson, et al., CHARMM: A Program for Macromolecular Energy, Minimization, and Dynamics Calculations, J. Comput. Chem., 4: 187--217, 1983.
• 8: C. L. Brooks, B. M. Pettit, and M. Karplus, Structural and Energetic Effects of Truncating Long Ranged Interactions in Ionic and Polar Fluids, J. Chem. Phys., 83(11): 5897--5908, 1985.
• 9: Franck Cappello , Daniel Etiemble, MPI versus MPI+OpenMP on IBM SP for the NAS benchmarks, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.12-es, November 04-10, 2000, Dallas, Texas, United States
• 10: D. A. Case, T. E. Cheatham, III, T. Darden, et al., The Amber Biomolecular Simulation Programs, J. Comput. Chem., 26(16): 1668--1688, 2005.
• 11: E. Chow and D. Hysom, Assessing Performance of Hybrid MPI/OpenMP Programs on SMP Clusters, Lawrence Livermore National Laboratory UCRL-JC-143957, 2001.
• 12: T. Darden, D. York, and L. Pedersen, Particle Mesh Ewald: An N Log(N) Method for Ewald Sums in Large Systems, J. Chem. Phys., 98(12): 10089--10092, 1993.
• 13: Y. Duan and P. A. Kollman, Pathways to a Protein Folding Intermediate Observed in a 1-Microsecond Simulation in Aqueous Solution, Science, 282(5389): 740--744, 1998.
• 14: M. Eleftheriou, B. G. Fitch, A. Rayshubskiy, et al., Scalable Framework for 3D FFTs on the Blue Gene/L Supercomputer: Implementation and Early Performance Measurements, IBM J. Res. & Dev., 49(2-3): 457--464, 2005.
• 15: B. G. Fitch, A. Rayshubskiy, M. Eleftheriou, et al., Blue Matter: Strong Scaling of Molecular Dynamics on Blue Gene/L, IBM RC23888, February 22, 2006.
• 16: B. G. Fitch, A. Rayshubskiy, M. Eleftheriou, et al., Blue Matter: Approaching the Limits of Concurrency for Classical Molecular Dynamics, IBM RC23956, May 12, 2006.
• 17: B. G. Fitch, A. Rayshubskiy, M. Eleftheriou, et al., Blue Matter: Strong Scaling of Molecular Dynamics on Blue Gene/L, IBM RC23688, August 5, 2005.
• 18: M. Frigo and S. G. Johnson, The Design and Implementation of FFTW3, Proceedings of the IEEE, 93(2): 216--231, 2005.
• 19: Robert S. Germain , Blake Fitch , Aleksandr Rayshubskiy , Maria Eleftheriou , Michael C. Pitman , Frank Suits , Mark Giampapa , T.J. Christopher Ward, Blue matter on blue gene/L: massively parallel computation for biomolecular simulation, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084888]
• 20: T. A. Halgren, MMFF VII. Characterization of MMFF94, MMFF94s, and Other Widely Available Force Fields for Conformational Energies and for Intermolecular-Interaction Energies and Geometries, J. Comput. Chem., 20(7): 730--748, 1999.
• 21: G. S. Heffelfinger, Parallel Atomistic Simulations, Comput. Phys. Commun., 128(1-2): 219--237, 2000.
• 22: W. L. Jorgensen, D. S. Maxwell, and J. Tirado-Rives, Development and Testing of the OPLS All-Atom Force Field on Conformational Energetics and Properties of Organic Liquids, J. Am. Chem. Soc., 118(45): 11225--11236, 1996.
• 23: P. A. Kollman, R. W. Dixon, W. D. Cornell, et al., "The Development/Application of a "Minimalist" Organic/Biomolecular Mechanic Forcefield Using a Combination of Ab Initio Calculations and Experimental Data," in Computer Simulation of Biomolecular Systems: Theoretical and Experimental Applications, W. F. van Gunsteren and P. K. Weiner, Eds. Dordrecht, Netherlands: ESCOM, 1997, 83--96.
• 24: S. Kumar, G. Almasi, C. Huang, et al., Achieving Strong Scaling with NAMD on Blue Gene/L, presented at IEEE International Parallel & Distributed Processing Symposium, Rhodes Island, Greece, 2006.
• 25: Jiuxing Liu , Jiesheng Wu , Sushmitha P. Kini , Pete Wyckoff , Dhabaleswar K. Panda, High performance RDMA-based MPI implementation over InfiniBand, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782855]
• 26: J. MacKerell, A. D., D. Bashford, M. Bellott, et al., All-Atom Empirical Potential for Molecular Modeling and Dynamics Studies of Proteins, J. Phys. Chem. B, 102(18): 3586--3616, 1998.
• 27: P. Mark and L. Nilsson, Structure and Dynamics of Liquid Water with Different Long-Range Interaction Truncation and Temperature Control Methods in Molecular Dynamics Simulations, J. Comput. Chem., 23(13): 1211--1219, 2002.
• 28: Mellanox Technologies, Mellanox IB-Verbs API (VAPI): Mellanox Software Programmer's Interface for InfiniBand Verbs, 2001.
• 29: Tetsu Narumi , Atsushi Kawai , Takahiro Koishi, An 8.61 Tflop/s molecular dynamics simulation for NaCl with a special-purpose computer: MDM, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.26-26, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582060]
• 30: J. Norberg and L. Nilsson, On the Truncation of Long-Range Electrostatic Interactions in DNA, Biophys. J., 79(3): 1537--1553, 2000.
• 31: V. S. Pande, I. Baker, J. Chapman, et al., Atomistic Protein Folding Simulations on the Submillisecond Time Scale Using Worldwide Distributed Computing, Biopolymers, 68(1): 91--109, 2003.
• 32: P. M. Papadopoulos, M. J. Katz, and G. Bruno, NPACI Rocks: Tools and Techniques for Easily Deploying Manageable Linux Clusters, Concurrency Comput. Pract. Ex., 15(7-8): 707--725, 2003.
• 33: M. Patra, M. Karttunen, T. Hyvönen, et al., Molecular Dynamics Simulations of Lipid Bilayers: Major Artifacts Due to Truncating Electrostatic Interactions, Biophys. J., 84: 3636--3645, 2003.
• 34: J. C. Phillips, R. Braun, W. Wang, et al., Scalable Molecular Dynamics with NAMD, J. Comput. Chem., 26(16): 1781--1802, 2005.
• 35: 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
• 36: Steve Plimpton, Fast parallel algorithms for short-range molecular dynamics, Journal of Computational Physics, v.117 n.1, p.1-19, March 1, 1995 [doi>10.1006/jcph.1995.1039 ]
• 37: S. Plimpton and B. Hendrickson, Parallel Molecular-Dynamics Simulations of Organic Materials, Int. J. Mod. Phys. C., 5(2): 295--298, 1994.
• 38: S. Plimpton and B. Hendrickson, A New Parallel Method for Molecular Dynamics Simulation of Macromolecular Systems, J. Comput. Chem., 17(3): 326--337, 1996.
• 39: W. R. P. Scott, P. H. Hünenberger, I. G. Tironi, et al., The GROMOS Biomolecular Simulation Program Package, J. Phys. Chem. A, 103(19): 3596--3607, 1999.
• 40: M. M. Seibert, A. Patriksson, B. Hess, et al., Reproducible Polypeptide Folding and Structure Prediction Using Molecular Dynamics Simulations, J. Mol. Biol., 354(1): 173--183, 2005.
• 41: Y. Shan, J. L. Klepeis, M. P. Eastwood, et al., Gaussian Split Ewald: A Fast Ewald Mesh Method for Molecular Simulation, J. Chem. Phys., 122: 054101, 2005.
• 42: Tom Shanley, Infiniband, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 43: D. E. Shaw, A Fast, Scalable Method for the Parallel Evaluation of Distance-Limited Pairwise Particle Interactions, J. Comput. Chem., 26(13): 1318--1328, 2005.
• 44: M. Snir, A Note on N-Body Computations with Cutoffs, Theor. Comput. Syst., 37: 295--318, 2004.
• 45: D. van der Spoel, E. Lindahl, B. Hess, et al., GROMACS: Fast, Flexible, and Free, Journal of Computational Chemistry, 26(16): 1701--1718, 2005.
• 46: Makoto Taiji , Tetsu Narumi , Yousuke Ohno , Noriyuki Futatsugi , Atsushi Suenaga , Naoki Takada , Akihiko Konagaya, Protein Explorer: A Petaflops Special-Purpose Computer System for Molecular Dynamics Simulations, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.15, November 15-21, 2003
• 47: R. Zhou and B. J. Berne, A New Molecular Dynamics Method Combining the Reference System Propagator Algorithm with a Fast Multipole Method for Simulating Proteins and Other Complex Systems, J. Chem. Phys., 103(21): 9444--9459, 1995.
• 48: R. Zhou, E. Harder, H. Xu, et al., Efficient Multiple Time Step Method for Use with Ewald and Particle Mesh Ewald for Large Biomolecular Systems, J. Chem. Phys., 115(5): 2348--2358, 2001.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Systems theory
      I.6.8 Types of Simulation
          Subjects: Parallel

General Terms:
Design, Theory