Computational Physics

16.4 Parallel algorithms for molecular dynamics 555

p

local

travel

local local local local

1 23 p–1

travel travel travel travel

Figure 16.7. The systolic algorithm for calculating the forces in a many-particle

system with pair-wise interactions.

different for each node. It is assumed that the local particles are initialised correctly
at the beginning – in practice this is done by a so-calledhost processor, which is
either one of the nodes, or a so-called front-end computer, which usually executes
the sequential parts of a program.

ROUTINE NodeStep

REPEAT

Calculate forces on local particles;

Perform leap-frog step for local particles;

UNTIL Program stops;

END ROUTINE Node Step;

ROUTINE Calculate forces on local particles

Calculate contributions from local particles;

Copy local particles to travelling particles;

DOK=1,P− 1

Send travelling particles to the left (modulo PBC);

Receive data from right neighbour and load into

memory used by travelling particles;

Calculate contributions to local forces from travelling particles;

END DO

END ROUTINE Calculate forces on local particles;

The systolic algorithm does not suffer from load-balance problems, as the work
to be executed at each node is the same. Only if the number of particlesNis not
equal to an integer times the number of nodes does the last processor contain fewer
particles than the remaining ones, so that a slight load-imbalance arises.
In the form described above, the systolic algorithm does not exploit the fact that
for every pairij, the force exerted by particlejon particleiis opposite to the force
exerted byionj, so that these two force contributions need only one calculation.
However, a modification exists which removes this disadvantage[ 4 ].A drawback