Astronomy and Astrophysics – Astrophysics
Scientific paper
2001-08-27
Astronomy and Astrophysics
Astrophysics
21 pages, 11 figures, submitted to New Astronomy
Scientific paper
10.1016/S1384-1076(02)00143-4
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.
No associations
LandOfFree
An efficient parallel algorithm for O(N^2) direct summation method and its variations on distributed-memory parallel machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An efficient parallel algorithm for O(N^2) direct summation method and its variations on distributed-memory parallel machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An efficient parallel algorithm for O(N^2) direct summation method and its variations on distributed-memory parallel machines will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-112854