A parallel hashed Oct-Tree N-body algorithm
- Creators
- Warren, Michael S.
- Salmon, John K.
- Others:
- Borchers, Bob
- Crawford, Dona
Abstract
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.
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.Additional details
- Eprint ID
- 73247
- DOI
- 10.1145/169627.169640
- Resolver ID
- CaltechAUTHORS:20170104-164232002
- NSF
- CRPC
- IGPP
- Air Force Office of Scientific Research (AFOSR)
- NASA
- Created
-
2017-01-05Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field