Neighbors list

Figure 2 A particle i interacts mainly with particles that are within the cutoff radius The neighbor list contains only those particles that are within a sphere of radius rj > Particles outside this sphere will not contribute to the force or energy affecting particleThe use of a neighbor list that is periodically updated during the simulation reduces the computer time required in calculating pairwise interactions.

It is clear that Eq. (85) is numerically reliable provided is sufficiently small. However, a detailed investigation in Ref. 69 reveals that can be as large as some ten percent of the diameter of a fluid molecule. Likewise, rj should not be smaller than, say, the distance at which the radial pair correlation function has its first minimum (corresponding to the nearest-neighbor shell). Under these conditions, and if combined with a neighbor list technique, savings in computer time of up to 40% over conventional implementations are measured for the first (canonical) step of the algorithm detailed in Sec. IIIB. These are achieved because, for pairwise interactions, only 1+ 2 contributions need to be computed here before i is moved U and F2), and only contributions need to be evaluated after i is displaced... 

Let us comment on the developed schematic Monte Carlo (MC) code. Of course there are many clever ways to improve the execution speed. There is the important concept of neighbor lists, of clever implementation of numerical instructions, and so on. In developing a computer simulation one usually plugs in these enhancing concepts bit by bit. 

Efficiency Issues Spring Constants and Neighbor Lists... 

Fig. 15. The scheme of neighbor list and cell lists. The particle of interest is black the grey particles are within the neighbor list cut-off.

The second stage scans the nearest-neighbor lists to create clusters that fulfill the three following neighborhood conditions ... 

To scan the nearest-neighbor lists and create the clusters in this stage of nonhierarchical clustering, the following three steps are carried out ... 

For each pair of compounds, i and j (i < j), compare the nearest-neighbor lists on the basis of the three neighborhood conditions. If the three conditions are passed, replace the cluster label for compound j with the cluster label for compound i. Then, scan all previously processed compounds and replace any occurrences of the cluster label for compound j by the cluster label for compound i. 

Implementing the shared-memory vector/parallel algorithms developed by Mertz et al. (fgr evaluation of the potential energies and forces, generation of the nonbonded neighbor list, and satisfaction of holonomic constraints) into CHARMM and AMBER resulted in near-linear speed-ups on eight processors of a Cray Y-MP for the forces and neighbor lists. For the holonomic constraints, speed-ups of 6.0 and 6.4 were obtained for the SHAKE and matrix inversion method, respectively. 

The basic methods to treat short-range interactions are often called by the common implementation methods used, i.e. Verlet neighbor lists [92] and linked lists [93,94]. We believe that this nomenclature should be reserved for the respective implementation methods since they tend to stand in the way for better implementation methods that could be developed. It is more appropriate to use names which describe the actual algorithmic ideas. In support of this view is the observation that neither Verlet neighbor lists nor linked list can be very efficient on cache-based processors, since they have a tendency to access memory in an unstructured way. The same access pattern is also a headache on vector architectures. Examples of data structures that are both efficient and likely to get better cache reuse can be found in [70,71,95]. An improvement in the construction of neighbor lists can be found in [96]. It is notable that Everaers and Kremer [71] also report very good vectorization of the method that have developed. 

A11 simulations involved 256 copper atoms, had timesteps of 10 fs, and were 200 ps in duration. Tt and Tp are the temperature and pressure time coupling constants. The system was treated as a cubic box, initially with side = 14.46 A. The neighbor lists were updated every 20 timesteps. 

The first apparent MD implementation to use CUDA was by Liu et al. [22]. Like Yang et al., they too chose to implement just a simplistic van der Waals potential allowing them to avoid all of the complexities inherent in production MD simulations of condensed-phase systems. Unlike Yang, Liu et al. recomputed their neighbor list periodically providing the first example of a neighbor list update for MD on GPUs. 

---