Please note: This PhD seminar will take place in DC 1304.
Rosina Kharal, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Trevor Brown
Modern computing systems process enormous volumes of data, arriving at unprecedented rates, across databases, online services, scientific applications, and machine-learning pipelines. These systems must store and provide access to data for search and analysis, use it for model training and decision support, and update it in real time as conditions change. GPUs are increasingly favoured for such high-speed, real-time applications. Supporting updates on GPU-resident data structures remains challenging, since a design must balance massive parallelism with efficient updates, bounded memory use, and fast queries.
The journey to a high-speed, state-of-the-art updatable GPU data structure has its origins in ray tracing. Accordingly, we begin with a brief introduction to cgRXu, a hybrid GPU–ray tracing data structure that uses the ray tracing cores of modern GPUs to perform queries and offers updatability through the general-purpose CUDA cores. cgRXu showed that updates can be applied on the GPU without rebuilding the structure; however, query performance declines as chains of nodes grow under updates. The lessons of cgRXu led to the design choices made in FliX.
FliX is a fully GPU-resident concurrent data structure that introduces a flipped indexing approach to assigning work. Instead of assigning GPU threads to individual operations that each search an index, FliX removes the index layer and assigns compute resources to partitions of the stored data. Each partition locates and processes its own operations from a sorted batch. FliX further introduces cooperative bulk insertion and deletion algorithms that process groups of keys within a node in place and physically reclaim deleted space. Experiments show that FliX answers queries faster than ordered GPU baselines and remains competitive with GPU hash tables, while its bulk insertions are over 8x faster than a GPU B-tree and maintain lower overall memory use.
We then address fully concurrent execution in FliX, in which updates and queries are applied to the data structure on the GPU simultaneously rather than in separate phases. This is a much more difficult problem, since operations on the same key can take effect in any order and correctness becomes harder to define and verify.
Together, these results show that careful, architecture-aware design makes it possible to achieve efficient and scalable updatability on GPU-resident data without compromising query performance, offering a practical path forward for data-intensive applications increasingly shifting to GPUs.