劉令斌，任 龍，黃建強，黃東強

(青海大學(xué)計算機技術(shù)與應(yīng)用系，青海 西寧 810016)

隨著信息技術(shù)的高速發(fā)展，人類迎來了大數(shù)據(jù)時代，導(dǎo)致數(shù)據(jù)規(guī)模急劇增長。近幾年，Twitter的月活躍用戶產(chǎn)生的數(shù)據(jù)占幾百GB甚至TB級別的存儲量[1]，現(xiàn)實生活所產(chǎn)生的規(guī)模龐大的各種類型的數(shù)據(jù)，基本都可以抽象為圖數(shù)據(jù)結(jié)構(gòu)(graph-structured data)[2-3]。然而，傳統(tǒng)的圖計算算法處理大規(guī)模圖數(shù)據(jù)具有很明顯的缺陷，因此，如何高效處理大規(guī)模圖數(shù)據(jù)成為很多研究的重點問題。Ligra是解決此類問題性能最好的圖計算系統(tǒng)之一[4]。Beamer等[5]提出了關(guān)于遍歷方式的優(yōu)化，Ligra使用這種優(yōu)化方式，以 廣度優(yōu)先搜索算法(Breadth First Search，BFS)為例，不同于傳統(tǒng)的 BFS 算法中由源點到底端的遍歷方式，Ligra 通過閾值判斷需要遍歷的點集是否稀疏——如果稀疏則使用 Top-Down 自上而下的方法進行遍歷；如果稠密，則使用 Bottom-Up 自下而上的方法進行遍歷，從而解決負載不均衡的問題[6-7]，能高效地使用多線程并行。同時，在大規(guī)模圖計算領(lǐng)域中，國內(nèi)外學(xué)者通過研究找到了新的優(yōu)化方向[8-12]。Ligra實現(xiàn)了 BFS、單源最短路徑(Single-Source Shortest Path，SSSP)等圖計算算法的優(yōu)化 ，但是支持的圖計算算法仍不全面，存在可拓展的空間。

本文通過對 Ligra 進行拓展，實現(xiàn)深度優(yōu)先搜索算法(Depth First Search，DFS)及子圖匹配算法，用來更好地解決傳統(tǒng)圖計算算法運算速度過慢的問題。

1 圖計算系統(tǒng)的實現(xiàn)

1.1 存儲格式

表1中以圖數(shù)據(jù)soc-Livejournal為例，展示不同格式下數(shù)據(jù)大小及獲取點的出度所需要的時間。其中，ELL(ELLPACK)格式與鄰接矩陣格式需要占用超過50 GB的存儲空間；如果使用COO(Coordinate)格式進行存儲，僅需要0.9 GB的存儲空間；使用CSR(Compressed Sparse Row)格式存儲需要0.5 GB的存儲空間。由此可見，CSR格式與COO格式在存儲圖數(shù)據(jù)方面具有比較明顯的優(yōu)勢。在獲取出度信息時，CSR格式需要的處理時間較少，由此可見， CSR格式的圖數(shù)據(jù)適用于大規(guī)模圖計算算法，故選取CSR格式來存儲圖數(shù)據(jù)。

表1 存儲數(shù)據(jù)大小及處理時間Tab.1 Storage capacity and processing time

1.2 接口的實現(xiàn)

1.2.1 EDGEMAP 接口 EDGEMAP接口具有要處理的圖數(shù)據(jù)G、要遍歷的頂點集合U、1個功能函數(shù)F及判斷某點是否被標(biāo)記的函數(shù)P等4個參數(shù)。以BFS 算法為例，該算法的遍歷過程是按層進行的，在每一層遍歷的時候，需要遍歷的點是對上一層進行處理后得到的未訪問過的點，也就是集合U，對某點是否被訪問過的判斷是通過函數(shù)P實現(xiàn)的，判斷訪問標(biāo)記是否需要修改及修改訪問的標(biāo)記是通過功能函數(shù) F實現(xiàn)的，需要遍歷的邊存儲在圖數(shù)據(jù)G中。同樣的，在Bellman-Ford算法中，U表示當(dāng)前層需要遍歷的點集，G表示需要處理的圖數(shù)據(jù)，函數(shù)P用于判斷某點是否被訪問過，而函數(shù)F的功能發(fā)生了變化。不同于BFS算法中判斷某點的標(biāo)記是否需要被修改與更改訪問標(biāo)記的功能，在Bellman-Ford算法中，函數(shù)F需要實現(xiàn)的功能是判斷某邊的出發(fā)頂點距離源點的最短距離與該邊的權(quán)值之和是否小于該邊的目標(biāo)頂點距離源點的最短距離，并且更改某點與源點之間的最短距離。

EDGEMAP接口的偽代碼如下所示。具體解釋為根據(jù)點集U的密集程度來判斷應(yīng)該使用自上而下的方式還是自下而上的方式進行遍歷，如果點集U中的點數(shù)與各點的出度之和大于圖數(shù)據(jù)的邊數(shù)/20，則使用自下而上的遍歷方式，反之，則使用自上而下的遍歷方式。

Algorithm 1 EDGEMAP1:procedure EDGEMAP(G(V,E),U,F,P)2:if (|U| + sum of out - degrees of U>|E|/20) then3: return EDGEMAPDENSE(G(V,E),U,F,P)4:else5: return EDGEMAPSPARSE(G(V,E),U,F,P)6:end if

1.2.2 EDGEMAPDENSE接口 EDGEMAPDENSE接口的偽代碼如下所示。接口包含要處理的圖數(shù)據(jù)G、要遍歷的頂點集合U、1個功能函數(shù)F及判斷某點是否被訪問的函數(shù)P等4個參數(shù)。EDGEMAPDENSE接口實現(xiàn)了自下而上遍歷的功能。具體思路為遍歷圖數(shù)據(jù)G中所有的點的集合V，每當(dāng)遇到未被訪問過的點時，就遍歷該點的所有入度點，通過函數(shù)P來判斷如果在該點的所有入度點中存在被訪問過的點，則通過函數(shù)F修改該點的標(biāo)記，并將該點記錄到下一層需要訪問的點集中，之后繼續(xù)通過函數(shù)P來尋找下一個未被訪問過的點，直到遍歷完V中全部的點。

Algorithm 2 EDGEMAPDENSE1:procedure EDGEMAPDENSE(G(V,E),U,F,P)2:New={}3:fori ∈ {0,|V| - 1} do4: ifP(i) == -1 then5: forn ∈ getlnDegree(i) do6: ifP(n)! = -1 & F(n,i) == 1 then7: New ←New U {i}8: end if9: ifP(i)! = -1 then10: break11: end if12: end for13: end if 14:end for 15:returnNew

1.2.3 EDGEMAPSPARSE 接口 EDGEMAPSPARSE接口的偽代碼如下所示。接口具有要處理的圖數(shù)據(jù)G、要遍歷的頂點集合U、1個功能函數(shù)F及判斷某點是否被訪問的函數(shù)P等4個參數(shù)。EDGEMAPSPARSE接口實現(xiàn)了自上而下遍歷的功能。具體思路為遍歷點集U中所有點的出度點，通過函數(shù)P來進行判斷，每當(dāng)遇到未被訪問過的點時，則通過函數(shù)F來判斷該點是否符合修改訪問標(biāo)記的要求，如果符合要求，則修改該點的標(biāo)記，并將該點記錄到下一層需要訪問的點集中，反之，則不進行修改與記錄，繼續(xù)遍歷，直到遍歷完點集U中全部點的出度點。

Algorithm 3 EDGEMAPSPARSE1:procedure EDGEMAPSPARSE(G(V,E),U,F,P)2:New={}3:forv ∈ U do4: forn ∈ getOutDegree(v) do5: ifP(n) == -1 & F(v,n) == 1 then6: New ← New U {n}7: end if8: end for9:end for10:returnNew

1.3 解決負載不均衡問題的方法

在圖計算算法運算時，由于圖分布的冪律特性[13]，在逐層遍歷的過程中，需要遍歷的點集規(guī)模會出現(xiàn)先是幾十倍地增長，然后幾十倍地減少現(xiàn)象。這是由于點集中存在少量的頂點出度遠遠大于其他頂點，在運算過程中，這些頂點的存在會給處理該點的線程帶來遠超于其他線程的任務(wù)量，從而造成嚴(yán)重的負載不均衡的問題，在很大程度上降低了圖計算算法的并行效率。

為了解決負載不均衡問題，本研究采用Top-Down與Bottom-Up相結(jié)合的遍歷方式。Top-Down從當(dāng)前層需要遍歷的點集出發(fā)，依次訪問它們的出度點，并將沒有訪問過的出度點加入到新的點集中。Bottom-Up掃描所有沒有訪問過的點，依次遍歷這些點的父節(jié)點，如果存在某個父節(jié)點被訪問過，則將該點加入到新的點集中。Bottom-Up的優(yōu)勢在于具有“提前跳出循環(huán)”的判斷，即只要某點有一個父節(jié)點被訪問過，剩余的父節(jié)點就不需要再進行遍歷，在最優(yōu)的情況下，只需要訪問一個父節(jié)點就可以將該點加入到新的點集中，而算法的復(fù)雜度由O(|E|)降為O(|V|)。而Top-Down不具有這種優(yōu)勢，必須要全部遍歷點所有的出度點。

一般而言，根據(jù)圖分布的冪律特性，在遍歷前幾層的過程中，由于點集中的點相對較少，Top-Down僅需遍歷當(dāng)前點集中的出度點，相對而言具有較高的效率。而到了中間幾層，點集中會出現(xiàn)出度較大的點，Bottom-Up對每一個沒有訪問過的點，只需遍歷其部分父節(jié)點，便可以判斷是否加入到新的點集中，避免出現(xiàn)有的線程任務(wù)量過多的情況，解決了負載不均衡的問題，因而會具有較高的效率。在處理最后幾層時，剩下的大多是度數(shù)較小的點，可以使用Top-Down進行遍歷。

1.4 減少互斥鎖的使用

在并行計算的過程中，會出現(xiàn)多個線程同時訪問并修改某一共享內(nèi)存中的數(shù)據(jù)的情況。以BFS過程為例，當(dāng)線程1訪問s0點時，發(fā)現(xiàn)該點沒有被訪問過，就會將該點加入到新的點集中，并修改s0點的標(biāo)記，但在線程1修改s0點的標(biāo)記之前，線程2可能也正在訪問s0點，那么線程2就會將s0點重復(fù)加入到新的點集中，于是在下一層遍歷時就會產(chǎn)生不必要的任務(wù)，增加算法運行時間。為了避免這種情況的出現(xiàn)，會使用互斥鎖或者原子操作來保證對某一變量的訪問或修改只允許一個線程來進行，當(dāng)一個線程操作結(jié)束后，才允許下一個線程進行相應(yīng)的操作。

相比較于原子操作，互斥鎖具有功能多樣的優(yōu)勢，使用更加靈活，可以自主選擇需要加鎖的區(qū)域。但是，互斥鎖的性能不及原子操作，需要運行的時間更久，而且可能會出現(xiàn)“死鎖”的情況。所以為了減少系統(tǒng)中算法的運行時間，要盡可能地使用原子操作來代替互斥鎖。一般情況下，原子操作可以實現(xiàn)的功能較為單一，所需要的功能要在原有的原子操作的基礎(chǔ)上進行拓展。此處便實現(xiàn)了在原子操作CAS(compare-and-swap)的基礎(chǔ)上，實現(xiàn)了比較并存儲兩者間較小值的原子功能，完成了優(yōu)化。

原子操作的偽代碼如下所示。接口具有地址L、舊值O、新值N等3個參數(shù)。如果L中存儲的值等于O，則將L中的值更改為N，且返回true，否則返回false。而拓展的原子功能便是基于CAS操作實現(xiàn)的，命名為writeMin。writeMin具有地址L、新值N等2個參數(shù)，如果L中存儲的值大于N，則將L中的值更改為N，且返回true，否則返回false。

Algorithm 4 writeMin1:procedure writeMin(*L,N) 2:O ← *L3:r ← false4:whileO>N & !(r = CAS (L,O,N)) do5: O ←*L6:end while7:return r

2 圖計算系統(tǒng)的拓展

2.1 深度優(yōu)先搜索算法

傳統(tǒng)的DFS算法需要輸入圖數(shù)據(jù)G=(V,E)及源點s，定義一個隊列來存儲需要遍歷的點，定義一個數(shù)組來標(biāo)記訪問過的點。首先，將所有點標(biāo)記為未訪問的狀態(tài)，遍歷s所能到達的所有頂點，并存入隊列中，將s的標(biāo)記改為已訪問；然后取出隊列末尾元素s1，如果s1未被訪問過，則將s1所能到達的所有頂點存入隊列中，并將s1的標(biāo)記改為已訪問。直到找到問題解或者隊列為空，結(jié)束搜索。

與傳統(tǒng)的遍歷方式不同，對Ligra圖計算系統(tǒng)拓展后實現(xiàn)的DFS算法，采用分塊遍歷的方法來盡可能地提高遍歷效率。首先，將源點的出度點按照線程數(shù)分塊，使得每一個線程處理的任務(wù)量盡可能相同，各線程并行進行搜索，從而提高運算效率；然后在遍歷的過程中，對隊列中的任務(wù)量進行判斷，如果某個線程中的任務(wù)量超過閾值，則將該線程的任務(wù)進行平分，由兩個線程來共同完成，直到各個線程的任務(wù)量小于或等于閾值。需要使用#pragmaomptask將任務(wù)加入到新的線程中，從而完成任務(wù)調(diào)度。通過分塊遍歷的方式來實現(xiàn)搜索，不僅較好地解決了負載不均衡的問題，而且能提高運算效率。

2.2 子圖匹配算法

子圖匹配算法是在深度優(yōu)先搜索算法的基礎(chǔ)上，對點的映射進行判斷的圖計算算法。該算法用于找出目標(biāo)圖中的點與子圖中點的映射關(guān)系。算法需要輸入子圖g=(v,e)及目標(biāo)圖G=(V,E)。首先，獲取子圖中每一個點的特征，如入度、出度、關(guān)聯(lián)點，以及該點是關(guān)聯(lián)點的入度點還是出度點等信息；目標(biāo)圖中的每一個點也需要獲取特征：入度、出度、入度點、出度點等信息。然后由目標(biāo)圖的0點開始，依次遍歷，找到一個與子圖0點相匹配的點。假設(shè)目標(biāo)圖中a點與0點相匹配，子圖中1點作為0點的出度點，則遍歷目標(biāo)圖中a點的所有出度點，找到一個與子圖中1點相匹配的點。重復(fù)這個過程，直到子圖中所有的點都找到匹配的點或者目標(biāo)圖遍歷完畢，沒有找到解。

對Ligra圖計算系統(tǒng)進行拓展，實現(xiàn)了子圖匹配算法。首先，對子圖中每一個點的特征信息進行提取，之后對目標(biāo)圖中的點依次處理，直到找到第一個與子圖0點相匹配的點；然后，找到子圖中將0點作為關(guān)聯(lián)點的1點。如果0點作為1點的出度點，則通過分塊遍歷的方式，使用多線程對目標(biāo)圖中與0點相匹配的點的出度點進行并行處理，并將相匹配的點加入到隊列中，找到完全匹配的一組點后，令多余點出隊列，繼續(xù)匹配所有的可能性，直到達到處理目的或者完成目標(biāo)圖的遍歷。

3 實驗結(jié)果與性能分析

3.1 實驗數(shù)據(jù)

實驗所選取的測試數(shù)據(jù)均為真實的圖數(shù)據(jù)。soc-livejournal[14]、twitter7[15]和high-twitter[16]是真實的社交網(wǎng)絡(luò)，其中soc-livejournal包含484萬個頂點和6 899萬條有向邊，twitter7包含4 165萬個頂點和14.7億條有向邊，high-twitter包含45萬個頂點和1 485萬條有向邊;uk-2002代表網(wǎng)頁間的超鏈接，包含1 852萬個頂點和2.98億條有向邊。圖數(shù)據(jù)規(guī)模如表2所示，表格中記錄了每一個數(shù)據(jù)集的點數(shù)(用|V|表示)、邊數(shù)(用|E|表示)及數(shù)據(jù)大小。

表2 數(shù)據(jù)規(guī)模Tab.2 Data scales

3.2 性能對比

表3的數(shù)據(jù)是測試high-twitter圖得到的結(jié)果(包括用傳統(tǒng)的圖計算算法和基于圖計算系統(tǒng)實現(xiàn)的圖算法處理圖數(shù)據(jù)得到的結(jié)果)。其中，Serial行中的“—”表示1 800 s內(nèi)仍未處理完畢，解決SSSP問題的Bellman_Ford算法的時間復(fù)雜度為O(V·E)，幾乎無法應(yīng)用于處理大規(guī)模的圖數(shù)據(jù)，子圖匹配算法是在目標(biāo)圖中找到100 000 00組不重復(fù)的子圖所需要的時間。性能加速比是以傳統(tǒng)圖計算算法的處理時間為基準(zhǔn)，來除以圖計算系統(tǒng)的處理時間得到的數(shù)值。由表3中性能加速比的數(shù)值可以看出，圖計算系統(tǒng)的處理速度遠高于傳統(tǒng)的圖計算算法。這是由于圖計算系統(tǒng)能夠更好地利用多核資源，并且通過自下而上與自上而下相結(jié)合的遍歷方式，解決了并行過程中負載不均衡的問題，使得圖計算系統(tǒng)的性能得以提高。

表3 high-twitter 處理時間Tab.3 Processing time of high-twitter

對于其他大規(guī)模圖數(shù)據(jù)的處理結(jié)果如表4所示。在處理超過900 MB的圖數(shù)據(jù)時，傳統(tǒng)的圖計算算法已經(jīng)無法在1 800 s內(nèi)完成計算。而基于圖計算系統(tǒng)實現(xiàn)的圖算法依然可以快速地處理大規(guī)模圖數(shù)據(jù)，更好地滿足人們的需求。

表4 其他數(shù)據(jù)集處理時間Tab.4 Processing time of other datasets

3.3 CPU利用率

表5為每一個程序在運行時CPU的有效利用率。因為傳統(tǒng)的圖計算算法都是串行算法，僅使用主線程來完成計算，所以CPU利用率很低。而基于圖計算系統(tǒng)實現(xiàn)的圖算法為并行算法，能充分地利用多線程資源來完成計算，并且通過合理的遍歷方式減少了負載不均衡問題的影響，使得CPU利用率得到提升。

表5 CPU利用率Tab.5 CPU utilization %

圖1為處理high-twitter圖數(shù)據(jù)時的CPU利用率。從圖1可以發(fā)現(xiàn)，基于圖計算系統(tǒng)的圖算法的CPU利用率仍然不是特別高，這是因為大部分的圖計算算法具有不規(guī)則性：圖中各個點的度數(shù)極度不規(guī)則，導(dǎo)致負載不規(guī)則，使得硬件效率低；圖遍歷依賴于圖結(jié)構(gòu)，導(dǎo)致遍歷不規(guī)則，使得cache命中率較低；更新依賴于上一層遍歷結(jié)果，導(dǎo)致更新不規(guī)則，使得圖計算更加復(fù)雜。這是目前圖算法問題中亟待解決的難題，也是未來努力的方向。

圖1 high-twitter CPU 利用率Fig.1 CPU utilization of high-twitter

4 討論與結(jié)論

本文從傳統(tǒng)的圖計算算法存在的劣勢切入，通過優(yōu)化圖算法來高效地處理大規(guī)模圖數(shù)據(jù)。與Shun等[4]實現(xiàn)的圖算法不同，本文拓展了DFS 算法及子圖匹配算法。在優(yōu)化圖計算的遍歷方式時，與Beamer等[5]提出的自上而下與自下而上的混合方式不同，加入CSC格式來簡化圖數(shù)據(jù)的訪問。同時，還拓展原子操作來代替互斥鎖，使得并行計算的運算速度得到提升。算法中，圖數(shù)據(jù)存儲為CSR格式，無法將需要遍歷的邊數(shù)據(jù)全部存儲到cache中，如果能進一步壓縮圖數(shù)據(jù)，使其可以存儲到cache中，則可以提高算法性能。在以后的研究中，可以嘗試使用位圖或者分塊等方法，對圖數(shù)據(jù)的存儲方式進行優(yōu)化，從而進一步優(yōu)化圖算法。