摘要: 提出一个多核CPU/GPU混合平台下的集合求交算法。针对CPU端求交问题,利用对数据空间局部性和中序求交的思想,给出内向求交算法和Baeza-Yates改进算法,算法速度分别提升0.79倍和1.25倍。在GPU端,提出有效搜索区间思想,通过计算GPU中每个Block在其余列表上的有效搜索区间来缩小搜索范围,进而提升求交速度,速度平均提升40%。在混合平台采用时间隐藏技术将数据预处理和输入输出操作隐藏在GPU计算过程中,结果显示系统平均速度可提升85%。
关键词:
集合求交,
多核CPU,
GPU求交算法,
并行算法,
时间隐藏,
有效搜索区间
Abstract: 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 improves 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%.
Key words:
list intersection,
multi-core CPU,
GPU intersection algorithm,
parallel algorithm,
time hiding,
valid search range
中图分类号:
王怀超, 赵雷. 多核CPU/GPU平台下的集合求交算法[J]. 计算机工程, 2013, 39(4): 296-299,304.
WANG Fu-Chao, DIAO Lei. List Intersection Algorithm on Multi-core CPU/GPU Platform[J]. Computer Engineering, 2013, 39(4): 296-299,304.