Parallel N-Body Simulations
The classical N-body problem simulates the evolution of a
system of N bodies, where the force exerted on each body arises due
to its interaction with all the other bodies in the
system. N-body algorithms have numerous applications in areas
such as astrophysics, molecular dynamics and plasma physics. The
simulation proceeds over timesteps, each time computing the net force
on every body and thereby updating its position and other attributes.
If all pairwise forces are computed directly, this requires
O(N2) operations at each timestep.
Hierarchical tree-based methods have been developed to reduce the
complexity. There have been several papers that have looked at
parallel implementations of these tree-based methods
In our work we have compared three tree-based algorithms, the
Barnes-Hut algorithm ,
Greengard's Fast Multipole algorithm , and the Multipole Tree algorithm , in terms of both the computational cost and the
accuracy of the methods. We have implemented the algorithms in NESL,
and have run extensive experiments on them.
The results of this work is summarized in the paper A
Practical Comparison of N-Body Algorithms.
Here is a brief description of the algorithms. The error for each of these
algorithms was measured with respect to the O(n^2)
- Barnes-Hut algorithm
- This is an O(n log n) algorithm based on a
hierarchical octree representation of space in three dimensions. It
computes interactions between distant particles by means of the first
order approximation. The NESL
- Fast Multipole Method
- This algorithm by Greengard is O(n). However, it uses
more complicated mathematics and is more difficult to program in
3-dimensions, and has larger constants in its order of complexity.
- Parallel Multipole Tree algorithm
- This is a hybrid of the Barnes-Hut and Multipole method developed
by the Scientific
Computing Group at Duke University . The
An important goal of these implementations is to study the constants
in their orders of complexity, and see how the complexity is affected
by non-uniform distributions. We are also interested in studying the
dependence of the efficiency and accuracy of these algorithms on their
Related Work (online)
S.J. Aarseth, M. Henon, and R. Wielen.
Numerical methods for the study of star cluster dynamics.
Astronomy and Astrophysics, 37(2):183-187, 1974.
J.E. Barnes and P. Hut.
A hierarchical O(N Log N) force calculation algorithm.
Nature, 324(4):446-449, December 1986.
S. Bhatt, M. Chen, C.Y. Lin, and P. Liu.
Abstractions for parallel N-body simulations.
In Proceedings Scalable High Performance Computing Conference,
pages 26-29, 1992.
Guy E. Blelloch.
Nesl: A nested data-parallel language.
Technical Report CMU-CS-93-129, CMU, School of Computer Science,
J.A. Board and W.S. Elliot.
Fast fourier transform accelerated fast multipole algorithm.
Technical Report 94-001, Duke University Dept of Electrical
J.A. Board, Z.S. Hakura, W.S. Elliot, D.C. Gray, W.J. Blanke, and J.F. Leathrum
Scalable implementations of multipole-accelerated algorithms for
Technical Report 94-002, Duke Univaersity, 1994.
J.A. Board, Z.S. Hakura, W.S. Elliot, and W.T. Rankin.
Scalable variants of multipole-accelerated algorithms for molecular
Technical Report 94-006, Duke University Dept of Electrical
Optimal parallel all-nearest-neighbours using the well-separated
In 34th Annual Symposium on Foundations of Computer Science,
pages 332-340, Palo Alto, 1993. IEEE.
The rapid evaluation of potential fields in particle systems.
The MIT Press, 1987.
L. Greengard and V. Rokhlin.
A fast algorithm for particle simulation.
Journal of Computational Physics, 73(325), 1987.
J.F. Leathrum, Jr., J.A. Board, and W.S. Elliot.
The parallel fast multipole algorithm in three dimensions.
Technical report, Duke University Dept of Electrical Engineering,
P.H. Mills, L.S. Nyland, J.F. Prins, and J.H. Reif.
Prototyping N-body simulation in proteus.
In Proceedings Sixth International Parallel Processing
Symposium, pages 476-482, 1992.
V.Y. Pan, J.H. Reif, and S.R. Tate.
The power of combining the techniques of algebraic and numerical
In 32nd Annual IEEE Symposium on Foundations of Computer Science
(FOCS 92), pages 703-713, 1992.
Parallel O(N Log N) N-body algorithms and applications to
In COMPCON Spring '91, Digest of Papers, pages 73-78, 1991.
Parallel hierarchical N-body methods.
PhD thesis, Caltech University, 1991.
K.E. Schmidt and M.A. Lee.
Implementing the fast multipole method in three dimensions.
Journal of Statistical Physics, 63(5):1223-1235, 1991.
J.P. Singh, W.D. Weber, and A. Gupta.
Splash: Stanford parallel applications for shared-memory.
Computer Architecture News, 20(1):5-44, March 1987.
M. Warren and J. Salmon.
Astrophysical n-body simulations using hierarchical tree data
In Proceedings of Supercomputing, 1992.
F. Zhao and S.L. Johnsson.
The parallel multipole method on the connection machine.
SIAM Journal on Scientific and Statistical Computing,
12(6):1420-1437, november 1991.
Up to the Irregular Algorithms page,
the NESL page, or
the Scandal page.