A data-parallel implementation of O(N) hierarchical N-body methods

ABSTRACT

The O(N) hierarchical N-body algorithms and Massively Parallel Processors allow particle systems of 100 million particles or more to be simulated in acceptable time. We present a data-parallel implementation of Anderson's method and demonstrate both efficiency and scalability of the implementation on the Connection Machine CM-5/5E systems. The communication time for large particle systems amounts to about 10-25%, and the overall efficiency is about 35%. The evaluation of the potential field of a system of 100 million particles takes 3 minutes and 15 minutes on a 256 node CM-5E, giving expected four and seven digits of accuracy, respectively. The speed of the code scales linearly with the number of processors and number of particles.

REFERENCES

• 1: Christopher R. Anderson, An implementation of the fast multipole method without multipoles, SIAM Journal on Scientific and Statistical Computing, v.13 n.4, p.923-947, July 1992 [doi>10.1137/0913055]
• 2: A. Appel. An efficient program for many-body simulation. SIAM J. Sci. Stat. Comput., 6(1):85-103, 1985.
• 3: James H. Applegate , Michael R. Douglas , Yekta Gürsel , Peter Hunter , Charles L. Seitz , Gerald J. Sussman, A digital orrery, IEEE Transactions on Computers, v.34 n.9, p.822-831, Sept. 1985 [doi>10.1109/TC.1985.1676638]
• 4: J. Barnes and P. Hut. A hierarchical O(N log N) force calculation algorithm. Nature, 324:446-449, 1986.
• 5: J. A. Board Jr., Z. S. Hakura, W. D. Elliott, D. C. Gray, W. J. Blanke, and J. Leathrum Jr. Scalable implementations of multipole-accelerated algorithms for molecular dynamics. In Proc. Scalable High Performance Computing Conference SHPCC94. IEEE Computer Society Press, May 1994.
• 6: J. Carrier, L. Greengard, and V. Rokhlin. A fast adaptive multipole algorithm for particle simulations. SIAM Journal of Scientific and Statistical Computing, July 1988.
• 7: J. J. Dongarra, J. D. Croz, I. Duff, and S. Hammarling. A Set of Level 3 Basic Linear Algebra Subprograms: Model implementation and test programs. Technical Report Reprint No. 2, Argonne National Laboratories, Mathematics and Computer Science Division, August 1988.
• 8: J. J. Dongarra, J. D. Croz, S. Hammarling, and R. J. Hanson. An Extended Set of Fortran Basic Linear Algebra Subprograms. Technical Report Technical Memorandum 41, Argonne National Laboratories, Mathematics and Computer Science Division, November 1986.
• 9: W. D. Elliott and J. A. Board. Fast fourier transform accelerated fast multipole algorithm. Technical Report 94-001, Dept. of Electrical Engineering, Duke Univ., 1994.
• 10: Klaas Esselink, The order of Appel's algorithm, Information Processing Letters, v.41 n.3, p.141-147, March 6, 1992 [doi>10.1016/0020-0190(92)90043-U]
• 11: K. Esselink. A comparison of algorithms for long range interactions. Technical Report 500.90.200GRA204-IN73916 AMER.94.006, Koninklijke/Shell-Laboratorium, Amsterdam, August 1994.
• 12: Leslie Greengard , William Gropp, A Parallel Version of the Fast Multipole Method-Invited Talk, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.213-222, December 01-04, 1987
• 13: 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]
• 14: L. F. Greengard. The rapid evaluation of potential fields in particle systems. MIT Press, 1988.
• 15: L. F. Greengard and V. Rokhlin. On the efficient implementation of the fast multipole algorithm. Technical Report YALEU/DCS/RR-602, Dept. of Computer Science, Yale Univ., February 1988.
• 16: High Performance Fortran Forum. High performance fortran; language specification, version 1.0. Scientific Programming, 2(1 - 2):1-170, 1993.
• 17: Y. Hu and S. L. Johnsson. A data parallel implementation of hierarchical N-body methods. Technical Report TR-26-94, Harvard University, Division of Applied Sciences, September 1994.
• 18: Y. Hu and S. L. Johnsson. On the accuracy of Anderson's fast N-body algorithm. Technical report TR-06-96, Harvard University, Division of Applied Sciences, January 1996.
• 19: Y. Hu and S. L. Johnsson. A data-parallel adaptive O(N) hierarchical N-body method. Technical report, Harvard University, Division of Applied Sciences, 1996.
• 20: S. Lennart Johnsson , Ching-Tien Ho, Optimum Broadcasting and Personalized Communication in Hypercubes, IEEE Transactions on Computers, v.38 n.9, p.1249-1268, September 1989 [doi>10.1109/12.29465]
• 21: Jacob Katzenelson, Computational structure of the N-body problem, SIAM Journal on Scientific and Statistical Computing, v.10 n.4, p.787-815, July 1989 [doi>10.1137/0910048]
• 22: C. L. Lawson , R. J. Hanson , F. T. Krogh , D. R. Kincaid, Algorithm 539: Basic Linear Algebra Subprograms for Fortran Usage [F1], ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.324-325, Sept. 1979 [doi>10.1145/355841.355848]
• 23: J. F. Leathrum. The parallel fast multipole method in three dimensions. PhD thesis, Duke University, 1992.
• 24: Pangfeng Liu , Sandeep N. Bhatt, Experiences with parallel N-body simulation, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.122-131, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181081]
• 25: P. S. Lomdahl , P. Tamayo , N. Grønbech-Jensen , D. M. Beazley, 50 GFlops molecular dynamics on the Connection Machine 5, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.520-527, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169794]
• 26: L. S. Nyland, J. F. Prins, and J. H. Reif. A data-parallel implementation of the adaptive fast multipole algorithm. In Proceedings of the DAGS '93 Symposium. Dartmouth Institute for Advanced Graduated Studies in Parallel Computation, Hanover, NH, 1993.
• 27: John K. Salmon, Parallel hierarchical N-body methods, California Institute of Technology, Pasadena, CA, 1992
• 28: K. E. Schmidt and M. A. Lee. Implementing the fast multipole method in three dimensions. J. Stat. Phy., 63(5/6), 1991.
• 29: J. Singh, J. Hennessey, and A. Gupta. Implications of hierarchical N-body methods for multiprocessor architectures. Technical Report CSL-TR-92-506, Stanford University, 1992.
• 30: J. P. Singh , C. Holt , J. L. Hennessy , A. Gupta, A parallel adaptive fast multipole method, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.54-65, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169651]
• 31: Thinking Machines Corp. CMSSL for CM Fortran, Version 3.1, 1993.
• 32: Thinking Machines Corp. CM Fortran Libraries Reference Manual, Version 2.2, 1994.
• 33: 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
• 34: M. S. Warren , J. K. Salmon, A parallel hashed Oct-Tree N-body algorithm, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.12-21, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169640]
• 35: M. S. Warren and J. K. Salmon. A portable parallel particle program. Computer Physics Communications, 87, 1995.
• 36: Feng Zhao, An {\it bf O(N)} Algorithm for Three-Dimensional N-body Simulations, Massachusetts Institute of Technology, Cambridge, MA, 1987
• 37: Feng Zhao , S. Lennart Johnsson, The parallel multipole method on the connection machine, SIAM Journal on Scientific and Statistical Computing, v.12 n.6, p.1420-1437, Nov. 1991 [doi>10.1137/0912077]

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Design, Measurement, Performance, Reliability, Theory

Keywords:
N-body simulation, multipole algorithms, hierarchical N-body methods, data-parallel programming, massively parallel processors