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>