Scalable parallel formulations of the Barnes-Hut method for n-body simulations

Ananth Y. Grama, Vipin Kumar, Ahmed Sameh

Research output: Contribution to journalConference articlepeer-review

37 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)439-448
Number of pages10
JournalProceedings of the ACM/IEEE Supercomputing Conference
StatePublished - 1994
EventProceedings of the 1994 Supercomputing Conference - Washington, DC, USA
Duration: Nov 14 1994Nov 18 1994

Bibliographical note

Funding Information:
This work is sponsored by the by Army Research Office contract DA/DAAH04-95-1-0538 and by Army High Performance Computing Research Center under the auspices of the Department of the Army, Army Research Laboratory cooperative agreement no. DAAH04-95-2-0003/contract no. DAAH04-95-C-0008, the content of which does not necessarily reflect the position or the policy of the government, and no official endorsement should be inferred. This work is also sponsored in part by MSI. Access to computing facilities was provided by Cray Research and by the Pittsburgh Supercomputing Center. Related papers are available via WWW at URL: The authors wish to acknowledge anonymous reviewers whose comments served to improve the quality of this manuscript.


Dive into the research topics of 'Scalable parallel formulations of the Barnes-Hut method for n-body simulations'. Together they form a unique fingerprint.

Cite this