计算机工程 ›› 2013, Vol. 39 ›› Issue (4): 296-299,304.doi: 10.3969/j.issn.1000-3428.2013.04.068

• 开发研究与工程应用 • 上一篇    下一篇

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

王怀超,赵 雷   

  1. (苏州大学计算机科学与技术学院,江苏 苏州 215006)
  • 收稿日期:2012-04-28 出版日期:2013-04-15 发布日期:2013-04-12
  • 作者简介:王怀超(1987-),男,硕士,主研方向:并行与分布式计算;赵 雷,副教授
  • 基金项目:
    国家自然科学基金资助项目(61073061)

List Intersection Algorithm on Multi-core CPU/GPU Platform

WANG Huai-chao, ZHAO Lei   

  1. (School of Computer Science and Technology, Soochow University, Suzhou 215006, China)
  • Received:2012-04-28 Online:2013-04-15 Published:2013-04-12

摘要: 提出一个多核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

中图分类号: