CPU/GPU平台下分布式集合求交算法的研究

摘要

互联网迅速膨胀所带来信息大爆炸使得现代搜索引擎正面临前所未有的性能挑战，每天约有数百亿条用户查询请求需要处理。作为搜索引擎处理用户查询的核心功能——倒排索引交集求取，一直是研究和关注的中心。随着计算机性能的不断发展，CPU从单核朝着多核方向发展。与此同时，受游戏市场的刺激，有着众核之称的图像处理单元(GPU)也飞速发展，逐渐成为高性能计算的研究热点。
　　 本文关注将这种新型多核CPU/GPU混合系统应用到倒排索引求交问题中。在对集合求交算法和CPU/GPU混合结构进行研究的基础上，本文给出了多核CPU/GPU平台下集合求交算法，并在由Sogou实验室提供的数据上进行实验验证，系统性能提升良好。本文工作可概括为以下几方面：
　　 首先，分析当前应用于CPU端集合求交算法和试验数据一般特性，然后综合几种快速的搜索和求交算法作为本文CPU端集合求交算法。试验结果显示集合求交速度有一定提升。
　　 其次，根据CUDA计算模型，在CPU端对数据搜索区间进行划分，然后由CPU将划分结果传递给GPU进行运算。CUDA中每个块的平均搜索范围急剧减少，从而在整体上大幅提升GPU端集合求交性能。
　　 第三，分析CPU和GPU共同计算倒排索引交集时的性能瓶颈。搜索引擎中倒排索引求交为数据密集型计算，经验证数据传输占用大量时间，因此文中采用流水线作业方法将传输延时和CPU端计算时间隐藏于交集计算过程中。
　　 最后，考虑到每个GPU只需一个CPU内核与之进行通信，CPU中其余内核计算资源将被浪费掉。为此文中采用并行编程将多核CPU的空闲内核充分利用起来进行集合求交运算，此部分内核贡献出很可观的计算能力。
　　 本文成功地将多核CPU/GPU混合平台应用于搜索引擎倒排索引求交算法上，大幅提升系统计算性能，对集合求交和通用GPU计算都有一定的参考价值。