RT-BarnesHut: Accelerating Barnes-Hut Using Ray-Tracing Hardware

The 𝑛-body problem involves calculating the effect of bodies on each other. 𝑛-body simulations are ubiquitous in the fields of physics and astronomy and notoriously computationally expensive. The naïve algorithm for 𝑛-body simulations has the prohibiting 𝑂 (𝑛 2 ) time complexity. Reducing the time complexity to 𝑂 (𝑛 • lg(𝑛)), the tree-based Barnes-Hut algorithm approximates the effect of bodies beyond a certain threshold distance. Other than algorithmic improvements, extensive research has gone into accelerating 𝑛-body simulations on GPUs and multi-core systems. However, Barnes-Hut is a tree-traversal algorithm, which makes it a poor target for acceleration using traditional GPU shader cores. In contrast, recent work shows that, for tree-based computations, GPU ray-tracing (RT) cores dominate shader cores. In this work, we reformulate the Barnes-Hut algorithm as a ray-tracing problem and implement it with NVIDIA OptiX. Our evaluation shows that the resulting system, RT-Bar-nesHut, outperforms current state-of-the-art GPU-based implementations.

We thank the anonymous PPoPP reviewers and our shepherd for their valuable feedback. We thank Dr. Tom Quinn for answering our questions about ChaNGa.