紀(jì)澤宇

【摘要】 對于圖數(shù)據(jù)來說，其是當(dāng)前很多學(xué)科的基礎(chǔ)理論，特別是對于數(shù)學(xué)和計算機學(xué)科，如何實現(xiàn)圖算法的計算效率是最主要的研究內(nèi)容之一，伴隨著算法的成熟，傳統(tǒng)的圖算法已經(jīng)無法滿足發(fā)展需要，為此，人們逐漸開始進(jìn)行并行圖算法的研究。但由于傳統(tǒng)的CPU對數(shù)據(jù)處理受到限制，研究人員逐漸引進(jìn)了新型的GPU運算處理器，其具有運算核心數(shù)量多和能力強等優(yōu)點，隨著對GPU研究的增多，GPU領(lǐng)域的圖算法發(fā)展也得到了有效的提高。本文對當(dāng)前的GPU加速技術(shù)在圖論算法中的應(yīng)用進(jìn)行了簡單的介紹。

【關(guān)鍵詞】 CUDA 強連通分量 最小生成樹 最短路徑

隨著信息時代的發(fā)展，數(shù)據(jù)總量也在逐漸增加，這使得人們對高性能的計算能力迫切需要，像基因序列的分析以及天氣預(yù)報等，但傳統(tǒng)的CPU單核計算已經(jīng)無法滿足人們工作的需要，為此，開發(fā)多核計算工具和并行算法是當(dāng)前信息技術(shù)發(fā)展的重要需求。這種情況下，圖算法作為圖論的核心內(nèi)容，逐漸被人們關(guān)注，其能夠通過海量的圖結(jié)構(gòu)數(shù)據(jù)進(jìn)行有效的分析，但由于其算法的不規(guī)則訪存特性使其設(shè)計難度不斷增加。為此，本文對如何實現(xiàn)圖算法的加速進(jìn)行了簡單的介紹，通過GPU加速技術(shù)的應(yīng)用能夠使圖算法的應(yīng)用成為現(xiàn)實。

一、GPU同傳統(tǒng)并行計算架構(gòu)的區(qū)別

1.1 同多核CPU的區(qū)別研究

對于CPU，其應(yīng)用目的對其體系是一種嚴(yán)重的限制，在CPU芯片上，大部分的電路都是用作邏輯控制或者緩存，這導(dǎo)致計算單元的晶體管數(shù)量非常少。通過大量的研究可以發(fā)現(xiàn)，對于GPU來說，其在應(yīng)用的過程中，并行指令的數(shù)量非常少，但CPU卻大部分采用的是長指令字等指令級的并行技術(shù)，這種技術(shù)使其架構(gòu)和GPU之間存在著本質(zhì)上的區(qū)別。此外，設(shè)計目的也存在著較大的差別，對于CPU，其主要是實現(xiàn)ALU指令的獲取和執(zhí)行，因此，邏輯控制電路等數(shù)量較大，但對于GPU來說，其主要是為了提高自身的計算能力，其更加注重的是對數(shù)據(jù)的吞吐效率，因此，對于邏輯控制設(shè)計相對較為簡單。

1.2 同分布式集群的區(qū)別

對于GPU和集群之間的區(qū)別，其主要分為兩個方面：首先是在計算方式上，對于集群，其采用的是主從模式，這種計算方式采用的是分割計算，通過Slave的計算和Master的集合和處理功能對數(shù)據(jù)進(jìn)行計算。對于GPU來說，其通用計算和集群的模式相似，但GPU是Slave。然后是通信方式之間的區(qū)別，對于集群，其通信主要是通過局域網(wǎng)或者互聯(lián)網(wǎng)等，這種算法在計算時需要對傳輸?shù)募?xì)節(jié)進(jìn)行重點的考慮，防止設(shè)計方面出現(xiàn)傳輸限制。而對于GPU芯片而言，其采用的是PCI-E接口進(jìn)行數(shù)據(jù)等的傳輸，因此，其僅僅需要考慮的是如何對計算內(nèi)容進(jìn)行分配以及哪一部分的CPU具有什么樣的特性等。

二、GPU加速計算有向圖的強連通分量

對于有向圖的強連通分量計算，其是圖論中一個非?；拘缘膯栴}，像對復(fù)雜產(chǎn)品設(shè)計中的耦合任務(wù)集進(jìn)行識別等。若將設(shè)計過程中所涉及到的各個人物看做是圖的頂點，然后通過不同任務(wù)之間的關(guān)系能夠建立一個有向圖，而其中的耦合任務(wù)集的識別就變?yōu)榱藢ν局械膹娺B通分量進(jìn)行尋找。在GPU加技術(shù)應(yīng)用之后，設(shè)計了一個FB算法，其能夠?qū)Ψ瞧椒矆D的強連通分量進(jìn)行計算。

2.1 FB算法

對于FB算法，其在計算過程中不是依靠DFS為子的一種算法，而是通過分配模式將不同的子問題分配到各個單元中對其進(jìn)行處理，而對于每個子問題，其都是通過頂點的可達(dá)性來進(jìn)行分析，因此，F(xiàn)B算法具有較強的并行化能力。對于FB算法，其需要對下面兩個引理進(jìn)行重點的觀察：

給定有向圖G=（V，E），v？V，那么對于任何不包含v的強連通分量，其一定是FWD（G，v）BWD（G，v）和Rem（G，v）三個和集中的一個。

通過這兩個理論可以得知，對于FB算法，其具體的計算過程是：首先選擇一個頂點，然后對其前閉包和后閉包進(jìn)行計算，兩個集合之間的交集就是強連通分量值。然后通過剩余的頂點對原圖進(jìn)行3個子集的劃分，并通過迭代計算對三個子圖進(jìn)行重復(fù)性的上述計算過程，這樣就能夠?qū)崿F(xiàn)子圖的并行處理計算。

2.2 基于CUDA的FB算法

首先是GPU中的圖存儲，對于當(dāng)前的圖算法，其采用的都是鄰接表或者鄰接矩陣，對于G=（V，E），其采用鄰接表來對其進(jìn)行表示，定義數(shù)組Adj代表|V|，其包含了滿足（v，u）∈E的全部頂點，然后通過|V|×|V|來對矩陣進(jìn)行表示，通過鄰接表對無向圖進(jìn)行表示時，其大小為2|E|，而有向圖的表達(dá)則是|E|。而采用鄰接矩陣進(jìn)行表示時，其空間需求都是O（V2）。而在通過GPU技術(shù)進(jìn)行圖數(shù)據(jù)的存儲時，需要對下面幾點內(nèi)容進(jìn)行考慮：首先，同現(xiàn)代的傳統(tǒng)CPU主機系統(tǒng)相比，GPU的系統(tǒng)內(nèi)存相對較小，然后是CUDA的模型，其采用的是一種CPU-GPU的異構(gòu)模型，這種模型在進(jìn)行數(shù)據(jù)的傳輸時同傳統(tǒng)的計算機不同，最后則是對于CUDA的存儲系統(tǒng)，其內(nèi)存和主存兩者之間選擇不同的地址空間，因此，在進(jìn)行指針數(shù)據(jù)的操作時較為困難，且設(shè)備的內(nèi)存采用的是線性內(nèi)存，這種存儲方式更加適合數(shù)組形式的數(shù)據(jù)結(jié)構(gòu)存取。

然后是算法的主體結(jié)構(gòu)，對于FB算法，其SIMT架構(gòu)也能夠?qū)旤c的閉包進(jìn)行計算，通過迭代方式能夠?qū)Ψ瞧椒驳膹娺B通分量進(jìn)行計算，然后通過核函數(shù)起到時的線程分配來實現(xiàn)線程的計算和訪存。

三、 GPU加速計算圖的最小生成樹

加入G的一個子圖包含了G的全部頂點，那么就將其稱為G的生成樹。對于生成樹中的各邊權(quán)，將其綜合定義為G的耗費，由于不同的子圖生成的生成樹具有不同的耗費，而其中耗費最小的就是最小生成樹。下面對CUDA模式下的最小生成樹進(jìn)行了簡單的介紹。

為了能夠更好的對圖的數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理，同時節(jié)省存儲空間，在對生成樹進(jìn)行計算時，往往采用的是兩種圖的數(shù)據(jù)結(jié)構(gòu)，下面的（a）和（b）兩種不同的結(jié)構(gòu)構(gòu)成了兩種不同的計算方法，其中，（a）可以將所有的邊都看做是沒有方向的，然后通過（S，E，W）來對其進(jìn)行表示，而對于（b）來說，其采用的是壓縮鄰接表而對方法，將每一條邊看做是方向完全相反的兩條邊對其進(jìn)行表示，采用的是（E，W）元組。而對于VP，其中存放的則是索引位置，而W數(shù)組的使用是為了對邊的權(quán)值進(jìn)行存儲。

四、GPU加速計算圖的最短路徑

對于這一問題，其在當(dāng)前的網(wǎng)絡(luò)和物流等中應(yīng)用非常頻繁，而對于如何高效的選擇最短路徑一直是科學(xué)家關(guān)注和研究的熱點問題。在本文中采用了一種基于CUDA的并行算法，其能夠通過對SSSP算法進(jìn)行多次的重復(fù)運行來實現(xiàn)邊權(quán)值的非負(fù)APSP問題。下面對基于CUDA的SSSP算法進(jìn)行了簡單的介紹：為了能夠?qū)崿F(xiàn)這一算法，可以通過壓縮鄰接表對圖中的數(shù)據(jù)結(jié)構(gòu)進(jìn)行計算，而在當(dāng)前的CUDA編程中，采用的是CPU和GPU兩種線程的同步運行，而通過開發(fā)multiprocer之間的同步，能夠?qū)θ志€程進(jìn)行有效的同步。為了實現(xiàn)APSP問題，可以通過在每一個頂點上運行上一節(jié)的SSSP算法來實現(xiàn)，這種并行方案能夠?qū)PU的全局內(nèi)存進(jìn)行有效的利用。

五、總結(jié)

伴隨著GPU計算能力的不斷發(fā)展，其在各個領(lǐng)域中的應(yīng)用和計算能力也將得到有效的提高，對比與傳統(tǒng)的CPU和集群算法，GPU具有成本低和功耗少等優(yōu)點，在未來的圖論算法中，GPU加速技術(shù)應(yīng)用將越來越廣泛。

參 考 文 獻(xiàn)

[1]王一同.GPU加速技術(shù)在圖論算法中的應(yīng)用[D].電子科技大學(xué)，2014.

[2]郭紹忠，王偉，周剛，胡艷.基于GPU的單源最短路徑算法設(shè)計與實現(xiàn)[J].計算機工程，2012，02：42-44.

[3]郭紹忠，王偉，王磊.基于GPU的并行最小生成樹算法的設(shè)計與實現(xiàn)[J].計算機應(yīng)用研究，2011，05：1682-1684+1702.