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

摘要

众核协处理器因其良好的并行计算能力和能源效率,正成为当前高性能计算普遍采用的加速设备.无划分哈希连接算法是多核平台上一种简单高效的连接算法,但随着众核上并发线程数的增加,其共享哈希表的锁同步问题正成为算法并行化的瓶颈.为解决上述问题,该文提出一种面向众核协处理器的自适应无锁哈希连接算法ALFHJ.该算法通过评估数据集的潜在冲突度动态调整算法参数及处理流程,支持基于CAS(比较与交换)原子操作的无锁共享哈希表构建,并利用SIMD指令进行哈希表探测.同时,该文进行了热点代码分析,讨论了一致性问题、ABA问题以及收敛性问题.在Xeon Phi上的实验结果表明,相比最新的基于锁同步的NPO(优化的无分区哈希连接)算法,ALFHJ算法有以下两点优势:(1)在提高哈希表空间利用率的同时,更能保持性能的相对稳定;(2)并行执行时间对于均匀数据集减少约1o％,对于倾斜数据集减少约30％～50％.%Many-core coprocessors are emerging as the widely-used acceleration devices in current high-performance computing area,due to their highly parallel computing capabilities and superior energy efficiencies.Non-partitioned hash join (NPHJ) is a simple and high efficient join algorithm for multi-core processors.But the lock-based synchronization for the shared hash table is becoming the bottleneck to parallelization when the number of concurrent threads is increasing on many-core coprocessors.To address this problem,we propose a novel algorithm named Adaptive Lock-Free Hash Join (ALFHJ).The ALFHJ can adaptively adjust the algorithm parameters and processing procedure by evaluating the potential conflict degree of input datasets,build the shared hash table in a lock-free manner based on Compare-And-Swap (CAS) atomic operations,and probe the hash table using SIMD instructions.This paper further performs detailed profiling at the critical code lines,and provides theoretical analysis over three crucial issues of ALFHJ:concurrent consistency,ABA and convergence.Finally,we compare our approach with NPO,the state-of-the-art lockbased non-partitioned hash join algorithm,on Xeon Phi coprocessor.The experimental results demonstrate that (1) ALFHJ can hold the performance stability better when the ratio of hash table's memory utilization increases;(2) the parallel execution time of ALFHJ is 10％ less than NPO on uniform datasets and 30％-50％ on skewed datasets.