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

紀(jì)澤宇

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

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

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

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

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

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

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

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

二、GPU加速計(jì)算有向圖的強(qiáng)連通分量

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

2.1 FB算法

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

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

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

2.2 基于CUDA的FB算法

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

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

三、 GPU加速計(jì)算圖的最小生成樹(shù)

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

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

四、GPU加速計(jì)算圖的最短路徑

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

五、總結(jié)

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

參 考 文 獻(xiàn)

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

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

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