GPU加速技術在圖論算法中的應用.pdf

1、圖數(shù)據(jù)是許多計算、科學和工程領域中經(jīng)常采用的數(shù)據(jù)結構,圖操作則是構建這些領域中許多應用的基石。一直以來,設計高效的圖算法就是數(shù)學與計算機科學的重要研究內容。隨著算法理論的成熟,研究人員意識到傳統(tǒng)的串行圖算法幾乎已達到理論上的時間復雜度極限,它們在生物基因工程、Web網(wǎng)絡分析、地理信息系統(tǒng)等新興應用產(chǎn)生的海量數(shù)據(jù)前遭遇到性能瓶頸。開發(fā)并行的圖算法勢在必行。然而,大多數(shù)研究集中在以CPU為處理部件的傳統(tǒng)并行架構上,受到處理器核心數(shù)限制和通信

2、代價方面的挑戰(zhàn)。
　　現(xiàn)代圖形處理器(Graphic Processing Units,GPUs)具有運算核心數(shù)量多、運算能力強、高帶寬的架構優(yōu)勢。近年來,利用GPU進行通用計算(General Purpose Computation on GPU,GPGPU)成為高性能計算領域新的趨勢。目前,GPGPU領域的圖算法研究還處于起步階段,圖算法具有的不規(guī)則訪存性增加了設計的難度。除此之外,也不是所有的圖算法都能夠被有效地并行,比如深

3、度優(yōu)先搜索本質上就是串行的。
　　本文研究和歸納了在CPU和GPU上設計實現(xiàn)并行圖算法的研究現(xiàn)狀,分析了GPU上圖的數(shù)據(jù)表示,開發(fā)了基于統(tǒng)一計算設備架構(Compute Unified Device Architecture,CUDA)的并行算法以用于求解強連通分量(SCC)、最小生成樹(MST)以及每對頂點間的最短路徑(APSP)等三種圖問題。首先,本文實現(xiàn)了基于CUDA的計算SCC的FB算法,在算法中引入了枝剪過程,并考慮到了

4、線程分歧的影響;接下來,設計了一種Kruskal算法和Boruvka算法相結合的混合MST算法,它使用基于CUDA的基數(shù)排序與前綴和Scan原語來劃分子圖、構造子圖結構以及過濾邊,并用Boruvka算法的CUDA實現(xiàn)來求解子圖的最小生成樹森林;然后,受到基于CUDA的單源最短路徑(SSSP)算法的啟發(fā),開發(fā)了一種利用SSSP求解APSP的并行方案,該方案一次求解多個源頂點的SSSP問題,能有效地利用GPU片上的共享內存。
　　最后