一句话：提出双层层次化哈希表与跳表设计，在 GPU 统一虚拟内存超额订阅下提升访问局部性与性能。
GPU 工作负载的内存占用不断增长，内核所使用的数据结构可能超出全局内存容量。统一虚拟内存（UVM）模型允许内核在不显式管理内存的情况下超额订阅 GPU 内存，但本文表明，在 UVM 下执行的数据结构会因数据迁移开销大以及不规则访问模式引发的抖动而性能退化。为此，作者为哈希表和跳表提出两级层次化设计，以最大化访问局部性并支持数据结构超额订阅 GPU 内存的场景：外层容器用于高效跳转到数据结构的目标区域，内层容器用于执行实际操作，且内层容器的大小经过设定，以便在 CPU 与 GPU 之间高效传输数据。在多种输入操作序列上的实验表明，该设计在支持高度 GPU 内存超额订阅的同时显著优于经过优化的 UVM 基线；将其用于宏基因组分类与 k-mer 计数应用中的键值存储时，哈希表取得 2.06×、跳表取得 2.37× 的几何平均加速。
Efficient concurrent data structures are important building blocks for accelerating applications on GPUs. With the ever-increasing memory footprint of GPU workloads, data structures used by kernels can exceed global memory capacity. Using the unified virtual memory (UVM) model is a popular approach for kernels to oversubscribe GPU memory without the need for explicit memory management by a programmer. However, we show that data structures executing with UVM can suffer from performance degradation due to the high overheads associated with data migration and thrashing for irregular access patterns. In this paper, we propose two-level hierarchical designs for hash table and skip list data structures that aim to maximize access locality and handle use cases where the data structure oversubscribes GPU memory. The outer-level container enables efficient jumps to desired regions of the data structure, while the inner container allows operating on the data. The inner container is sized to facilitate efficient data transfers between the CPU and the GPU. Experimental results on a diverse set of input operation sequences show that our data structure designs substantially improve performance over optimized UVM baselines while supporting high degrees of GPU memory oversubscription. Importantly, our proposed design, when used to implement key-value stores in metagenomics classification and k-mer counting applications, achieves a geomean speedup of 2.06× for hash table and 2.37× for skip list over baseline UVM implementations.
@article{paperbot3782,
title = {Designing GPU Data Structures for Efficient Memory Oversubscription},
author = {Vipin Patel and Srinjoy Sarkar and Swarnendu Biswas and Mainak Chaudhuri},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {OOPSLA1},
year = {2026},
doi = {10.1145/3798244}
}