A Caltech Library Service

An O(NlogN) hypercube N-body integrator

Warren, Mike and Salmon, John (1988) An O(NlogN) hypercube N-body integrator. In: C3P Proceedings of the third conference on Hypercube concurrent computers and applications. Vol.2. ACM , New York, NY, pp. 971-975. ISBN 0-89791-278-0.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The gravitational N-body algorithm of Barnes and Hut [1] has been successfully implemented on a hypercube concurrent processor. The novel approach of their sequential algorithm has demonstrated itself to be well suited to hypercube architectures. The sequential code achieves O (NlogN) speed by recursively dividing space into subcells, thereby creating a hierarchical grouping of particles. Computing interactions between these groups dramatically reduces the amount of communication between processors, as well as the number of force calculations. Parallelism is achieved through an irregular spatial grid decomposition. Since the decomposition topology is not simple, a general loosely synchronous communication routine has been developed. Operations are simplified if the conventional grey code decomposition is modified so that the bits are taken alternately from each Cartesian dimension. A speedup of 180 has been achieved for a 500,000 particle two-dimensional calculation on 256 processors. A speedup of 65 has been obtained for a 64,000 particle three-dimensional calculation on 256 processors.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 1988 ACM. This work was supported in part by Department of Energy Grant No. DE-FG03-85ER25009, the Program Manager of the Joint Tactical Fusion Office and the ESD division of the USAF as well as grants from IBM and SANDIA and a Shell Foundation Fellowship. We are indebted to Josh Barnes and Piet Hut for generously providing their C implementation of the sequential version of the algorithm.
Funding AgencyGrant Number
Department of Energy (DOE)DE-FG03-85ER25009
Joint Tactical Fusion OfficeUNSPECIFIED
Sandia National LaboratoriesUNSPECIFIED
Shell FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20170104-162747213
Persistent URL:
Official Citation:M. Warren and J. Salmon. 1989. An O(NlogN) hypercube N-body integrator. In Proceedings of the third conference on Hypercube concurrent computers and applications - Volume 2 (C3P), Geoffrey Fox (Ed.), Vol. 2. ACM, New York, NY, USA, 971-975. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73244
Deposited By: Kristin Buxton
Deposited On:05 Jan 2017 00:43
Last Modified:11 Nov 2021 05:13

Repository Staff Only: item control page