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

发布时间：2018-03-24 04:19

本文选题：哈希连接　切入点：无锁　出处：《计算机学报》2017年10期

【摘要】：众核协处理器因其良好的并行计算能力和能源效率,正成为当前高性能计算普遍采用的加速设备.无划分哈希连接算法是多核平台上一种简单高效的连接算法,但随着众核上并发线程数的增加,其共享哈希表的锁同步问题正成为算法并行化的瓶颈.为解决上述问题,该文提出一种面向众核协处理器的自适应无锁哈希连接算法ALFHJ.该算法通过评估数据集的潜在冲突度动态调整算法参数及处理流程,支持基于CAS(比较与交换)原子操作的无锁共享哈希表构建,并利用SIMD指令进行哈希表探测.同时,该文进行了热点代码分析,讨论了一致性问题、ABA问题以及收敛性问题.在Xeon Phi上的实验结果表明,相比最新的基于锁同步的NPO(优化的无分区哈希连接)算法,ALFHJ算法有以下两点优势:(1)在提高哈希表空间利用率的同时,更能保持性能的相对稳定;(2)并行执行时间对于均匀数据集减少约10%,对于倾斜数据集减少约30%~50%.
[Abstract]:Due to its good parallel computing capability and energy efficiency, multi-core coprocessor is becoming a widely used accelerator in high performance computing. Non-partition hash join algorithm is a simple and efficient join algorithm on multi-core platform. However, with the increase of the number of concurrent threads on the multikernel, the lock synchronization problem of the shared hash table is becoming the bottleneck of the parallelization of the algorithm. In this paper, an adaptive unlocked hashing algorithm ALFHJ for multi-kernel coprocessor is proposed. The algorithm dynamically adjusts the parameters and processing flow of the algorithm by evaluating the potential conflict degree of the data set. It supports the construction of unlocked shared hash table based on CAS atomic operation, and detects the hash table using SIMD instruction. At the same time, the hot spot code analysis is carried out in this paper. The consistency problem and convergence problem are discussed. The experimental results on Xeon Phi show that, Compared with the new Lock Synchron-based NPO (optimized Partition Free Hash join) algorithm, ALFHJ has the following two advantages: 1) improving the utilization rate of hash table space, A relatively stable parallel execution time is reduced by about 10 for uniform data sets and 30, 50 for tilted datasets.
【作者单位】：中国人民大学数据工程与知识工程国家教育部重点实验室;中国人民大学信息学院;西南林业大学计算机与信息学院;
【基金】：国家自然科学基金(61532021,61772537,61772536,61702522) 国家重点研发计划(2016YFB1000702) 国家“九七三”重点基础研究发展计划项目基金(2014CB340402) 云南省应用基础研究基金(2011FB070)资助~~
【分类号】：TP301.6;TP332

【相似文献】