Article

Free access

Highly portable and efficient implementations of parallel adaptive N-body methods

Authors:

David Blackston,

Torsten SuelAuthors Info & Claims

SC '97: Proceedings of the 1997 ACM/IEEE conference on Supercomputing

Pages 1 - 20

https://doi.org/10.1145/509593.509597

Published: 15 November 1997 Publication History

Abstract

We describe the design of several portable and efficient parallel implementations of adaptive N-body methods, including the adaptive Fast Multipole Method, the adaptive version of Anderson's Method, and the Barnes-Hut algorithm. Our codes are based on a communication and work partitioning scheme that allows an efficient implementation of adaptive multipole methods even on high-latency systems. Our test runs demonstrate high performance and speedup on several parallel architectures, including traditional MPPs, shared-memory machines, and networks of workstations connected by Ethernet.

References

[1]

C. Anderson. An implementation of the fast multipole method without multipoles. SIAM, J. Sci. Stat. Comput., 13(4):923-947, July 1992.

Digital Library

[2]

Andrew W. Appel. An efficient program for many-body simulation. SIAM Journal on Scientific and Statistical Computing, 6(1):85-103, January 1985.

Digital Library

[3]

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

[4]

Guy Blelloch and Girija Narlikar. A practical comparison of N-body algorithms. In Dimacs Implementation Challenge Workshop, October 1994.

[5]

Guy E. Blelloch. Programming parallel algorithms. Communications of the ACM, 39(3):85-97, March 1996.

Digital Library

[6]

John A. Board, Ziyad S. Hakura, William D. Elliott, and William T. Rankin. Scalable variants of multipole-based algorithms for molecular dynamics applications. In Proceedings of the 7th Conference on Parallel Processing for Scientific Computing, pages 295-300. SIAM Press, February 15-17 1995.

[7]

J. Carrier, L. Greengard, and V. Rokhlin. A fast adaptive multipole algorithm for particle simulations. SIAM Journal on Scientific and Statistical Computing, 9(4):669-686, July 1988.

Digital Library

[8]

Mark W. Goudreau, Kevin Lang, Satish Rao, Torsten Suel, and Thanasis Tsantilas. Towards efficiency and portability: Programming with the BSP model. In Eighth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'96), pages 1-12, June 1996.

Digital Library

[9]

A. Greenbaum. Parallelizing the adaptive fast multipole method on a shared memory MIMD machine. Ultrcomputer Note 162, June 1989.

[10]

L. Greengard and V. Rokhlin. A fast algorithm for particle simulations. Journal of Computational Physics, 73(2):325-348, December 1987.

Digital Library

[11]

William Gropp, Ewing Lusk, and Anthony Skjellum. Using MPI: Portable Parallel Programming with the Message Passing Interface. MIT Press, 1994.

Digital Library

[12]

P. Hanrahan, D. Saltzman, and L. Aupperle. A rapid hierarchical radiosity algorithm. Computer Graphics, 25(4):197-206, July 1991.

Digital Library

[13]

L. Hernquist. Performance characteristics of tree codes. Astrophysical Journal Supplement Series, (64):715-734, 1987.

[14]

T. Hrycak and V. Rokhlin. An improved fast multipole algorithm for potential fields. Technical Report RR-1089, Department of Computer Science, Yale University, November 1995.

Digital Library

[15]

Y. Hu, S. L. Johnsson, and S.-H. Teng. A data-parallel adaptive N-body method. In Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing. SIAM Press, 1997.

[16]

Y. Hu, S. L. Johnsson, and S.-H.Teng. High performance fortran for highly irregular problems. In Proceedings of the 6th ACM Symp. on Principles and Practice of Parallel Porgramming. ACM Press, 1997.

Digital Library

[17]

Yu Hu and S. Lennart Johnsson. A data-parallel implementation of hierarchical N-body methods. The International Journal of Supercomputer Applications and High Performance Computing, 10(1):3-40, 1996.

Digital Library

[18]

S. Krishnan and L. V. Kalé. A parallel adaptive fast multipole algorithm for N-body problems. In Proceedings of the 24th International Conference on Parallel Processing, pages III:46-51, Oconomowoc, WI, August 1995.

[19]

George Lake, Thomas Quinn, and Derek C. Richardson. From Sir Isaac to the Sloan survey: Calculating the structure and chaos owing to gravity in the universe. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1-10, New Orleans, Louisiana, 5-7 January 1997.

Digital Library

[20]

Pangfeng Liu and Sandeep N. Bhatt. Experiences with parallel N-body simulations. In 6th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'94), pages 122-131, 1994.

Digital Library

[21]

Lars S. Nyland, Jan F. Prins, and John H. Reif. A data-parallel implementation of the adaptive fast multipole algorithm. In Proceedings of the 1993 DAGS/PC Symposium, pages 111-123, Hanover, NH, June 1993. Dartmouth Institute for Advanced Graduate Studies.

[22]

K. E. Schmidt and M. A. Lee. Implementing the fast multipole method in three dimensions. Journal of Statistical Physics, 63:1223-1235, 1991.

[23]

Jürgen Singer. The Parallel Fast Multipole Method in Molecular Dynamics. PhD thesis, University of Houston, August 1995.

Digital Library

[24]

Jaswinder Pal Singh. Parallel Hierarchical N-Body methods and their implications for parallel processors. PhD thesis, Stanford University, February 1993.

[25]

Leslie G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103-111, 1990.

Digital Library

[26]

M. S. Warren and J. K. Salmon. A parallel hashed oct-tree N-body algorithm. In ACM, editor, Proceedings, Supercomputing '93: Portland, Oregon, November 15-19, 1993, pages 12-21. ACM Press, 1993.

Digital Library

[27]

Michael S. Warren and John K. Salmon. A portable parallel particle program. Computer Physics Communications, 87, 1995.

[28]

M. S. Warren and J. K. Salmon. Astrophysical N-body simulations using hierarchical tree data structures. In Supercomputing '92, pages 570-576, 1992.

Digital Library

[29]

F. Zhao and S. L. Johnsson. The parallel multipole method on the connection machine. SIAM Journal on Scientific and Statistical Computing, 12:1420-1437, 1991.

Digital Library

[30]

Feng Zhao. An O(N) algorithm for three-dimensional N-body simulations. Technical report, Artificial Intelligence Laboratory, Massachusetts Institute of Technology (MIT), Cambridge, Massachusetts, October 1987.

Digital Library

Cited By

Liu JYang XZhang ZLiu M(2024)A massive MPI parallel framework of smoothed particle hydrodynamics with optimized memory management for extreme mechanics problemsComputer Physics Communications10.1016/j.cpc.2023.108970295(108970)Online publication date: Feb-2024
https://doi.org/10.1016/j.cpc.2023.108970
Keller SCavelan ACabezon RMayer LCiorba FHuebl ASilvano CRobinson T(2023)Cornerstone: Octree Construction Algorithms for Scalable Particle SimulationsProceedings of the Platform for Advanced Scientific Computing Conference10.1145/3592979.3593417(1-10)Online publication date: 26-Jun-2023
https://dl.acm.org/doi/10.1145/3592979.3593417
Liu ZWang QLv XLiu XMeng HZhu GGao LFu HYang G(2023) swPHoToNs : Toward trillion‐body‐scale cosmological N ‐body simulations on Sunway TaihuLight supercomputer Engineering Reports10.1002/eng2.12640Online publication date: 19-Feb-2023
https://doi.org/10.1002/eng2.12640
Show More Cited By

Recommendations

Parallel Haskell implementations of the N-body problem

This paper provides an assessment of high-level parallel programming models for multi-core programming by implementing two versions of the n-body problem. We compare three different parallel programming models on the basis of parallel Haskell, differing ...
Portable and Efficient Parallel Computing Using the BSP Model

The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a standard interface between parallel software and hardware. In theory, the BSP model has been shown to allow the asymptotically optimal execution of architecture-independent software ...
A portable parallel algorithm for logic synthesis using transduction

Combinational logic synthesis is a very important phase of VLSI system design. But the logic synthesis process requires large computing times if near optimal quality of the logic network is desired. Parallel processing is fast becoming an attractive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '97: Proceedings of the 1997 ACM/IEEE conference on Supercomputing

November 1997

921 pages

ISBN:0897919858

DOI:10.1145/509593

General Chair:
Dona Crawford

Copyright © 1997 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 November 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SC '97

Sponsor:

SIGARCH
IEEE-CS

SC '97: International Conference for High Performance Computing, Networking, Storage and Analysis

November 15 - 21, 1997

CA, San Jose

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
501
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)10

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu JYang XZhang ZLiu M(2024)A massive MPI parallel framework of smoothed particle hydrodynamics with optimized memory management for extreme mechanics problemsComputer Physics Communications10.1016/j.cpc.2023.108970295(108970)Online publication date: Feb-2024
https://doi.org/10.1016/j.cpc.2023.108970
Keller SCavelan ACabezon RMayer LCiorba FHuebl ASilvano CRobinson T(2023)Cornerstone: Octree Construction Algorithms for Scalable Particle SimulationsProceedings of the Platform for Advanced Scientific Computing Conference10.1145/3592979.3593417(1-10)Online publication date: 26-Jun-2023
https://dl.acm.org/doi/10.1145/3592979.3593417
Liu ZWang QLv XLiu XMeng HZhu GGao LFu HYang G(2023) swPHoToNs : Toward trillion‐body‐scale cosmological N ‐body simulations on Sunway TaihuLight supercomputer Engineering Reports10.1002/eng2.12640Online publication date: 19-Feb-2023
https://doi.org/10.1002/eng2.12640
Du YMarchal LPallez (Aupy) GRobert Y(2020)Robustness of the Young/Daly formula for stochastic iterative applicationsProceedings of the 49th International Conference on Parallel Processing10.1145/3404397.3404418(1-11)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1145/3404397.3404418
Iwasawa MNamekata DNomura KTsubouchi MMakino J(2020)Extreme-scale particle-based simulations on advanced HPC platformsCCF Transactions on High Performance Computing10.1007/s42514-020-00020-1Online publication date: 19-Feb-2020
https://doi.org/10.1007/s42514-020-00020-1
Iwasawa MTanikawa AHosono NNitadori KMuranushi TMakino J(2016)Implementation and performance of FDPS: a framework for developing parallel particle simulation codesPublications of the Astronomical Society of Japan10.1093/pasj/psw05368:4(54)Online publication date: 7-Jun-2016
https://doi.org/10.1093/pasj/psw053
Drozd AWitkowski OMatsuoka SIkegami T(2016)Critical mass in the emergence of collective intelligenceArtificial Life and Robotics10.1007/s10015-016-0303-821:3(317-323)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s10015-016-0303-8
Iwasawa MTanikawa AHosono NNitadori KMuranushi TMakino J(2015)FDPSProceedings of the 5th International Workshop on Domain-Specific Languages and High-Level Frameworks for High Performance Computing10.1145/2830018.2830019(1-10)Online publication date: 15-Nov-2015
https://dl.acm.org/doi/10.1145/2830018.2830019
Bédorf JGaburov EFujii MNitadori KIshiyama TZwart SDamkroger TDongarra J(2014)24.77 Pflops on a gravitational tree-code to simulate the Milky Way Galaxy with 18600 GPUsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC.2014.10(54-65)Online publication date: 16-Nov-2014
https://dl.acm.org/doi/10.1109/SC.2014.10
Ishiyama TNitadori KMakino JHollingsworth J(2012)4.45 Pflops astrophysical N-body simulation on K computerProceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis10.5555/2388996.2389003(1-10)Online publication date: 10-Nov-2012
https://dl.acm.org/doi/10.5555/2388996.2389003
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents