An Implementation of a Tree-Based N-Body Algorithm on Message-Passing Architectures

In this paper, a “manager-worker” model for a parallel implementation of hierarchical N-body algorithm is introduced. We describe a load-balanced, extremely simple algorithm for solving the Astrophysics simulation of N-body problem using tree-based data structures and coarse-grained parallel architectures. This algorithm, based on the Barnes-Hut method, first assembles a tree data structure which represents the distribution of bodies, or particles, at all length-scales. A domain decomposition, or an adaptive load balancing technique is used to assign bodies to processors as well as to insure that processors are assigned equal amounts of work. Therefore, the problem of load balancing for parallelized particle simulations implemented on MIMD machines is addressed and a simple dynamic had balancing algorithm, called costzones, is employed A number of measurements were carried out in order to reveal the behavior of the N-body application with respect to a partitioning technique and load imbalance overhead. We also show that, with using the introduced manager-worker model and the costzones domain decomposition technique, the algorithm is load balanced and that the majority of the time of the algorithm is spent in performing on-processor functions and not in inter-processor communications. We have conducted our study on several MIMD machines such as the 256-processor Cray T3D and the 64-processor Intel Paragon at JPL/ESS-NASA and on the 32-processor Thinking Machines CMS at UMC.