Abstract
We provide a theoretical analysis of the communication requirements of parallel algorithms for molecular dynamic simulations. We describe two commonly used algorithms, space decomposition and force decomposition, and analyze their communication requirements; each is better in a distinct computation regime. We next introduce a new hybrid algorithm that further reduces communication. We show that the new algorithm is optimal, by providing a matching lower bound.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M.P. Allen and D.J. Tildesley. Computer Simulation of Liquid}. Oxford Science Publications, Oxford, 1987.
G.S. Almasi C. Cascaval J.G. Castaños M. Denneau et al. (2002) ArticleTitleDemonstrating the scalability of a molecular dynamics application on a petaflop computer Journal of Parallel Programming 30 317–351 Occurrence Handle10.1023/A:1019856029918 Occurrence Handle1012.68048
A.Bar-Noy and S.Kipnis. Designing broadcasting algorithms in the postal model for message-passing systems. In Proceedings of the 4th Annual Symposium on Parallel Algorithms and Architectures, pages 13–22, 1992.
J. Board K. Schulten (2000) ArticleTitleThe fast multipole algorithm IEEE Computational Science & Engineering 2 56–59
Yu.D. Burago and V.A. Zalgaller. \Geometric Inequalities}. Springer-Verlag, Berlin, 1988.
M.T. Dickerson D. Eppstein (1996) ArticleTitleAlgorithms for proximity problems in higher dimensions Computational Geometry Theory and Applications 5 277–291
P. Ewald (192) ArticleTitleDie Berechnung optischer und elektrostatischer Gitterpotentiale Annalen der Physik 64 253–287 Occurrence Handle48.0566
L.F. Greengard. The Rapid Evaluation of Potential Fields in Particle Systems. MIT Press, Cambridge, MA, 1988.
L. Greengard V. Rokhlin (1987) ArticleTitleA fast algorithm for particle simulation Journal of Computational Physics 73 325–348
R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995.
S. Plimpton (1995) ArticleTitleFast parallel algorithms for short-range molecular dynamics Journal of Computational Physics 117 1–19
M. Snir. A note on n-body computation with cutoffs. Technical Report RC22059, IBM T. J. Watson Research Center, 2001.
V.E. Taylor R. Stevens K. Arnold (1997) ArticleTitleParallel molecular dynamics: implications for massively parallel machines Journal on Parallel and Distributed Computin 45 166–175
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Snir, M. A Note on N-Body Computations with Cutoffs. Theory Comput Systems 37, 295–318 (2004). https://doi.org/10.1007/s00224-003-1071-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-003-1071-0