Parallel NBody Simulations
The classical Nbody 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. Nbody 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(N^{2}) operations at each timestep.
Hierarchical treebased methods have been developed to reduce the
complexity. There have been several papers that have looked at
parallel implementations of these treebased methods
[17,
14,
19,
12,
3]
In our work we have compared three treebased algorithms, the
BarnesHut algorithm [2],
Greengard's Fast Multipole algorithm [9], and the Multipole Tree algorithm [6], 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 NBody 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)
allpairs algorithm.
 BarnesHut 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
code.
 Fast Multipole Method
 This algorithm by Greengard is O(n). However, it uses
more complicated mathematics and is more difficult to program in
3dimensions, and has larger constants in its order of complexity.
The NESL
code.
 Parallel Multipole Tree algorithm
 This is a hybrid of the BarnesHut and Multipole method developed
by the Scientific
Computing Group at Duke University [6]. The
NESL
code.
An important goal of these implementations is to study the constants
in their orders of complexity, and see how the complexity is affected
by nonuniform distributions. We are also interested in studying the
dependence of the efficiency and accuracy of these algorithms on their
variable parameters.
Related Work (online)
Relevant Papers
 1

S.J. Aarseth, M. Henon, and R. Wielen.
Numerical methods for the study of star cluster dynamics.
Astronomy and Astrophysics, 37(2):183187, 1974.
 2

J.E. Barnes and P. Hut.
A hierarchical O(N Log N) force calculation algorithm.
Nature, 324(4):446449, December 1986.
 3

S. Bhatt, M. Chen, C.Y. Lin, and P. Liu.
Abstractions for parallel Nbody simulations.
In Proceedings Scalable High Performance Computing Conference,
pages 2629, 1992.
 4

Guy E. Blelloch.
Nesl: A nested dataparallel language.
Technical Report CMUCS93129, CMU, School of Computer Science,
April 1993.
 5

J.A. Board and W.S. Elliot.
Fast fourier transform accelerated fast multipole algorithm.
Technical Report 94001, Duke University Dept of Electrical
Engineering, 1994.
 6

J.A. Board, Z.S. Hakura, W.S. Elliot, D.C. Gray, W.J. Blanke, and J.F. Leathrum
Jr.
Scalable implementations of multipoleaccelerated algorithms for
molecular dynamics.
Technical Report 94002, Duke Univaersity, 1994.
 7

J.A. Board, Z.S. Hakura, W.S. Elliot, and W.T. Rankin.
Scalable variants of multipoleaccelerated algorithms for molecular
dynamics.
Technical Report 94006, Duke University Dept of Electrical
Engineering, 1994.
 8

P.B. Callahan.
Optimal parallel allnearestneighbours using the wellseparated
pairs decomposition.
In 34th Annual Symposium on Foundations of Computer Science,
pages 332340, Palo Alto, 1993. IEEE.
 9

L. Greengard.
The rapid evaluation of potential fields in particle systems.
The MIT Press, 1987.
 10

L. Greengard and V. Rokhlin.
A fast algorithm for particle simulation.
Journal of Computational Physics, 73(325), 1987.
 11

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,
1992.
 12

P.H. Mills, L.S. Nyland, J.F. Prins, and J.H. Reif.
Prototyping Nbody simulation in proteus.
In Proceedings Sixth International Parallel Processing
Symposium, pages 476482, 1992.
 13

V.Y. Pan, J.H. Reif, and S.R. Tate.
The power of combining the techniques of algebraic and numerical
computing.
In 32nd Annual IEEE Symposium on Foundations of Computer Science
(FOCS 92), pages 703713, 1992.
 14

J. Salmon.
Parallel O(N Log N) Nbody algorithms and applications to
astrophysics.
In COMPCON Spring '91, Digest of Papers, pages 7378, 1991.
 15

J.K. Salmon.
Parallel hierarchical Nbody methods.
PhD thesis, Caltech University, 1991.
 16

K.E. Schmidt and M.A. Lee.
Implementing the fast multipole method in three dimensions.
Journal of Statistical Physics, 63(5):12231235, 1991.
 17

J.P. Singh, W.D. Weber, and A. Gupta.
Splash: Stanford parallel applications for sharedmemory.
Computer Architecture News, 20(1):544, March 1987.
 18

M. Warren and J. Salmon.
Astrophysical nbody simulations using hierarchical tree data
structures.
In Proceedings of Supercomputing, 1992.
 19

F. Zhao and S.L. Johnsson.
The parallel multipole method on the connection machine.
SIAM Journal on Scientific and Statistical Computing,
12(6):14201437, november 1991.
Up to the Irregular Algorithms page,
the NESL page, or
the Scandal page.
girija@cs.cmu.edu.