Abstract
We have parallelized the fast multipole method (FMM) on multicore computers using OpenMP programming model. The FMM is the one of the fastest approximate force calculation algorithms for molecular dynamics simulations. Its computational complexity is linear. Parallelization of FMM on multicore computers using OpenMP has been reported since the multicore processors become increasingly popular. However the number of those FMM implementations is not large. The main reason is that those FMM implementations have moderate or low parallel efficiency for high expansion orders due to sophisticated formulae of the FMM. In addition, parallel efficiency of those implementations for high expansion orders rapidly drops to 40% or lower as the number of threads increases to 8 or higher. Our FMM implementation on multicore computers using a combination approach as well as a newly developed formula and a computational procedure (A2P) solved the above issues. Test results of our FMM implementation on a multicore computer show that our parallel efficiency with 8 threads is at least 70% for moderate and high expansion orders pā=ā4,5,6,7. Moreover, the parallel efficiency for moderate and high expansion orders gradually drops from 96% to 70% as the number of threads increases.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Haile, M.: Molecular dynamics simulation: Elementary methods. Wiley-Interscience (1997)
Rappaport, D.C.: The art of molecular dynamics simulation, 2nd edn. Cambridge University Press (2004)
Satou, A.: Introduction to Practice of Molecular Simulation: Molecular Dynamics, Monte Carlo, Brownian Dynamics, Lattice Boltzmann and Dissipative Particle Dynamics. Elsevier (2010)
Griebel, M.: Numerical Simulation in Molecular Dynamics: Numerics, Algorithms, Parallelization, Applications. Springer (2010)
Barnes, J.E., Hut, P.: A hierarchical O(NlogN) force calculation algorithm. NatureĀ 324, 446ā449 (1986)
Barnes, J.E.: A modified tree code: Donāt laugh, it runs. Journal of Computational PhysicsĀ 87, 161ā170 (1990)
Greengard, L., Rokhlin, V.: A fast algorithm for particle simulations. Journal of Computational PhysicsĀ 73, 325ā348 (1987)
Greengard, L., Rokhlin, V.: A new version of the fast multipole method for the Laplace equation in three dimensions. Acta NumericaĀ 6, 229ā269 (1997)
Cheng, H., Greengard, L., Rokhlin, V.: A fast adaptive multipole algorithm in three dimensions. Journal of computational physicsĀ 155, 468ā498 (1999)
Lupo, J.A., Wang, Z.Q., McKenney, A.M., Pachter, R., Mattson, W.: A large scale molecular dynamics simulation code using the fast multipole algorithm (FMD): performance and application. Journal of Molecular Graphics and ModellingĀ 21, 89ā99 (2002)
Gumerov, N.A., Duraiswami, R., Zotkin, D.N., Fantalgo, M.D.: Fast Multipole Accelerated Boundary Elements for Numerical Computation of the Head Related Transfer Function. In: IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2007 (2007)
Gumerov, N.A., Duraiswami, R.: Efficient FMM accelerated vortex methods in three dimensions via the Lamb-Helmholtz decomposition. Submitted to Journal of Computational Physics, arXiv:1201.5430
Pan, X.M., Pi, W.C., Sheng, X.Q.: On OpenMP parallelization of the multilevel fast multipole algorithm. Progress in Electromagnetics ResearchĀ 112, 199ā213 (2011)
Yokota, R., Barba, L.: A Tuned and Scalable Fast Multipole Method as a Preeminent Algorithm for Exascale Systems, arXiv:1106.2176v2 [cs.NA] (2011)
Anderson, C.R.: An implementation of the fast multipole method without multipoles. SIAM Journal on Scientific and Statistical ComputingĀ 13(4), 923ā947 (1992)
Hardin, R.H., Sloane, N.J.A.: McLarenās improved snub cube and other new spherical design in three dimensions. Discrete and Computational GeometryĀ 15, 429ā441 (1996)
Makino, J.: Yet another fast multipole method without multipoles - pseudoparticle multipole method. Journal of Computational PhysicsĀ 151, 910ā920 (1999)
Kawai, J.M.: Pseudoparticle multipole method: A simple method to implement a high-accuracy treecode. The Astrophysical JournalĀ 550, L143āL146 (2001)
Chau, N.H., Kawai, A., Ebisuzaki, T.: Implementation of fast multipole algorithm on special-purpose computer MDGRAPE-2. In: Proceedings of the 6th World Multiconference on Systemics, Cybernetics and Informatics, SCI 2002, Orlando, Colorado, USA, July 14-18, pp. 477ā481 (2002)
Chau, N.H., Kawai, A., Ebisuzaki, T.: Acceleration of fast multipole method using special-purpose computer GRAPE. International Journal of High Performance Computing ApplicationsĀ 22(2), 194ā205 (2008)
Chau, N.H.: A new formulation for fast calculation of far field force in molecular dynamics simulations. Journal of Science (Mathematics-Physics)Ā 23(1), 1ā8 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
Ā© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Chau, N.H. (2013). Parallelization of the Fast Multipole Method for Molecular Dynamics Simulations on Multicore Computers. In: Nguyen, N., van Do, T., le Thi, H. (eds) Advanced Computational Methods for Knowledge Engineering. Studies in Computational Intelligence, vol 479. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-00293-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-00293-4_16
Publisher Name: Springer, Heidelberg
Print ISBN: 978-3-319-00292-7
Online ISBN: 978-3-319-00293-4
eBook Packages: EngineeringEngineering (R0)