Exploiting Hardware-Accelerated Ray Tracing for Spatial Tree Algorithms
Creators: name: Nagarajan, Vani
Publisher: name: Purdue University Graduate School
Year: 2024
Subjects: classificationCode: 460607
subject: High performance computing
classificationCode: 511001
subject: Accelerators

description: General Purpose computing on Graphical Processing Units (GPGPU) has resulted in un-precedented levels of speedup over its CPU counterparts, allowing programmers to harness the computational power of GPU shader cores to accelerate other computing applications. But this style of acceleration is best suited for regular computations (e.g., linear algebra). Recent GPUs feature new Ray Tracing (RT) cores that instead speed up the irregular process of ray tracing using Bounding Volume Hierarchies. While these cores seem limited in functionality, recent works have shown that it is possible to leverage the acceleration of RT cores by restructuring irregular problems to resemble ray tracing queries. In this dissertation, we explore leveraging RT cores to accelerate general-purpose computations. We introduce RT-accelerated variations of algorithms and suggest enhancements for current implementations. First, we propose RT-DBSCAN, the first RT-accelerated DBSCAN implementation. We use RT cores to accelerate Density-Based Clustering of Applications with Noise (DBSCAN) by translating fixed-radius nearest neighbor queries to ray tracing queries. As the neighbor queries are the main performance bottleneck in DBSCAN, we find that leveraging the RT hardware results in speedups between 1.3x to 4x over current state-of-the-art, GPU-based DBSCAN implementations. Though the existing translation of nearest neighbor search (NNS) problems to ray tracing queries has been shown to be effective, it imposes a constraint on the search space for neighbors. Due to this, we can only use RT cores to accelerate fixed-radius NNS, which requires the user to set a search radius a priori and hence can miss neighbors. To remedy this, we propose TrueKNN, the first unbounded RT-accelerated neighbor search. We solve the k-nearest neighbor search problem by adopting an iterative approach where we incrementally grow the search space until all points have found their k neighbors. We show that our approach is orders of magnitude faster than existing approaches and can even be used to accelerate fixed-radius neighbor searches. 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 naïve algorithm for n-body simulations has the prohibiting O(n2) time complexity. Reducing the time complexity to O(n · lg(n)), the tree-based Barnes-Hut algorithm approximates the effect of bodies beyond a certain threshold distance. In tree-based NNS, computation is restricted solely to the leaf nodes of the tree, whereas Barnes-Hut requires computation to occur at both the leaf and internal nodes of the tree. 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.