面向大规模查询处理的GPU缓存框架设计

摘要

随着搜索引擎面临越来越大的性能压力，使用现代图形处理器(Graphic Processing Units)进行搜索引擎查询处理加速被证明是一个有效提高搜索引擎效率的途径。GPU的众核架构十分有利于加速查询处理算法。但是，由于搜索引擎需要处理的数据量日益增长，GPU有限的显存空间限制了它在这个领域的应用。在本文中，我们提出一种面向大规模查询处理的GPU缓存框架。该框架使得在GPU上处理远大于显存空间的倒排索引成为可能。另一方面，我们注意到，在查询处理中应用提前停止算法（early termination）后，大部分倒排链表只被部分地访问到。基于此，我们提出了一种基于倒排链表剪枝的GPU静态缓存算法。该算法只缓存倒排链表中被频繁访问到的部分，使得显存中能够容纳更多的链表。
　　为了提高在剪枝索引上的查询效率，我们在 GPU上实现了数据并行的查询处理算法，包括链表求交、top-k排序和提前停止算法等多个步骤。对比于CPU查询处理算法，GPU算法达到11倍的加速比。此外，为了保证在剪枝索引上进行的查询处理的结果是正确、完整的，我们提出了一种GPU-CPU协同查询处理的方案。
　　作为一种静态缓存策略，我们提出的缓存算法需要将一部分的显存预留作为存储缓存失效数据的临时存储空间（缓冲区空间）。实验表明，缓存空间和缓冲区空间的大小比例对于查询处理的性能至关重要。因此，我们从理论上讨论并分析了显存空间的划分问题并提出了两种寻找最优划分经验值的方法。
　　实验表明，我们提出的 GPU查询处理缓存框架和缓存算法能够有效减少GPU和CPU之间的数据传输量，进而显著提高系统吞吐率。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

第一节 研究背景

第二节 本文主要工作和组织结构

第二章 背景知识和相关工作

第三节 搜索引擎架构概述

第四节 查询处理流程综述

第五节 查询处理的提前停止技术

第六节 GPU硬件架构和CUDA 编程模型

第七节 基于GPU的查询处理相关研究

第八节 搜索引擎缓存算法相关研究

第三章 基于GPU的查询处理缓存框架

第九节 CPU-GPU 协同处理框架

第十节 基于倒排链表剪枝的GPU缓存算法

第十一节 GPU显存划分

第四章 基于GPU的提前停止算法设计

第十二节 基于GPU的倒排索引求交算法

第十三节 基于GPU的提前停止算法

第五章 实验和分析

第十四节 数据集和实验设置

第十五节 接纳阈值??的影响

第十六节 命中率和数据传输量

第十七节 系统吞吐率

第六章 总结和展望

第十八节 本文总结

第十九节 工作展望

参考文献

致谢

个人简历