GPU加速技術(shù)在圖論算法中的應(yīng)用.pdf

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

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

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

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