GPU加速技術在圖論算法中的應用探討

紀澤宇

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

【關鍵詞】 CUDA 強連通分量 最小生成樹 最短路徑

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

一、GPU同傳統并行計算架構的區別

1.1 同多核CPU的區別研究

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

1.2 同分布式集群的區別

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

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

對于有向圖的強連通分量計算，其是圖論中一個非常基本性的問題，像對復雜產品設計中的耦合任務集進行識別等。若將設計過程中所涉及到的各個人物看做是圖的頂點，然后通過不同任務之間的關系能夠建立一個有向圖，而其中的耦合任務集的識別就變為了對途中的強連通分量進行尋找。在GPU加技術應用之后，設計了一個FB算法，其能夠對非平凡圖的強連通分量進行計算。

2.1 FB算法

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

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

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

2.2 基于CUDA的FB算法

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

然后是算法的主體結構，對于FB算法，其SIMT架構也能夠對頂點的閉包進行計算，通過迭代方式能夠對非平凡的強連通分量進行計算，然后通過核函數起到時的線程分配來實現線程的計算和訪存。

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

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

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

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

對于這一問題，其在當前的網絡和物流等中應用非常頻繁，而對于如何高效的選擇最短路徑一直是科學家關注和研究的熱點問題。在本文中采用了一種基于CUDA的并行算法，其能夠通過對SSSP算法進行多次的重復運行來實現邊權值的非負APSP問題。下面對基于CUDA的SSSP算法進行了簡單的介紹：為了能夠實現這一算法，可以通過壓縮鄰接表對圖中的數據結構進行計算，而在當前的CUDA編程中，采用的是CPU和GPU兩種線程的同步運行，而通過開發multiprocer之間的同步，能夠對全局線程進行有效的同步。為了實現APSP問題，可以通過在每一個頂點上運行上一節的SSSP算法來實現，這種并行方案能夠對GPU的全局內存進行有效的利用。

五、總結

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

參 考 文 獻

[1]王一同.GPU加速技術在圖論算法中的應用[D].電子科技大學，2014.

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

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