面向大規(guī)模圖計(jì)算的連通分量算法分析與優(yōu)化*

白 皓，甘新標(biāo)，楊文祥,賈孟涵，涂旭平，張一鳴，郭 敏，來 樂，張 意，朱春平

(1.國防科技大學(xué)計(jì)算機(jī)學(xué)院,湖南 長沙 410073;2.中國空氣動(dòng)力研究與發(fā)展中心計(jì)算空氣動(dòng)力研究所，四川 綿陽 621000;3.黃岡師范學(xué)院計(jì)算機(jī)學(xué)院,湖北 黃岡 438000;4.中國人民解放軍66061部隊(duì),北京 100144)

1 引言

圖作為一種常見的數(shù)據(jù)結(jié)構(gòu)，可以用來抽象表達(dá)現(xiàn)實(shí)事物間各種復(fù)雜的關(guān)聯(lián)關(guān)系[1]。例如，社交網(wǎng)絡(luò)、萬維網(wǎng)等可以采用圖表示。近年來，圖數(shù)據(jù)的規(guī)模不斷增長，根據(jù)相關(guān)報(bào)告顯示，2021年第一季度，F(xiàn)acebook每月活躍用戶為2.85億[2]，騰訊WeChat月活躍用戶達(dá)到1.24億[3]，把用戶和其之間的關(guān)系抽象為圖中的節(jié)點(diǎn)和邊，那么圖中節(jié)點(diǎn)的規(guī)模達(dá)到了數(shù)十億，邊的規(guī)模更是達(dá)到了數(shù)千億。圖計(jì)算是針對圖數(shù)據(jù)進(jìn)行處理和計(jì)算，在現(xiàn)實(shí)生活的諸多場景中都發(fā)揮著重要作用。

從圖中某一節(jié)點(diǎn)出發(fā)訪遍圖中其余節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)僅被訪問一次，這一過程叫做圖的遍歷。無向圖的連通分量，也叫極大連通子圖，指的是每對節(jié)點(diǎn)都能通過通路來互相連通的子圖。連通分量算法通過某種方式來求解圖中的連通分量，可以應(yīng)用于可達(dá)性查詢、一致性檢測等眾多場景，通常是大規(guī)模圖處理的重要步驟[4]。對連通圖進(jìn)行遍歷過程中所經(jīng)過的邊和節(jié)點(diǎn)的組合稱為生成樹。非連通圖可分解為多個(gè)連通分量，而每個(gè)連通分量又各自對應(yīng)至少一棵生成樹，面向超級(jí)計(jì)算機(jī)的大規(guī)模圖計(jì)算Graph500[5]測試的目的就是通過大規(guī)模圖計(jì)算遍歷找到一棵最小生成樹。

如果在連通分量上進(jìn)行遍歷運(yùn)算，得到對應(yīng)于該連通分量的生成樹，就是極大連通子圖的極小連通子圖，這樣，只需要在每個(gè)連通分量中選定一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)就可以把整個(gè)連通分量遍歷完，連通分量中的其他節(jié)點(diǎn)不需要再做遍歷算法根節(jié)點(diǎn)的嘗試，可見依靠連通分量可以幫助減少一些不必要的遍歷開銷。在并行計(jì)算環(huán)境下，在點(diǎn)劃分時(shí)把同一個(gè)連通分量中的節(jié)點(diǎn)劃分到邏輯中相近的物理節(jié)點(diǎn)上，可以實(shí)現(xiàn)負(fù)載均衡，降低通信開銷，加快生成樹的生成。因此，求解非連通無向圖的連通分量成為了加速大規(guī)模圖遍歷的重要方法。

在單處理器上，Hopcroft等人[6]使用深度優(yōu)先搜索DFS(Depth First Search)來求解連通分量，其時(shí)間復(fù)雜度為O(m+n)，m和n分別是圖中邊和節(jié)點(diǎn)的數(shù)量。然而這種方法很難并行實(shí)現(xiàn)[7]。Hirschberg等人[8 - 10]分別用不同數(shù)量級(jí)的處理器實(shí)現(xiàn)了O(log2n)的時(shí)間復(fù)雜度。van Scoy等人[11,12]分別提出了時(shí)間復(fù)雜度為O(n)的并行處理方法。Chen等人[13]提出了一種基于k步上近似的粗糙集算法來求解連通分量，進(jìn)一步優(yōu)化了性能。Pedroche等人[14]利用RCM(Reverse Cuthill-McKee)方法實(shí)現(xiàn)了時(shí)間復(fù)雜度為O(m+n)的算法。Kofman等人[15]在特定條件下在基于集合的無向圖中實(shí)現(xiàn)了常數(shù)級(jí)的計(jì)算開銷。孫斌[16]對串行算法和多個(gè)典型的并行算法進(jìn)行了比較。Zhang等人[17]提出了性能和擴(kuò)展性較好的FastSV(Fast Shiloach-Vishkin)算法。Liu等人[18]在PRAM(Parameter Random Access Memory)上實(shí)現(xiàn)了時(shí)間復(fù)雜度為O(logd+log logm/nn)的算法，其中，最大連通分量直徑為d，這為在超算平臺(tái)上運(yùn)行連通分量算法提供了借鑒。Bentert等人[19]基于無線傳感器網(wǎng)絡(luò)對連通分量算法進(jìn)行了討論。Durgut等人[20]則利用連通分量算法對求解網(wǎng)絡(luò)通信中圖的破裂程度進(jìn)行了優(yōu)化。上述研究將連通分量算法應(yīng)用于網(wǎng)絡(luò)通信，把網(wǎng)絡(luò)問題抽象為尋找生成樹或最短路徑問題，根本目的是為了減少不必要的訪問，實(shí)現(xiàn)系統(tǒng)的最低能耗。

無向圖連通分量的基礎(chǔ)方法主要有3種:BFS(Breadth First Search)、DFS和并查集算法(Union-Find Algorithm)[21,22]。前兩者都是遍歷算法，通過遍歷圖中所有的節(jié)點(diǎn),得到獨(dú)立的子圖,即連通分量。并查集算法是通過指定某一連通分量中的唯一根節(jié)點(diǎn)，然后不斷添加新的連通信息，從而找到連通分量。

本文圍繞連通分量算法，著重研究了算法和數(shù)據(jù)結(jié)構(gòu)的性能等問題，主要有以下貢獻(xiàn)：

(1)對并查集算法和數(shù)據(jù)結(jié)構(gòu)進(jìn)行配合度分析，提出捷徑向量算法。

(2)單線程與多線程相結(jié)合，利用迭代輪轉(zhuǎn)對算法進(jìn)行并行優(yōu)化。

(3)全面分析比較了BFS、DFS和并查集算法對無向圖連通分量算法的實(shí)現(xiàn)性能和應(yīng)用場景。

2 連通分量算法

廣度優(yōu)先搜索、深度優(yōu)先搜索和并查集算法都可實(shí)現(xiàn)無向圖連通分量算法，其中廣度優(yōu)先搜索和深度優(yōu)先搜索都是利用遍歷的思想對所有相連的節(jié)點(diǎn)進(jìn)行搜索訪問，當(dāng)以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，其算法復(fù)雜度均為O(n2)。并查集算法是通過合并具有等價(jià)關(guān)系的節(jié)點(diǎn)對(即一條邊)，來找到所有的連通分量，其傳統(tǒng)方法實(shí)現(xiàn)的時(shí)間復(fù)雜度是O(fu)，其中f是下文中Find的次數(shù)，u是Union的次數(shù)。

2.1 用遍歷算法尋找連通分量

BFS算法初始時(shí)把所有節(jié)點(diǎn)都加載到內(nèi)存，并遍歷這些節(jié)點(diǎn)，每訪問到一個(gè)節(jié)點(diǎn)，如果其未被訪問過，就以其為根節(jié)點(diǎn)執(zhí)行BFS算法，這樣每次執(zhí)行BFS算法都會(huì)得到一個(gè)連通分量。

DFS算法與之類似，所不同的是遍歷過程采用的是DFS算法。

2.2 用并查集算法尋找連通分量

并查集算法在初始狀態(tài)時(shí)，每個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)均設(shè)置為自身，建立指向自身的指針，自成一棵樹，如圖 1所示。在掃描邊進(jìn)行迭代的過程中，如果2個(gè)節(jié)點(diǎn)的指針未指向同一個(gè)節(jié)點(diǎn)，則改變指針，將2個(gè)節(jié)點(diǎn)置于同一棵樹中。

Figure 1 Initial state of Union-Find Algorithm圖1 并查集算法初始狀態(tài)

該算法主要有2個(gè)基本數(shù)據(jù)操作：(1)查找(Find)：確定節(jié)點(diǎn)屬于哪一棵樹，用來確定2個(gè)節(jié)點(diǎn)是否處于同一棵樹，如圖 2所示，雙箭頭表示掃描到的邊，黑色連接線表示在樹中節(jié)點(diǎn)的父子關(guān)系，虛線箭頭表示尋找根節(jié)點(diǎn)的過程。(2)合并(Union)：如果一條邊的2個(gè)節(jié)點(diǎn)不屬于同一棵樹，則將2個(gè)節(jié)點(diǎn)合并到一棵樹中，如圖 3所示。

Figure 2 Operation of finding root node圖2 查找根節(jié)點(diǎn)操作

Figure 3 Operation of unioning tree圖3 合并樹操作

利用并查集實(shí)現(xiàn)的連通分量算法如算法1所示。

算法1利用并查集算法實(shí)現(xiàn)的連通分量算法

Input:edge.bin.//輸入邊數(shù)據(jù)集

Output:connectedcomponent.//輸出連通分量

initialization;//初始化

functionfind(x);//定義find子函數(shù)

whileeinedge.bindo//遍歷邊數(shù)據(jù)集

//把出現(xiàn)的節(jié)點(diǎn)放入節(jié)點(diǎn)集合

vertexset.insert(e.v1);

vertexset.insert(e.v2);

end

whileeinedge.bindo//遍歷邊數(shù)據(jù)集

//尋找2個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)

xroot=find(e.v1);

yroot=find(e.v2);

/*如果2個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)不相同，則把一個(gè)的根節(jié)點(diǎn)置為另一個(gè)的子節(jié)點(diǎn)*/

ifxroot!=yrootthen

xroot.parent=yroot;

end

end

//輸出連通分量

forvinvertexsetdo

ifson[v].size!=0then

output(connectedcomponent);

end

end

算法中，edge.bin表示從Graph500中生成的二進(jìn)制邊數(shù)據(jù)集，connectedcomponent指的是每個(gè)連通分量的基本信息，如包含的節(jié)點(diǎn)、邊等，e是每次從數(shù)據(jù)集中讀取的包含邊信息的結(jié)構(gòu)體，v1/v2表示構(gòu)成邊的2個(gè)節(jié)點(diǎn)，insert()就是節(jié)點(diǎn)載入內(nèi)存的過程,find()用來查找節(jié)點(diǎn)的根節(jié)點(diǎn)，parent表示節(jié)點(diǎn)的父節(jié)點(diǎn)，son[v]表示以v節(jié)點(diǎn)為根節(jié)點(diǎn)的所有節(jié)點(diǎn)。

3 捷徑向量算法

3.1 串行捷徑向量算法

傳統(tǒng)的并查集算法創(chuàng)建的樹可能會(huì)不平衡，其優(yōu)化算法主要有2種，第1種是“按秩合并”，把深度較小的樹(即秩較小的樹)連接到更大的樹上，從而增加樹的平衡性，如圖 4所示。第2種是“捷徑”(Shortcutting)，讓節(jié)點(diǎn)從指向父節(jié)點(diǎn)改成直接指向根節(jié)點(diǎn)，減小樹的層級(jí)，如圖 5所示。這2種方法避免了過多的find(·)函數(shù)的遞歸次數(shù)，在Graph500生成的節(jié)點(diǎn)規(guī)模為240數(shù)據(jù)集的條件下，每次遞歸都需要開辟資源來完成子函數(shù)的初始化，這無疑是巨大的開銷，因此這2種優(yōu)化是十分有必要的。這2種優(yōu)化算法的時(shí)間復(fù)雜度均是O(kα(k,n)),其中，k表示合并查找的操作次數(shù)，n為節(jié)點(diǎn)數(shù)量，α(k,n)為反Ackermann函數(shù)[23 - 25]。

Figure 4 Union by rank圖4 按秩合并

Figure 5 Shortcutting圖5 捷徑操作

雖然2個(gè)優(yōu)化算法的時(shí)間復(fù)雜度一樣，但如果結(jié)合數(shù)據(jù)結(jié)構(gòu)考慮，性能會(huì)有差異。為了更好地結(jié)合算法和數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢，本文提出了捷徑向量算法。

并查集算法需要建立一個(gè)數(shù)組來存儲(chǔ)節(jié)點(diǎn)的根節(jié)點(diǎn)。此外，每棵樹的根節(jié)點(diǎn)需要存儲(chǔ)所有子節(jié)點(diǎn)即以自己為根的所有節(jié)點(diǎn)的信息，這就需要建立一個(gè)二維的數(shù)據(jù)結(jié)構(gòu)，由于涉及節(jié)點(diǎn)的按下標(biāo)隨機(jī)訪問，第1維采用向量。對第2維，集合具有排序和去重的開銷，而算法的實(shí)現(xiàn)細(xì)節(jié)中并不需要這樣的功能，故本文不考慮使用集合來實(shí)現(xiàn)。對比向量和鏈表的特點(diǎn)，向量的構(gòu)造函數(shù)會(huì)把每個(gè)元素初始化一遍，訪問時(shí)Cache的命中率較高，賦值和訪問速度極快，插入則相對較慢，本文根據(jù)數(shù)據(jù)規(guī)模能夠預(yù)估一些用向量表示的變量的大小，也避免了在向量插入過程中的擴(kuò)大容量、拷貝內(nèi)存和釋放原有內(nèi)存的操作。而鏈表雖然在按秩合并算法中只改變2個(gè)節(jié)點(diǎn)的指針，但其缺點(diǎn)也是比較明顯的，一是遍歷時(shí)需要用迭代器，訪問迭代器需要進(jìn)行迭代器越位、有效性、是否指向同一容器等方面的判斷，開銷較大；二是插入時(shí)需要改變指針，而向量在插入時(shí)雖然需要多次擴(kuò)容，但這種開銷對整體算法的加速是值得的。

從數(shù)據(jù)結(jié)構(gòu)與算法結(jié)合來看，使用捷徑向量算法時(shí)，需要把一棵樹中所有節(jié)點(diǎn)的根節(jié)點(diǎn)都改換成另一棵樹的根節(jié)點(diǎn)，這需要遍歷訪問，向量比鏈表快。按秩合并如果采用鏈表，在更新子節(jié)點(diǎn)信息時(shí)，只需要改變2個(gè)節(jié)點(diǎn)的指針，雖然在這方面比向量的遍歷增加子節(jié)點(diǎn)要占優(yōu)，但它在調(diào)用子函數(shù)find(·)時(shí)開辟的新資源比向量不使用子函數(shù)的情況要大得多，還需要存儲(chǔ)標(biāo)志秩大小的rank的結(jié)構(gòu)。綜合考慮，捷徑向量算法省去了多次調(diào)用子函數(shù)的開銷，性能表現(xiàn)會(huì)更好。

捷徑向量算法的過程如圖 6所示，在合并前，2棵樹各自用二維向量來存儲(chǔ)各自的信息，樹根節(jié)點(diǎn)是向量最頂端的節(jié)點(diǎn)，尾部的箭頭表示新插入節(jié)點(diǎn)元素的向量增長方向，當(dāng)新訪問到的邊的2個(gè)節(jié)點(diǎn)分別屬于2棵樹時(shí)(邊由雙向箭頭表示)，一棵樹所對應(yīng)的向量被整體復(fù)制到另一棵樹的向量尾部，沿增長方向依次插入，所以新加入節(jié)點(diǎn)元素的根節(jié)點(diǎn)指針均改換為指向目的樹向量的根。

Figure 6 Shortcutting-vector algorithm圖6 捷徑向量算法

3.2 捷徑向量算法與遍歷算法比較

從時(shí)間復(fù)雜度來講，并查集算法要更快。因此，如果只是為了求基本的連通分量的節(jié)點(diǎn)信息，而沒有太多其他需求，就使用并查集算法來實(shí)現(xiàn)。

遍歷算法的鄰接表保存了邊的信息，當(dāng)建立連通分量的時(shí)候，可以很自然地把邊的信息表示出來，但鄰接表中存儲(chǔ)了重復(fù)的信息，每一條邊的2個(gè)節(jié)點(diǎn)都存儲(chǔ)了對方的信息，造成了2倍的開銷。而并查集算法在合并時(shí)忽略了邊的信息，導(dǎo)致一部分信息的缺失。

在空間開銷方面，遍歷算法需要存儲(chǔ)以下數(shù)據(jù)結(jié)構(gòu)：鄰接表、狀態(tài)數(shù)組、正在處理的節(jié)點(diǎn)的隊(duì)列或棧。在Graph500使用的Kronecker生成圖中，默認(rèn)的節(jié)點(diǎn)平均度數(shù)為16，設(shè)圖中節(jié)點(diǎn)的數(shù)量為n，則鄰接表包含了16n規(guī)模的整型數(shù)據(jù)，對應(yīng)每個(gè)節(jié)點(diǎn)，建立一個(gè)長度與節(jié)點(diǎn)數(shù)量n相等的狀態(tài)數(shù)組，還需要維護(hù)隊(duì)列或棧的大小，其大小分別與BFS生成樹的每層的節(jié)點(diǎn)數(shù)量或DFS生成樹的層數(shù)有關(guān)。因此，遍歷算法的空間復(fù)雜度為O(n)，n表示節(jié)點(diǎn)數(shù)量，占用空間隨著參數(shù)n的平均增加速率為16。

捷徑向量算法需要存儲(chǔ)以下數(shù)據(jù)結(jié)構(gòu)：二維子節(jié)點(diǎn)向量和根節(jié)點(diǎn)數(shù)組。各個(gè)連通分量的根節(jié)點(diǎn)存儲(chǔ)了屬于自己的子節(jié)點(diǎn)信息，由于Kronecker生成圖滿足冪律分布的特點(diǎn)且該算法按照擴(kuò)容因子為2的規(guī)則來設(shè)置子向量長度，故對節(jié)點(diǎn)數(shù)量為n的圖，二維子節(jié)點(diǎn)向量占據(jù)的空間為2m，其中表示邊數(shù)量的m滿足如式(1)所示的關(guān)系：

lbn

(1)

隨著規(guī)模n的增加，占用空間的平均增加速率如式(2)所示：

(2)

由式(1)和式(2)可以得出空間開銷平均增加速率的上限如式(3)所示：

rate<2

(3)

這與遍歷算法平均增加速率16相比更具優(yōu)勢。雖然在存儲(chǔ)過程中沒有存儲(chǔ)邊的信息，但達(dá)到了連通分量算法的基本需求。

并查集算法的合并和查找工作不需要一次性把連通分量中所有節(jié)點(diǎn)都找到，利用跳躍式、間斷式的累加操作，來實(shí)現(xiàn)連通分量規(guī)模的逐步擴(kuò)大，從局部連通分量擴(kuò)展到全局連通分量，均可用分布式來實(shí)現(xiàn)，可以比較方便地并行化。但是，DFS需要不斷往圖的深處訪問，不能適應(yīng)在數(shù)據(jù)爆炸環(huán)境下的大圖處理,在訪問時(shí)需要把相連的節(jié)點(diǎn)一次性地訪問完畢，難以實(shí)現(xiàn)分布式化。

此外，遍歷算法還可以作為尋找生成樹的基礎(chǔ)和先導(dǎo)，在不增加算法復(fù)雜度的基礎(chǔ)上，可以增加一些標(biāo)志狀態(tài)和判定狀態(tài)的邏輯來判定有沒有環(huán)的情況，這對后面的工作是十分有意義的。遍歷算法和捷徑向量算法的綜合比較如表1所示。

Table 1 Comparison of traversal algorithmand shortcutting-vector algorithm

3.3 多線程捷徑向量算法

考慮到本文設(shè)計(jì)的串行算法的實(shí)現(xiàn)特點(diǎn)，由算法1可知，對查找操作有4種子情況：

(1)2個(gè)節(jié)點(diǎn)均已被訪問過，且根節(jié)點(diǎn)相同。此時(shí)不需要做任何操作，繼續(xù)掃描下一條邊。

(2)2個(gè)節(jié)點(diǎn)均已被訪問過，且根節(jié)點(diǎn)不同。

(3)2個(gè)節(jié)點(diǎn)一個(gè)被訪問過，另一個(gè)未被訪問過。

(4)2個(gè)節(jié)點(diǎn)均未被訪問過。

對于情況(2)～(4)，下一步需要進(jìn)行合并操作，把2個(gè)節(jié)點(diǎn)放置于同一個(gè)根節(jié)點(diǎn)之下。

對于情況(1)，僅僅是判斷根節(jié)點(diǎn)并跳過本條邊，這與合并操作在算法邏輯上可以實(shí)現(xiàn)并行，即使情況(1)中出現(xiàn)了臟讀，即讀到了合并操作正在修改的臟數(shù)據(jù)，對邊的狀態(tài)的判斷出現(xiàn)了差錯(cuò)，也不會(huì)影響結(jié)果的準(zhǔn)確性。情況(1)與合并操作不需要作為2個(gè)事務(wù)來嚴(yán)格保證原子性，這為利用多線程并行加速提供了機(jī)會(huì)。

在本文設(shè)計(jì)的并行算法中，主線程(線程0)仍執(zhí)行串行捷徑向量算法，但需要其他線程對主線程要處理的邊進(jìn)行預(yù)分類，把不需要主線程處理的邊篩掉，存儲(chǔ)在連續(xù)存儲(chǔ)的狀態(tài)向量中。雖然主線程在處理邊前仍然需要判斷，但狀態(tài)向量的存儲(chǔ)空間是順序存儲(chǔ)，能進(jìn)行線性連續(xù)地訪問，減少了主線程的運(yùn)行時(shí)間。

算法分成2個(gè)階段：

(1)串行階段。

令主線程單獨(dú)對數(shù)據(jù)集的一部分執(zhí)行捷徑向量算法，主要目的是更改若干節(jié)點(diǎn)的根信息，為下一步并行地預(yù)處理提供必要信息，只有一些節(jié)點(diǎn)已經(jīng)位于相同的根節(jié)點(diǎn)下面時(shí)，才會(huì)出現(xiàn)需要優(yōu)化訪問的邊。

(2)并行階段。

對數(shù)據(jù)集的其余部分，多線程進(jìn)行多輪迭代讀取。主線程創(chuàng)建子線程，與子線程執(zhí)行不同的操作。完成各自的任務(wù)后，執(zhí)行柵欄同步，再開始新一輪的并行，直到多次輪轉(zhuǎn)后把數(shù)據(jù)集處理完畢。

主線程和子線程分配相同大小的數(shù)據(jù)，子線程對屬于自身的每條邊進(jìn)行判定，查看其2個(gè)節(jié)點(diǎn)是否有相同的根節(jié)點(diǎn)，設(shè)置相應(yīng)的標(biāo)志位，如果有，則說明不需要進(jìn)行進(jìn)一步處理，否則，需要主線程執(zhí)行合并操作。

主線程主要分成2個(gè)階段：

①處理本段數(shù)據(jù)。此時(shí)任務(wù)與子線程完全相同，只是不需要更改標(biāo)志位，因?yàn)檫@已經(jīng)是最終的處理結(jié)果，設(shè)置該步驟的目的是在等待子線程處理時(shí)不讓主線程閑置。

②處理剩余數(shù)據(jù)。當(dāng)子線程處理完畢對應(yīng)數(shù)據(jù)后，由主線程對每個(gè)子線程的數(shù)據(jù)分別進(jìn)行處理，根據(jù)標(biāo)志位來決定是否執(zhí)行合并操作，直到把本輪所有數(shù)據(jù)處理完畢。

并行算法的流程如圖 7所示。

Figure 7 Multi-thread shortcutting-vector algorithm圖7 多線程捷徑向量算法

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

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境的配置是：Intel(R) Core(TM) i7-7700K CPU @ 4.20 GHz；64 GB內(nèi)存。操作系統(tǒng)為Ubuntu 16.04.7 LTS。

Graph500數(shù)據(jù)集采用的是Kronecker生成圖，本文在不同規(guī)模的生成圖下進(jìn)行測試比較，其中，用參數(shù)scale來衡量圖的大小，表示圖中包含2scale個(gè)節(jié)點(diǎn)。

4.2 捷徑向量算法性能分析

本文比較了并查集算法的數(shù)據(jù)結(jié)構(gòu)與算法的不同組合的性能，如表 2所示，其中scale表示數(shù)據(jù)集的規(guī)模，即圖包含2scale個(gè)節(jié)點(diǎn)。可以發(fā)現(xiàn)，若采用按秩合并，向量和鏈表2個(gè)數(shù)據(jù)結(jié)構(gòu)的時(shí)間比較接近，但捷徑向量比另外3種實(shí)現(xiàn)方式都要快，在220～225規(guī)模均取得了最好的性能，在scale=25(包含225個(gè)節(jié)點(diǎn))時(shí)，與其他2個(gè)性能接近的算法的性能之比分別是1.38倍和1.40倍。因此，捷徑向量算法具有顯著的優(yōu)越性。

Table 2 Performance comparison of Union-Find Algorithm

4.3 連通分量算法3種實(shí)現(xiàn)時(shí)空開銷分析

本文比較了3種算法對連通分量算法的時(shí)間開銷，如圖 8所示?？梢钥吹紹FS和DFS算法性能接近，捷徑向量算法遠(yuǎn)好于遍歷算法，在scale=25(包含225個(gè)節(jié)點(diǎn))時(shí)，其對BFS、DFS的加速比分別為4.76倍和4.70倍，這符合本文的分析和預(yù)期。

Figure 8 Time comparison of connected component algorithms圖8 連通分量算法時(shí)間開銷比較

本文還測試了3種算法的空間開銷，如圖 9所示。3條折線對應(yīng)主坐標(biāo)軸，單位為int，表示占用整型變量的數(shù)量，2個(gè)長條柱對應(yīng)次坐標(biāo)軸，分別是捷徑向量算法的空間開銷占BFS、DFS算法存儲(chǔ)開銷的比例。可以看出，本文算法空間占用為另外2個(gè)算法的4.1%～4.6%，且增長趨勢也較慢，有著明顯的優(yōu)勢。

Figure 9 Storage comparison of connected component algorithms圖9 連通分量算法空間開銷比較

4.4 捷徑向量算法的串并行比較

多線程程序中的可變參數(shù)包括：線程數(shù)量、并行處理數(shù)據(jù)比例和多線程并行迭代輪數(shù)，在不同的數(shù)據(jù)規(guī)模下，對參數(shù)取定若干有代表性的值，進(jìn)行了多組實(shí)驗(yàn)。結(jié)果表明，并行算法與串行算法相比有著明顯的性能提升，隨著數(shù)據(jù)規(guī)模的擴(kuò)大，并行的加速效果越來越明顯，如圖 10所示。在225節(jié)點(diǎn)規(guī)模的圖中，加速比達(dá)到了1.57倍。

Figure 10 Performance comparison of parallel algorithm and serial algorithm圖10 并行算法與串行算法的性能比較

在本文給定的數(shù)據(jù)規(guī)模下，使用2線程時(shí)，程序的性能最好。輪數(shù)大多數(shù)不大于10，對于并行比例，隨著圖規(guī)模的增大，取得最佳性能的并行比例越高，這也說明了并行的加速效果，如表 3所示。

Table 3 Parameter configuration for optimal performance of multi-threaded algorithm

5 結(jié)束語

本文針對面向大規(guī)模圖遍歷的連通分量算法，以Graph500生成的真實(shí)數(shù)據(jù)集為支撐，進(jìn)行優(yōu)化分析。連通分量算法和數(shù)據(jù)結(jié)構(gòu)的優(yōu)化，對Graph500測試的加速有著重要意義。連通分量算法找到的極大連通子圖，為Graph500找到BFS最小生成樹提供了輔助，合理利用了數(shù)據(jù)集節(jié)點(diǎn)的局部性，減少了無效的BFS根節(jié)點(diǎn)嘗試，提升了節(jié)點(diǎn)劃分的有效性，減小了節(jié)點(diǎn)間的通信開銷。采用捷徑向量算法對并查集算法進(jìn)行了優(yōu)化，并進(jìn)行了算法和數(shù)據(jù)結(jié)構(gòu)的協(xié)同度分析，對實(shí)現(xiàn)連通分量算法的3個(gè)基礎(chǔ)算法進(jìn)行了多維度比較和測試，并利用多線程迭代輪轉(zhuǎn)進(jìn)行了并行算法優(yōu)化。實(shí)驗(yàn)結(jié)果表明，所提出的優(yōu)化方法對其他方案均有著明顯優(yōu)勢。向量作為一個(gè)常見的數(shù)據(jù)結(jié)構(gòu)在面向圖遍歷的連通分量算法中表現(xiàn)較好，雖然它存在著一些不足，但通過與算法的配合，兩者仍然能發(fā)揮出較好的效果。在后續(xù)的研究中，可以探索在本文研究成果的基礎(chǔ)上，利用進(jìn)程和線程混合并行來優(yōu)化算法，這將極大提高本文算法的可擴(kuò)展性。