A parallel hashed Oct-Tree N-body algorithm
Michael S. Warren, John K. Salmon · 1993
We report on an eficient 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 acclwacy of the force calculations is analytically bounded, and can be adjusted via a user dejined parameter be fit'een a few percent relative accaracy, doivn 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 eflcient 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 benejitfiom application of this type of algorithm.1 Introduction N-body simulations have become a fundamental tool in the study of complex physical systems.Starting fkom a basic physical interaction (e.g., gravitational, Coulombic, Biot-Savart, van der Waals) one can follow the dynamical evolution of a system of N bodies, which represent the phase-space density distribution of the system.N-body simulations are essentially statistical in nature (unless the physical system can be directly modeled by N bodies, as is the case in some molectdar dynamics simulations).More bodies implies a more accurate and complete sampling of the phase space, and hence more accurate or complete results.Unfortunately, the minimum aeeuracy required to model systems of interest often depends on having N be much larger than current computational resources allow.Because interactions occur between each pair of particles in a N-body simulation, the computational work scales