Consideration of Data Load Time on Modern Processors for the Verlet Table and Linked-Cell Algorithms

ES Fomin, JOURNAL OF COMPUTATIONAL CHEMISTRY, 32, 1386-1399 (2011).

DOI: 10.1002/jcc.21722

Neighbor search algorithms are widely used in molecular dynamics for the direct computation of short-range pairwise interatomic potentials. These algorithms are based on the Verlet table (VT) and linked-cell (LC) methods. It is widely believed that the VT is more efficient than the LC. The analysis of these methods shows that in case when the average number of interactions per particle is relatively large, or more specifically, the particle density rho and skin radius r(skin) meet the condition (4 pi/6)rho r(skin)(3)/27 >> 1, which may be true for most simulations of liquids, the number of memory data load operations in the LC is much less than that in the VT. Because memory access on modern processors is a bottleneck, this advantage of the LC should be and was in fact used, and a code outperforming the VT by a factor of almost 2 was obtained. Some modifications of the VT were proposed to reduce its disadvantage concerning memory data loading. The key modifications included automated skin radius tuning during simulations and compression of the VT to minimize duplications of atom identifiers in its nearby rows. Although these modifications had improved the performance, the VT failed to regain the superiority over the LC. The methods were tested in the MOLKERN simulation software by using SIMD and multithreading. (C) 2011 Wiley Periodicals, Inc. J Comput Chem 32: 1386-1399, 2011

Return to Publications page