Communication computation trade-off

This is a simple molecular dynamics code, with a relatively large amount of communication relative to the computation. The code solves Newton’s second law of motion for every atom: \({\bf F}=m{\bf a}\).

The basic algorithm used is shown below:

for i = 1, N {
    intialise x_i (atom i position) and v_i (atom i velocity)
}

while ( t < t_end ) {
    for i = 1, N {
        calculate force F_i
        update positions x_i
        update velocities v_i
    }
    
    t = t + dt
}

The domain decomposition is such that each MPI process has N / p atoms, where p is the number of processes (assuming this is perfectly divisible). The parallel (MPI) algorithm is shown below:

while ( t < t_end ) {
    1. send/receive particle positions to/from all other processes
    2. determine which non-bonded forces need to be computed
    3. compute partial forces for particles assigned to this process
    4. send particle forces needed by other processes and receive particle forces needed by this process
}

Stage 4 in the algorithm ensures that \({\bf F}_{i,j}\) is not calculated twice as \({\bf F}_{i,j}=-{\bf F}_{j,i}\).