Pseudo-Verlet lists: a new, compact neighbour list representation

Abstract

Verlet lists, or neighbour lists, are a popular device to speed up the computation of non-bonded interactions in molecular dynamics and other particle-based simulations, in which a list of interacting particles for a given geometry is computed once and reused over several time steps until the geometry changes significantly. The size of the Verlet list is generally indices in the range , where N is the total number of particles, ρ_N is the particle number density and r_c and r_s are the cutoff and skin distances, respectively. Due to their memory requirements, Verlet lists are not always an optimal choice on multi-core or graphics processing unit systems in which the memory bandwidth per core is limited. This paper introduces pseudo-Verlet lists, an alternative neighbour list representation which requires only 13N indices in the range , thus requiring less storage, and resulting in better cache reuse.

Keywords::

• Verlet list
• neighbour list
• molecular dynamics simulation
• cell-linked list

Acknowledgments

The author thanks Jörg Stelling of the Department of Biosystems Sciences and Engineering (D-BSSE) at the ETH Zürich for providing access to the Brutus cluster on which the simulation results in this paper were obtained, as well as Urban Borstnik from the Brutus Cluster Support Team for his valuable technical advice.

Notes

^1. Note that this is similar to the erroneous description of the original algorithm in Ref. [7], but differs in the order in which the particles are sorted. Note also that this is only a conceptual description for the purpose of illustration: How the particles are actually sorted and traversed is descried in detail in the following section.

^2. This ratio differs slightly from the 59.4% computed in Ref. [4], as the latter figure did not include the cell self-interactions.

^3. This could arguably be reduced if the particles are stored cell-wise, as the neighbouring particles would reside in either the same cell or one of the 26 adjacent cells, by encoding the particle identifier as five bits encoding which of the (relative) neighbouring cells the particle is in, along with the offset of the particle relative to the first particle of that cell.