An efficient parallel algorithm for O(N2) direct summation method and its variations on distributed-memory parallel machines

We present a novel, highly efficient algorithm to parallelize O(N-2) direct summation method for N-body problems with individual timesteps on distributed-memory parallel machines such as Beowulf clusters. Previously known algorithms, in which all processors have complete copies of the N-body system, has the serious problem that the communication-computation ratio increases as we increase the number of processors, since the communication cost is independent of the number of processors. In the new algorithm, p processors are organized as a rootp x rootp two-dimensional array. Each processor has N/rootp particles, but the data are distributed in such a way that complete system is presented if we look at any row or column consisting of rootp processors. In this algorithm, the communication cost scales as N/rootp, while the calculation cost scales as N-2/p. Thus, we can use a much larger number of processors without losing efficiency compared to what was practical with previously known algorithms. (C) 2002 Elsevier Science B.V. All rights reserved.