N-body simulations play a crucial role in theoretical astrophysics.
Recently hierarchical methods such as the Barnes-Hut algorithm [25]
have been introduced which reduce the time required for N-body simulations
from O( 
) for standard algorithms to O( 
) or even O(N).
These methods work by reducing an M-body force calculation for a cluster of
stars to a single calculation using the center of mass of the cluster.
This involves constructing an irregular, hierarchical tree-like
data structure (shown in Fig. 4), where each particle is in a single cell.
Clusters of particles may be represented by the center of mass of a
coarser cell.
Using the standard O( ) algorithm, simulations are limited to
O( 
) particles.
Using clustering methods, much more realistic simulations of O( 
)
particles are possible.
These methods have been used for simulations of the evolution of structure
in the Universe following the Big Bang, and for the study of galactic
structure caused by collisions of galaxies.
Due to the irregularity of the problem and the complexity of the data structure, this problem is not well expressed in parallel (or even sequential) Fortran, and is difficult to parallelize. In spite of the irregular and complex nature of this problem, John Salmon and Mike Warren have implemented a parallel Barnes-Hut algorithm using message passing on MIMD machines which has given extremely good performance (approximately 5 GFlops on the Intel Delta). [26] This work was acknowledged by the 1992 Gordon Bell Prize.
Figure 4:
Decomposition of particles into a hierarchical tree structure
for a Barnes-Hut N-body particle dynamics algorithm.
In spite of the apparent difficulties in expressing this kind of algorithm in HPF, Warren and Salmon have recently reformulated the parallel Barnes-Hut algorithm in a form which appears suitable for incorporation into an extended HPF compiler as a generalization of the PARTI methods used to parallelize irregular grids. [18]