Systolic calculation of pair interactions using the cell linked-lists method on multi-processor systems

Methods generally used in molecular dynamics (MD) simulations to speed up the calculation of forces by reducing the number of operations that have to be performed mostly fall into two classes: neighbour list [1] or cell linked-lists [2] algorithms. The relative merits of both methods have been discussed extensively in the literature and the discussion is not to be repeated here. Let us only recall the conclusion that the cell linked-lists method becomes competitive if the potential cutoff radius rc used in the particle--particle interaction calculation is small compared to the system dimensions. According to this method the simulation box is geometrically divided into a regular lattice of cells. These cells are chosen so that the side of the cell l is greater than the cutoff distance rc. For each cell it is established which particles it contains. Two arrays are created during the particle sorting process. The head-of-chain array HEAD which has one entry for each cell containing the identification number of one particle contained in that cell, and the linked-list array LIST containing the rest of particles indices. By means of these arrays searching through the neighbours is a rapid process. With reference to the two-dimensional example of Fig. I the neighbours of any particle in cell 24 are to be found in cells 16, 17, 18, 23, 24, 25, 30, 31, 32 for each of which a different path exists from HEAD through LIST array which singles out all the particles contained in it. The present note describes how to access the cell linked-lists method in a systolic parallel context. In this case, no natural partitioning of the cells can be relied upon