基于CUDA平台的并行相似对搜索技术研究

发布时间：2020-03-29 00:53

【摘要】：相似对搜索广泛应用于信息检索、数据挖掘、数据库等计算机科学领域,也是大量实际应用中的关键步骤,例如副本检测、协同过滤以及聚类等,因而得到深入研究。串行相似对搜索算法主要基于过滤策略减少查询对象的相似候选项。然而,随着相似性阈值减小,串行算法的性能严重降低。基于MapReduce或OpenMP的并行相似对搜索算法大多也采用过滤策略,因此也没有完全地解决这个问题。本文针对余弦相似度的相似对搜索问题进行了研究,提出了两种基于CUDA并行相似对搜索算法,主要工作如下:(1)基于CUDA架构设计了几种高维稀疏向量数据结构。本文提出了基于分段的前向表结构SFL(Segment-based Forward List),可以有效地实现内存合并访问;提出了倒排表结构CU-IL(CUDA-based Inverted List),避免了不必要的点积计算;结合上述两种数据结构,提出了一种混合型结构HSV(Hybrid Sparse Vector),可以在内存访问和点积运算之间取得一个折中。(2)提出并实现了一种新的基于CUDA架构的并行相似对搜索算法FCuAPSS。该算法基于前向表结构计算相似度,并使用共享内存优化算法性能。实验结果表明FCuAPSS取得了不错的加速效果,验证了共享内存优化方法的有效性。(3)为了克服FCuAPSS的缺点,提出并实现了一种混合结构的相似对搜索算法CuAPSS。CuAPSS结合向量对并行扫描和特征对并行扫描两种不同的方法,在向量的不同部分分别执行这两种方法。然后,本文提出针对参数p的调整方法,通过调整p,CuAPSS达到最优性能。实验结果表明CuAPSS取得了显著的加速效果,与CUDA库cuSPARSE相比CuAPSS取得14-85倍的加速比,与当前最优的并行算法相比CuAPSS能够达到1.5-23倍的加速比,而且在不同阈值下保持稳定的执行时间。
【图文】：

架构图,架构

单核处理器的发展遭遇了前所未有的瓶颈，在这种情况下，多核、众核处理逡逑器开始慢慢地受到人们的关注，成为发展的必然趋势。其中，ＧＰＵ是一种近年来倍受逡逑关注的众核处理器。如图１－１所示，与ＣＰＵ相比，ＧＰＵ在单个芯片上集成了更多的计逡逑算核心，具有高吞吐量、高显存带宽和高计算能力。逡逑诞生之初，ＧＰＵ主要用于执行图像渲染任务，其通用计算功能并没有得到广泛关逡逑注。随着ＧＰＵ可编程性逐渐提高，高性能计算领域开始使用ＧＰＵ加速运算，基于ＧＰＵ逡逑的算法优化也成为学术界和工业界的热点，ＧＰＵ通用计算（ＧＰＧＰＵ）逐渐发展起来。逡逑与目前的通用微处理器和云平台等其它主流计算平台相比，ＧＰＵ众核处理平台具逡逑有明显的优势：逡逑（１）并行度高，，计算能力强，带宽高。相比于ＣＰＵ，邋ＧＰＵ的单个芯片上集成了更逡逑多的计算单元，因此ＧＰＵ的并行度更高。同时期的ＧＰＵ的浮点计算能力高于ＣＰＵ邋—逡逑４逡逑

示意图,架构,示意图,单元

第二章相似对搜索算法概述．２基于ＧＰＵ的并行计算逡逑ＮＶＩＤＩＡ邋ＧＰＵ逦Ｆｅｒｍｉ［４９］＞Ｋｅｐｌｅｒ１５０１，Ｐａｓｃａｌ１５ｌ］＾ｎ邋Ｖｏｌｔａ［５２２－２为ＮＶＩＤＩＡ邋ＧＰＵ的Ｆｅｒｍｉ架构示意图。如图２－２所示，该ＧＰＵ包括１５个流多器，每个流多处理器有３２个ＣＵＤＡ核、１６个ＬＤ／ＳＴ（ｌｏａｄ／ｓｔｏｒｅｕｎｉｔ，加载／存储），４个ＳＦＵ邋（ｓｐｅｃｉａｌ邋ｆｕｎｃｔｉｏｎ邋ｕｎｉｔ，特殊函数单元），６４ＫＢ大小的共享内存和Ｌ１，１２８ＫＢ大小的寄存器文件，一个指令缓存以及两个ｗａｒｐ调度器和指令分派单个ＣＵＤＡ核包括一个算术运算单元和一个浮点数运算单元。每个指令分派单元控邋个邋ＣＵＤＡ邋核。逡逑？ｒｅａｍｉｎＭｕｌｔｉｒｏｃｅｓｓｏｒ邋１４逡逑
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP311.13

【相似文献】