基于GPU的相似度計(jì)算關(guān)鍵技術(shù)研究.pdf

1、相似度計(jì)算是計(jì)算機(jī)學(xué)科中一個(gè)重要的問(wèn)題，其應(yīng)用遍及多個(gè)領(lǐng)域，如互聯(lián)網(wǎng)、數(shù)據(jù)挖掘以及生物信息學(xué)等。隨著信息技術(shù)的發(fā)展，每時(shí)每刻都會(huì)產(chǎn)生龐大的數(shù)據(jù)，使得相似度計(jì)算在海量信息的快速檢索中顯得非常重要。為了適應(yīng)數(shù)據(jù)的急劇增長(zhǎng)，迫切需要利用高性能的計(jì)算平臺(tái)對(duì)已有方法進(jìn)行改進(jìn)和加速。
　　GPU具有強(qiáng)大的計(jì)算能力和高內(nèi)存帶寬，可以很好地滿足相似度計(jì)算并行化的需求。此外，GPU擁有很高的性能/價(jià)格比和性能/功耗比，使得GPU成為搭建超級(jí)計(jì)算機(jī)的

2、良好選擇，而其低廉的價(jià)格也使其普遍出現(xiàn)在桌面計(jì)算機(jī)中。
　　利用GPU平臺(tái)對(duì)相似度計(jì)算的性能進(jìn)行優(yōu)化，一方面要解決相似度計(jì)算的高維、數(shù)據(jù)稀疏性、數(shù)據(jù)依賴性等問(wèn)題，另一方面要考慮GPU內(nèi)部架構(gòu)、執(zhí)行模式的特殊性和局限性，如多級(jí)存儲(chǔ)層次有效利用、訪存優(yōu)化、線程負(fù)載均衡、規(guī)避線程分支等。對(duì)于不同的相似度計(jì)算方法，存在著不同的問(wèn)題，相應(yīng)的性能優(yōu)化機(jī)制也會(huì)有所不一樣。
　　當(dāng)利用稀疏矩陣向量乘算法來(lái)計(jì)算相似度時(shí)，其性能往往受限于計(jì)算平

3、臺(tái)的內(nèi)存帶寬。為了解決這個(gè)問(wèn)題，一種基于混合存儲(chǔ)的稀疏矩陣存儲(chǔ)格式從一些經(jīng)典稀疏矩陣存儲(chǔ)格式的數(shù)據(jù)布局、數(shù)據(jù)處理策略和存儲(chǔ)空間開(kāi)銷入手，分析潛在的存儲(chǔ)格式發(fā)展方向，從而采用行交錯(cuò)合并的方式來(lái)減少存儲(chǔ)空間的開(kāi)銷，其相應(yīng)的稀疏矩陣向量乘處理過(guò)程采用分段處理的方式來(lái)控制負(fù)載均衡。結(jié)果表明，新的存儲(chǔ)格式無(wú)論在計(jì)算性能方面還是在存儲(chǔ)空間開(kāi)銷方面，都優(yōu)于NVIDIA公司實(shí)現(xiàn)的多種稀疏矩陣格式。
　　當(dāng)利用矩陣奇異值分解來(lái)計(jì)算相似度時(shí)，傳統(tǒng)QR

4、迭代分解法耗時(shí)嚴(yán)重，并且難以使用GPU并行化?？紤]到很多計(jì)算機(jī)配備了多核CPU和多個(gè)GPU，基于分而治之模型的奇異值分解方法能充分發(fā)揮此類平臺(tái)所有計(jì)算資源的計(jì)算能力。該方法采用兩級(jí)分而治之模型，使得GPU盡量處于忙碌狀態(tài)，達(dá)到GPU資源的最大化利用；同時(shí)CPU與GPU協(xié)同計(jì)算使得多GPU平臺(tái)中的空閑CPU核心也利用起來(lái)。結(jié)果表明基于兩級(jí)分而治之模型的奇異值分解算法比較適合大規(guī)模的矩陣計(jì)算，并且能在多GPU平臺(tái)達(dá)到良好的加速效果。

5、　　針對(duì)Smith-Waterman算法需要大量的計(jì)算和內(nèi)存空間，并且當(dāng)實(shí)現(xiàn)于GPU平臺(tái)時(shí)受限于全局內(nèi)存的訪問(wèn)速度等問(wèn)題，一種基于壓縮的多線程處理方法能利用有限的GPU內(nèi)存來(lái)進(jìn)行物種的序列比對(duì)。該方法使Smith-Waterman算法的兩個(gè)階段連續(xù)地在GPU上執(zhí)行，提供所有比對(duì)序列的相似度和最優(yōu)匹配片段。此外，該方法能滿足生物學(xué)家對(duì)其研究領(lǐng)域內(nèi)的一個(gè)或多個(gè)物種進(jìn)行比對(duì)的需求。結(jié)果表明，對(duì)于中等規(guī)模的數(shù)據(jù)庫(kù)，該方法能取得優(yōu)于使用Ssear

6、ch回溯的CUDASW++2.0和DOPA。
　　為加快大規(guī)模信息數(shù)據(jù)的相似拷貝檢測(cè)，一種結(jié)合simhash與漢明距離的檢測(cè)方法使用GPU平臺(tái)并行執(zhí)行。該方法包含三個(gè)內(nèi)核，分別為指紋生成內(nèi)核、候選指紋篩選內(nèi)核和漢明距離計(jì)算內(nèi)核。為了適應(yīng)GPU平臺(tái)，該方法采用兩種優(yōu)化策略：數(shù)據(jù)緩存策略可以減少全局內(nèi)存的訪問(wèn)次數(shù)、內(nèi)存動(dòng)態(tài)分配策略用來(lái)改善內(nèi)存的使用狀況和后續(xù)線程的分配。結(jié)果表明，該GPU實(shí)現(xiàn)方案能達(dá)到很好的加速效果。
　　綜上所