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(N²) 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 [17, 14, 19, 12, 3]

In our work we have compared three tree-based algorithms, the Barnes-Hut 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 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) all-pairs algorithm.

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 code.

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. The NESL code.

Parallel Multipole Tree algorithm

This is a hybrid of the Barnes-Hut 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 non-uniform distributions. We are also interested in studying the dependence of the efficiency and accuracy of these algorithms on their variable parameters.

Related Work (online)

• A Java applet demo of the Barnes-Hut algorithm.
• A Survey from the Edinburgh Parallel Computing Centre.
• The N-body Shop at the University of Washington.
• A Data-Parallel Implementation of the Adaptive Fast Multipole Algorithm by Lars Nyland, Jan Prins, and John Reif
• Studying Galaxy formation with N-body tree codes by John Salmon and Michael Warren.
• A theoretical astrophysics page from Los Alomos national labs.
• Scientific Computing Group at the Dept. of Electrical Eng, Duke University.

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):183-187, 1974.

2

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

3

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.

4

Guy E. Blelloch. Nesl: A nested data-parallel language. Technical Report CMU-CS-93-129, CMU, School of Computer Science, April 1993.

5

J.A. Board and W.S. Elliot. Fast fourier transform accelerated fast multipole algorithm. Technical Report 94-001, 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 multipole-accelerated algorithms for molecular dynamics. Technical Report 94-002, Duke Univaersity, 1994.

7

J.A. Board, Z.S. Hakura, W.S. Elliot, and W.T. Rankin. Scalable variants of multipole-accelerated algorithms for molecular dynamics. Technical Report 94-006, Duke University Dept of Electrical Engineering, 1994.

8

P.B. Callahan. Optimal parallel all-nearest-neighbours using the well-separated pairs decomposition. In 34th Annual Symposium on Foundations of Computer Science, pages 332-340, 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 N-body simulation in proteus. In Proceedings Sixth International Parallel Processing Symposium, pages 476-482, 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 703-713, 1992.

14

J. Salmon. Parallel O(N Log N) N-body algorithms and applications to astrophysics. In COMPCON Spring '91, Digest of Papers, pages 73-78, 1991.

15

J.K. Salmon. Parallel hierarchical N-body 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):1223-1235, 1991.

17

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.

18

M. Warren and J. Salmon. Astrophysical n-body 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):1420-1437, november 1991.

Up to the Irregular Algorithms page, the NESL page, or the Scandal page.