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

摘要：

提出一个多核CPU/GPU混合平台下的集合求交算法.针对CPU端求交问题,利用对数据空间局部性和中序求交的思想,给出内向求交算法和Baeza-Yates改进算法,算法速度分别提升0.79倍和1.25倍.在GPU端,提出有效搜索区间思想,通过计算GPU中每个Block在其余列表上的有效搜索区间来缩小搜索范围,进而提升求交速度,速度平均提升40％.在混合平台采用时间隐藏技术将数据预处理和输入输出操作隐藏在GPU计算过程中,结果显示系统平均速度可提升85％.

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

所属期刊栏目：39

分类号：TP301.6(计算技术、计算机技术)

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

在线出版日期：2013-08-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：296-299,304