计算机科学与探索

作者：张娟，孙建伶

单位：1. 浙江大学 计算机科学与技术学院,杭州 3100272. 阿里巴巴-浙江大学前沿技术联合研究中心，杭州 311121

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

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

来源：2019年第6期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2019年第6期