  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 $\sqrt{p}\times \sqrt{p}$ two-dimensional array. Each processor
has $N/\sqrt{p}$ 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
$\sqrt{p}$ processors. In this algorithm, the communication cost scales as $N
/\sqrt{p}$, 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.
