The O(N) hierarchical N-body algorithms and mas sively parallel processors allow particle systems of 100 million particles or more to be simulated in acceptable time. We describe a data-parallel implementation of Anderson's method and demonstrate both efficiency and scalability of the implementation on the Connec tion Machine CM-5/5E systems. The communication time for large particle systems amounts to about 10%- 25%, and the overall efficiency is about 35%, corre sponding to a performance of about 60 Mflop/s per CM-5E node, independent of the number of nodes.
Get full access to this article
View all access options for this article.
References
1.
Anderson, C.R.1992. An implementation of the fast multipole method without multipoles. SIAM J. Sci. Stat. Comp.13(4): 923-947.
2.
Appel, A.W.1985. An efficient program for many-body simulation. SIAM J. Sci. Stat. Comp.6(1):85-103.
3.
Applegate, J.H., Douglas, M.R., Gursel, Y., Hunter, P., Seitz, C.L., and Sussman, G.J.1985. A digital orrery. IEEE Trans. Comp.C-34(9):822-831.
4.
Barnes, J., and Hut, P.1986. A hierarchical O(N log N) force calculation algorithm . Nature324: 446-449.
5.
Board Jr.,J.A., Hakura, Z.S., Elliott, W.D., Gray, D.C., Blanke, W.J., and Leathrum Jr.J.F.1994. Scalable implementations of multipole-accelerated algorithms for molecular dynamics. In Proc. Scalable High Performance Computing Conference SHPCC94Los Alamitos: IEEE Computer Society.
6.
Carrier, J., Greengard, L., and Rokhlin, V.1988. A fast adaptive multipole algorithm for particle simulations . SIAM J. Sci. Stat. Comp.9(4):669-686.
7.
Dongarra, J.J., Croz, J.D., Duff, I., and Hammarling, S.1988. A set of level 3 basic linear algebra subprograms. Technical Report reprint no. 1, Argonne National Laboratories, Mathematics and Computer Science Division.
8.
Dongarra, J.J., Croz, J.D., Hammarling, S., and Hanson, R.J.1986. An extended set of Fortran basic linear algebra subprograms. Technical Memorandum 41. Argonne National Laboratories, Mathematics and Computer Science Division.
9.
Elliott, W.D., and Board, J.A.1994. Fast Fourier transform accelerated fast multipole algorithm. Technical Report 94-001. Durham, North Carolina : Duke University, Dept. of Electrical Engineering .
10.
Esselink, K.1992. The order of Appel's algorithm. Information Processing Letter41:141-147.
11.
Esselink, K.1994. A comparison of algorithms for long range interactions . Technical report. 500.90.200GRA204-IN73916AMER.94.006. Koninkilke/Shell-Laboratorium, Amsterdam.
12.
Greengard, L.1988. The rapid evaluation of potential fields in particle systems . Cambridge, Massachusetts: MIT Press.
13.
Greengard, L., and Gropp, W.D.1989. A parallel version of the fast multipole method . In Parallel processing for scientific computing. Philadelphia: Society for Industrial and Applied Mathematics , pp. 213-222.
14.
Greengard, L., and Rokhlin, V.1987a. A fast algorithm for particle simulations. J. Comp. Phys.73:325-348.
15.
Greengard, L., and Rokhlin, V.1987b. Rapid evaluation of potential fields in three dimensions. Technical Report YALEU/DCS/RR-515New Haven, Connecticut : Yale University, Dept. of Computer Science .
16.
Greengard, L., and Rokhlin, V.1988. On the efficient implementation of the fast multipole method. Technical Report YALEU/DCS/RR-602New Haven, Connecticut : Yale University, Dept. of Computer Science.
17.
Hennessy, J.L., and Patterson, D.A.1990. Computer architecture: a quantitative approach . San Mateo, California: Morgan Kaufmann.
18.
High Performance Fortran Forum.1993. High performance Fortran language specification, version 1.0. Scientific Programming2(1/2):1-170.
19.
Johnsson, S.L., and Ho, C.-T.1989. Spanning graphs for optimum broadcasting and personalized communication in hypercubes. IEEE Trans. Comp.38(9):1249-1268.
20.
Katzenelson, J.1989. Computational structure of the N-body problem. SIAM J. Sci. Stat. Comp.10(4):787-815.
21.
Lawson, C., Hanson, R., Kincaid, D., and Krogh, F.1979. Basic linear algebra subprograms for Fortran usage . ACM Transactions on Mathematical Software5(3):308-323.
22.
Leathrum, J.F.1992. The parallel fast multipole method in three dimensions. Ph.D. thesis. Durham, North Carolina: Duke University.
23.
Leathrum Jr.J.F., and Board Jr.J.A.1992. The parallel fast multipole algorithm in three dimensions. Technical Report CSL-TR-92-506. Durham, North Carolina : Duke University, Dept. of Computer Science.
24.
Liu, P.1994. The parallel implementation of N-body algorithms. Ph.D. thesis. New Haven, Connecticut: Yale University.
25.
Liu, P., and Bhatt, S.N.1994. Experiences with parallel N-body simulation. In Proceedings of the 6th annual ACM symposium on parallel algorithms and architecture. New York: ACM Press.
26.
Lomdahl, P.S., Tamayo, P., Gronbech-Jensen, N., and Beazley, D.M.1993. 50 GFlops molecular dynamics on the Connection Machine 5. In Proceedings of Supercomputing '93Los Alamitos : IEEE Computer Society.
27.
McLaren, A.D.1963. Optimal numerical integration on a sphere. MathematicalComputing17:361-383.
28.
Nyland, L.S., Prins, J.F., and Reif, J.H.1993. A data-parallel implementation of the adaptive fast multipole algorithm. In Proceedings of the DAGS '93 Symposium. Hanover, New Hampshire: Dartmouth Institute for Advanced Graduate Studies in Parallel Computation.
29.
Salmon, J.K.1990. Parallel hierarchical N-body methods. Ph.D. thesis . Pasadena, California: California Institute of Technology .
30.
Schmidt, K.E., and Lee, M.A.1991. Implementing the fast multipole method in three dimensions . J. Stat. Phys.63(5/6): 1223-1235.
31.
Singh, J., Holt, C., Hennessey, J., and Gupta, A.1993. A parallel adaptive fast multipole method. In Proceedings of Supercomputing '93. Los Alamitos: IEEE Computer Society, pp. 54-65.
32.
Singh, J., Holt, C., Totsuka, T., Gupta, A., and Hennessey, J.1992. Load balancing and data locality in hierarchical N-body methods. Technical Report CSL-TR-92-505. Stanford, California : Stanford University.
Thinking Machines Corp.1993a. CM Fortran reference manual, version 2.1. Cambridge, Massachusetts .
35.
Thinking Machines Corp.1993b. CMSSL for CM Fortran, version 3.1. Cambridge, Massachusetts .
36.
Warren, M., and Salmon, J.1992. Astrophysical N-body simulations using hierarchical tree data structures. In Proceedings of Supercomputing '92. Los Alamitos: IEEE Computer Society, pp. 570-576.
37.
Warren, M., and Salmon, J.1993. A parallel hashed oct-tree N-body algorithm. In Proceedings of Supercomputing '93. Los Alamitos: IEEE Computer Society, pp. 12-21.
38.
Warren, M., and Salmon, J.1995. A portable parallel particle program. Comp. Phys. Comm.87: 266-290.
39.
Zhao, F.1987. An O(N) algorithm for three-dimensional N-body simulations. AI Memo 995. Cambridge, Massachusetts: Massachusetts Institute of Technology, Artificial Intelligence Laboratory .
40.
Zhao, F., and Johnsson, S.L.1991. The parallel multipole method on the Connection Machine . SIAM J. Stat. Sci. Comp.12(6):1420-1437.
