Barnes-Hut: An Implementation and Study


Introduction

The Barnes-Hut algorithm is a classic solution method for the N-body problem [6]. An N-body problem is often characterized by the necessity to interact each of the N bodies with every other one [3, 7], potentially an O(n^2) set of operations. A trivial algorithm is necessarily limited by the number of objects that it can interact per unit time. It may additionally incur memory limitations and an unbalanced ratio of computation to communication due to latency effects, bandwidth constraints, or network overhead. Barnes-Hut attempts to avoid these pitfalls by partitioning the data set into space-separated clusters and using this information to prune the number of interactions from O(n^2) to approximately O(n log n). (For an in-depth discussion on the time and error bounds, please see [13]. We include a summary.) It does so by taking advantage of the locality inherent in the space-partitioning: groups of particles far from one another can approximate their effect on each other, rather than calculate it precisely.

There are four basic steps performed during each iteration of the algorithm. They include:

(Note that in some implementations, the tree-build and load-balancing stages are done in tandem.)

In short, once the bodies have been partitioned into spatially decomposed subsets by the tree-build phase, these subsets' local dependencies should far outweigh those of more distant clusters of nodes. Thus, they may act as a group, or cell, when affecting these non-local bodies. The adaptive nature of the tree insures that there is sufficient precision in the separations to enable this simplification.

During the force computation phase, body-to-body and body-to-cell interactions are actually performed. The hope is that by choosing the groupings successfully in the tree-build phase, the number of force calculations in this third phase can be drastically reduced. In all current implementations of Barnes-Hut, the time required for the force-calculation phase dominates the time required to build the space-partitioning tree [3, 4, 8, 10]. Nevertheless, the computation phase in inherently dependent on the tree-build in that the part ions must successfully expose where simplification is reasonable.

Some Difficulties of the N-body problem:

There are many factors that contribute to difficulty of the problem:


Continue to Motivation


See a time step view of evolving galaxies

-----

maintained by <hodes@cs.berkeley.edu>