## Barnes-Hut: An Implementation and Study

### Motivation

Starting from our initial implementation, some of the issues we
were interested in examining included the following:

For the first part of our project, we spent much of our time
exploring the design space afforded by Split-C, first by implementing
the *O(n^2)* algorithm, then by implementing the single-node
tree-build algorithm, and finally by doing a parallel tree-build based
on an atomic update procedure. While the *O(n^2)* algorithm may
be a poor choice for many N-body problems (such as the ones Barnes-Hut
is oriented toward), we imagine that there are other applications where
*O(n^2)* steps are necessary even in their most aggressive parallel
implementation. This will occur when it is simply impossible to prune
any of the body-to-body interactions because no single subset dominates.
For he second part of our project, we concentrated on refining our
parallel implementation and studying the various tree-build algorithms
from the literature. We added
caching of body and cell nodes, and developed
a parallel hash-table based tree build based on
[10]. We additionally ported our code to additional architectures. We now
run on the CM5, Meiko, and the Recent cluster.

Continue to
Tree Building

-----

maintained by <hodes@cs.berkeley.edu>