GPU无锁跳步哈希表

摘要

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