多核CPU/GPU平台下的集合求交算法  

List Intersection Algorithm on Multi-core CPU/GPU Platform

作　　者：王怀超[1] 赵雷[1] 

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《计算机工程》2013年第4期296-299,304,共5页Computer Engineering

基　　金：国家自然科学基金资助项目(61073061)

摘　　要：提出一个多核CPU/GPU混合平台下的集合求交算法。针对CPU端求交问题,利用对数据空间局部性和中序求交的思想,给出内向求交算法和Baeza-Yates改进算法,算法速度分别提升0.79倍和1.25倍。在GPU端,提出有效搜索区间思想,通过计算GPU中每个Block在其余列表上的有效搜索区间来缩小搜索范围,进而提升求交速度,速度平均提升40%。在混合平台采用时间隐藏技术将数据预处理和输入输出操作隐藏在GPU计算过程中,结果显示系统平均速度可提升85%。A list intersection algorithm on Multi-Core CPU/GPU platform is put forward. For CPU, inwards intersection algorithm and refined Baeza-Yates algorithm are proposed, by taking advantage of data locality and in-order intersection strategy. they gain 0.79 and 1.25 times speed up respectively. For GPU, effective search interval thought is proposed. The search range is reduced by computing effective search interval in other lists of each Block, thus enhance the speed of the intersection, which irfiproves the speed of list intersection by 40%. For mixed-platform, the operation of data preprocessing and I/O is hidden by time hiding technology, and the final system has a speed up of about 85%.

关 键 词：集合求交 多核CPU GPU求交算法 并行算法 时间隐藏 有效搜索区间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]