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

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