A Parallel Hashed Oct-Tree N-Body Algorithm

by Michael S. Warren and John K. Salmon

in Supercomputing '93 pages 12-21, Los Alamitos, IEEE Comp. Soc, 1993

The Supercomputing 2018 Test of Time Award (ToTA) Committee selected this paper as the "test of time" winner. The award-winning paper describes a technique for solving N-body problems, which arise in a large number of fields from astrophysics to chemistry at both large and small scales.

Abstract:

We report on an efficient adaptive N-body method which we 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.


Several formats for this paper are available.

Other Publications


John Salmon