ALFHJ:一种面向众核协处理器的自适应无锁哈希连接算法

• 作者: 周开来 孙辉 李翠平 董兆安 陈红
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 哈希连接 无锁 众核 协处理器 比较与交换
• 年，卷（期）: 2017,（10）
• 所属期刊栏目: 数据科学与工程
• 页码范围: 2404-2420
• 页数: 17页
• 分类号: TP391
• 字数: 17079字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2017.02404

摘要

众核协处理器因其良好的并行计算能力和能源效率,正成为当前高性能计算普遍采用的加速设备.无划分哈希连接算法是多核平台上一种简单高效的连接算法,但随着众核上并发线程数的增加,其共享哈希表的锁同步问题正成为算法并行化的瓶颈.为解决上述问题,该文提出一种面向众核协处理器的自适应无锁哈希连接算法ALFHJ.该算法通过评估数据集的潜在冲突度动态调整算法参数及处理流程,支持基于CAS(比较与交换)原子操作的无锁共享哈希表构建,并利用SIMD指令进行哈希表探测.同时,该文进行了热点代码分析,讨论了一致性问题、ABA问题以及收敛性问题.在Xeon Phi上的实验结果表明,相比最新的基于锁同步的NPO(优化的无分区哈希连接)算法,ALFHJ算法有以下两点优势:(1)在提高哈希表空间利用率的同时,更能保持性能的相对稳定;(2)并行执行时间对于均匀数据集减少约1o％,对于倾斜数据集减少约30％～50％.