图形处理器对倒排索引求交运算的优化

图形处理器对倒排索引求交运算的优化 学校代码:,,,,, 中图分类号: ,,,: 密级:公开 高蕊犬淫 硕士学位论文 图形处理器对倒排索引求交运算的优化 ,,,,;,,,,,,,,,,,,，,,,,,,,,,, ,,，,,,,,,;,,,,,,,,,,,,,, 。 ,,,,,,;,,,,;,, ,,,,,,,,,,,,,, ,,,,,,;,,,,,;, ,,,,,, 答辩委员会主席评阅人 南开大学研究生院 二。一一年五月 南开大学学位论文原创性声明 本人郑重声明:所呈交的学位论文，是本人在导师指导下进行研究工作所取得的研究成 果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开 发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。 学位论文作者签名:昱遮,,,,年,月,,日 非公开学位论文标注说明 (本页表中填写内容须打印) 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申请和相关部门 批准方能标注。未经批准的均为公开学位论文，公开学位论文本说明为空白。 论文题目图形处理器对倒排索引求交运算的优化 申请密级口限制(?,年)口秘密(?,,年)口机密(?,,年) 保密期限,,年月日至,,年月日 审批表编号批准日期,,年月日 南开大学学位评定委员会办公室盖章(有效) 注:限制?,年(可少于,年):秘密?,,年(可少于,,年):机密?,,年(可少于,,年) 中文摘要 中文摘要 大型搜索引擎系统每秒钟都在响应着大量的用户请求。这些查询请求希望从 上百亿张网页中检索出最相关的网页集合。随着互联网业务的迅猛发展，搜索引 擎系统检索的信息量和承担的计算负载正以指数增长速度膨胀。为了快速完成这 些沉重的任务压力，我们利用图形处理器(,,,,,,;,,,,;,,,,,,,,,,,)来完成部 分计算任务。在本文中，我们探讨了几种新的算法来加速搜索引擎中的一个重要 且频繁的操作:倒排索引求交。 本文的主要工作包括: ,(为了充分发挥,,,的计算潜力，本文设计了批次处理模式。在批次模式 下，若干个查询被绑定为一个批次发送到,,,上进行并行处理，以此取 得较高的系统吞吐率。本文设计了查询(线程块并行策略(？,,,,,,,,,, ,,,,) 来实现这个批次模型。为了改善负载均衡的情况，我们设计了,,;，,(线 程并行策略(？,,,,(,,,,,, ,,)。 ,(在系统负载较低的情况下，,,,或者,,,应该立即处理当前到达的查询 请求，以取得最低的响应时间。为此，本文设计了一个在线调度算法， 用于将当前到达的查询派发到能够最快完成任务的处理器上。 ,(本文将,,,,,,,,,,,应用到,,,倒排索引求交领域。虽然,,,,,,, ,,,,具 有一定的误称率，但本文通过选择合适的哈希函数，将错误结果比例控 制在很低的水平。实验显示，,,,,,,,,,,, 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 符合,,,的并行特征， 能 够大幅度提升系统吞吐率。 ,(本文分析了倒排索引的数据分布特征，总结出了大部分倒排索引都具备 明显线性形态的重要结论。这种线性性质来源于搜索引擎抓取网页和分 配,,;,,过程中的随机性和不确定性。为了增强这种线性特征，我们设 计了利用,,,,,,,,,,,,随机算法进行倒排索引重排的策略。在线性性质 明 显的数据集合上，一元线性回归能够取得较好的拟合效果。 ,(本文在倒排索引数据分布的基础上，设计了线性回归搜索算法。良好的 线性性质等价于,,;,,在倒排索引中的较均匀分布。因此，本文设计了 哈希分段搜索算法。实验显示，线性回归搜索和哈希分段搜索均能够实 现可观的加速比。 关键词:,,,;搜索引擎;倒排索引 ,,,,,,;, ,,,,,,;, ,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,？,,,,,,,,,,, ;,,,,,？,,,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(,,,,,,,,,,,,,,,？,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,(,,,,,,,,,,,,,,,,,,,,,,,,，,,;,,,,,,,,,;,,,？,,,,,, ,,,,,,,,,,,,,,,,;,,,,;,,,,,,,,,,(,,,)(,,,,,,,,,,,,,,,,,,,,,,;,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,,,,,,:,,,,,,,,,,,,,,,,,,,,;,,,,( ，,,,,,,,;,,,,,,,,;,,,,,，？,,,,,,,,,,,,,,,,,,,,,,,;,,,,, ,,,,;,,,,,,, ,,,,,,,,曲,,,,,,,,,,(,,,,,,,,,？,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ？,,,,,,,,;,,,,,,,,,,,,,,,,(,,,,,,,,,,,,;,,,，,,,,,,,,,？,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(，,,,,,,,,,,,,,,, ,,,,;,,,,,,,,,,,,，？,,,,,,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,;,,,,,,,,,,,,,(,,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,;,,,,,,,,？,,,,,,,,,,(,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,,,,,, ,,,,,;( ，,,,,,,,,,,，,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,,,,,,,,,,, ,,;,,,,,,,,,,,,, ,,,,,,,;,,,,,,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,，,,,,,,,,,,,,, ,,,,,,,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,;,,,,,,,,,,,,,,,;,,,,？,,,,,,,,,,,,,,,(,,,,,,,,,;,,,,,,,,,,,,,,,,,,,;,,,,;,,,, ;,,,,,，,,, ,,,,,？,,,,,,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,,,,, ,,,;,,,,,,,,,,,,,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,,;,,,,,,,,,,,,,,,, ,,,,,?,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,,,;,,,,;,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,？,,,,,,,;,,,,,,,,,,,,,？,,,,,,,,,;,,,,,, ,,,曲( ,,,,,,,,,,,;,,,？,,,,,,,,,;,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,,;,,,,,,,,,, ,,,,,,,,,,,;,,,,,,,,,,(,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,,,(,,,,,,,,,,, ,,,,,,,,,,,，,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,？,,,,,, ;,,,,,;,,,,,,,,,,,;,,,,,,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,, ,, ,,,,,,;, ,,,,,？,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,( ,,,,,,,,:,,,;,,,,;,,,,,,,;,,,,,,,,,,,,, ，，了 目录 目录 中文摘要……………(…………………………((， ,,,,,,;,(((((((((((((((((((((((((((((((((((((((((((((((((， ， 目录(…………………………………………((，, 第一章绪论…………………………………………………………((, 第一节研究背景………………………………………………………………, 第二节本文主要工作…………………………………………………………, 第三节本文组织结构…………………………………………………………, 第二章背景知识介绍…………………………………………………(, 第一节,,,,,,,,,硬件体系结构…………………………………………。, 第二节,,,,,,,,,,存储模型……………………………………………。, ,(,(,寄存器(,,,,,,,,)……………………………………………………………(, ,(,(,共享存储空间(,,,,,,,,,,,,)…………………………………………。, ,(,(,只读存储空间(;,,,,,,,,,,,,,)…………………………………………(, ,(,(,纹理存储空间(,,,,,,,,,,,,,)…………………………………………一, ,(,(,全局存储空间(,,,,,,,,,,,,)……………………………………………(, 第三节,,,,,,,,,,线程模型……………………………………………一, 第四节倒排索引的交运算……………………………………………………, 第五节实验环境和数据集……………………………………………………, ,(,(,实验环境………………………………………………………………………, ,(,(,,,,,数据集…………………………………………………………………, ,(,(,百度数据集……………………………………………………………………, ,(,(,数据集特征……………………………………………………………………, 第三章,,,并行求交计算框架……………………………………((,, 第一节查询的处理模式……………………………………………………(,, ,(,(,异步模式……………………………………………………………………,, ,(,(,同步模式…………………………………………………………。………。,, (:，, 目录 第二节按查询划分的粗粒度并行框架……………………………………((,, 第三节按,,;,,划分的细粒度并行框架…………………………………(,, 第四节低负载情况下的动态处理器选择…………………………………((,, 第四章搜索算法的分析与改造………………………………………,, 第一节搜索算法的分析和比较……………………………………………((,, 第二节,,,,,,,,,,,搜索算法………………………………………………,, ,(,(,,,,,,,,,,,,介绍………………………………………………………………………………((, , ,(,(,,,,,,,,,,,,在,,,上的应用………………………………………………。,, ,(,,,哈希函数的选择……………………………………………………………,, ,(,(,,,,,,,,,,,,搜索算法的性能………………………………………………(,, 第五章倒排索引数据分布的分析和利用…………………………(,, 第一节倒排索引重排和随机化方法………………………………………(,, 第二节数据分布特征………………………………………………………。,, 第三节一元线性回归…………………………………………………………,, 第四节线性回归加速搜索…………………………………………………(,, 第五节哈希分段加速搜索……………………………………………矗…(,, 第六节?实验分析……………………………………………………………(,, 第六章总结和展望…………………………………………………((,, 第一节总结…………………………………………………………………(,, 第二节工作展望……………………………………………………………(,, 参考文献……………………………………………………………………((,, 致 谢……………………………………………………………………………………………一,, 个人简历……………………………………………………………………(,, 学术论文…………………………………………………………………((,, , 第一章绪论 第一章绪论 第一节研究背景 如今的大型商用搜索引擎系统，正处理着日益繁重的计算任务。例如，作为 全球最大的中文搜索引擎，百度每天接受几十亿次的用户查询请求;而垂直搜索 领域的翘楚一淘宝，每天处理的查询数量也已超过了十亿次。随着业务的迅猛增 长以及对多元化查询请求的进一步满足，搜索引擎后台的服务集群，正承受着巨 大的压力。 系统效率和结果质量是衡量搜索引擎系统的主要指标，而“平均查询响应时 间”则是衡量系统效率的重要指标。如果响应时间过长则会伤害到用户体验，并 限制了系统能够同时处理的查询数量。结果质量的衡量 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 是“召回率:和“精 确度:【,,，前者是搜索结果中有价值的相关网页的数量占互联网上所有相关文档 数量的比例，它衡量了搜索引擎的查全率;后者是搜索结果中有价值的相关网页 数量占结果中的所有文档数量的比例，它衡量了搜索引擎的查准率。系统效率和 结果质量相辅相成，互为补充。在系统效率得到保证的前提下，搜索引擎才能够 为语义分析和排序算法分配足够的计算能力，从而在“召回率:和“精确度:上 取得最优平衡。 系统效率的瓶颈在于,,,计算能力的限制和，,吞吐限制(包含单机的磁盘 ，,，集群内部的网络，,)。通常，搜索引擎通过数据压缩和索引库均匀分散策略 来缓解，,方面的不足。为了降低,,,的负载，系统可以通过省略用户查询中某 些表义能力不强的关键词，从而达到减少查询过程中的计算量的目的;也可以采 用较为简单的排序规则，使得能够在规定的时间内完成查询。这些释放,,,资 源的策略，直接伤害了搜索结果的相关性。 在处理用户查询的过程中，倒排表的相交运算占用了,,,很大比例的时间， 这是产生,,,性能瓶颈的重要原因之一。正因为倒排表交运算在查询过程中如 此重要，前人已对此做了广泛而深入的研究。这类研究工作主要着眼于对,,, 算法的改进。一方面，搜索引擎系统采用更高效的,,,算法;另一方面，为了 应对计算压力的迅速增长，搜索引擎必须不断扩大集群规模，来提供和需求相匹 配的计算能力。在这个粗放式的增长过程中，经济成本和能源消耗这两个因素同 时阻碍了企业的快速增长。 近年来，随着图形计算的成熟和普及，作为增加单机运算能力的一个重要选 , 第一章绪论 择，,,,(,,,,,,;,,,,;,,,,,,,,,,,),,算卡受到学术界和企业界的普遍关注。本 文主要探讨了两种不同的,,,(,,,协同工作架构，设计了几种,,,上倒排表 求交运算算法，充分卸载了,,,的计算压力，同时显著提升了系统的整体吞吐 能力。 第二节本文主要工作 本文首先研究了,,,并行求交计算框架，包括按照查询划分的粗粒度并行 框架和按照,,;,,划分的细粒度并行框架。在这两个框架中，本文提出了批处 理模式中,,,(,,,协作平台上的详细应用 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。 在细粒度并行框架的基础上，本文详细对比了几种典型的搜索算法在,,, 交运算中的使用，同时论证了二分查找算法是,,,求交过程中的一个好的选择 这一结论。此外，本文首次将,,,,,,,,,,,引入了,,,交运算平台，在可以接受 的误称率和空间使用的前提下，显著提升了速度。 本文通过大量的实验数据，详细研究了倒排索引的数据分布特征，总结出了 在各种倒排索引【,】中广泛存在的线性特征。通过基于最小二乘法的线性回归，构 造出了能够让,,,进行快速解压的压缩算法。与此同时，本文还提出了基于 ,,,,,,,,,,,,随机化方法的倒排索引重排策略，用于强化既有倒排索引的线性特 征。 本文的部分成果已经应用于百度搜索引擎中。 第三节本文组织结构 本文组织结构如下: 第一章:绪论。本章介绍了研究背景和本文的主要工作，并且展示了本文的 层次结构。 第二章:背景知识介绍。本章介绍了,,,,,,,,,的硬件体系结构，介绍了 最新的,,,,,架构在科学计算方面做出的改进。在第二节和第三节中，本章介绍 了,,,,的存储模型和线程模型。在第四节中，本章介绍了倒排索引交运算在 搜索引擎中的重要位置。最后，本章介绍了本文使用的数据集和实验环境。 第三章提出,,,(,,,,,,;,,,,;,,,,,,,,,,,)并行求交计算 框架。本章首先 介绍了异步和同步的查询处理模式。接下来，提出了按照查询划分的粗粒度并行 , 第一章绪论 框架,,,,(？,,,,,,,,,,,,,,,,,,,,,,,,)和按照,,;,,划分的细粒度并行框架,,,, (？,,,,,,,,,,,,,,,,,,,,,,)，并通过实验对这两种框架进行了比对。在第四节中， 介绍了低负载情况下的动态处理器选择策略。 第四章:搜索算法的分析与改造。本章首先对比了几种传统搜索算法的性能。 在此基础上，提出了,,,,,,,,,,,搜索算法，并通过翔实的实验展示了新搜索算 法的优势和不足。 第五章:倒排索引数据分布的分析和利用。本章首先介绍了倒排索引重排和 随机化方法。在第二节和第三节中，分析了在倒排索引中普遍存在的数据分布特 征，以及能够很好地展现出这种分布特征的一元线性回归方法。在第四节和第五 节中，阐述了线性回归搜索方法和哈希分段搜索方法的基本原理。在六节中，通 过实验数据展示了上述搜索方法的性能。 第六章:总结和展望。在总结部分，本章回顾了,,,并行求交运算的应用 背景，,,,,并行框架和,,,,并行框架的异同，以及利用倒排索引的线性特征 对求交运算进行加速的基本思想。在工作展望部分，本章指出了,,,显存容量 不足和功耗较大的两大问题是阻碍,,,在大规模集群中实际应用的主要原因。 , 第二章背景知识介绍 第二章背景知识介绍 在过去的十余年中，游戏图形处理需求迅猛发展，,,,(,,,,,,;,,,,; ,,,,,, ,,,,,)的浮点计算能力和可编程性也得到了显著提升。今天的,,,在浮点运算 速度上已经大幅度超越了,,,，成为了科学计算加速的理想选择。 本章通过,,,,,,公司最新的,,,,,架构，介绍了新一代,,,计算框架的硬 件体系结构。,(,节和,(,介绍了,,,,,,计算统一设备架构,,,,(,,,,,,, ,,,,,,,,,,,;,,,;,,,,;,,,,)【,】的线程模型和存储模型。,(,节对搜索引擎处理一 个查询的基本流程进行了简单介绍。,(,节通过形式化的表达，描述了倒排表的 交运算。 第一节,,,,,,,,,硬件体系结构 新一代的,,,,,架构,,,，最多装备,,,个,,,,核心。一个,,,,核心 在一个时钟周期内，为一个,,,线程执行一条浮点指令或整数指令。这些,,,, 核心被组织为,,组流式多处理器(,,,,,,,,,,,,,,,,,,,,,;,,,,,)，缩写为,,。 每个,,内部含有,,个,,,,核心。 ,,,计算卡上共有,组显存为,,,提供存储支持，每组的接口带宽为,,,,,， 构造出接口带宽为,,,,,,的存储阵列。 图,(,,,,,核心结构,,】 如图,(,所示，每个,,,,核心内均含有一个管线化的整数算术逻辑单元 (,,,)和一个浮点计算单元(,,,)。,,,,核心的浮点部分，支持，,,, ,,,(,,,,浮点标准;整数部分对所有的计算操作，都提供了,,,,,的全精度支持， 并为,,,,,整数计算提供了良好的优化。 , 第二章背景知识介绍 从图,(,中可以看出，每个,,配有,,组访存单元(,,,,,)，支持读写双 向操作。在一个时钟周期内，一个,,可以为,,个,,,线程的访存提供地址运 算。在,,,,,;,,,,,,,显卡上，访存带宽最高可达,,,,,,,。四个特殊函数处 理单元(,,,)为,,,,核心提供正弦、余弦、平方根等指令支持，每个,,, 在一个时钟周期内，为一个,,,线程执行一条指令。 ,,将每,,个线程视为一组，称之为“,,,,”。每个,,装备有两个,,,,调 度器和两套指令分派单元，这使得同时能有两个,,,,在一个,,上并发执行。 这两个,,,,调度器会根据一定的策略，选取两个,,,,执行。每个,,,,中的线 程会被分配到,,个,,,,核心上，并同时运行一条指令，符合,，,,(,,,,,, ，,,,,,;,,,,,,,,,,,,,,,,,,,)体系结构 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 【,,。,,,,可以利用的资源还包括,, 个访存单元和,个,,,。因为,,,,,间的执行是独立的，所以调度器无需检查指 令的依赖性。程序的代码如果能够很好地符合,，,,的相关要求，就能让,,, 的性能得到很好地发挥。 ,,,,,架构的,,,装备了,,和,,两级;,;,,。,,;,;,,为每个,, 所独享， 其中的一部分被划分为,,,,,,,,,,,,。,,,,,,,,,,,,需要由开发者编码控制， 一般用它来实现线程间的通信，以及可编程的高速数据缓存。,,;,;,,为,,, 所共享，提供了对所有读写操作的快速缓存。 , 第二章背景知识介绍 第二节,,,,,,,,,,存储模型 开发者需要重点考虑,,,线程访问显存的方式，以此取得尽可能高的访存 带宽，减少访存延迟，从而发挥出,,,,核心的最大计算能力。,,,,,,,,的 显存以层次化结构进行组织。 ,(,(,寄存器(,,,,, ,,,) 每个,,装备有,,,,,个,,,,,寄存器，作为在,,,函数的局部变量的存储 空间。寄存器的读写速度很快，在,,个周期内就可以完成。寄存器是稀缺资源， 超过其承载能力的数据，会被自动放入,,,,,,,,,,,,中。因此，对寄存器的使 用情况直接影响了程序效率。 ,(,(,共享存储空间(,,,,,,,, ,,,,) 一个线程块(,,,,,,,,,,,,;,)中的线程共享,,,,或,,,,的,, ,,,, ,,,,,,。,,,,,,,,,,,,同样具有较高的吞吐能力，其读写速度与寄存器近似。 但是，线程块之间会争抢,,,,,,,,,,,,资源。如果每个线程块都占用了较多的 ,,,,,,,,,,,,资源，会使得,,上活跃的线程块总数下降，影响程序的并发度。 ,(,(,只读存储空间(;,,,,,,,,, ,,,,) 所有,,,线程共享,,,,的只读存储空间。这部分空间本身包含;,;,,，在 局部性要求满足的情况下，能够实现较快的读操作。 ,(,(,纹理存储空间(,,,,,,,,, ,,,,) 所有线程共享只读的纹理存储空间。纹理存储空间中的数据，实际上保存在 ,,,,,,,,,,,,中。由于,,,为这块空间专门提供了接口电路，并带有;,;,,， 从而使得纹理存储空间中的数据在一定的模式下，能够被更快地读取。 ,(,(,全局存储空间(,,,,,,,,, ,,,) 所有线程共享,,,,,,,,,,,,，它占据了显存的主要空间，用于存放大规模数 据。读写百,,,,,,,,,,有较高的代价，一次操作需要耗费几百个时钟周期。因 此，开发者需要通过提高程序的并行程度，让,,,线程的计算和访存重叠起来， 以此来隐藏对,丑,,,,,,,,,,的访问延迟。 , 第二章背景知识介绍 第三节,,,,,,,,,,线程模型 ,,,,, 蒜菘套,。 , ,,,( 骥嚣 糕,, ,,,,,;越,,,,,,糊吐 ,，,,,，,,,～ ， 麓渤 淡,。馘嘲, 溪嚣蘸，、 蠢 ?释 图,(,,,,,线程模型;,】 一次,,,调用(,,,,,,,,,;,,,)会启动一个线程网格(,,,,,,, ,,,)，每个 ,,,,含有最多,,,,,个线程块(,,,,,,,,,;,)，每个线程块最多含有,,,,个,,, 线程。图,(,展示了三层线程组织形式，以及相应的存储层次。每个线程块在 ,,,的,,上，会被拆分为多个包含,,个线程的,,,,。在一个,,,,内的线程， 应该尽可能遵循,，,,规范，避免逻辑分叉，从而保证程序的并发度。 第四节倒排索引的交运算 本节介绍倒排索引的背景知识，并给出倒排索引求交运算的形式化说明。 搜索引擎为每个网页分配一个独一无二的文档编号,,;,,，其值域范围是 ,,，,，,，(((，【，)，,是系统收录的总文档数量。每个网页都是一些词语(,,,,)的集 合。在此基础上，搜索引擎掌握了任何一个词语,会存在于哪些网页中。随后， 系统为每个词语,生成一个严格递增的整型数组比,，数组元素指的是出现了, 的网页的编号。砸)被称为倒排索引。通过倒排索引，系统能够高效地检索到出 现了词语,的网页集合。 当用户输入一个含有,个关键词的查询,,,，,,，(((，,,,，用户需要知道和 这,个关 键词都有关联的网页。因此，系统会在这,个关键词对应的倒排索引上，进行求 交运算，返回查询结果,，(,,)。系统会根据长度，重新排列,个倒排索引。 ,,(,,)，,,,,(,,)，,(((, ,,(,,),(,(,) 例如，当用户输入查询,“,,,,:，“,,,,,”，“;,,:,，搜索引擎会找到对 应 的三条倒排索引 ，(;印),(,,，,,，, ,，,,，,,) ,(,,,,,),(,，,?,,，,,，,,，,,，, ,，,,，,,，,,，,,) ,(,,,,),(,，,，,，,，,，,,，,,， ,,，,,，,,，,,，,,) , 第二章背景知识介绍 求交运算返回了包含着三个词的网页集合 ，(唧),，(,,蒯),，(,, ,,),(,,，,,，,,，,,) 在实际的搜索引擎系统中，倒排索引往往要比这个例子长得多。按照索引库 的规模不同，一条倒排索引甚至可能含有上千万个,,;，,。因此，求交运算在 ,,,上形成了可观的负载。 第五节实验环境和数据集 ,(,(,实验环境 本文中所有算法的性能测试均运行于,,,四核,,;,,,，，,,,,,,,,平 台。系统配备,,,,,,,,,,,,,,,,计算卡，或者,,,,,,,,,,,,, ,,,,。系统的详 细性能见表,(,。 表,(,,闯”::,,纷 ,,, ,,,;,,(,,,, ,,,,,, ,,;,,,,,,,(,,),,,,(,,) ,,,,,,,,,宰,,,，玛,,,, ,,，(,,,,,,一,,,,,(,,,,, ,,，,(,,,,,,(,,,,,(,,,,, ,,, ,,,,,,,,,,, ,,,;,,,,,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,(,,,,,,, ,,,,,,,,,,,,,,,,,,(,,,,, ,,,,,,,,,,,,;,;,,,,,,, 本文采用若干学术界和产业界各具代表性的实际数据集进行算法评估。 ,(,(,,，也,数据集 , 第二章背景知识介绍 ,,,,,,,,,】和,,,,,,,,,,】数据集，它们分别由,，,,(,,,,,,,,，,,,,, ,,,,, ,,,,,,,,,,,,,;,,,,,,,)在,,,,年与,,,,年从(,,,域名中抓取而来。我们利 用这两个数据集(,,,,,,,)生成相应的倒排索引集。本文采用,,,,,,,;,,,,(,,,) 查询集【,】，在,,,,数据集上进行用户的查询模拟。,,,含有,,万个独立的用 户查询请求。本文关注在显存中存放的，会被频繁使用的倒排索引。因此，本文 根据,,,对原始的,,,,数据集进行筛选，只保留被,,,使用到的文档集合。 最后，本文使用的,,,数据集中，含有,，,,,，,,,个网页;,,,,数据集中，含 有,，,,,(,,,个网页。 ,(,(,百度数据集 百度搜索引擎中的,,数据集。此数据集含有,,，,,,，,,,个网页，收集于,, ,, 年。本文同时采用百度,,,,年的一个查询集合,,,。该查询集合包括,,，,,,个 查询请求。 ,(,(,数据集特征 图,(,倒排索引长度分布 图,(,展示了,,,数据集和百度数据集的倒排索引长度分布。百度数据集 的倒排索引普遍较短，同时，,,,数据集中的长倒排索引比例较高。这是因为 在百度搜索引擎上，为了实现查询的并行化，一个查询请求会被分布到若干台机 器上同时计算。因此，相应的倒排索引也需要被划分到多台机器上。因此，单台 服务器上的倒排索引的长度较短。因此，平均到每个查询，百度的查询请求所包 含的计算量少于,,,对应的查询请求。 , 第二章背景知识介绍 图,(,查询集的关键词个数分布 图,(,展示了,,,和,,,查询集合中，不同数量关键词的查询所占的比例。 ,,,中，大部分查询仅含有,个以下的关键词。,,,的查询规模分布更为均衡。 ,, 第三章,,,并行求交计算框架 第三章,,,并行求交计算框架 第一节查询的处理模式 本文致力于利用,,,来提高集群的计算性能，给用户提供良好的查询体验。 实际上，搜索引擎的负载在每天的不同时段动态发生变化。例如，从上午十点到 晚上八点，是查询请求密集的时段;从午夜到凌晨，是查询请求稀疏的时段。具 体的波动情况，还会因为节日或重大事件的到来而改变。系统负载的波动，会给 系统性能和用户体验带来不利影响;而开发者对处理模式的选择，则会影响到系 统应对负载波动而采取的策略。本节将探讨异步处理模式(,,,,;,,,,,,,,,,,) 和同步处理模式(,,,;,,,,,,,,, ,,)。 ,(,(,异步模式 系统立即处理每一个新到达的查询请求，这种模式称为异步模式。这是在商 用搜索引擎系统中广泛采用的处理方式。在系统负载较低的时候，异步模式能够 迅速响应每个用户的请求。前一个查询的处理，不会对后一个查询造成影响。在 系统负载较高的时候，系统对新到达的查询需要延迟响应，从而造成查询请求队 列变长。这时，搜索引擎的响应时间相应增加。在极端情况下，系统需要有选择 地抛弃队列中的部分查询请求，以保证大多数查询请求能够在合理的时间内得到 处理。 ,(,(,同步模式 突然增高的查询请求压力，会对搜索引擎的整体性能产生显著影响。 ,,,,,;,;,,】讨论了这种情况，并提出了相应的解决策略一同步模式。当系统处于 高负载状态的时候，系统并不立即处理新到达的查询请求，而是将若干个查询请 求绑定为一个批次，一次性发送到系统后台，利用多线程并行处理。,,,,,,,,,【,】 研究了在多核心上查询请求的并行处理方式。 在异步模式下，系统为每一个查询开启一个独立线程进行处理。因为各个查 询请求含有的计算量差异较大，因此子线程的工作时间长短不一。为一个含有很 少计算量的查询请求(例如，查询中的关键词对应的倒排索引很短)单独开启一 个子线程，其额外开销会占据相当的比例。在同步模式下，系统需要等待一定量 的查询请求，达到指定的计算量之后，才将它们打包发送到后台。因此，同步模 ,, 第三章,,,并行求交计算框架 式避免了异步模式下的额外开销，适合于高负载的计算环境。 因为需要足够多的计算任务才能充分发挥,,,的计算能力，因此，这里假 设系统工作在高负荷环境下，并采用同步模式作为,,,的处理模式。下文将同 步模式称为“批次模式:。 在,(,节中，作者探讨了在低负载情况下，,,,(,,,的协作策略。 第二节按查询划分的粗粒度并行框架 图,(,查询请求的调度 如图,(,所示，搜索引擎后台的服务器串行接收互联网上的查询请求，在 ,,,段进行调度和打包，按照批次传输给,,,进行处理。批次内应用了,,, 的大规模并行处理能力，批次间是串行关系(同一时间，只有一个批次中,,, 上计算)。 整个调度过程分为,个步骤: ,),,,持续接收查询请求，直到凑齐刀个查询。随后，,,,将它们打包成 一个批次，通过,,，,总线传输给,,,。在本文的实验中，所有倒排索 引已经预先保存在显存中。因此，,,,只需要传输相关的定位信息。 ,,,,,并行处理每个批次中的查询请求，并将结果写入显存中预先开辟好 的缓存区域。 ,),,,收到,,,处理完毕的信号后，将结果传输回内存。随后，将一个新 的批次传输给,,,。 本文将,)和,)中的,,，,传输时间，统称为“动态传输时间:。本节的重点是 对,)进行详细设计。 首先，本节为每个查询请求分配一个,,,线程块，每个线程块中含有相同 的线程数量。因此，每个查询请求都将被,,,个,,,线程并行处理。本文将这 种按照查询划分的粗粒度并行框架，称为,,,,(？,,,,,,,,,,,,,,,,,,,,,,,)。 在此基础上，每个线程获取，(,,)中的若干个,,;，,，逐个在，(,,)一(， („)中做二 分搜索。如果某个,,;，,在，(„)((,(气)中都存在，则在预分配的,,,数组的对应位 置标记,。 (一个线程块中的所有线程都完成了搜索操作之后，对,,数组进行前缀和操 ,, 第三章,,,并行求交计算框架 作(,,,,,,,,,,;,,)。本节采用,,,,,,,,,,,,,,,,,】提出 ,,,,,,,,,,,,,,,,, 的,,,并行化前缀和操作。 ,,印, 、(,,、、,、,、?、,、、,(,、“、,„、、(,、 一、(, ,,,,, ,,,,:,,,,:,,,,:,,,,:,,,,:,,,,:, ,,,:,, ,,?一?:,,?:。:,一二::,,,(((((,(: ，,,一,(,:,„士::??、士,(, ,,,,:,,,,:,,,,:,,,,:,,,,:,,,,:,,,,,, ,,,:,, ,,((,,::二二::壬毫:景,:聋::::，: ,:,,，((』,一, ,,,,, ,,,,:,,,,:,,,,:,,,,:,,,,:,,,,:, ,,,:,, 图,(,,,,并行化前缀和 如图,(,所示，前缀和操作的主体是一个循环。在循环的每一步，第,个元 素被加到第,，,,,,,,)个元素上。如果,,,数组含有?个元素，循环需要,,,(,,步。 第,步需要进行,一,,,,次加法。因此，本算法一共需要?,,,(?一,)一(?一,)次 加法操作。 ,;,,操作完成之后，,,,将,(,数组中对应位置为,的元素，按照,,,,,结 果数组提供的位置，保存到结果数组中。 ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,, ,,,, ,,,,,,,, ,,,,,,,, ,,，, ,;,,,,,,,, ,,,,,,,, ,,,一,———一一 ,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,, „;,,，,,;,,,) 图,,,查询请求的,,,处理模式 图,(,展示了一个线程块在一个查询上进行操作的完整过程。 在一个批次中，由一个线程块独立处理一个查询;例如系统在每个批次中包 含了,,,,个查询，那么在调用,,,,,,,,,的时候，就将启动,,,,个含有相同 线程数量的线程块来计算。因此，每个查询将获得相同的计算能力，而查询问的 计算量差异可能是巨大的，这就造成了负载不均的情况。这,,,,个,,,;,将等 待其中耗时最多的那一个完成之后，才能统一返回。因此，每批次的处理速度都 会被其中最复杂的查询拖慢。因此，本文要实现线程块问的负载均衡。( 本文用一个查询的最短桶的长度来标识这个查询的计算量(在一个查询中， 随着交运算的进行，需要查找的元素数以最短桶长为起点，逐渐减少)。系统把 短时间内涌入服务器的查询按其计算量范围划分成若干个子查询集合，这样每个 子集合中各查询的计算量接近。例如在很短的时间内服务器收到,,,,个查询请 求，按照最短倒排索引长的分布情况，划分为,,,,，,,,,,，,,,,,,，,,,，这 四个子集合，划分见图,(,。 】, 第三章,,,并行求交计算框架 图,(,按照最短倒排索引的长度划分查询请求 当子集合较小时，用一个批次就能计算完成;而当子集合较大时，本文依然 对子集合划分批次进行计算。例如设置每个批次的查询数量是,,,，图,(,中四 个子集合分别需要划分为,、,、,、,个批次进行计算。 本文对百度查询集中含有的,,，,,,个查询，按照每个查询的最短倒排索引进 行了划分。 图,(,,,个查询子集的查询数分布 图,(,展示了按照最短倒排索引长度，将完整的查询集划分为,,个子集的 统计信息。同属于一个子集的查询所包含的计算量接近。 ,, 第三章,,,并行求交计算框架 —?,,,,，,，,,,,,,(,,,,,,,,,,,)(,，,,,,,,,(,,,,,,,,;,) 厘 莒躲 ,? ,?妒????? 查询子集 图,(,各查询子集的运行时间 ???????? 本文对这,,个子集进行分组测试，从而对比,,,和,,,的性能差异，并 且分析不同批次规模下，,,,的性能表现。 从图,(,中可以看到，当每批次查询数量等于,,,时，,,,在所有子集合上 柳梦 相对于,,,，都能有速度优势。而每批次查询,,个的时侯，在一些情况下不能 体现出优势，这是因为,,,,,,,,,,有,,个,,，每次,,,调用仅分配,,个线 程块，不能把,,,的计算潜力发挥出来。 本文对含有,,，,,,个查询请求的原输入文件(,,,,,,,,)进行计算量从小 到 大的重新排列，得到一个新的静态输入文件(,,,,,,,,,,,,,,)。用这个查询文件， 模拟高负载下的用户请求。 ,,? ,宙,, ,, 、,二,,, 要,,々 甚,,, ,。—————? ,、(((((卿枷 ,,, ,?? ,,“,嚣,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,醴 批次规模 图,(,不同批次规模下的运行时间 图,(,显示，当每批次处理的查询数量大于等于,,,,之后，,,,的计算能 力能得到比较充分的利用，整体计算时间维持在,,,,,左右。但是每批次的查 询数量过大，将导致每批次的返回延迟太长。例如各批次含有,,,,,个查询的情 况下，共分为,个批次，平均每批次的计算时间是,,,,,左右，这是不能接受 的。相反，当每批次的查询数量减少，批次数量成倍增加，而总耗时仅温和上升 的情况下(例如,,,？,,,,,,,,,,,,;,)，时间延迟将大大缩短。, ,, 第三章,,,并行求交计算框架 图,(,不同批次规模下的响应时间 图,(,展示了在不同批次规模下，批次的平均响应时间。可以看到，设置每 批次处理,,,,个查询的情况下，各批次响应时间为,,(,,,，总耗时,,,,,，能 达到一个理想的均衡状态。如果追求更短的响应时间，可以把各批次查询数降低 到,,,或,,,，响应时间将响应下降到,,,,以下，而仍能保持对,,,单线程算 法的,(,倍左右的加速比。 ,,,,框架存在一些不足之处。首先，一个,,,线程块处理一个查询请求的 粗粒度并行模式，限制了一次调用所能利用到的最大线程数量，浪费了,,,的 高并发度;其次，查询之间计算量的差异，造成了负载不均的情况。为了缓解负 载不均的程度，需要,,,在接收到足够的查询之后，按最短倒排索引长度进行 一次排序。这个操作占用了额外的,,,资源。因此，本文在,(,节提出了改进 策略。 第三节按,,;,,划分的细粒度并行框架 在,,,,的基础上，本文提出了自适应的细粒度并行框架(？ ,,,,,,,,,,,,, ,,,,,,,,,)，简称为,,,,。这里，自适应的概念指的是:通过动态调整计算阈 值(;,,,,,,,,,,,,,,,,,,,)，对每批次查询的计算量进行约束，从而实现系统吞 吐能力和查询响应时间的灵活变化。 与,,,,类似，每个线程块中的线程数量是固定且相等的。不同的是，我们 在,,,线程和各个查询中最短倒排索引的,,;,,之间，建立一一对应关系。也 就是说，一个,,,线程仅搜索一个最短倒排索引中的,,;,,。这样，计算量将 在,,,线程块之间均匀地分散开来。 ,, 第三章,,,并行求交计算框架 ,二塑,, 图,(,,,,,线程分配 ,二】匦二 在图,(,中，查询,和查询,分别表示了这两个查询的最短倒排索引长度。 因为一个,,,线程被映射到一个,,;，,上，所以，最短倒排索引较长的查询会 被拆分到若干个线程块中执行。因为一个,,,线程块仅能处理一个查询的某一 部分，所以在各查询末尾的线程块，大概率会留有部分空闲线程(如图中,,,;,, 和,,,;,,的阴影部分)。假设查询,的最短倒排索引长度为,,,个,,;，,，同时， 我们把线程块规模限定在,,,个线程。这样，查询,会被分配到前三个线程块中， 并且前两个线程块处于完全活跃的状态。,,,;,,中的,,,个线程，有,,,个处于 活跃状态，剩余的,,个线程的计算能力将被闲置。 在,,,接收互联网上传来的查询请求，并进行包装调度的时候，我们设置 了一个自适应计算阈值;。与,,,,不同的是，;不是简单的查询个数，而是流 入,,,的各个查询的最短倒排索引长度之和。,,,持续接收查询，直到它们的 ;值超过预设值，才把这些查询打包为一个批次，发送给,,,。;的形式化描述 如下: ，，(„)表示第，个查询的第,个倒排索引，并且在每个查询内部，将倒排索引 按照其长度进行排序，使得，，，“)，,,,,,小，,)，。,,,持续接收查询，直到 ?肥(„)，?;。 计算阈值;本质上反应了每个批次所包含的计算量，它由三个因素决定: 第一，,,,的计算能力。对于计算能力较强的,,,(,,,,,,，,,,;,,, ,)， 我们设置较高的阈值。对于计算能力较弱的,,,(,,,,,,，,,,;,,,,)，我们设 置较低的阈值。 第二，系统实时负载。当系统正在承受较高的查询请求压力时，我们增大计 算阈值，以充分利用,,,的计算能力，提升系统的吞吐能力。在查询请求稀疏 的时段，我们减小阈值，以降低查询请求的排队时间。 第三，系统吞吐能力和查询响应时间的平衡。更高的阈值能够让,,,将更 多的计算量打包进入一个批次，从而充分发挥,,,的计算能力，增大系统吞吐 能力。然而，,,,处理大规模批次需要花费更多的时间，从而延长了查询的响 应时间。因此，系统需要在这两个相互对立的指标中寻找动态平衡点。 与,,,,框架类似，,,,,中的,,,线程获取一个,,;，,之后，在其查询请 】, 第三章,,,并行求交计算框架 求中的其余倒排索引上进行二分搜索，从而确定自己持有的这个,,;,,是否存在 于最后的交运算结果集合中。如果存在，,,,线程将,,数组的对应位设置为,。 因为细粒度并行的优势，每个查询不再被单独的线程块独自处理，而是被均匀地 分散给若干个相邻的线程块。这就使得在提升处理速度的同时，节约了显存空间。 如图,(,,所示，在,,,,中，每个线程块单独处理一个查询，使得前缀和(,,,,,, ,,,,，,;,,)操作和结果收集操作被割裂开来，从而不可避免地造成了空间的浪费。 而在,,,,中，查询被散布到连续的若干个线程块上，使得前缀和操作得以连续 进行，无需进行额外的分段。从而，各个查询的交运算结果可以连续存储，有效 利用了珍贵的显存空间。 ,,,, 对 ,,,,,,,,,,,,,,,,,, ,,上上上 , ,,,,,,,,, 萼堇? 上上上上上 ,;,,,,,,,, ,,,,,,,,, ,,。,二二三,二;二,—一 ,,,,,, ,,,,,,,,,, ,,,, ,,,,,,,, ,,,,,,,,,,,,,,,,,, ,,,, 上上上上上 ,,,,,,,, ,,,,,,,,, ?,上上上上 ,;,,,,,,,, ,,,,,,,,, ,,,。—:二, ,,,,,, ,,,,,虬?,,,,,,,,,?,,,:,,, 图,(,,,,,,与,,,,对比 本文首先使用百度数据集，对比,,,,和,,,,两种并行框架的性能表现。 注意到在,,,,中，批次规模由计算阈值,间接控制，与,,,,的固定每批次查 询数量的策略不同。为了公平地比较两种框架，我们设定了对应相同的平均批次 规模(用,,,,中的查询数量来衡量)。例如，当计算阈值;,,,,,,时，实验表 明，,,,,把百度查询集中含有的,,,,,个查询请求，分为了,,个批次，平均 每批次含有,,,个查询请求。每批次含有的查询数量不同，但每批次包含的计算 量近似相同。因此，我们把,,,,的相应批次规模也固定在,,,个查询。 ,, 第三章,,,并行求交计算框架 图,(,,,,,,与,,,,的吞吐能力对比 系统吞吐能力用每秒钟能够处理的查询数量来表示。图,(,,展示了两种并 行框架的吞吐能力差异。,,,,对,,,,维持着明显的吞吐率优势。当批次规模 增长到,,,之后，,,,,的吞吐率曲线近乎平稳，表示,,,的计算能力得到了 充分利用。,,,,由于并发度不足等原因，远未能将,,,的能力充分发挥。 响应时间的波动情况，对于搜索引擎用户的体验，是一个重要指标。较大的 波动会伤害用户体验，因为一些查询能够迅速返回结果，而另一些查询则要花费 许多时间。此外，响应时间的过分波动，对系统管理员评估集群的实时性能，也 带来了很大的挑战。 图,(,,蝴与腓的响应时 间波动对比 我们为,,,,和,,,,选定了一个相同的平均批次规模，在 此基础上， 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 每批次查询所花费的时间，由此评估两个并行框架的性能波动。如图,(,,所示， ,,,,的响应时间比,,,,的响应时间波动剧烈。这个结果是可以预期的，因为 :,,, 第三章,,,并行求交计算框架 在,,,,中，每个线程块负责一个单独的查询请求，而查询请求之间的计算量存 在差异，从而造成了每个批次的处理时间差异较大。在,,,,中，由于充分分散 了计算压力，系统收获了一条平稳的响应时间曲线。 ,(,,,,, ,基,, 秽一融煺 图,(,,,,,,与,,,,的时间构成对比 图,(,,展示了两种并行框架耗时的时间构成。时间构成分为:,,,预处理 时间，,,，,传输时间和,,,核心计算时间(,,,,,,,,,,,,,)三部分。因为,,,, ,, 在转储结果的时候，占用的显存空间较小，所以，在,,，,传输阶段，,,,,节 时 约了大量时间。额外开销的减少，使得,,,有效时间占总时间的比例上升，这 也表示负载被更充分地转移到了,,,上。在,,,预处理阶段，,,,,需要为每 个线程块计算它们处理的查询的定位信息。因此，,,,,耗费略微多一些的,,, 时间。 图,(,,不同计算阈值下的,,,,吞吐率 ,, 第三章,,,并行求交计算框架 图,(,,不同计算阈值下的,,,,响应时间 图,(,,和图,(,,展示了,,,,在不同计算阈值下的的吞吐能力和响应时 间。,,,,,,,,,,在,,,,框架下，达到了每秒,,,,,个查询的峰值吞吐能力。 当计算阈值超过,(,,,之后，吞吐能力增长明显放缓，这表示,,,的计算能力 已达到饱和。在此基础上，进一步升高计算阈值对系统性能帮助不大。结合图 ,(,,和图,(,,，系统管理员可以动态地选择恰当的计算阈值，在一定的响应时 间内尽可能增加系统的吞吐能力。 为了进一步提高系统的计算性能，本节还尝试了双,;,,,,,,,,卡环境下的 实验。详细数据见表,(,。 表,(,双,,,计算卡的性能细节 计算单卡,,,,,(,,,,,，—,,,,,,,,),,,,,(,,,,,，,,,,,,(,,) 阈值,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,“,, ,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,生成两个工作者线程，分别负责两块卡的控制工作。每个,,,线程内 部的调度逻辑与上文介绍的单卡环境下的,,,调度逻辑一致。两个线程采用动 态争抢的方式来实现两块计算卡的负载均衡。两个,,,工作者线程中自身空闲 的时候，就会主动到查询请求队列中争抢查询。一旦取得的查询的,值达到了计 算阈值的设定，,,,线程就会把自己负责的查询请求绑定为一个批次，发送到 ,,,上。 ,, 第三章,,,并行求交计算框架 从表,(,中，我们可以看到，两块卡处理了近似数量的查询请求。其中，, 是,,,计算时间，,是传输时间，,是,,,预处理时间，它们均以,,为单位。 ,,是吞吐率，以？,,,,,,,,为单位。它们的,,,核心计算时间和,,,预处理时 间基本相同，这表示负载被较为均匀地分散在两块计算卡上。因此，系统的整体 吞吐能力接近原先的两倍。 但是，当计算阈值较高时，两个,,,控制线程争抢查询的额外开销逐渐显 现出来。这使得,,,预处理时间的加和大于单卡环境下的,,,预处理时间。此 外，,,，,总线传输能力的限制，也造成了一定的影响。因此，双卡系统不能将 系统吞吐能力严格倍增。 第四节低负载情况下的动态处理器选择 前两节详细讨论了当系统处于高负载的情况下，这两种基于批次模式的并行 框架的性能和优缺点。但是，当系统处于低负载运行状态时，上述的并行框架仍 有待改进。本节主要探讨了基于,,,,框架的,,,(,,,协同工作模型。 如果系统负载低到,,,已经能够游刃有余地及时处理所有的查询请求，那 么，将多个查询请求绑定为批次传输到,,,上进行计算，并不一定是一个好的 选择。在这样的场景下，查询排队等待的时间，,,，,总线的传输开销，,,,核 心函数的调用开销等额外损耗，都会严重削弱,,,的速度优势。因此，在低负 载的情况下系统可以将,,,,的计算阈值降为,。此时，,,,,框架将退化为异 步处理模式，,,,会立刻派发收到的每一个查询。此外，某些符合一定特征的 查询可以直接由,,,处理，从而获得更低的响应时间。本节基于统计的方法， 提出了异步模式下的查询派发策略。,,,调度程序会根据查询的特征值，来决 定是该交由,,,还是,,,来处理该查询，以期达到最快的速度。 当查询被派发到,,,上执行的时候，,,,可以处于空闲状态。,,,,,,驱动 会为空闲的,,,自动下降,,,的核心频率和显存外频。因此，本节的策略对节 能也有一定帮助。 本节将,,,,,个百度查询请求，逐一分别用,,,和,,,进行处理。得到的 ,,,处理时间减去,,,处理时间之差，作为回归分析的因变量。如果时间差是 正数，这个查询就应该被派发到,,,上进行处理;反之则表示，,,,能够更快 地处理该查询。 ,, 第三章,,,并行求交计算框架 ,(),,, ,,,,, 查,,,,, 询 敷 量,(,,,, ,,,,, ,,,,, ,,,,, , ,,,,,,,, 时问差 图,(,,,,,与,,,时间差统计 图,(,,前三千个查询的详细时间差 图,(,,,,,与,,,时间差统计中的直方图显示，,,,对于大多数的百度 查询，都具有速度优势。但是，图,(,,前三千个查询的详细时间差显示，,,, 的优势并不明显(,轴下方区域)。如果一个查询更适合于,,,，那么将它调度 到,,,上，很有可能节省较多的时间(,轴上方区域)。 系统需要构造一个指标，来评判哪一种处理器更适合处理当前到达服务器的 查询请求。一般而言，对于包含计算任务较少的查询，更适合交由,,,来进行 处理。但是，当一个查询到达服务器的时候，系统所能得到的信息仅包括:关键 ,, 第三章,,,并行求交计算框架 词的个数以及它们对应的倒排索引的长度。本节利用这些有限的信息来构造指 标，进行统计学上的回归分析。为了尽可能降低派发决策过程中的计算开销，本 节仅引入了单自变量的一元回归分析【,,】。本节构造了如下三个指标，用来估计 一个查询中包含的准确计算量: ,),,,。,,,是查询中的最短倒排索引长度(,,,,,,,,,(,,,,, ,,,,,,,,,)。 ,,,,…(,(,) 因为求交运算的结果数不可能多于,,,，并且,,,,根据,,,决定给一 个查询分配的线程块数量，因此可以用,,,估算查询中包含的计算量。 ,),,,,。,,,,是串行计算复杂度上界(,,,,,,,,,,,,,,,, ,,,,,,,,,, ;,,,,,,,,,,)。其形式化表达如 下: ,,,,,,,,幸(,,,,,,，,,,,,, ,，…，,,,,,,)(,(,) ,,,,精确地表示了一个查询能够包含的比较次数的上限。 ,),,,,,。,,,,,是并行计算复杂度上界(,,,,,,,,,,,,,, ,,,,,,,,,, ,,;,,,,,,,,,,,,,;,,,,)，表征了一个,,,线程能够包含的比较次数的 上限。 ,,,,,,,,,，,,,，,,,，,, ,，…，,,,,,,，(,(,) 如果所有线程能够被,,,理想化地并发执行，,,,,,就可以准确反映 ,,,上的并行执行时间。 上述三个指标分别作为三组回归分析的自变量，对应查询的,,,与,,,处 理时间差作为回归分析的因变量。回归结果见表,(,。 表,(,回归分析结果 指标,,,,,,,,,系数截距 ,,,,(,,,,,,(,,,,,(,,,,,,,,一,(,,,,, ,,,,,(,,,,,,(,,,,,(,,,,,,,(,,,(,,,,, ,,,,,,(,,,,,,(,,,,,(,,,,,一,(,,,,, 时间差和指标之间的关系决定了采用何种派发决策。在统计学中，如果 ,(,,,,,小于,(,,,，则意味着在,,的显著性水平上，我们不能拒绝原假设。 ,,,？,,,,是决定系数(拟合优度)，它表示回归方程中的自变量能够在多大程度上 解释因变量，也就是说该指标衡量了回归模型的拟合效果。 表,(,表示，在相同显著性水平下，,,,,能够最大程度地解释时间差的变 化，因为,,,？,,,,达到,(,,,,，所以我们可以说，,,,,能够解释时间差,,,的 波动情况。因此，本节选择,,,,作为回归方程的自变量，所得出的回归方程 ;,((?(,，,二(,:„( ,, 第三章,,,并行求交计算框架 如下所示: ,,,,,,,,,,,(,,,,,，(,(,,,,,, ,)毒,,,,(,(,) 本节用这个方程，作为查询的派发策略。当服务器获得一个查询请求的时候， ,,,首先计算出该查询的,,,,，并代入回归方程中计算,,,,,,,,，，如果 ,,,,,,,,,,，就把该查询派发到,,,上计算。反之，则将该查询派发给,,, 处理。 ,, 第四章搜索算法的分析与改造 第四章搜索算法的分析与改造 第一节搜索算法的分析和比较 在过去的数十年间，集合求交问题已得到了深入而广泛的研究。研究者们的 工作主要集中在自适应(,,,,,,,,)算法上【,,】【,,】【,,】。这类算法对输入的数据不做 任何假设，而是随着交运算的进行来决定算法行为。,,,,,,,,,,】【”】提出了在,个 有序集合上，利用循环方式(,,,,,,,,,,,)来自适应地进行交运算的方法。 这些算法很好地挖掘了,,,串行处理的潜力，特别着眼于对,,,,,,,,缓 存的充分利用。例如，基于跳表(,,,,,,,,)的搜索算法【,,】,,,】是在,,,,,,,,,数 据集上，是迄今为止我们所知道的用于集合求交的最快速算法。因此，我们将其 用作,,,处理查询请求的对照组。 则跳跃则跳跃则跳跃则返回 图,(,跳表搜索算法 如图,(,所示，跳表搜索算法将较长的倒排索引划分为若干个相邻等长度 段。较短的倒排索引中的,,;，,在这些段间进行跳跃查找。在搜索的过程中，算 法比较各段段首和,,;，,之间的大小关系。如果段首小于待查找的,,;，,，算法 就会直接跳跃到下一段的段首进行比较。如是往复，直到找到段首大于,,;，,的 段。此后，算法在前一段中进行顺序搜索。算法需要用,,,;,;,,,,,,的大小指 导段长的选择，以此提高每一次访存的缓存命中率。 因为段首元素以段长为间隔，均匀地分散在内存空间中，所以跳跃访问前后 相邻的段首元素很可能造成;,;,,,,,,，从而引发一次高开销的内存访问。为了 解决这个问题，本文将各段段首事先复制到一块连续的内存区域(,,,,,,,,,,) 中。因为,,,,,,,,,,只占用很小的空间并且被频繁访问，因此可以认为，算法对 ,,,,,,,,:;,的访问，会大概率地命中,,,缓存。 ,, 第四章搜索算法的分析与改造 在,,,上，每个线程负责一个独立的,,,,,，因此线程之间的依赖关系被完 全消除了。显然，这些针对,,,缓存进行优化的串行算法并不适合,,,的并行 计算环境。 另一类求交算法为了追求性能上的提升，采用了近似策略。例如，,,,,,,,,,,】 的研究成果展示了在,,,环境下的集合求交算法。,,,,,,,,】采用了,,,,,一,,】的中心 思想，利用哈希函数值来取代对原始集合的存储。 在并行求交领域，,,,,,,,,,,,,,,,】研究了适合于片上多处理器,,, (,,,,(,,,,, ,,,,,,,,,,,,,,,)的并行求交算法。研究者们设计了一种平衡的分片算法(？,,,,,,, ,,,,,,,,,,,,,)，在多个处理器间实现负载均衡。此外，研究者们还设计了一种 动态探测方法(,,,,,,;,,,,,,,,,,,)，很好地利用了,,,的多级缓存结构， 以此减少对内存的访问开销。 我们需要为,,,选择一类合适的搜索算法。因为倒排索引的体积庞大，因 此系统需要将其保存在最大的显存空间—曾,,,,,,,,,,中。但是，访问,,,,,, ,,,,,,有着较高的时间代价。在,,,,,,,,,,,,,,,,上，进行一次,,,,,,,,,,,, 访问需要消耗不少于,,,个时间周期。此外，在,,,,,架构之前的显卡系列 (,,,,,系列和,,,系列)中，,,,,,,没有为,,,,,,,,,,,,装备缓存。这就使 得访存操作成为搜索过程的主要瓶颈。 在,,,上，二分搜索算法(,,,,,,,,,,;,)不适合进行倒排索引的求交运 算。 这是因为倒排索引较长，二分搜索在大范围的内存空间中进行跳跃，会产生多次 ;,;,,,,,,。此外，在二分搜索算法框架内，上一次搜索对下一次搜索的指导意 义不大，尤其是在刚开始的几次搜索操作中。但是，二分搜索非常适合被应用到 ,,,并行求交环境中，这是因为: ,)较早的,,,中，,,,,,,,,,,,,没有配备缓存。这使得二分搜索对缓 存 利用不佳的缺点不复存在。 ,),,,线程之间的搜索操作互相独立，没有依赖性。因此，前一个线程的 搜索结果，不会对后一个线程的搜索提供帮助。 ,)二分搜索具有对数复杂度。当倒排索引的长度呈线性增长时，二分搜索 的比较次数增长缓慢。 插值搜索,,,】也是一种被广泛使用的，具有对数复杂度的搜索算法。在每一步 的搜索过程中，插值搜索根据当前正在访问的元素值以及搜索区间的前后边界 值，计算出待搜索的元素最有可能出现的位置。插值搜索利用了数据分布的特性: 如果集合中的元素值呈现完美的均匀分布(例如，等差数列)，插值搜索能够取 得,(,,,,,,,)的计算复杂度。实际上，插值搜索在,,,上的并行性能，相比二 分搜索算法有明显劣势。这是因为: ,, 第四章搜索算法的分析与改造 ,)真实的倒排索引数据不能满足插值搜索所要求的严格均匀分布。此外， 现代搜索引擎系统常常通过对倒排索引数据的重排序，人为构造出许多 ,,,，,值分布密集的局部，以此取得更好的压缩效果。关于倒排索引数据 分布的详细分析，请参见第五章第二节。这些不均匀性，都损害了插值 搜索的性能。如果插值搜索陷落在这些分布不均的局部，其最坏算法复 杂度将退化为伙甩)。 ,)在,,,的,,内部，,,,,,,采用了,，,,结构。每个,,,线程块都需 要等待其中最慢的线程退出之后，才能完全释放出资源，供下一个线程 块使用。因此，少数运行缓慢的线程，会拖慢整个线程块的运行速度。 ,)在每一步的搜索过程中，二分搜索仅需要将,,;，,和当前正在访问的元 素值进行比较，以此决定跳跃方向;而插值搜索则不仅需要将,,,，,和 当前正在访问的元素值进行比较，还需要获得当前搜索范围前后边界的 值。这使得插值搜索的每一个搜索步，需要比二分搜索更多的访存次数。 在,,,,,内部的,，,,机制的约束下，一个,,,,中的线程不仅需要尽可 能地执行相同的代码，还需要满足一定的访存模式才能取得对,,,,,,,,,,,,的 最大读写速度。这样的访存模式要求:在每个,,,,,,,,,中，全部线程必须读取 同一块连续的,,,字节的显存区域，才可以在一次传输事务中完成数据访问。否 则，,,,要发起两次传输，增大了访存开销。在二分搜索的过程中，相邻的,,, 线程所持有的,,;，,值，可能分布在距离较远的两个位置。显然，二分搜索在大 数据范围内跳跃的时候，很难符合此访存模式。 此外，,,,配备的,,,,,,,,,,,,，能够提供在,,个时钟周期以内的访存 速 度。如果在二分搜索的过程中，系统能够对,,,,,,,,,,,,加以利用，就将取得 很高的访存速度。但是，在,,,,,以前的,,,上，每个线程块最多只能利用,,,, 的,,,,,,,,,,,,;在,,,,,架构,,,上，每个线程块最多也只能利用,,,,的 ,,,,,,,,,,,,。对于规模较为庞大的倒排索引而言，这部分存储空间仅是杯水 车薪。为了利用这部分,,,,,,,,,,,,，本节设计了分段的二分搜索算法，希望 以此提高二分搜索算法的性能。 ,, 第四章搜索算法的分析与改造 厂,;,?,„，,,上,,;,,,,„?,„, ，， ,,,,,,,,,, 】,,,,,,,,,,,,,,,,,,,,,,,, , , ，,,,,,,;,,,,,,,,,,,,;,,,,,,, 厂姊,一 ,,,,,,? ,,,,,,,,,,,,,,,,,,,,,,,, 图,(,分段的二分搜索 如图,(,所示，当两个倒排索引相交时，系统按照,,,,,,,,,,,,的大小， 对较长的倒排索引进行均匀分段。在搜索开始的时刻，,,,线程严格遵循,,,,,, ,,,,,,的访存模式，将第一段中的,,;，,全部放入,,,,,,,,,,,,中。在此期 间，系统收获了最大的,,,,,,,,,,,,访问带宽。接下来，每个线程在,,,,,, ,,,,,,中二分搜索自己持有的,,;，,。在此期间，二分搜索的访存代价被降到 最低限度。搜索完毕之后，如果某些线程发现自己持有的,,;，,超过了本段的最 大值，则表示有一部分待搜索的,,;，,可能存在于随后的若干段中。因此，,,, 将进行新一轮的迭代，将第二段以同样的方式放入到,,,,,,,,,,,,中，如是往 „ 复。 本策略的优点在于:系统最大化访问,,,,,,,,,,,,的带宽，并最大限度地 减小了二分搜索的访存代价。本策略的缺点在于:算法访问,,,,,,,,,,,,和 ,,,,,,,,,,,,的次数总和超过了单纯的二分搜索。假设各段段长为丘，那么较 长的倒排索引将被划分为，,(,,)，,厶段。因此，在,,;，,均匀分布以及,,,线程 被充分并行的前提下，我们需要进行，,(,,)，,„次,,,,,,,,,,,,访问，以及 (，,(,,)，,,，),,,,，次,,,,,,,,,,,,访问。能会抵消高速访存带来的优势。 当倒排索引较长时，额外的访存代价可 第四章搜索算法的分析与改造 ， ，,,)厦窖 咖啪黜瑚鲫 ,,段的数量,,,,,捣 姗枷珊瑚蛐 , 图,(,两种搜索算法的性能对比 ,(, ,,一一,,? ,, 瑙,(, 较 , , ,,(, 、,?,， , ,,,,段的数铲,,,,,,, 图,(,分段二分搜索相对于一般二分搜索的加速比 如图,(,和图,(,所示，分段的二分搜索在段数量少于,,的情况下，能够 取得一定的优势。但是，随着倒排索引继续加长以及分段的数量不断增长，分段 二分搜索的运行时间迅速增多。分段本身带来的额外代价逐渐占据了主导地位， 它抵消了高速访存带来的优势。 基于上述的分析和实验，我们得出了如下结论: ,)在真实的数据集上，将,,,,,,,,,,,,引入倒排索引相交运算的思路， 暂时是不可行的。 ,)在访问,,,,,,,,,,,,的过程中，保证严格符合访存模式的思路，暂时是 不可行的。 ,)综上所述，提高搜索速度的最佳途径是尽可能减少访问,,,,,,,,,,,, 的次数。 第四章搜索算法的分析与改造 第二节,,,,,,,,,,,搜索算法 在本节中，我们提出了将,,,,,,,,,,,应用到,,,求交运算的具体策略。本 节的目的在于，将二分搜索具有的对数复杂度,(,,,,)降低到常数复杂度,(;)。 其中，,是,,,,,,,,,,,的哈希函数计算次数。本策略引入了如下两个额外代价: ,)除了保存原始的倒排索引之外，系统还需要保存倒排索引的近似表征: ,,,,,,,,,,,。因此，本策略带来了一定的额外存储压力。 ,),,,,,,,,,,,策略引入了一定的结果冗余。有些不属于最终交运算结果的 ,,;，,也会出现在结果集合中。 ,(,(,,,,,,,,,,,,介绍 ,(,(,,,,,在,,,,年提出了高效存储的数据结构,,,,,,,,,,,, ,。这是一种 用于集合近似表达的高效数据结构。,(,,,,,,,】讨论了一系列精确和近似的集合 表达方法，并研究了它们的空间复杂度。 从存储角度而言，,,,,,,,,,,,是一条含有,个比特的连续数据区域。对于 一个含有力个数据元素的集合,(,,毡，岛，岛，((,))，系统通过,个相互独立的 哈希函数(，，红，鬼，((也)，将集合中的,映射到,，…，,一,的值域空间上。 对集合中的每一个元素工?,，系统将曩(功的值映射到,,,,,,,,,,,的对应 比 特上，并将该比特置为,。,,,,,,,,,,,中的各比特可以被多次置位，但只有第一 次置位动作可以发生效力。 ,, 图,(,对,,,,,,,,,,,的置 位 如图,(,所示，三个元素被两个哈希函数映射到图中的灰色比特位上。相应 位置被置,。两个哈希函数指向的重复比特，仅被置位一次。 为了检测一个值,是否属于集合,，系统会将,代入,个哈希函数中，逐一 检验,个制定比特是否都被置为,。如果不是，那么显然,不存在于集合,中。 如果,个比特位都已被置位，那么系统可以断言:在一定的概率下，,属于,。 这个断言存在出错的概率，使得本不属于,的元素被认为是,的成员。我们将其 称为假正错误率(,,,,,,,,,,,,,,,,,，以下简称“误 称率”)。 误称率的大小受两方面影响: ,, 第四章搜索算法的分析与改造 ,,,,,,,,,,,,,占用的比特数小。一般来说，误称率随着,的增大而减小。 ,)哈希函数的个数。 当集合,中的刀个元素全部被映射进,,,,,,,,,,,之后，对于任何,个给定 的比特位，它的值仍然是,的概率是: ,,(,一二),?,由,”(,(,) 因此，出现误称的概率是 ,,(,,,)„(,(,) 对误称率进行变换，得到: 厂,,,,(,，,(,,,,,,,,”(,(,) 定义,为,的指数部分，得到 ,,,,,(,一矿翩佃)(,(,) 改变哈希函数的个数,，最小化误称率厂的过程，等价于最小化,的过程。 因此，对,求导，得到 褰,,,(, 当,(,,(,,,),,,的时候，,的倒数为,，使得厂取到最大 值。 假设系统在,,,,,,,,,,,中，平均为每个,,;,,分配;个比特，则有,,,,,南, ,力,;。 假设;,,,，当,,,,时，能取得最低的误称率。在实际应用中，我们没有必要 设置这么多的哈希函数，以取得最优的误称率。例如，当,,,时，误称率仅为 ,:),鱼,,(,,,,,,。 在非压缩的情况下，倒排索引以,,位无符号整型数组的形式保存。因此当 ;,,,时，系统需要付出一半的额外存储开销来保存,,,,,,,,,,,。,,,,,,妄, ,,,,,,, 大小的选择与误称率的具体关系，我们将在,(,(,节中详细讨论。 ,,,,,,,,,,,作为一个快速搜索策略，被嵌在,,,,框架中，用来替换二分搜 (,(,)施索算法。,,,,,,,,,,,在搜索引擎建立倒排索引的同时被计算好，并和倒排索引 一起被实现传输到显存中。,,,,,,,,,,,所引入的误称率，会使得交运算的结果 中包含一些非正确结果。这些结果并非出现在查询所涉及的所有倒排索引中。但 ,一,一驯是，这些结果对搜索体验的影响微乎其微，因为: ,)系统通过选择合适的哈希函数和,,,,,,,,,,,长度，主动将误称率控制在 肘、? 百分之一以下。因为误称而产生的多余的错误结果，我们称之为“冗余 结果??。结果冗余率,冗余结果数,总结果数。这个指标表示错误结果出现 的可能概率。结果冗余率和误称率呈正比例关系。 ,, 第四章搜索算法的分析与改造 ,)在求交运算完成之后，搜索引擎系统还需要对此结果进行排名。因为冗 余结果并没有真正包含全部的查询关键词，所以这些冗余结果大概率地 会被系统自动调整到结果集合的尾部。在一般情况下，用户并不会关注 搜索引擎召回结果中数十页以后的内容。 ,(,(,,,,,,,,,,,,在,,,上的应用 本节深度分析了,,,,,,,,,,,搜索算法在,,,上的执行效 率。 ,,,线程的执行时间与访问,,,,,,,,,,,,的次数成正比例关系。因此，本 节用系统中,,,,,,,,,,,中的探查次数(,,,,,,,,,,,)来估算执行时间。 ,,,线程为了确认自己持有的,,;，,是否存在，最多进行,次探查。每次探 查均引发一次,,,,,,,,,,,,访问，并且花费一定的计算时间。如果在第,次的 探查显示赡(,)位置上的比特为,，系统无需再探查红，，(功。也(功位置上的比特。 对于任意的,,,线程，探查次数的期望为: , ,,? ,, 其中，,是式,(,中，一个比特位为,的概率。 (，, 对于,,以,,,并且,,,的情况，,,,(,,。这意味着各线程平均进行,(,, ,), (,(次,,,,,,,,,,,,访问，即可确定自己持有的,,;，,是否存在于倒排索引,(,,)中。 ,),但是上述分析忽略了,,,线程模型的特点。在,,,,,,,,,上，线程按照,, ,， 为单位，被组织成,,,,。,,,,是线程在,,上执行的最小单位。因此，一个,,,, 的执行时间，受限于其中最慢的线程。 假设,表示探查次数少于等于,的事件，有: 只,),? ,(,一 假设置是一个,,,,中的全部线程的探查次数都小于等于,的事件，有: ,)卜, 【,(,)以吃),尸(,)“(,(,) ,,， 在,,,,,,并且,,,的情况下，可以得到不同,值的对应概率: ,, 第四章搜索算法的分析与改造 表,(,,,,,中线程结束探查的概率 探查次数,(,, ,,(,,,, ,,(,,,, ,,,(,,,, ,,,(,,,, ,,,(,,,, 如表,(,所示，任何一个,,,,中的全部线程，有,,(,,,,的概率在,次探查 之内完成对，以)的搜索过程;更进一步地，这些线程有,,(,,,,的概率能够在, 次探查之内完成搜索过程。因此，只要,,,,,均匀地分散在各个,,上，,,,,, ,,,,,,搜索算法就能够取得很好的性能。 本节讨论了,,,,的批次批次模式对,,,,,在,,,之间分布的均匀程度有所 帮助。不失一般性地，本节认为: ,),,,之间的计算是独立的。一个,,的计算过程，无需依赖其他,,,。 ,),,,在,,,之间调度,,,,,的开销极低，可以忽略不计。 ,),,开始处理一个,,,,的时候，不能预测这个,,,,的运行时间。( ,)一个,,处理完成一个,,,,之后，,,,从待处理的,,,,集合中随机地 选取下一个,,,,分配给它;因为任务的分配是随机的，并且任务量很大 (基于,,,,的批次模式)，所以各个,,处理的任务量很可能是接近均 匀的。 假设,。是,,,,,所需的处理时间。如上文所述，一个,,结束了一个,,,, 的处理之后，可以从任务队列中随机选取下一个,,,,进行处理。假设,是,,, 处理完所有分配给它的任务所需的总时间，本节有如下的定理: 定理: 对任意两个,,,和,，，假设局，仍，岛，((以和,,，？,，吼，(((，,，是它 们分别处理的 两个,,,,序列。我们可以得到如下关系: (,(,) 乃?乃一, (,(,,) 弓?墨一? 证明: 本节用反证法进行论证。不失一般性地，假设乃?乃一乞，。完成所有任务的 总时间,表示，当,,,处理完毕见之后，,,,不会再从任务队列出取得任何 ,,,,。这表明只结束之后，任务队列为空。但是巧?乃一?暗示了至少还有一个 未完成的吼在任务队列中。这与本节之前的假设矛盾。, 二,,, 第四章搜索算法的分析与改造 上述定理告诉我们，对于任意的两个,,,，它们之间的处理事件的差异不会 超过他们各自所处理的最后一个,,,,所需的运行时间。在批次模式下，,,处 理的总,,,,数量不断增长，而,,,之间的时间差异的上限始终被最后一个,,,, 的处理时间所限定。因为,,,调度,,,,的方式服从随机化原则，因此各,,处 理的最后一个,,,,所需的时间也服从相同的分布规律。综上所述，,,,,,在,,, 之间的分布是均匀的。 因此，一个批次的处理时间与平均一个,,,,的处理时间呈正比例关系。,,,, 的平均处理时间如下: 五 ?, 量 (, (七，,)尸(,),,一?(尽„。, (,(,,) ， ,(,),,, )一 (七，,), ,,, 一?尸(,(忍 七一?『),,,一， ,(,),,, ))注意到当,?,,,的时候，以,),,，这使得尸(,),,是一个极小的值。因,,,,,此， 平均一个批次的处理时间(响应时间)和哈希函数的个数,,,呈近似的正比例关系。 ,, ,, 这个结论在后续的实验中得到了验证。 ,(,(,哈希函数的选择 本节探讨了不同的哈希函数族，对冗余率和系统吞吐能力的影响。 在,(,(,节中，本文讨论了哈希函数的个数对冗余率的影响。哈希函数族的 选取同样影响着结果冗余率和系统吞吐能力，这是因为: ,)好的哈希函数能够将,,;，,均匀地，随机地散布到,,,,,,,,,,,的整 个空 间内，从而降低误称率和结果冗余率。因为,,,,,,,,,,,得到了充分利用， 所以其效果等价于加大,,,,,,,,,,,空间。因此，选取好的哈希函数族， 有助于降低,,,,,,,,,,,所需的额外空间开 销。 ,)好的哈希函数族的计算较为简单。本文利用较少次数的瑰,)探查操作， 取代二分搜索对数复杂度的访存。因此，本文希望计算鹿,)的代价尽可 能低，以免抵消较少的访存操作带来的优势。 基于上述考虑，本文在以下三种哈希函数族中进行选择: ,)哈希函数族,: ,,,(功,,,,,,(,(,,) (一?„， ,,? 第四章搜索算法的分析与改造 其中，口，(,?,?七)是从,,,,,，,,,,,,,范围中随机选取 的质数。 ,)哈希函数族,: ,,,(功,勿加 (,(,,) 其中，勿(,?,?七)是从(,，,,,,,,范围中随机选取的 质数。 ,,哈希函数族,: ,,,(曲,？,,,,,,【,(,,) 其中，;:,(,?,?,)是从,,，,,,(,,;，,,)】范围中随机选取的质数。 ,,,(,,;,,,)代表一个数据集中的最大,,; ，,值。 ,(陀, ,(,, , 脏 降始硬 吼 ,?, , ,,,,,, 哈希函数的数量 图,(,哈希函数数量与冗余率的关系(基于,,,数据集) ,(,, 一，,,，,,，,, ,,,, 、 ,,, 、 静,,,, 。、 簧,,, ?,、 ,(,, ,,, ,,, ,?,、 ,,,, —,:„,?一?,? ,(,, ?考， , ,,,,,, 哈希函数的数量 图,(,哈希函数数量与冗余率的关系(基于百度数据集) 图,(,和图,(,分析了不同的哈希函数族，在使用不同哈希函数个数的情况 下，所取得的冗余率情况。好的哈希函数族应该在函数个数相同的情况下，取得 ?(„: ,, 第四章搜索算法的分析与改造 更低的冗余率。显然，利用小质数作为乘法系数的,,在两个数据集上，都取得 了最高的冗余率。这是因为小质数作为乘法系数的哈希函数，不能将,,;，,在较 大的,,,,,,,,,,,空间中均匀散布，造成,,,,,,,,,,,空间利用不充分。利用大质 数作为乘法系数的,,，以及利用随机数作为异或系数的,,，可以较均匀地将 ,,;,,分散到整个,,,,,,,,,,,空间中。因此，这两个哈希函数族在两个数据集 上，都取得了近似的较低的冗余率。尤其在,,,数据集上，这两个哈希函数族 在,,,的情况下，都能取得小于千分之一的冗余率。这样低的冗余率使得用户 很难察觉到不良结果的存在。 随着,的增加，冗余率逐渐下降。但是这种下降趋势在,大于,之后迅速放 缓。,,,,,,,,】指出，在误称率合理的情况下，最小的,,,,,,,,,,,空间可以在有 一半的比特数被置为,时取得。因此，进一步增加哈希函数的数量并不会让冗余 率明显降低。 图,(,哈希函数族的吞吐能力 图,(,展示了不同的哈希函数族所取得的系统吞吐能力。在,,,上，因为 异或运算快于大整数乘法，因此，,,在两种数据集上能够取得最高的系统吞吐 能力。对异或系数？的选择至关重要。我们在整个,,;，,值域空间内随机选取,， 使得二进制比特位,能够随机分布在,个;:,中。这样，尽可能均匀地散布在,,,,,,,,,,,毋(力的计算结果，能够 上。 作为对比，本文曾选取一系列有规律的异或系数进行实验。这些有规律的异 或系数分为两类: ,)依次递增的,个有序数字。例如: ,,，,， ,，((() ,)有规律地将比特位,分布到,个,中。例如: ?,,,,,响，,,,,,,,,，,) ,, 髑,,,,，((、 第四章搜索算法的分析与改造 前期实验已经证明了这些有规律的异或系数，会带来较高的冗余率。 虽然,,拥有最少的计算时间和较低的冗余率，但是,,在某些情况下能够取 得最低的冗余率。例如，百度数据集拥有倒排索引较短，查询关键词较少的数据 特征。在这样的数据集上，利用大整数作为乘法系数的,,，能够取得最低的冗 余率。 结合图,(,和图,(,，,,在冗余率和系统吞吐能力上，能取到最好的均衡。 因此，本文采用,,作为后续实验的哈希函数族。 ,(,(,,,,,,,,,,,,搜索算法的性能 本节分析了在不同的计算阈值下，二分搜索算法和,,,,,,,,,,,搜索算法的 性能差异。 本文在第三节中介绍了计算阈值的概念。,,,,的计算阈值直接决定了每批 次所包含的计算量。对于给定数量的查询请求，更大的批次规模意味着更少的 ,,,调用次数。因此，较大的批次能够有效降低,,，,传输代价，使,,,有效 计算时间比例上升。但是，更大的批次规模会升高响应时间，从而伤害用户体验。 系统需要在吞吐能力和响应时间上取得一个良好的平衡。 ,??,，,,,,,,,,,,,，,，,,,忾,,,,,,,,, ,的?, ,,,?,，,,,,,,,,,,,,,??(,,,，?,,,,,,,,,,,,,),—,——————,( 。?一， 乏,,?? 罟,,(,?,? 夕，。,,,,,,,,, 妊,,,,,×,。,—，,一 躲,,,,,,,,， ,,?,》;二,,一一一, ,()?,薹,;)。,二一?,;;„? ?————一，? ,? ,(,,,,,弼,,,,掀,,,,,鲫(,?,,,,, 计算阈值 图,(,计算阈值与吞吐率的关系 图,(,计算阈值与吞吐率的关系显示，对比二分搜索算法，,,,,,,,,,,,搜 索算法显著提升了系统的吞吐能力。这主要归功于,,,,,,,,,,,减少了对,,,,,, ,,,,,,的访问次数。在,,,数据集上，当计算阈值达到,(,,,之后，,,,,,,,,,,, 搜索算法将系统吞吐能力推升到,,,,,？,,,,,,,,，相对二分搜索算法增长了 ,,(,,。系统为如此显著的性能提升付出的代价是: ,),(,倍的空间占用。本实验中，将,,刀设置为,,，表示系统平均为每个 ,,;,,分配,,比特的,,,,,,,,, ,,空间。 ,, 第四章搜索算法的分析与改造 ,,,(,,的结果冗余率。这意味着算法在每一千个正确结果中，掺入了一个 错误结果。在这个冗余水平下用户很难察觉到搜索结果相关性的改变， 并且系统后续的调权步骤会主动把冗余结果放到结果列表的尾部。这使 得用户在前若干页的搜索结果中都不会看到冗余结果。 在,,,数据集上，当计算阈值超过,,,,之后，系统吞吐能力增速明显放 缓。这表明,,,得到了近似饱和的计算量。在充分利用,,,之后，进一步增加 计算阈值是不明智的。 图,(,,计算阈值与响应时间的关系 百度数据集的系统吞吐能力明显高于,,,数据集，其响应时间也小于,,, 数据集的响应时间。这是因为百度数据集的倒排索引相对较短，查询关键词大部 分在,个之内，因而，百度查询中包含的计算量少于,,,查询。类似地，,,,,, ,,,,,,搜索算法在百度数据集上也显著提高了系统吞吐能力。 值得注意的是，在百度数据集上，计算阈值高于,(,,,之后，系统吞吐能力 依然保持了明显的增长势头。这个趋势表明，在百度数据集上，,,,的计算潜 力没有得到完全利用。,,,需要更为沉重的计算压力，才能在百度数据集上工 作于饱和状态。这是因为,,,,,,,,,,,搜索算法使得,,,处理各个查询所花费的 代价降低，,,,能够更为轻松地做完全部的查询任务。在这种情况下，百度查 询所包含的计算量无法充分发挥,,,的计算能力。但是，因为响应时间的快速 增加，迸一步提高计算阈值的意义不大。 基于上述实验结果，我们可以得出如下结论: 类似百度进行倒排索引划分的搜索引擎，在使用,,,,框架进行批次计算的 时候，可以改用低功耗的,,,计算卡(例如,,,,,)。一方面，可以充分发挥 ,,,的计算能力;另一方面，这样的配置降低了能源方面的开销。 图,(,,计算阈值与响应时间的关系展示了两种搜索算法在各种数据集上的 童,, 第四章搜索算法的分析与改造 响应时间。四条响应时间曲线均呈现出类似的上升趋势。当计算阈值低于,,, 的时候，响应时间的差距极小。这是因为在低计算压力下，不同的计算量和不同 的搜索算法对,,,的效能影响不大。但是，随着计算阈值的进一步升高，响应 时间曲线明确地体现出不同搜索算法的效能差异。 系统需要结合图,(,和图,(,,，在系统吞吐能力和响应时间上取得动态的平 衡。例如在,,,数据集上，如果系统要求将响应时间约束在,毫秒之内，管理 员就需要将计算阈值调整为,,,,。 ,(, , 王, ,,, 量,(, 景, 善,(, , ,(, , ,,哈希—‰数量,哈希函数技量 图,(,,哈希函数数量与响应时间的关系 图,(,,展示了不同的哈希函数个数,对系统响应时间的影响。在两个数据 集上，响应时间均与,呈正比例关系。本文在,(,(,，通过式(,(,)得出了形式化 结论:各批次的响应时间与,呈正比例关系。图,(,,的实验很好地契合了理论 分析。 表,(,,,,,,,,,,,,长度与算法性能的关 系 ,,,空间占用倍数冗余率吞吐率(？,,,,,,,,) ,,(,,,,(,,,,,,, ,,,(,,,(,,,,,,, ,,,,,(,,,,,,,,,, ,,,,,(,,,,,,,,, 表,(,展示了在不同的,,,,,,,,,,,长度下，空间占用情况、冗余率和系统 吞 吐能力的变化。同前文中的约定，这里用,,表示倒排索引中,,;,,的数量，用册 表示,,,,,,,,,,,中的比特数。因此，比例历,,反映了,,,,,,,,,,,的相对长度。 表格中的第一列就是,,刀的不同情况。 随着,,,,,,,,,,,空间的增长，冗余率从,(,,迅速下降到,(,,以下。 在,,, ,,数据集中，当,,,,,,，系统用与原始倒排索引等大的空间来保存额外的,,,,, ,,,,,,信息。因此，此时空间占用为原来的,倍。当空间占用由,，,倍增长为,倍”… „,, 第四章搜索算法的分析与改造 冗余率显著下降了,,倍。因此，如果显存空间充足，适当增加,,,,,,,,,,,的体 积能够有效控制冗余率。但是，当空间占用从,倍增加到,倍时，冗余率仅略微 下降。这表明与原始倒排索引等大的,,,,,,,,,,,空间，已经能够很好地控制哈 希函数的冲突机率。进一步对,,,,,,,,,,,扩容的做法，不能取得明显收益。相 反地，系统吞吐能力在这个阶段出现了下降的倾向。这是因为相邻的,,,线程 探查的比特会间隔很远的距离，从而使得读取,,,,,,,,,,,,的带宽下降。 ,,?,,,,,,,,,,,”,,,(,阻 鬟姗,,自,,,,,,一?,, ,,;,,,,,,,,, 善,,,,,?, ,, 等,,,,,,,(,瓠，, 静,,??猡„～?一,黟—— 苫 褥知哪一,,,帆一 ,,,,,?,,姗 “…。鬟。,, ,,,,,,,,,,,,,, ,,,,,(,,,,,,) ,,,,,,,,,,,,,,,,,,,碰为,, ,,,,,,,,,,,,,,,,,,?,,,,,,,,, 图,(,,加速比对照 ,,,,,架构的,,,,,,计算卡相对于,,,,,架构的,,,,,,,,,, 计算卡，做 出了大量改进，其中包括但不仅限于: ,,增加了大量,,,,核心; ,)提升了核心频率和显存外频; ,)优化了线程的调度逻辑; ,)为,,,,,,,,,,,,加上了缓存。 这些改进使得,,,,,计算卡更适合于工程和科学计算方面的任务。 在,,,,,,,,,,,搜索算法中，,,,线程通过计算曩,)获得了一个比特位之 后， 仅进行一个是否为,的简单比较。因此，本运算对访存速度非常敏感，显存带宽 在一定程度上成为系统性能的瓶颈。,,,,,,的显存带宽是,,,,,,,,,,显存带 宽的,(,,倍，这对系统性能的提升有很大帮助。 图,(,,展示了不同计算平台针对两种数据集合的吞吐能力(？,,,,,,,,)。 数 据标签中表明了在同一种数据集合中，不同计算平台相对于,,,的加速比。在 ,,,数据集上，,,,,,,,,,,取得了,,(,,倍的加速比;,,,,,,将这个优势扩 大到,,(,,倍。从功耗角度来看，,,,,,,,,,,和,,,,,,的峰值功耗分别是,,, 瓦和,,,瓦。因此，,,,,,,多付出,(,,倍的能源开销，收获了,倍的系统吞吐 能力。( ,, 第五章倒排索引数据分布的分析和利用 第五章倒排索引数据分布的分析和利用 第一节倒排索引重排和随机化方法 倒排索引重排指的是将数据集合中的文档按照某种映射规则重新分配文档 编号,,;，,，并生成新的倒排索引集合的过程。倒排索引的原有性质(单调增， 不重复)不变。例如，有如下两条倒排索引: ，(,,),(,，,， ,) ,(,,),(,，,， ,，,) 其中的,,;，,值按照表,(,中的规则进行映射: 表,(,新旧,,;，,映射表 ,,,,,,,,,, ,,,,,,,,,, 从而生成新的倒排索引集合，如下: ，((,,),(,， ,，,) ，乜),(,，,，,， ,) ，(„)与，?(„)包含的文档相同。只是文档编号重新分配的过程，改变它们的 ,,;，,分布特征。 倒排索引重排被广泛应用于搜索引擎当中，主要目的是改善,,,,,类压缩算 法的倒排索引压缩效果。 ,,,,,类压缩算法，压缩的是倒排索引中，两个,,;，,之间的差值。例如， 系统先将,,(,,)转化为: ?,(,,),(,;,， ,，,) ?，?(乞)中的首元素是,,(,,)中首元素的原始值。其后跟着， ，,(,,),,,个差值。显 然，??(,?)中的元素占用的比特数，要明显少于，?(,,)中元素需要的比特数。 如果能够让，,)中的,,;,,值尽可能接近，那么世?(„)中的元素的平均值就 会下降，从而进一步节约存储空间。基于这个思路，研究者们做了大量的工作。 ,,,,,,,,,,,,利用相似图(,,,,,,,,,,,,,,,)来表示文档之间的关系。图中的定点代 表文档，边代表文档之间的关系。两个有共同边的定点，代表了两个包含同一个 关键词的文档。随后，利用递归算法在图上生成有层次的聚类，通过深度优先遍 历进行,,;,,分配。,,,,,,,,】也利用了相似图的结构，但是，他为每条边进行赋 第五章倒排索引数据分布的分析和利用 权。权值根据两个文档包含的公共关键词的个数来决定。算法在带权的相似图上 寻找权值之和最大的环。在此基础上，算法遍历这个环，进行,,;，,的分配。上 述文献提出的重排策略的复杂度较高。为了在线性时间内完成重排过程， ,,,,,,,,,,,,】提出了基于“,(,,,,,(,,,,:的聚类算法进行,,;,,分配的策略。 前人的研究成果在倒排索引中构造出许多,,;,,值密集分布的局部，从而减 少世,)中元素的平均值，改善压缩效果。但是，从倒排索引的全局角度而言， ,,;，,分布的均匀性被严重破坏。本节反其道而行之，提出了利用随机化方法重 排,,;，,，从而改善,,;，,分布均匀性的策略。随机化重排策略会恶化,(,,,类 压缩算法的压缩效果，但是对后文提到的倒排索引的线性特征有极大的助益，从 而改善了后文提出的搜索算法和压缩算法。 本文采用,,,,,,,,,,,,随机化方法来构造类似表,,,,,所体现的映射 关系，以 此消弭在原始倒排索引中存在的不均匀性。,,,,,,,,,,,,随机化方法的伪代码如 下: 本文利用,,,,,,,,,,,,随机化方法，对,,,，,,,,及百度倒排索引集 进行 重排，生成新的,,,,，,,,,,及,,,数据集。除了数据分布有所不同以外， 原有数据集合的一切性质均没有改变。 此外，本文还对,,,中的,,;，,，利用各网页自身的,,,,,,,,进行重排， 使得,,,,,,,,较高的网页获得较小的,,;,,。由此产生了,,,,,数据集合。 第二节数据分布特征 根据数据分布特征设计对应的搜索算法，往往能有针对性地提高算法效率。 第四章第一节中提到的插值搜索，就是一个典型例子。 本节将一条倒排索引的,,;，,映射到二维平面上，,,;,,在倒排索引中的位 置作为,轴上的坐标，,,;，,值作为,轴上的坐标。 第五章倒排索引数据分布的分析和利用 ,,,? ,,,,, ,,,,, ,,?, 口,,,,, 垒,,,, 暑,,,, ,? ,啪 , 。量量晷誊晏誊曼萎萎囊璺萎莩曼墨莩晷 ，,,,,““ 一一一,,？,呐,，?卜卜?,,,— 图,(,倒排索引散点图 图,(,给出了两组不同的数据集，分别对同一条倒排索引做二维映射得出的 散点图。可以看到，五条曲线都体现出了较好的线性特征。但是，随机化之后的 倒排索引具有更为显著的线性特征。本文将利用倒排索引中普遍存在的线性性 质，加速,,,的交运算速度。 第三节一元线性回归 在统计学中，一元线性回归是利用最,,,,乘法原理【,,】对一个自变量和一个因 变量之间的关系进行建模的回归分析方法。对于给定的一个随机样本,,，置)， ,,,，,，…，刀。线性回归模型假设因变量鬈和自变量五。之间的线性关系可能是不完 美的。事实上，这种不完美是普遍存在的。因此，一元线性回归可以表示为如下 形式: 】厂,口，?,，占(,(,) 为了估计口和?，对于样本如，五)，扛,，,，。刀，利用最小二乘法将残 差平 方和最小化: ?毛,,? (乃一口 对口和?求导得到正规方程: 一氏), (,(,) ,,,，?„?,,，,(,(,) ,?乃』一„。』,, ?蕾口，?玉,?一。„„,,„,, ,?毛咒,,,, 用克莱姆法则求解此线性方程组，得到: ,,,,, 第五章倒排索引数据分布的分析和利用 (?(薯一;)?,,) 。 (,(,) 窆(毛一;): …， 口,,,,,, 利用方差分析得到决定系数,,(拟合优度): ,,,,,，(,， 一五), ,,,,,(,，,,，),(,(,) ,,:,一—,,— ,,，? , 在一元回归模型中，尺,是回归直线对散点的拟合程度的重要指标，它表示 的自变量和因变量之间的线性相关程度。,,,,,，,】。尺,越接近,，表示回归直 线对散点的变化趋势拟合得越准确，该模型越有说服力。 第四节线性回归加速搜索 如本章第二节中所述，因为倒排索引不能呈现严格的均匀性，并且,,,,, 内部,，,,规范的限制，因此使得简单利用线性特征加速搜索的插值搜索算法在 ,,,上表现较差。本节介绍了通过线性回归方法利用倒排索引线性特征的搜索 算法，简称线性回归搜索(,,搜索)。和,,,,,,,,,,,搜索类似，,,搜索也是应 用于,,,,框架中，用以取代单纯二分搜索。 第四章第一节阐述了单纯二分搜索(,,,,,,,,,,;,)适合,,,硬件结构的 原 因。因此，,,搜索致力于在收缩各,,,线程中倒排索引中的搜索范围，从而达 到降低访存次数的目的。与插值搜索不同的是，虽然,,搜索也利用了倒排索引 的线性特征，但,,搜索在确定了搜索范围之后转而调用二分搜索进行查找。这 使得,,搜索的性能不会被局部数据的分布不均匀所打扰。 对任意一条倒排索引，(,)，系统利用本章第二节的方法，将其映射到二维平 面上。随后，系统利用线性回归方法，计算回归方程: 厂(,),,,吒，反,(,(,) 其中，气和反由最小二乘法计算而得。 对七?,,，,，(((，，，(„)，)?假设，(„)陋】是倒排索引， („)的第七个,,;,,。在此定义 最大左水平距离„和最大右水平距离气: ,, 第五章倒排索引数据分布的分析和利用 厶。,,,,女(厂„,(，(„)坼,)?((,(,) 一七) ,(,,,,，(,一厂,(，(„) 【忌】)) 图,(,线性回归搜索算法 如图,(,所示，,是在回归直线上方，距离直线最远的点。,到直线的水平 距离，形成厶。同理，,是指回归直线下方，距离直线最远的点。,到直线的水 平距离，形成足。经过,点和,点，可以分别画一条平行于回归直线的虚线。 显然，两条虚线包围的平面空间，涵盖了一条倒排索引中全部的散点。倒排索引 数据的线性特征越显著，回归直线就会和散点拟合得越为紧凑，从而厶，冠越 小。 假设系统需要搜索,,;，,,。首先，系统计算出,透过回归直线在横坐标上 的投影厂,(,),,一尼),？。随后，系统在如下范围中进行二分搜索: ,,,,(,，厂。,(功一厶()，,,，, (，，(„)，，,叫(功，足，)】 由图,(,可知，如果,存在，那么在此范围内一定能够找到。因为从厂,(曲开 始向左寻找厶个元素，可以涵盖和直线有最大左距离的,点;从厂,(功开始向 右寻找冠个元素，可以涵盖和直线有最大右距离的,点。我们将此根据回归方 程和最大左右水平距离计算而得的搜索范围，称为安全搜索范围。如果,在安全 搜索范围内无法找到，就可以断言，,在倒排索引，(„)中不存在。 单纯二分搜索的最大搜索区间是整个倒排索引，含有,，(„),个,,;,,: ,,搜 索算法的搜索区间是安全搜索范围，最多含有厶，，足个,,;,,。本节定义收缩率 如下: ,,,,,,(厶，，足),，,(,，)， (,(,) 本节用收缩率来衡量,,搜索算法对比单纯二分搜索算法的相对优势。对于 同一条倒排索引而言，如果收缩率能够被降低，就意味着安全搜索范围被缩小; (,,( 第五章倒排索引数据分布的分析和利用 也就是说后续二分搜索因此也能更快地完成。假设,,搜索需要的访存次数比单 纯二分搜索需要的访存次数少仃次，则有: 晖,， 盯,,,, ,去, 表,(,倒排索引的分类决定系数和收缩率 ,,,,,,,,,,,,,,,,,,,,, ,，(„)，,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, (,,,,,,),(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,, 【,,,,(,,,,),(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,, 【,,,,，,,,,),(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,, 【,,,,，,,,,),(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,, 【,,,,，,,,,),(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,, 【,,,,，,,),(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,,,(,,,,,(,, 本节研究了,个有代表性的实际数据集合，并对它们所拥有的倒排索引按照 长度进行分类。本节对每类倒排索引子集计算了平均收缩率和平均决定系数，这 些数据展示在表,(,倒排索引的分类决定系数和收缩率中。可以看到，未做任何 处理的原始倒排索引集合(,,,，,,,,和,,)已经具有了显著的线性特征， 其平均尺,可以维持在,(,以上。随着倒排索引长度的增长，,,总体上呈上升趋 势。这表明更长的倒排索引，有可能具有更好的线性特征，从而能被回归直线更 准确地表达。 被随机化之后的数据集合(,,,,，,,,,,，,,,)同比随机化之前的对应 数据集合(,,,，,,,,，,,)，具有更为显著的线性特征。这表明随机化重排 策略对改善,,;,,分布的均匀性有很好的效果。类似地，随机化之后的数据集合 的收缩率也出现了明显下降。 例如，在,,,数据集中，长度为一百万个,,;,,的倒排索引拥有的平均收 缩率是,(,,,,，由此节省了,次访存。如果利用单纯二分搜索在全局范围内跳跃， 需要,,次访存。因此，,,相对于二分搜索，节约了,,,的访存代价。由此可 见，,,搜索在随机化后且含有大量长倒排索引的数据集中，与二分搜索相比具 有明显优势。 ,,搜索算法的额外存储空间极小。系统仅需要为每条倒排索引保存如下的 四元组: ,印吆,,？，，屈，，,,， ,)(,(,,), 其中，回归方程系数是单精度浮点整数，最大水平距离是无符号整数。因此， „,, 第五章倒排索引数据分布的分析和利用 在绝大多数计算平台上，此四元组仅需要占用,,个字节。 搜索引擎系统在完成倒排索引，(,)的建立之后，随即完成却,的计 算。待 全部倒排索引及相应的回归信息建立完毕之后，系统将它们事先传输到,,,计 算卡上。这样，在,,,进行查询请求的实时处理时，可以直接利用回归信息进 行定位。 第五节哈希分段加速搜索 本节利用倒排索引的线性特征，提出利用哈希分段方法进行搜索的策略，称 为哈希分段搜索(,,搜索算法)。和,,搜索类似，,,搜索算法致力于收缩后 续二分搜索的搜索范围。 ,,将各条倒排索引，(„)划分为若干个哈希段,。对于任何,?，(„)，,,利 用一个确定的哈希函数,,，(曲，将,映射到哈希段色中。如果在倒排索引中搜 索,,;，,,，系统仅需要在对应的哈希段色中进行二分搜索。 在哈希函数的选取方面，系统需要考虑两个因素: 。,)哈希段的大小基本相同。 ,)哈希函数的计算开销尽可能小。 实际应用中的倒排索引集合大都有显著的线性特征。因此，本节选用了一个 简单而有效的哈希函数。,,;，,的值域范围是,,，,，(((，?，设,是满足,,,„的最 小整数。定义哈希函数如下: ,(,),,?,，,,,扣慨，砚?,,， ,】(,(,,) 对于一条给定的倒排索引，(,,)，砚是给定的。不同倒排索引的,可能有所不 同。,((,)的本质，是将,,;，,,的高强位，作为哈希段的段号。他越大，哈希 段的段数越多，平均段长越短。在实践中，系统根据，，(„)，动态选取,。统希望哈希段的平均段长小于等于,,,，那么系统选定最小的砚，满足: 如果系 幽?,鸭(,(,,】 ,,, 根据性能需要，系统为全部倒排索引指定相同的平均段长(例如上式中的 ,,,)。因为，，(„)，有较大的差异，因此各倒排索引私有的,不同。 当系统设置期望段长为,,,个,,;,,时，本文将其体现在算法名称中，简称 ,,,,,搜索算法。 因为局部分布不均的缘故，存在着一些包含,个,,;,,的哈希段。系统在进 行求交运算时，可以直接忽略这些空段。因此，空段的存在不影响系统性能。? ，? ,, 第五章倒排索引数据分布的分析和利用 ,,,,,, ,,? ,,,,,,, 翌 ,,,,,, , ?,,,,,, , ,,,,,,, , ，(一，，，，(一 , ,， 吕蒸氢,旨牙熹爵辜辜旨赛富, 一一一一一一一一一一一一聂苌丽范卣巴一一一一一一一一一一一一一 , 薹薹富基富蚤萤萤莹量虽虽莹虽图,(,非空哈希段的段长分布情况 莹曼虽萤萤,詈 从,,,数据集中，我们选取了所有满足,”?,，(„)，?,”的倒排索引，并设置 ,,,，使平均段长为,,,。从图,(,可以看到，哈希段长的分布集中在,,,,，,,,, 这个狭窄的区间内。如果利用单纯二分搜索在全局范围内跳跃，最多需要,,次 访存;而,,,,,能够把绝大多数的哈希段长约束在,,,之内，使得最多访存次 数减少为,次。 因为,,;，,的分配很大程度上服从随机化原则，因此任一个给定的,,;，, ,?,,，,，(((，?在倒排索引，(„)中的概率,,,,(,，),,,。在此基础上，对一个给定的 倒排索引，(,)，其中的非空哈希段的段长近似服从二项分布: 一?，一, ，最,,,,(,,(,，) ,，,)其中,,昔(,(,二项分布的期望是,,(,，),,，方差是,，(„),,(,,,)。 图,(,展示了一个近似于 二项分布的图表形态，契合于理论分析。因为图,(,包含了一个长度范围内的多 ,), 条倒排索引，因此二项分布的形态有一定变形。 第六节实验分析 本节讨论了不同的搜索算法在不同计算阈值下的性能。第三章第三节详细介 绍了,,,,框架下的计算阈值的含义和赋值依据。计算阈值和每批次所包含的计 算量呈正比例。更高的计算阈值能够更好地利用,,,的计算能力，但会引入更 长的响应时间。 ,, 第五章倒排索引数据分布的分析和利用 ,,,,? 四，,口,,因,,口,,,,,,,,? ,,,? 宙,,,,,备 口芒,,,,,,,, ,一臣三 ,,匿,,,,, 量,,,,,:,(， 錾; 麟錾 够,,,,,,委 蘧镬;,,缸,,,,, ,,咖一 ,,,?, :羹鼋耋毫羹 蔗,该蓁匡二,墨鼋蓬 双,涨,,,“,,,,计,算阐瑟,,,,,,,,,,,, 图,(,不同计算阈值下的吞吐率 理 瑗鐾薹 正如图,(,所示，,,搜索算法和,,搜索算法明显提高了系统吞吐能力。这 是因为,,和,,通过收缩二分搜索的查找范围，降低了,,,线程的访存次数。 ,,的搜索范围由线性回归方法界定，,,的搜索范围由哈希方法界定。当计算阈 值为,,时，,,,,(平均段长为,,的哈希分段)将系统吞吐能力推升至二分搜 索的,(,倍，同时付出,,的额外存储空间，用来保存对应的哈希段信息。,,,, 的吞吐能力在计算阈值为,,时并没有显著放缓，这表明,,,,,,的计算能力尚 未充分发挥。因此，搜索引擎可以采用功耗更低的,,,计算卡(例如,,,,,,)， 以此降低能源消耗。 坫 ? , ? , , —,,一暮鲁毪霉 , , , ,,,,,叙,,,,,(,,,,,,,,,,,,,,,，„计算闽值 图,(,计算阈值与响应时间的关系 如上文所述，响应时间是衡量用户体验的重要指标。在,,,,框架中，响应 时间由,,,预处理时间，,,，,传输时间和,,,计算时间三部分组成。 如图,(,所示，当计算阈值小于,,,,时，响应时间之间的差距不明显。这 (是因为,,,能够很轻松地处理小计算量任务。随着计算阈值的增加，高效搜索 算法的优势逐渐体现出来。主流搜索引擎对响应时间有着严格要求，因此对计算 一,, 第五章倒排索引数据分布的分析和利用 阈值的选取，需要在吞吐能力和响应时间之间取得平衡。 表,(,对照,,,的加速比 ,,,,,,,,,,,,,, ,,,,,(,,,,(,,,,(,,,,(,,,(,, ,,,,,,(,,,,(,,,,(,,,,(,,,(,, ,,,(,,,(,,,,(,,,,(,,,(,, ,,,,(,,,(,,,,(,,,,(,,,(,, 第四章第一节详细介绍了本文使用的,,,对照组算法—捌,表搜素【,,】。这是 我们己知的最优的,,,求交算法。,,,对照组算法基于单线程实现。多线程或 多进程版本的,,,算法效能受限于处理器核心数型,,】，因此可以很容易地估算 出其上界。 本节在表,(,对照,,,的加速比中罗列出了,种不同的搜索算法在,种不 同特征的数据集上，相对于,,,对照组的加速比。,,,,在所有的搜索算法中胜 出。,,,,和,,,,在,,,,,上取得最大加速比，而非线性性质更显著的,,,, 数据集。这说明良好的线性特征虽然可以使得哈希分段更为均匀，但是对,,搜 索算法的影响并不显著。,,,,在,,,数据集上的加速比达到了,,(,,倍，超过 了,,,,,,,,,,,算法取得的,,(,,倍的加速比。 我们注意到，,,在,,,上的加速比略微高于,,,,。同样的情况也出现在 ,,和,,,数据集合上。这是因为随机化虽然贡献了更低的收缩率，但是加剧 了同一个,,,,,,,的线程分支情况。,,,,,,,,,,,,,,】显示，利用,,和,,在 ,,,上进行搜索的时候，同一个,,,,内的线程出现分支的概率分别增长了,,, 和,,,。在这样的场景下，线程分支相对于搜索范围的缩小，扮演了更为重要的 角色，从而抵消了随机化重排带来的收益。因此，在选择倒排索引重排策略时， 需要考虑到线程分支和线性特征之间的平衡。从实验中可以发现，随机化重排虽 然可以很好地改善倒排索引的线性特征，但是对,,搜索和,,搜索没有直接帮 助。我们将在未来工作中，针对这两种搜索算法进行优化的重排策略进行进一步 的研究。 ,, ,, ,, 求,一 蔓 ,, 七 , 星 翟 删,, 蜮 收 走, 乱。 , , 奄冷冷毒梦?。?枣零 ,,,,,,,,,,, ,,数量 计算阙值 (,) (,) 图,(,(,),,数量与加速比的关系(,)计算阈值与,,,时间占总时间的比例的关系 我们通过修改,,,,，,,的方式来屏蔽指定数目的,,,,,，来研究不同的 ,,,核心数对加速比的影响。图,(,(,)展示了,,,,在,,,数据集上的性能。 计算阈值被事先设置为,,，以取得吞吐能力和响应时间之间的平衡。,,,,的 加速比和核心数量呈正比例关系。随着,,,数目的增加，算法的效率都有所提 高。这在并行计算中比较常见。 图,(,(,)展现了,,,,的,,,以及与计算阈值相关的,,,数据集的使用 情况。假设计算阈值决定了倒排索引的长度和，那么，对于一个批次计算模型来 说，它就代表了问题的规模。我们可以看出,,,运算时间占总时间的比例随着 计算阈值的增长而增长，这表明了随着问题规模的增大，算法的效率也随之提升。 试验结果表明，在同时增加处理器的数量和问题规模的情况下，我们的新算法能 够维持一个固定的效率，也就是说，算法具有可扩展性。 图,(,(,)也揭示了另一种现象。,,,(,,,之间的传输和,,,的计算总是 占据了总执行时间的,,,以上。将这部分处理时间和,,,计算时间叠加起来， 以此来减少总的处理时间，这对改进我们未来的工作很有帮助。 ,, 第六章总结和展望 第六章总结和展望 第一节总结 倒排索引求交运算在搜索引擎的计算流程中，占据,,,时间的可观比例。 本文着眼于将,,,的计算压力充分卸载到,,,计算卡上;并且利用,,,的强 大并行计算能力，实现尽可能高的加速比，提升单个节点的计算能力。实验表明， 单台服务器的交运算速度最多能被提升,,余倍。这使得搜索引擎公司在不扩大 集群规模的情况下，就能够从容应对日益沉重的查询请求压力。 本文假定单位时间内到达的查询请求数量庞大，以至于,,,无法在规定的 响应时间范围内处理完毕。在此基础上，本文提出了对应,,,的查询请求批次 处理模式，并设计了相应的粗粒度实验表明，,,,,框架对提高系统的吞吐能力有很大帮助。本文也研究了在查询 并行框架(姗)和细粒度并行框架请求稀疏的情况下，,,,和,,,进行协同工作的处理模式。 本文分析了在,,,和,,,上表现较好的搜索算法，并将,,,,,,,,,,,利用 (眦)。 到,,,求交领域。本文从理论上分析了在,,,这个独特的硬件结构上，,,,,, ,,,,,,搜索算法的预期表现，并在实验中证明了理论分析的相关观点。 本文还分析了倒排索引的数据分布特征。从全局的角度看，大部分倒排索引 的数值分布是近似均匀的。在此基础上，本文利用一元一次线性回归方法对倒排 索引在二维平面上的投影进行拟合，从而预测出待搜索的,,;，,可能出现的位 置。此外，本文还利用倒排索引的数据分布特征，构造出一个简单有效的哈希分 段策略，使得,,,在伙,)的时间复杂度下，能够定位到一个极小的搜索区间。 实验证明，利用倒排索引数据分布构造出的搜索算法，相对于单纯二分搜索算法 而言，有着明显更好的性能。 第二节工作展望 在本文中，我们事先将全部需要的倒排索引传输到显存中。因此，在整个实 验过程中，算法不需要通过,,，,总线从,,,向,,,传输倒排索引。但是，,,,,, 架构的,,,计算卡最多装备,,,的,,,,显存;最新发布的,,,,,计算卡最多 装备,,,,,,,显存。目前一台服务器,般最多装备,个,,，,插槽。如果这些 插槽被全部用上，在可预见的未来，一台服务器最多可以配备,,,,显存。这个 第六章总结和展望 存储能力和一台服务器的硬盘中要保存的上百,,的倒排索引总量相比，有着明 显差距。此外，一张,,,计算卡有着,,,,左右的功耗，更多的计算卡的引入， 对服务器的能耗压力不可忽视。因此，如何解决显存不足的问题，是大规模部署 ,,,计算集群的一个重要问题。 为了解决这个问题，我们还需要设计出适合,,,进行解压缩的压缩算法; 以此让有限的显存空间能够容纳更多的倒排索引。此外，我们希望效仿操作系统 中的页面文件替换算法，设计出高效的显存空间替换算法。此替换算法保证最频 繁使用的倒排索引常驻显存;其余倒排索引按照各自所需，在显存和内存之间实 时传输。 参考文献 参考文献 ,,,,,,,,,,,,,,,，,(,,,;,,,,,;,,，,,,,(,,,,,,,,,,,,,,,,,,,,,,,,,,，,,,,,,,,,(,,, ,,,,,,,,,,,。,,, ,( 【,】,,，,，,,,,,,,,,,,,(,,，,，,,,,,,,,,,,,,,,,,,,,,,,(,,,,( 【,】,,,,,,,,,,,,,,,,(,,,,,,,,;,,,,,,,,,,,,,,,,,,;,,，,,,,;,,,,,,,,,,,,,,;,, ,,,,,,;,(,,,,,,,,,,,, ,，,,,, ,,】,(,(,,,,,,,,(,,,,,,,,,,?违,,,,,(，,,,,;(,,,,,,,,,,,,,,,,,,,,,,,,,;, (,,,,,,,,)，,,,,,,—,,， ,,,,( 【,】,(,,,,,,,,(,,,,,,,,,,,,,,,,,,(，,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,;,(,,,,)(,,,，,,,,,,,,(,,,(, ,,,,,,,，,,,,( 【,】,(,,,,,;,,,，,(,(,(,,,,,,，,,,,,,,,,,,,(,,,,,，汪,,,,,,,,,,,,,,,,;,(，,,,,;( ,,,,,,,,,,,,,,,,,,,,,,,,,;,(,,,,)，,,,,( 【,】,(,,,,;,;，,(,,,;,,，,(,,,,,，,(,,,,,,，,,,,,,,，,,,,(,,;,,,,，“，,,,,,,,, ,,,,;,,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,,,,,,,;,,,,,,，”,,,,,;,,,,,,,,,,, ，,,,,,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,;,? ,,,,,,,,,,，,硼,,,,，,,,,;,，,,,,,,,，,,(, ,,,,,,( 【,】,(,,,,,,,,,，,,,,？,,,,,，,(,(,,,,,,,,,,，,,,,,,,;,,,,,,，“,,,,,,;,,,,,,,,,,, ,,,,,,,,,,,;,,,,,,,,,,,,,;,,,,,,;,,,,,,，”,,,,,;,,,,,,,,,,,,,,,,,,,,,,，,,,,,,,,,,,, ,,,,，,瓜,,,,,,,,;,,,,,,,,,,;,,,,,,,,,,,,,,,,,，,,,,,,,,,,,,,,,,,,,(,,,取 ,,,,，,,,,,,，,,，,,,，,,,,,,,，, ,(,,,,,,,( 【,】,,(,,,,,,，“,,,,,,,,,,,,,,,,,(,;,,)、?,,,,,,”，,,,(,,,,,,(;,,，,,,,,,,,,( 【,,】，乙,,(,,,,,,,,,(,(,,,,,,，,,,,;,,,,,,,,,,,;,,,,,,,,,,,,,,,,;,(,,,,,,,: ,;,,,,,,,,,，,, ,,( 【,,】,,,,,,,,,,,,，„„,,,,,,,,，,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,？,,,;,,,?，,,,;,,,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,,(,,,)，,,,(,,,,,, 【，,,,，,(,,,,,,,，,,,,,,,,， ,,,,( 【,,】,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(,,,,(,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,？,,,;,,(，,,(,,,,;,,,,,,,,,,,,,，,,,,,,,，,,,;(,, ,,，,,,,,,,,,,,,,,,,,,,，,,,,,,,,,,，,,,, ,,(,,,,,,,,,,,,,,,( 【,,】,,,,,,,(，,,,,,,,,,,，,(，,，,,,(:,,,,,,,,,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,,,;,,,,(，, ,,,,,,,，,(，,,,,，,。,,,,(:,,,,,,,,,,,,,,,,,,,,,,，,,,，,,,,,,,,,,,,,,,,,,,,，,,八 ,,,,,,,,,,,,,呵,,(，,,,,,,,,(,,,,), ,,,,,,( 【,,】,(,,,,,,,，,(,,,,,,,,,,,，,,,,(，,,,,,,,(,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,;埴,,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,，,,,,, ,,(,,,( 【,,】,,,;,,,,,，,(,,,,,,,,,,,，,,,，(,,,,,(,,,,,,,,,,,,,,,,,,;,,,,,，,,,,,,，,,, ,,,,,,,,;,,(，,,,,,,,,:,,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(,,,,,,,,,,,,,,, ,,,;,,,,,,,,,,,,,,，,,,,,,,,,,,,，,,,,,,,,,,,,，,,，,,凡,,,,(,,;,,,,,,,，,,,,,,,,,,,, ,,,,,,,,,,,,,,,,;,(?? ,, 参考文献 ,;,,,,,,(，,,,,,,;,,,,,,,,,,,,,,【,,】,(,(,,,,,,,，,(,,,,,,,,,,,,,,,,,,( ,,，,,,,( ,,,,,,,,,,,,,,,,,,,,,,, ,，,,,,( ,,,,,,,,,,,,,,,,,,;,,,,,,,(,,,【,,】,(,,,,,(,,,,,,,,,:,,,,(,,,， ,,,,,,,,,,; ,,(,):,,,,,,,，, ,,,( 【,,】,,,,,,,,,,,,,(,,,,,,(,,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,,(，,,,,,,,,,, ,,,,(,,,,,,,,,,,,(,,,,,,, ,，,,,,( 【,,】只,,,,,，,(,,,,，,,,，,,,,,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,,( ,,,,,,,,,,,,,,,,,,,,,,,,，,,,,,,,,—,, ,(,,,,,,,,，,,,, 【,,】,(,,,,,,，凡,,,,,，,(,,,,，,,,,,,,,,,，,,,,(,,,,,,，,,,;,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,(,,,,,;,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,(,,,,?,,)，,,,,,,,,，,,,,,,,，,,, ,，,,(,,,,,( ,,,】,(,,,,,,,,,,,,，,(,,,,，,,,,(,,,,,,(，,,,,,,,,,,,,,,,,,,,,;,,,,,,,,,,,，僦,,,( ,,,;,,,,,,,,,,,,,,,,,,,,,,,,,，,(,): ,,,,,,,，,,,,( 【,,】,(,;,,，,(，,,,，,,,,(,,,,(，,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,;,(,,,,,,,;,,,,,,,, ,,,,,,，,,(,):,,,,,,,，,,,, ,,,,( 【,,】,(,,,,,(,,,;,,,,,,,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,,,,,,,，,,,,(,,,,,,,;,,,,,, ,,,,,,,,，,,(,):,,,,,,,， ,,,,( 【,,】,，,,,,,,,(，,,,,,,,(，,,,,,,,,,,(:,,,,;,,,,,,,,,,;,,,,;,,,,,,谢,, ,,,,,,,,,,(;,,,,,;,,,,;,,,,,(，,,,,?,,:,,,;,,,,,,,,,,,,,,,,,,,,;,,,,,,, ,,,,,,,,,;,,,,,,,;,,,,,(,,,,)，,,(,,,,,,,(,,,,,,,,,,，,,,,,,,,,，,,,( 【,,】,,;,,,;,，,(,(,,,,,,,,，,(,,,,,,,，,,,,(,,,,,(,,,,,,,,,,,,,,,,;,,,,,,,,,,,,,, ,,,,？,,,,,,,,,,,,,,(，,,,,;(,,,,,,,,,,，,,,,,,,,,,,,,,,,，,，,,,,,,,,,;,,,, ,,,,,,;,,,,,,,,,,,,,,,,,，,,,,,,,,,,,,,,,,,,,，,,,,,,,,,,,,，,,,,(,,,,,,,， ,,,,,,,( 【,,】,(,,,,,,,,，,(,,,,,,，,,,,,,，,,,,(,(,,,,,(,;,,,,,,,,,,,,,,,,,,;,,,,,,,,( ，,,,,;(,,,,,,,,，,,,,,,,,,,,,,舯,，,,,,,,,,,,,,,,,,,,,;,,,,,,,,,， ,,,,,,,,,,,，,,,,(,,,,,,,,，,,,,, ,,,,,，,,,(