Parallel Algorithms for Molecular Simulations
Team
Summary
Pair-potentials are ubiquitous in molecular simulations. In principle, such a potential implies that an atom or molecule interacts with all other ones that are inside a simulation box. But the resulting naive algorithm has a quadratic complexity, and it is therefore for most applications too expensive. Instead, the interaction is often restricted to a neighborhood of the atom or molecule.
In certain cases, however, leads the truncation of the potential to inaccurate results. An alternative path the provides accuracy combined with computational efficiency is the approximation of the full formulation. The nowadays most popular of such long-range methods are based on an approach introduced by Ewald in 1921. But there is a problem associated with the contemporary incarnations of this approach. All of them incorporate fast Fourier transforms (FFTs); thus, their complexity is O(N log N) and their performance degrades for large simulations as the communication becomes dominant. Therefore, there is the need within the community to investigate alternative long-range solvers.
One of these alternatives is the recently introduced multilevel summation method. The attractiveness of this method arises from the fact that it has a better complexity than the Ewald-based techniques: it scales linear in the number of atoms and molecules. Moreover, it avoids the FFTs completely, and its execution time is hence not dominated by communication for large systems. These two improvements compared to the state-of-the-art techniques make the multilevel summation method an attractive tool to tackle large scale problems.
Related Publications and Talks
Journal Article
- Multilevel Summation for Dispersion: A Linear-Time Algorithm for 1/r^6 PotentialsJournal of Chemical Physics, Volume 140, pp. 024105, January 2014.
@article{Tameling2014:590, author = "Daniel Tameling and Paul Springer and Paolo Bientinesi and {Ahmed E.} Ismail", title = "Multilevel Summation for Dispersion: A Linear-Time Algorithm for 1/r^6 Potentials", journal = "Journal of Chemical Physics", year = 2014, volume = 140, pages = 24105, month = jan, doi = "10.1063/1.4857735", url = "https://arxiv.org/pdf/1308.4005.pdf" }abstractwebPDFbibtexThe multilevel summation (MLS) method was developed to evaluate long-range interactions in molecular dynamics (MD) simulations. MLS was initially introduced for Coulombic potentials; we have extended this method to dispersion interactions. While formally short-ranged, for an accurate calculation of forces and energies in cases such as in interfacial systems, dispersion potentials require long-range methods. Since long-range solvers tend to dominate the time needed to perform MD calculations, increasing their performance is of vital importance. The MLS method offers some significant advantages when compared to mesh-based Ewald methods like the particle-particle particle-mesh and particle mesh Ewald methods. Unlike mesh-based Ewald methods, MLS does not use fast Fourier transforms and is thus not limited by communication and bandwidth concerns. In addition, it scales linearly in the number of particles, as compared to the O(N log N) complexity of the mesh-based Ewald methods. While the structure of the MLS method is invariant for different potentials, every algorithmic step had to be adapted to accommodate the 1/r^6 form of the dispersion interactions. In addition, we have derived error bounds, similar to those obtained by Hardy for the electrostatic MLS. Using a prototype implementation, we can already demonstrate the linear scaling of the MLS method for dispersion, and present results establishing the accuracy and efficiency of the method.
Technical Report
- A Note on Time Measurements in LAMMPSAachen Institute for Computational Engineering Science, RWTH Aachen, February 2016.
Technical Report AICES-2016/02-1.@techreport{Tameling2016:140, author = "Daniel Tameling and Paolo Bientinesi and {Ahmed E.} Ismail", title = "A Note on Time Measurements in LAMMPS", institution = "Aachen Institute for Computational Engineering Science, RWTH Aachen", year = 2016, month = feb, note = "Technical Report AICES-2016/02-1", url = "http://arxiv.org/abs/1602.05566" }abstractPDFbibtexWe examine the issue of assessing the efficiency of components of a parallel program at the example of the MD package LAMMPS. In particular, we look at how LAMMPS deals with the issue and explain why the approach adopted might lead to inaccurate conclusions. The misleading nature of this approach is subsequently verified experimentally with a case study. Afterwards, we demonstrate how one should correctly determine the efficiency of the components and show what changes to the code base of LAMMPS are necessary in order to get the correct behavior.
Talks
- Multilevel Summation for Dispersion: A Linear-Time Algorithm for 1/r^6 Potentials 2013 AIChE Annual Meeting.
San Francisco, USA, November 2013.abstractPDFThe multilevel summation method (MLS) was developed to evaluate long-range interactions in molecular dynamics (MD) simulations. Previously MLS was investigated in detail for the electrostatic potential by Hardy et al., and we have applied this new method to dispersion interactions. While dispersion interactions are formally short-ranged, long-range methods have to be used to calculate accurately dispersion forces in certain situations, such as in interfacial systems. Because long-range solvers tend to dominate the time needed to perform a step in MD calculations, increasing their performance is of vital importance. The multilevel summation method offers some significant advantages when compared to mesh-based Ewald methods like the particle-particle particle-mesh and particle mesh Ewald methods. Because, unlike mesh-based Ewald methods, the multilevel summation method does not use fast Fourier transforms, they are not limited by communication and bandwidth concerns. In addition, it scales linearly in the number of particles, as compared to the O(N log N) complexity of the mesh-based methods. While the structure of the Multilevel Summation is invariant for different potentials, every algorithmic step had to be adapted to accommodate the 1/r^6 form of the dispersion interactions. In addition, we have derived strict error bounds, similar to those obtained by Hardy for the electrostatic multilevel summation method. Using an unoptimized implementation in C++, we can already demonstrate the linear scaling of the multilevel summation method for dispersion, and present results that suggest it will be competitive in terms of accuracy and performance with mesh-based methods. - Multilevel Summation for Dispersion: A Linear-Time Algorithm for 1/r^6 PotentialsInternational Conference on Scientific Computation and Differential Equations (SciCADE).
Valladolid, Spain, September 2013.abstractPDFThe multilevel summation (MLS) method was developed to evaluate long-range interactions in molecular dynamics (MD) simulations. In MD the MLS was initially introduced for Coulombic potentials by Skeel et al., based on the multilevel matrix summation; we have extended the MLS to dispersion interactions. While formally short-ranged, dispersion potentials require long-range methods for accurate calculation of forces and energies in certain situations, such as in interfacial systems. Because long-range solvers tend to dominate the time needed to perform a step in MD calculations, increasing their performance is of vital importance. Because of its properties, the MLS is particularly attractive compared to other long-range solvers, e.g. the mesh-based Ewald and the fast Multipole methods. While the structure of the MLS is invariant for different potentials, every algorithmic step had to be adapted to accommodate the 1/r^6 form of the dispersion interactions.