Article

Free access

Experiences with parallel N-body simulation

Authors:

Sandeep N. BhattAuthors Info & Claims

SPAA '94: Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures

Pages 122 - 131

https://doi.org/10.1145/181014.181081

Published: 01 August 1994 Publication History

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]

J. Barnes. A modified tree code: Don't laugh; it runs. Journal o/ Computational Physics, 87:161- 170, 1990.

Digital Library

[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 and V. Rokhlin. A fast algorithm for particle simulations. J. Comput. Physics, 73:325, 1987.

Digital Library

[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]

P. Liu, W. Aiello, and S. Bhatt. An atomic model for message passing. In 5th Annual A CM Symposium on Parallel Algorithms and Architecture, 1993.

Digital Library

[12]

L. Nyland, J. Prins, and J. Reif. A data-parallel implementation of the adaptive fast multipole algorithm. In DAGS/PC Symposium, 1993.

[13]

J. Salmon. Parallel Hierarchical N-body Methods. PhD thesis, Caltech, 1990.

Digital Library

[14]

J. Singh. Parallel Hierarchical N-body Methods and their Implications for Multiprocessors. PhD thesis, Stanford University, 1993.

Digital Library

[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]

S. Sundaram. Fast Algorithms/or N-body Simulations. PhD thesis, Cornell University, 1993.

Digital Library

[17]

M. Warren and J. Salmon. Astrophysical n-body simulations using hierarchical tree data structures. In Proceedings of Supercomputing, 1992.

Digital Library

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

Cited By

Dekate CAnderson MBrodowicz MKaiser HAdelstein-Lelbach BSterling T(2012) Improving the scalability of parallel N -body applications with an event-driven constraint-based execution model The International Journal of High Performance Computing Applications10.1177/109434201244058526:3(319-332)Online publication date: 11-Apr-2012
https://doi.org/10.1177/1094342012440585
Kurzak JPettitt B(2005)Massively parallel implementation of a fast multipole method for distributed memory machinesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2005.02.00165:7(870-881)Online publication date: 1-Jul-2005
https://dl.acm.org/doi/10.1016/j.jpdc.2005.02.001
Yu YIbarra OYang T(2005)Parallel progressive radiosity with adaptive meshingParallel Algorithms for Irregularly Structured Problems10.1007/BFb0030106(159-170)Online publication date: 16-Jun-2005
https://doi.org/10.1007/BFb0030106
Show More Cited By

Index Terms

Experiences with parallel N-body simulation
1. Computing methodologies
  1. Modeling and simulation
  2. Parallel computing methodologies
    1. Parallel algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Parallel algorithms

Recommendations

Experiences with Parallel N-Body Simulation

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; ...
Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation

We present an efficient and provably good partitioning and load balancing algorithm for parallel adaptive N-body simulation. The main ingredient of our method is a novel geometric characterization of a class of communication graphs that can be used to ...
Parallel multigrid summation for the N-body problem

An @Q(n) parallel multigrid summation method (MG) for the N-body problem is presented. The method was originally devised for vacuum boundary conditions. Here, it is extended to periodic boundary conditions and implemented in parallel using force ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '94: Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures

August 1994

374 pages

ISBN:0897916719

DOI:10.1145/181014

Chairmen:
Lawrence Snyder
Univ. of Washington, Seattle
,
Charles E. Leiserson
Massachusetts Institute of Technology, Cambridge

Copyright © 1994 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

European Comp Soc: European Computer Society
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

6SPAA94

Sponsor:

European Comp Soc
SIGACT
SIGARCH

6SPAA94: 6th Annual ACM Symposium on Parallel Algorithms and Architectures

June 27 - 29, 1994

New Jersey, Cape May, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
212
Total Downloads

Downloads (Last 12 months)140
Downloads (Last 6 weeks)12

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dekate CAnderson MBrodowicz MKaiser HAdelstein-Lelbach BSterling T(2012) Improving the scalability of parallel N -body applications with an event-driven constraint-based execution model The International Journal of High Performance Computing Applications10.1177/109434201244058526:3(319-332)Online publication date: 11-Apr-2012
https://doi.org/10.1177/1094342012440585
Kurzak JPettitt B(2005)Massively parallel implementation of a fast multipole method for distributed memory machinesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2005.02.00165:7(870-881)Online publication date: 1-Jul-2005
https://dl.acm.org/doi/10.1016/j.jpdc.2005.02.001
Yu YIbarra OYang T(2005)Parallel progressive radiosity with adaptive meshingParallel Algorithms for Irregularly Structured Problems10.1007/BFb0030106(159-170)Online publication date: 16-Jun-2005
https://doi.org/10.1007/BFb0030106
Ranade A(2005)Bandwidth efficient parallel computationAutomata, Languages and Programming10.1007/3-540-61440-0_114(4-23)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-61440-0_114
Zhou BZhou S(2004)Parallel simulation of group behaviorsProceedings of the 36th conference on Winter simulation10.5555/1161734.1161806(364-370)Online publication date: 5-Dec-2004
https://dl.acm.org/doi/10.5555/1161734.1161806
Bo Zhou Suiping Zhou (2004)Parallel Simulation of Group BehaviorsProceedings of the 2004 Winter Simulation Conference, 2004.10.1109/WSC.2004.1371337(356-362)Online publication date: 2004
https://doi.org/10.1109/WSC.2004.1371337
Chen ZDelis ABertoni H(2004)Radio-wave propagation prediction using ray-tracing techniques on a network of workstations (NOW)Journal of Parallel and Distributed Computing10.1016/j.jpdc.2004.07.00464:10(1127-1156)Online publication date: 1-Oct-2004
https://dl.acm.org/doi/10.1016/j.jpdc.2004.07.004
Shan HSingh JOliker LBiswas R(2002)A Comparison of Three Programming Models for Adaptive Applications on the Origin2000Journal of Parallel and Distributed Computing10.1006/jpdc.2001.177762:2(241-266)Online publication date: 1-Feb-2002
https://dl.acm.org/doi/10.1006/jpdc.2001.1777
Shan HSingh JOliker LBiswas RTurcotte L(2000)A comparison of three programming models for adaptive applications on the Origin2000Proceedings of the 2000 ACM/IEEE conference on Supercomputing10.5555/370049.370070(11-es)Online publication date: 1-Nov-2000
https://dl.acm.org/doi/10.5555/370049.370070
Hongzhang Shan Singh JOliker LBiswas R(2000)A Comparison of Three Programming Models for Adaptive Applications on the Origin2000ACM/IEEE SC 2000 Conference (SC'00)10.1109/SC.2000.10004(11-11)Online publication date: 2000
https://doi.org/10.1109/SC.2000.10004
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