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

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

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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李學(xué)貴;許少華;李娜;張強(qiáng);;基于渦流搜索算法的支持向量機(jī)分類模型[J];化工自動(dòng)化及儀表;2016年12期

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

3 杜永峰;李萬潤;李慧;唐少玉;;和聲搜索算法在結(jié)構(gòu)有限元模型修正中的應(yīng)用[J];蘭州理工大學(xué)學(xué)報(bào);2013年05期

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

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

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

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

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

9

本文編號：2605179