Abstract: Because of the excellent parallel acceleration capabilities of GPU, applying common in-memory index structures to GPU has become a new research direction. At present, the number of in-memory index structures optimized for GPU that support concurrent access and can be dynamically updated is still relatively small. This paper presents GLHT (GPU lock-free hopscotch Hash table) that supports concurrent access and can be dynamically updated. Using global memory coordinating with atomic operations and specific concurrency control strategies, it implements concurrent access and lock-free feature, while ensuring the wait-free feature of read operations. GLHT combines efficient coalesced access of GPU memory and warp-cooperative work sharing strategy to achieve high parallel acceleration capability. GLHT has 4—9x performance advantages over existing CPU hopscotch Hash tables. GLHT is more flexible than GPU lock-free chained Hash tables with pre-allocated memory and has better performance in write-weighted workloads.

Key words: hopscotch Hash table, coalesced access, warp-cooperative work sharing strategy, atomicCAS

摘要： 由于GPU具有卓越的并行加速能力，将通用的内存索引结构应用于GPU成了一个新的研究方向。目前，针对GPU进行优化的支持并发访问且可动态更新的内存索引结构还比较少。提出一种支持并发访问且可动态更新的GPU无锁跳步哈希表（GPU lock-free hopscotch Hash table，GLHT），采用全局内存配合原子操作以及特定的并发控制策略，在实现并发访问和无锁特性的同时，保证了读操作的无等待特性。GLHT结合高效的GPU内存合并访问和warp协同工作共享策略，获得了很高的并行加速能力。与现有CPU跳步哈希表相比，具有4~9倍的性能优势；比采取预先分配内存的GPU无锁链式哈希表更加灵活，并且在写操作较重的工作负载中获得了更好的性能。

关键词: 跳步哈希表, 合并访问, warp协同工作共享策略, atomicCAS