552 High performance computing and parallelism
of a set ofNreal values. The aim is to filter the data according to some scheme
defined in terms of the Fourier components. In that case, the first node would
Fourier-transform the data, the second one would operate on the Fourier coeffi-
cients (this is the actual filter) and a third one would Fourier-transform the results
back to real time; the three parts are arranged in a pipeline.
16.4 Parallel algorithms for molecular dynamics
InChapter 8we discussed the molecular dynamics (MD) method in some detail.
In the standard microcanonical MD algorithm, Newton’s equations of motion are
solved in order to predict the evolution in time of an isolated classical many-
particle system. From the trajectory of the system in phase space we can determine
expectation values of physical quantities such as temperature, pressure, and the pair
correlation function.
We consider the MD simulation of argon in the liquid phase, which was discussed
rather extensively inChapter 8. The total interaction energy is a sum of the Lennard–
Jones potentials between all particle pairs. The force on a particular particle is
therefore the sum of the Lennard–Jones forces between this and all the other
particles in the system. The evaluation of these forces is the most time-consuming
step of the simulation, as this scales as the square of the numberNof particles
in the system. It therefore seems useful to parallelise this part of the simulation.
There exist essentially two methods for doing this. The first method is based
on a spatial decomposition of the system volume: the system is divided up into
cells, and the particles in each cell are allocated to one node. The nodes must have
the same topology as the system cells, in the sense that neighbouring cells should
be allocated to neighbouring nodes whenever possible. The particles interact with
the other particles in their own cell, and with the particles in neighbouring cells.
Interactions between particles in non-neighbouring cells are neglected. The smallest
diameter of a cell must therefore be large enough to justify this approximation: in
other words, the Lennard–Jones interaction must be small enough for this distance
and beyond. A problem is that particles may tend to cluster in some regions in phase
space, in particular when there is phase separation or when the system is close to a
second order phase transition. Then some nodes may contain many more particles
than others. In that case the nodes with fewer particles remain inactive for a large
part of the time. This is a general problem in parallelism, calledload balancing.
Moreover, particles move and may leave the cell they are in, and therefore the
allocation of the particles to the cells must be updated from time to time (similar to
the procedure in Verlet’s neighbour list: see Section 8.2).
The simplest version of this algorithm is realised by dividing up the system along
one dimension. In this way, one obtains slices of the system, the thickness of which