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

Abstract

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-BarnesHut, outperforms current state-of-the-art GPU-based implementations.