A Caltech Library Service

A parallel hashed Oct-Tree N-body algorithm

Warren, Michael S. and Salmon, John K. (1993) A parallel hashed Oct-Tree N-body algorithm. In: Supercomputing '93 Proceedings of the 1993 ACM/IEEE conference on Supercomputing. ACM , New York, NY, pp. 12-21. ISBN 0-8186-4340-4.

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

Use this Persistent URL to link to this item:


We report on an efficient adaptive N-body method which u~e have recently designed and implemented. The algorithm computes the forces on an arbitrary distribution of bodies in a time which scales as N log N with the particle number. The accuracy of the force calculations is analytically bounded, and can be adjusted via a user defined parameter between a few percent relative accuracy, down to machine arithmetic accuracy. Instead of using pointers to indicate the topology of the tree, we identify each possible cell with a key. The mapping of keys into memory locations is achieved via a hash table. This allows the program to access data in an efficient manner across multiple processors. Performance of the parallel program is measured on the 512 processor Intel Touchstone Delta system. We also comment on a number of wide-ranging applications which can benefit from application of this type of algorithm.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 1993 ACM. We thank Sanjay Ranka for pointing out the utility of Peano-Hilbert ordering. We thank the CSCC and the CCSF for providing computational resources. JS wishes to acknowledge support from the Advanced Computing Division of the NSF, as well as the CRPC. MSW wishes to acknowledge support from IGPP and AFOSR. This research was supported in part by a grant from NASA under the HPCC program. This research was performed in part using the Intel Touchstone Delta System operated by Caltech on behalf of the Concurrent Supercomputing Consortium.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)UNSPECIFIED
Record Number:CaltechAUTHORS:20170104-164232002
Persistent URL:
Official Citation:M. S. Warren and J. K. Salmon. 1993. A parallel hashed Oct-Tree N-body algorithm. In Proceedings of the 1993 ACM/IEEE conference on Supercomputing (Supercomputing '93). ACM, New York, NY, USA, 12-21. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73247
Deposited By: Kristin Buxton
Deposited On:05 Jan 2017 01:02
Last Modified:03 Oct 2019 16:26

Repository Staff Only: item control page