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

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

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

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

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

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

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