<p dir="ltr">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.</p>

The propagation paths of sound in water can be somewhat complicated due to the fact that the sound speed in water varies with properties such as water temperature and pressure, which has the effect of curving the propagation paths. This thesis shows how sound propagation in water can be simulated using a ray-tracing based approach on a GPU using Nvidia’s OptiX ray-tracing engine. In particular, it investigates how much speed-up can be achieved compared to CPU based implementations and whether the RT cores introduced in Nvidia’s Turing architecture, which provide hardware accelerated ray-tracing, can be used to speed up the computations. The presented GPU implementation is shown to be up to 310 times faster then the CPU based Fortran implementation Bellhop. Although the speed-up is significant, it is hard to say how much speed-up is gained by utilizing the RT cores due to not having anything equivalent to compare the performance to.