Nagarajan, VaniGangaraju, RohanSundararajah, KirshanthanPelenitsyn, ArtemKulkarni, Milind2025-03-062025-03-062025-03https://hdl.handle.net/10919/124811The 𝑛-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.application/pdfenCreative Commons Attribution 4.0 InternationalArticle - Refereed2025-03-01The author(s)https://doi.org/10.1145/3710848.3710885