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-throughput, low-latency applications, yet supporting updates on GPU-resident data structures remains challenging, since a design must balance massive parallelism with efficient memory access and fast queries.
The journey to a high-speed, state-of-the-art updatable GPU data structure has its origins in ray tracing. We begin with a brief introduction to cgRXu, a hybrid GPU–ray tracing data structure that uses ray tracing cores to perform queries and offers updatability through general-purpose CUDA cores. cgRXu illustrates that updates can be applied on the GPU without rebuilding the structure; however, query performance declines as chains of nodes grow under updates. Lessons from cgRXu helped shape the design of FliX.
FliX is a fully GPU-resident ordered data structure that introduces an index-less approach to database indexing, where compute is assigned to partitions of stored data rather than to individual operations. FliX also provides cooperative bulk insertion and deletion algorithms that process groups of keys in-place within a node and reclaim unused space. Experiments show that FliX significantly outperforms state-of-the-art ordered baselines and is comparable to or outperforms GPU hash tables; it achieves orders-of-magnitude faster successor queries than a GPU LSM-tree and over 8x faster bulk insertions than a GPU B-tree.
We then address fully concurrent execution in FliX, in which updates and queries are applied to the data structure 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 studies demonstrate 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.