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

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.