A symmetric transformation for 3-body potential molecular dynamics using force-decomposition in a heterogeneous distributed environment

ABSTRACT

Evaluating the Force Matrix constitutes the most computationally intensive part of a Classical Molecular Dynamics (MD) simulation. In three-body MD simulations, the total energy of the system is determined by the energy of every unique triple in the system and the force matrix is three-dimensional. The execution time of a three-body MD algorithm is thus proportional to the cube of the number of atoms in the system. Fortunately, there exist symmetries in the Force Matrix that can be exploited to improve the running time of the algorithm. While this optimization is straight forward to implement in the case of sequential code, it has proven to be nontrivial for parallel code even in a homogeneous environment.

In this paper, we present two force matrix transformations that are capable of exploiting the symmetries in a 3-body force matrix in both a homogeneous and a heterogeneous environment while balancing the load among all the participating processors. The first transformation distributes the number of interactions to be computed uniformly among all the slices of the force matrix along any of the axes. The transformed matrix can be scheduled using any well known heterogeneous slice-level scheduling technique. The second transformation distributes interactions to be computed uniformly over the entire volume of the force matrix allowing us to perform a block decomposition of the force matrix. The transformed force matrix can be scheduled by any block level scheduling algorithm. We also derive theoretical bounds for efficiency and load balance for our transformations and prove some interesting and useful properties of our transformations and evaluate their advantages and disadvantages. The performance of an MPI implementation of the transformations is studied in terms of the Step Time Variation Ratio (STVR) in a homogeneous and heterogeneous environment.

REFERENCES

• 1: M. P. Allen , D. J. Tildesley, Computer simulation of liquids, Clarendon Press, New York, NY, 1988
• 2: O. Beaumont, V. Boudet, F. Rastello, and Y. Robert. Partitioning a square into rectangles: NP-completeness and approximation algorithms. Algorithmica, 34:217--239, 2002.
• 3: T. W. Clark, R. v. Hanxleden, J. A. McCammon, and L. R. Scott. Parallelizing molecular dynamics using spatial decomposition. In Proceedings of the Scalable High-Performance Computing Conference, pages 95--102. IEEE Computer Soc. Press, 1994.
• 4: Phyllis E. Crandall , Michael J. Quinn, Three-dimensional grid partitioning for network parallel processing, Proceedings of the 22nd annual ACM computer science conference on Scaling up : meeting the challenge of complexity in real-world computing applications: meeting the challenge of complexity in real-world computing applications, p.210-217, March 08-10, 1994, Phoenix, Arizona, United States [doi>10.1145/197530.197612]
• 5: Bruce Hendrickson , Steve Plimpton, Parallel many-body simulations without all-to-all communication, Journal of Parallel and Distributed Computing, v.27 n.1, p.15-25, May 1995 [doi>10.1006/jpdc.1995.1068]
• 6: S. J. V. Novel force matrix transformations with optimal load-balance for 3-body potential based parallel molecular dynamics in a heterogeneous cluster environment. Technical Report TR-UNL-CSE-2007-0010, University of Nebraska-Lincoln, 2007.
• 7: A. Kalinov and S. Klimov. Multidimensional static block data decomposition for heterogeneous clusters. In R. Wyrzykowski, J. Dongarra, M. Paprzycki, and J. Wasniewski, editors, PPAM, volume 3019 of Lecture Notes in Computer Science, pages 907--914. Springer, 2003.
• 8: Jianhui Li , Zhongwu Zhou , Richard. J. Sadus, A Cyclic Force Decomposition Algorithm for Parallelising Three-Body Interactions in Molecular Dynamics Simulations, Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences - Volume 1 (IMSCCS'06), p.338-343, June 20-24, 2006 [doi>10.1109/IMSCCS.2006.3]
• 9: 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]
• 10: S. Gupta. Computing aspects of molecular dynamics simulations. In J. Comp. Phys. Comm., volume 70:243--270, 1992.
• 11: F. H. Stillinger and T. A. Weber. Computer simulation of local order in condensed phases of silicon. Physical Review B (Condensed Matter), 31:5262--5271, Apr. 1985.
• 12: J. V. Sumanth, D. R. Swanson, and H. Jiang. Performance and Cost Effectiveness of a Cluster of Workstations and MD-GRAPE 2 for MD Simulations. In M. Williams, editor, ISPDC, pages 244--249. IEEE Computer Society, 2003.
• 13: J. V. Sumanth, D. R. Swanson, and H. Jiang. Scheduling Many-Body Short Range MD Simulations on a Cluster of Workstations and Custom VLSI hardware. In L. Bougé and V. K. Prasanna, editors, HiPC, volume 3296 of Lecture Notes in Computer Science, pages 166--175. Springer, 2004.
• 14: Sumanth J.V. , David R. Swanson , Hong Jiang, Adaptive Load Balancing for Long-Range MD Simulations in A Distributed Environment, Proceedings of the 2006 International Conference on Parallel Processing, p.135-146, August 14-18, 2006 [doi>10.1109/ICPP.2006.17]
• 15: L. Verlet. Computer experiments on classical fluids i. thermodynamical properties of lennard-jones molecules. In Phys. Rev., volume 159:98--103, 1967.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING

General Terms:
Algorithms

Keywords:
grid computing, load balancing, molecular dynamics