## Barnes-Hut: An Implementation and Study

### Introduction

The Barnes-Hut algorithm is a classic solution method for the N-body problem . 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 . 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:

• a tree-build phase where a space-separated decomposition of the bodies and the resulting tree is created
• a load-balancing phase where the timestep's necessary total work (or an approximation thereof) is partitioned among the processors
• a particle interaction (or force computation) phase where some body-to-body interaction rule (such as he inverse-square law for gravity) is used to calculate the effects of each particle on the others
• an update phase where the effects of the interactions are propagated in preparation for the next iteration

(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:

• The body distribution is:
• highly non-uniform
• dynamic
• The computation requires adaptive data structures
• Updates need both local and global data
• often very large data sets are involved (sometimes as large as possible.)

Continue to Motivation

See a time step view of evolving galaxies

-----

maintained by <hodes@cs.berkeley.edu>