面向圖計(jì)算內(nèi)存系統(tǒng)的實(shí)現(xiàn)與拓展

劉令斌，任 龍，黃建強(qiáng)，黃東強(qiáng)

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

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

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

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

1.1 存儲(chǔ)格式

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

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

1.2 接口的實(shí)現(xiàn)

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

EDGEMAP接口的偽代碼如下所示。具體解釋為根據(jù)點(diǎn)集U的密集程度來(lái)判斷應(yīng)該使用自上而下的方式還是自下而上的方式進(jìn)行遍歷，如果點(diǎn)集U中的點(diǎn)數(shù)與各點(diǎn)的出度之和大于圖數(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、要遍歷的頂點(diǎn)集合U、1個(gè)功能函數(shù)F及判斷某點(diǎn)是否被訪問(wèn)的函數(shù)P等4個(gè)參數(shù)。EDGEMAPDENSE接口實(shí)現(xiàn)了自下而上遍歷的功能。具體思路為遍歷圖數(shù)據(jù)G中所有的點(diǎn)的集合V，每當(dāng)遇到未被訪問(wèn)過(guò)的點(diǎn)時(shí)，就遍歷該點(diǎn)的所有入度點(diǎn)，通過(guò)函數(shù)P來(lái)判斷如果在該點(diǎn)的所有入度點(diǎn)中存在被訪問(wèn)過(guò)的點(diǎn)，則通過(guò)函數(shù)F修改該點(diǎn)的標(biāo)記，并將該點(diǎn)記錄到下一層需要訪問(wèn)的點(diǎn)集中，之后繼續(xù)通過(guò)函數(shù)P來(lái)尋找下一個(gè)未被訪問(wèn)過(guò)的點(diǎn)，直到遍歷完V中全部的點(diǎn)。

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、要遍歷的頂點(diǎn)集合U、1個(gè)功能函數(shù)F及判斷某點(diǎn)是否被訪問(wèn)的函數(shù)P等4個(gè)參數(shù)。EDGEMAPSPARSE接口實(shí)現(xiàn)了自上而下遍歷的功能。具體思路為遍歷點(diǎn)集U中所有點(diǎn)的出度點(diǎn)，通過(guò)函數(shù)P來(lái)進(jìn)行判斷，每當(dāng)遇到未被訪問(wèn)過(guò)的點(diǎn)時(shí)，則通過(guò)函數(shù)F來(lái)判斷該點(diǎn)是否符合修改訪問(wèn)標(biāo)記的要求，如果符合要求，則修改該點(diǎn)的標(biāo)記，并將該點(diǎn)記錄到下一層需要訪問(wèn)的點(diǎn)集中，反之，則不進(jìn)行修改與記錄，繼續(xù)遍歷，直到遍歷完點(diǎn)集U中全部點(diǎn)的出度點(diǎn)。

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 解決負(fù)載不均衡問(wèn)題的方法

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

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

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

1.4 減少互斥鎖的使用

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

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

原子操作的偽代碼如下所示。接口具有地址L、舊值O、新值N等3個(gè)參數(shù)。如果L中存儲(chǔ)的值等于O，則將L中的值更改為N，且返回true，否則返回false。而拓展的原子功能便是基于CAS操作實(shí)現(xiàn)的，命名為writeMin。writeMin具有地址L、新值N等2個(gè)參數(shù)，如果L中存儲(chǔ)的值大于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 圖計(jì)算系統(tǒng)的拓展

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

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

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

2.2 子圖匹配算法

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

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

3 實(shí)驗(yàn)結(jié)果與性能分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

3.2 性能對(duì)比

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

表3 high-twitter 處理時(shí)間Tab.3 Processing time of high-twitter

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

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

3.3 CPU利用率

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

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

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

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

4 討論與結(jié)論

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