Barnes-Hut: An Implementation and Study


Motivation

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

  • How does caching affect tree-build performance? Overall performance?
  • What is the maximum problem size we can support?
  • What are other tree-building schemes, and what are their strengths and weaknesses?
  • 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>