ºìÐÓÊÓƵ

Topic

Yijie Wu

Department of Computer Science

Date & location

• Friday, April 11, 2025

• 1:00 P.M.

• Engineering Computer Science Building

• Room 468

Reviewers

Supervisory Committee

• Dr. Sean Chester, Department of Computer Science, University of Victoria (Supervisor)

• Dr. Brandon Haworth, Department of Computer Science, UVic (Member) 

External Examiner

• Dr. Amirali Baniasadi, Department of Electrical and Computer Engineering, University of Victoria 

Chair of Oral Examination

• Dr. Junling Ma, Department of Mathematics and Statistics, UVic

   

Abstract

With the increase in GPU memory and computing power, GPU databases have become more popular, driving extensive research on GPU-based indexing. One study introduced a novel approach called RTX(Ray-tracing Index), which utilizes ray-tracing cores(RT cores) to accelerate GPU indexing. However, RTX suffers from a large build size and slow range queries. A follow-up work called cgRX(Coarse-granular Indexing), optimized the construction and range query algorithms, improving throughput by 1.5x–3x in relation to memory footprint, the range query time by 2x, and 5.5x faster updatability compared to RTX. However, the experimental results of cgRX may be inaccurate because RTX was not properly optimized as a baseline in cgRX, at least for the range query.

To optimize the RTX, this thesis explores multiple OptiX(Nvidia’s Ray-tracing Software API) optimization strategies for RTX, including a revised range query algorithm, BVH partitioning, reverse mapping, and spatially closed query map ping. Additionally, the best configurations are applied to other baselines, including cgRX. All these improvements together are used to reproduce the experiments in cgRX.The evaluation is first based on the impact of each optimization technique on RTX. These optimizations reduce RTX’s memory usage during construction and improve range query performance. Then, cgRX, optimized RTX, and other baselines are compared using the same experimental setup as cgRX, all using their best configurations. The re-evaluated results differ significantly from those in cgRX.

In summary, this thesis contributes to RTX optimization by exploring the effects of multiple optimization techniques. The optimized RTX and baselines configured with optimized settings collectively aim to develop a high-performance GPU database index.