RT–BarnesHut: Accelerating Barnes–Hut Using Ray-Tracing Hardware
This program is tentative and subject to change.
The n-body problem involves calculating the effect of bodies on each other. n-body simulations are ubiquitous in the fields of physics and astronomy and notoriously computationally expensive. The naive algorithm for n-body simulations has the prohibiting $O(n^2)$ time complexity. Reducing the time complexity to $O(n \cdot \lg(n))$, 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 n-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.
This program is tentative and subject to change.
Mon 3 MarDisplayed time zone: Pacific Time (US & Canada) change
11:20 - 12:20 | |||
11:20 20mTalk | RT–BarnesHut: Accelerating Barnes–Hut Using Ray-Tracing Hardware Main Conference Vani Nagarajan Purdue University, Rohan Gangaraju Purdue University, Kirshanthan Sundararajah Virginia Tech, Artem Pelenitsyn Purdue University, Milind Kulkarni Purdue University | ||
11:40 20mTalk | EVeREST: An Effective and Versatile Runtime Energy Saving Tool for GPUs Main Conference Anna Yue University of Minnesota at Twin Cities, Pen-Chung Yew University of Minnesota at Twin Cities, Sanyam Mehta HPE | ||
12:00 20mTalk | TurboFFT: Co-Designed High-Performance and Fault-Tolerant Fast Fourier Transform on GPUs Main Conference Shixun Wu University of California, Riverside, Yujia Zhai NVIDIA Corporation, Jinyang Liu University of California, Riverside, Jiajun Huang University of California, Riverside, Zizhe Jian University of California, Riverside, Huangliang Dai University of California, Riverside, Sheng Di Argonne National Laboratory, Franck Cappello Argonne National Laboratory, zizhong chen University of California, Riverside |