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

Junichiro Makino

doi:10.1016/S1384-1076(02)00143-4

paper

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

arXiv:astro-ph/0108412 · doi:10.1016/S1384-1076(02)00143-4

Abstract

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

21 pages, 11 figures, submitted to New Astronomy

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

Abstract

Cited by in corpus (16)