Experiences with parallel N-body simulation

ABSTRACT

This paper describes our experiences developing high-performance code for astrophysical N-body simulations. Recent N-body methods are based on an adaptive tree structure. The tree must be built and maintained across physically distributed memory; moreover, the communication requirements are irregular and adaptive. Together with the need to balance the computational work-load among processors, these issues pose interesting challenges and tradeoffs for high-performance implementation. Our implementation was guided by the need to keep solutions simple and general. We use a technique for implicitly representing a dynamic global tree across multiple processors which substantially reduces the programming complexity as well as the performance overheads of distributed memory architectures. The contributions include methods to vectorize the computation and minimize communication time which are theoretically and experimentally justified. The code has been tested by varying the number and distribution of bodies on different configurations of the Connection Machine CM-5. The overall performance on instances with 10 million bodies is typically over 30% of the peak machine rate. Preliminary timings compare favorably with other approaches.

REFERENCES

• 1: Cmmd reference manual. Technical report, Thinking Machine Corporation, 1993.
• 2: S.J. Aarseth, M. Henon, and R. Wielen. Astronomy and Astrophysics, 37, 1974.
• 3: R. Anderson. personal communication. 1993.
• 4: A.W. Appel. An efficient program for many-body simulation. SIAM J. Sci. Star. Comput., 6, 1985.
• 5: Joshua E. Barnes, A modified tree code: don't laugh; it runs, Journal of Computational Physics, v.87 n.1, p.161-170, March 1990 [doi>10.1016/0021-9991(90)90232-P]
• 6: J. Barnes and P. Hut. A hierarchical O(Nlog N) force-calculation algorithm. Nature, 324:446-449, 1986.
• 7: S. Bhatt, M. Chen, C-Y Lin, and P. Liu. Abstractions for parallel N-body simulations. In Proceedings o# SHPCC 9P.
• 8: L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
• 9: L. Johnsson and Y. Hu. personal communication. 1993.
• 10: J. F. Leathrum Jr. and J. Board Jr. The parallel fast multipole algorithm in three dimensions.
• 11: Pangfeng Liu , William Aiello , Sandeep Bhatt, An atomic model for message-passing, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.154-163, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165251]
• 12: L. Nyland, J. Prins, and J. Reif. A data-parallel implementation of the adaptive fast multipole algorithm. In DAGS/PC Symposium, 1993.
• 13: John K. Salmon, Parallel hierarchical N-body methods, California Institute of Technology, Pasadena, CA, 1992
• 14: Jaswinder Pal Singh, Parallel hierarchical N-body methods and their implications for multiprocessors, Stanford University, Stanford, CA, 1993
• 15: J. Singh, C. Holt, T. Totsuka, A. Gupta, and J. Hennessy. Load balancing and data locality in hierarchical n-body methods. Technical Report CSL- TR-92-505, Stanford University, 1992.
• 16: Sridhar Sundaram, Fast algorithms for N-body simulations, Cornell University, Ithaca, NY, 1993
• 17: M. S. Warren , J. K. Salmon, Astrophysical N-body simulations using hierarchical tree data structures, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.570-576, November 16-20, 1992, Minneapolis, Minnesota, United States
• 18: M. Warren and J. Salmon. A parallel hashed octtree n-body algorithm, 1993.
• 19: F. Zhao and S.L. Johnsson. The parallel multipole method on the connection machine. Technical Report DCS/TR-749, Yale University, 1989.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Measurement, Performance, Theory