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

ALFHJ:An Adaptive Lock-Free Hash Join Algorithm for Many-Core Coprocessors

作　　者：周开来 陈红[1,2] 孙辉[1,2] 李翠平[1,2] 董兆安[1,2] ZHOU Kai-Lai CHEN Hong SUN Hui LI Cui-Ping DONG Zhao-An(Key Laboratory of Data Engineering and Knowledge Engineering of the Ministry of Education （Renmin University of China ）, Beijing 100872 School of Information, Renmin University of China, Beijing 100872 School of Computer and Information, Southwest Forestry University, Kunming 650224)

机构地区：[1]中国人民大学数据工程与知识工程国家教育部重点实验室,北京100872 [2]中国人民大学信息学院,北京100872 [3]西南林业大学计算机与信息学院,昆明650224

出　　处：《计算机学报》2017年第10期2404-2420,共17页Chinese Journal of Computers

基　　金：国家自然科学基金(61532021;61772537;61772536;61702522);国家重点研发计划(2016YFB1000702);国家"九七三"重点基础研究发展计划项目基金(2014CB340402);云南省应用基础研究基金(2011FB070)资助~~

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

关 键 词：哈希连接 无锁 众核 协处理器 比较与交换 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]