Scalable parallel formulations of the Barnes-Hut method for n-body simulations
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper, we present two new parallel formulations of the Barnes-Hut method. These parallel formulations are especially suited for simulations with irregular particle densities. We first present a parallel formulation that uses a static partitioning of the domain and assignment of subdomains to processors. We demonstrate that this scheme delivers acceptable load balance, and coupled with two collective communication operations, it yields good performance. We present a second parallel formulation which combines static decomposition of the domain with an assignment of subdomains to processors based on Morton ordering. This alleviates the load imbalance inherent in the first scheme. The second parallel formulation is inspired by two currently best known parallel algorithms for the Barnes-Hut method. We present an experimental evaluation of these schemes on a 256 processor nCUBE2 parallel computer for an astrophysical simulation.Keywords
This publication has 12 references indexed in Scilit:
- Astrophysical N-body simulations using hierarchical tree data structuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Scalable parallel formulations of the Barnes-Hut method for n-body simulationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A parallel hashed Oct-Tree N-body algorithmPublished by Association for Computing Machinery (ACM) ,1993
- Accelerated molecular dynamics simulation with the parallel fast multipole algorithmChemical Physics Letters, 1992
- The order of Appel's algorithmInformation Processing Letters, 1992
- The Parallel Multipole Method on the Connection MachineSIAM Journal on Scientific and Statistical Computing, 1991
- Implementing the fast multipole method in three dimensionsJournal of Statistical Physics, 1991
- A parallel version of the fast multipole methodComputers & Mathematics with Applications, 1990
- An analysis of scatter decompositionIEEE Transactions on Computers, 1990
- A fast algorithm for particle simulationsJournal of Computational Physics, 1987