Comparison of the Verlet table and cell-linked list algorithms for sequential, vectorized and multithreaded implementations

Authors

  • E.S. Fomin Institute of Cytology and Genetics of SB RAS (ICG SB RAS)

Keywords:

Verlet table method, cell-linked list method, nearest neighbor search, SIMD, multithreading

Abstract

Neighbor search algorithms are widely used in molecular dynamics for the direct computation of short-range inter-atomic potentials. These algorithms are based on the Verlet table (VT) or cell-linked list (CLL) methods. In this work, we have analyzed some features of these methods and found that for a dense system, such as water, the CLL reduces both the memory size and the number of data transfer operations significantly in comparison with the IVT and it can be efficiently used for parallel implementation. A new technique for parallelizing short-range interactions referred to as dynamic spatial decomposition is proposed for the CLL approach. It has been shown that the CLL method, especially its version improved by P.~Gonnet, outperforms the VT by up to 40% or more in parallel SIMD implementations in spite of a large number of unnecessary inter-particle distance calculations. The efficiency gain is achieved due to the fact that the CLL is more suitable for modern multi-core SIMD processors. The methods were tested in the MOLKERN simulation software.

Author Biography

E.S. Fomin

References

  1. Allen M.P., Tildesley D.J. Computer simulation of liquids. New York: Oxford University Press, 1990.
  2. Yao Z., Wang J.-S., Liu G.-R., Cheng M. Improved neighbor list algorithm in molecular simulations using cell decomposition and data sorting method // Comput. Phys. Commun. 2004. 161. 27-36.
  3. Gonnet P. A simple algorithm to accelerate the computation of non-bonded interactions in cell-based molecular dynamics simulations // J. Comput. Chem. 2007. 28. 570-573.
  4. Mattson W., Rice B.M. Near-neighbor calculations using a modified cell-linked list method // Comput. Phys. Commun. 1999. 119. 135-148.
  5. Kahle J.A., Day M.N., Hofstee H.P., Johns C.R., Maeurer T.R., Shippy D. Introduction to the Cell multiprocessor // IBM J. of Research and Development. 2005. 49, N 4/5. 589-604.
  6. Anderson J.A., Lorenz C.D., Travesset A. General purpose molecular dynamics simulations fully implemented on graphics processing units // J. Comput. Science. 2008. 227. 5342-5359.
  7. Smith W. Molecular dynamics on hypercube parallel computers // Comput. Phys. Commun. 1991. 62. 229-248.
  8. Fincham D. Parallel computers and molecular simulation // Molecular Simulation. 1987. 1. 1-45.
  9. Fomin E.S., Alemasov N.A., Chirtsov A.S., Fomin A.E. MOLKERN: A library of software components for molecular modeling programs // Biophysics. 2006. 51 , Suppl. 1. 110-112.
  10. http://www.boost.org
  11. http://www2.sscc.ru

Published

05-10-2010

How to Cite

Фомин Э. Comparison of the Verlet Table and Cell-Linked List Algorithms for Sequential, Vectorized and Multithreaded Implementations // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2010. 11. 299-305

Issue

Section

Section 1. Numerical methods and applications