【摘要】：相似對搜索廣泛應用于信息檢索、數(shù)據(jù)挖掘、數(shù)據(jù)庫等計算機科學領域,也是大量實際應用中的關鍵步驟,例如副本檢測、協(xié)同過濾以及聚類等,因而得到深入研究。串行相似對搜索算法主要基于過濾策略減少查詢對象的相似候選項。然而,隨著相似性閾值減小,串行算法的性能嚴重降低�；贛apReduce或OpenMP的并行相似對搜索算法大多也采用過濾策略,因此也沒有完全地解決這個問題。本文針對余弦相似度的相似對搜索問題進行了研究,提出了兩種基于CUDA并行相似對搜索算法,主要工作如下:(1)基于CUDA架構設計了幾種高維稀疏向量數(shù)據(jù)結構。本文提出了基于分段的前向表結構SFL(Segment-based Forward List),可以有效地實現(xiàn)內存合并訪問;提出了倒排表結構CU-IL(CUDA-based Inverted List),避免了不必要的點積計算;結合上述兩種數(shù)據(jù)結構,提出了一種混合型結構HSV(Hybrid Sparse Vector),可以在內存訪問和點積運算之間取得一個折中。(2)提出并實現(xiàn)了一種新的基于CUDA架構的并行相似對搜索算法FCuAPSS。該算法基于前向表結構計算相似度,并使用共享內存優(yōu)化算法性能。實驗結果表明FCuAPSS取得了不錯的加速效果,驗證了共享內存優(yōu)化方法的有效性。(3)為了克服FCuAPSS的缺點,提出并實現(xiàn)了一種混合結構的相似對搜索算法CuAPSS。CuAPSS結合向量對并行掃描和特征對并行掃描兩種不同的方法,在向量的不同部分分別執(zhí)行這兩種方法。然后,本文提出針對參數(shù)p的調整方法,通過調整p,CuAPSS達到最優(yōu)性能。實驗結果表明CuAPSS取得了顯著的加速效果,與CUDA庫cuSPARSE相比CuAPSS取得14-85倍的加速比,與當前最優(yōu)的并行算法相比CuAPSS能夠達到1.5-23倍的加速比,而且在不同閾值下保持穩(wěn)定的執(zhí)行時間。
【圖文】：

單核處理器的發(fā)展遭遇了前所未有的瓶頸，在這種情況下，多核、眾核處理逡逑器開始慢慢地受到人們的關注，成為發(fā)展的必然趨勢。其中，ＧＰＵ是一種近年來倍受逡逑關注的眾核處理器。如圖１－１所示，與ＣＰＵ相比，ＧＰＵ在單個芯片上集成了更多的計逡逑算核心，具有高吞吐量、高顯存帶寬和高計算能力。逡逑誕生之初，ＧＰＵ主要用于執(zhí)行圖像渲染任務，其通用計算功能并沒有得到廣泛關逡逑注。隨著ＧＰＵ可編程性逐漸提高，高性能計算領域開始使用ＧＰＵ加速運算，基于ＧＰＵ逡逑的算法優(yōu)化也成為學術界和工業(yè)界的熱點，ＧＰＵ通用計算（ＧＰＧＰＵ）逐漸發(fā)展起來。逡逑與目前的通用微處理器和云平臺等其它主流計算平臺相比，ＧＰＵ眾核處理平臺具逡逑有明顯的優(yōu)勢：逡逑（１）并行度高，，計算能力強，帶寬高。相比于ＣＰＵ，邋ＧＰＵ的單個芯片上集成了更逡逑多的計算單元，因此ＧＰＵ的并行度更高。同時期的ＧＰＵ的浮點計算能力高于ＣＰＵ邋—逡逑４逡逑

第二章相似對搜索算法概述．２基于ＧＰＵ的并行計算逡逑ＮＶＩＤＩＡ邋ＧＰＵ邐Ｆｅｒｍｉ［４９］＞Ｋｅｐｌｅｒ１５０１，Ｐａｓｃａｌ１５ｌ］＾ｎ邋Ｖｏｌｔａ［５２２－２為ＮＶＩＤＩＡ邋ＧＰＵ的Ｆｅｒｍｉ架構示意圖。如圖２－２所示，該ＧＰＵ包括１５個流多器，每個流多處理器有３２個ＣＵＤＡ核、１６個ＬＤ／ＳＴ（ｌｏａｄ／ｓｔｏｒｅｕｎｉｔ，加載／存儲），４個ＳＦＵ邋（ｓｐｅｃｉａｌ邋ｆｕｎｃｔｉｏｎ邋ｕｎｉｔ，特殊函數(shù)單元），６４ＫＢ大小的共享內存和Ｌ１，１２８ＫＢ大小的寄存器文件，一個指令緩存以及兩個ｗａｒｐ調度器和指令分派單個ＣＵＤＡ核包括一個算術運算單元和一個浮點數(shù)運算單元。每個指令分派單元控邋個邋ＣＵＤＡ邋核。逡逑？ｒｅａｍｉｎＭｕｌｔｉｒｏｃｅｓｓｏｒ邋１４逡逑
【學位授予單位】：南京大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP311.13

【相似文獻】

相關期刊論文 前10條

1 李學貴;許少華;李娜;張強;;基于渦流搜索算法的支持向量機分類模型[J];化工自動化及儀表;2016年12期

2 王保民;;基于和聲搜索算法的電力系統(tǒng)經濟調度[J];科技資訊;2014年06期

3 杜永峰;李萬潤;李慧;唐少玉;;和聲搜索算法在結構有限元模型修正中的應用[J];蘭州理工大學學報;2013年05期

4 李陽;;基于改進的群搜索算法求解分類規(guī)則[J];無線互聯(lián)科技;2012年10期

5 李冉;褚雪松;李亮;;動態(tài)和聲搜索算法在土坡穩(wěn)定分析中的應用[J];人民黃河;2011年02期

6 李紅;彭方;;窮舉式搜索算法及其應用[J];福建電腦;2007年05期

7 王士同;;S模下啟發(fā)式圖搜索算法A~的研究[J];微電子學與計算機;1988年03期

8 王士同;隨機產生式系統(tǒng)的啟發(fā)式圖搜索算法RA~*及其若干性質[J];鎮(zhèn)江船舶學院學報;1988年01期

9

本文編號：2605179