孫茹君 張魯飛 郝子宇 陳左寧

1(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室 江蘇無(wú)錫 214125)2 (國(guó)家并行計(jì)算機(jī)工程技術(shù)研究中心 北京 100190)

在圖計(jì)算模型中，圖用點(diǎn)和邊上的數(shù)據(jù)來(lái)表示，計(jì)算在點(diǎn)上進(jìn)行.迭代計(jì)算是圖計(jì)算的重要執(zhí)行方式，大多數(shù)數(shù)據(jù)挖掘的算法都可以描述為迭代的形式.在分布式并行計(jì)算環(huán)境下，迭代過(guò)程復(fù)雜，也關(guān)系到算法的執(zhí)行結(jié)果.

在大規(guī)模分布式條件下，圖的并行策略包括同步和異步的執(zhí)行方式.本研究將從圖并行的同步和異步方式入手，討論2種不同的執(zhí)行模式對(duì)圖計(jì)算不同算法的適應(yīng)性.并在一致性條件的約束下，分析不同一致性模型異步迭代的特征，提出一種基于一致性約束的自適應(yīng)弱一致迭代模型.

本文首先介紹圖計(jì)算和迭代計(jì)算的背景和相關(guān)工作，對(duì)迭代計(jì)算進(jìn)行理論建模和分析，接著分析了同步和異步迭代執(zhí)行模式并提出了弱一致迭代模型，隨后對(duì)之前的理論分析和提出的新模型進(jìn)行了實(shí)驗(yàn).

1 背 景

1.1 相關(guān)工作

迭代計(jì)算用數(shù)值逼近的方式解決了許多科學(xué)計(jì)算問(wèn)題.在圖計(jì)算中，迭代執(zhí)行是主要的計(jì)算方式.每一輪中，每個(gè)點(diǎn)根據(jù)自己及鄰居的信息完成計(jì)算，更新自己的值.

串行的迭代方法有雅可比(Jacobi)和高斯-賽德?tīng)?Gauss-Seidel)方法[1].迭代計(jì)算可以轉(zhuǎn)化為矩陣乘法，迭代的收斂性可以用矩陣的特征值對(duì)應(yīng)：當(dāng)矩陣的譜小于1時(shí)，迭代問(wèn)題收斂[2].

并行的迭代方法起源于塊同步并行(bulk syn-chronize parallelism, BSP)模型[3-4]，目前許多圖計(jì)算框架都基于BSP模型實(shí)現(xiàn)，例如Pregel[5],GraphX[6]等.ApacheFlink[7]提供了BSP迭代和增量迭代，后者可減少每一步迭代的計(jì)算量.在不規(guī)則的圖數(shù)據(jù)上，并行同步迭代各個(gè)點(diǎn)上的計(jì)算難以同時(shí)結(jié)束，同步迭代可能面臨著嚴(yán)重的“落后者問(wèn)題”(一個(gè)節(jié)點(diǎn)的延遲會(huì)影響整體計(jì)算).異步迭代能充分利用計(jì)算資源，避免每輪迭代的同步開(kāi)銷.除了一些圖算法的異步實(shí)現(xiàn)，如PageRank[8]等，一些圖計(jì)算框架也加入了異步機(jī)制.GRACE[9]圖計(jì)算模型提供了用戶友好的BSP編程接口，迭代執(zhí)行時(shí)采用異步方式.PowerGraph[10]圖計(jì)算模型提供了同步和異步迭代2種計(jì)算引擎，用戶只需描述圖中點(diǎn)的計(jì)算，可以指定任意一種執(zhí)行方式.除了以上SMP(symmetric multi-processor)模式的框架，F(xiàn)rog[11]和Gunrock[12]等框架提供了GPU上的異步圖計(jì)算實(shí)現(xiàn).

同步迭代和異步迭代有不同的適用條件.Power-Switch[13]將同步迭代和異步迭代相結(jié)合，能夠在計(jì)算過(guò)程中按照設(shè)定的閾值在二者之間進(jìn)行切換.

異步迭代執(zhí)行面臨數(shù)據(jù)一致性的問(wèn)題，為了迭代的收斂和迭代速度，針對(duì)邊和點(diǎn)的數(shù)據(jù)讀寫(xiě)，還有異步迭代的不同一致性之分：完全一致、邊一致和點(diǎn)一致.不同一致性下的異步迭代執(zhí)行會(huì)有不同的執(zhí)行過(guò)程甚至結(jié)果[9].目前圖計(jì)算模型的一致性研究不多，且僅有單一異步一致性的迭代方式，即只單獨(dú)使用完全一致、邊一致、點(diǎn)一致這3種方式里的1種.

1.2 圖計(jì)算中迭代執(zhí)行算法

大規(guī)模分布式并行圖計(jì)算的執(zhí)行模式可稱為圖并行，是一種迭代的模型.計(jì)算發(fā)生在圖中的點(diǎn)上，通信沿邊的方向.以圖中點(diǎn)的視角，整個(gè)執(zhí)行過(guò)程是不停迭代地“計(jì)算”、“通信”，直至收斂或達(dá)到其他終止條件.

和迭代相關(guān)的圖算法可以歸為3類：隨機(jī)漫步算法(random walk)[14]、串行遍歷算法(sequential traversal)和并行遍歷算法(parallel traversal).隨機(jī)漫步算法中每輪迭代當(dāng)前節(jié)點(diǎn)的值都會(huì)按照一定的比例影響其鄰居節(jié)點(diǎn)，也接受鄰居節(jié)點(diǎn)的影響，例如PageRank[15]、近似計(jì)數(shù)、k-SAT[16]算法、HITS(hyperlink-induced topic search)算法等.串行遍歷算法在迭代的每一輪當(dāng)前節(jié)點(diǎn)會(huì)將值傳播給鄰居節(jié)點(diǎn)，如路徑可達(dá)判定、單源最短路徑(single-source shortest path, SSSP)、寬度優(yōu)先搜索(breadth-first search, BFS)、深度優(yōu)先搜索(depth-first search, DFS)等.并行遍歷算法下，圖中的每個(gè)點(diǎn)都作為起始點(diǎn)執(zhí)行串行遍歷算法，如標(biāo)簽傳播、圖聚類、圖著色(graph coloring)等.

1.3 迭代的串行執(zhí)行方式

迭代計(jì)算的后一步依賴于前一步的計(jì)算結(jié)果.如果將計(jì)算第t輪的中間值描述為x(t)，那么迭代計(jì)算可被描述為x(t+1)=f(x(t))，初始值為x0，結(jié)束條件為g(x(t+1)-x(t))<δ.在矩陣計(jì)算中，函數(shù)f一般為f(x(t))=x(t)A+b.

迭代有雅可比法(Jacobi method)和高斯-賽德?tīng)柗?Gauss-Seidel method).設(shè)x=(x0,x1,…,xn)，雅可比法每次迭代可以被描述為

而高斯-賽德?tīng)柗看蔚牡梢员幻枋鰹?/p>

雅可比法和高斯-賽德?tīng)柗ǘ贾庇^地描述了迭代的串行執(zhí)行過(guò)程.在串行迭代時(shí)，每輪迭代依次進(jìn)行，1輪迭代中圖中的點(diǎn)按照編號(hào)依次更新值.雅可比迭代每一輪中計(jì)算的參數(shù)是上一輪的值，而高斯-賽德?tīng)柕恳惠唴R總計(jì)算的參數(shù)是最近產(chǎn)生的值(包括本輪之前產(chǎn)生的值和上一輪產(chǎn)生而在本輪還未更新的值).

1.4 迭代的并行執(zhí)行方式

1.4.1 同步迭代

同步迭代下，每一輪的執(zhí)行僅與當(dāng)前輪有關(guān)，本輪之內(nèi)各節(jié)點(diǎn)并行計(jì)算.只有當(dāng)所有節(jié)點(diǎn)本輪計(jì)算完畢之后，才會(huì)進(jìn)入下一輪迭代.這種同步執(zhí)行方式是BSP.

1.4.2 異步迭代

異步迭代下，各節(jié)點(diǎn)的計(jì)算與其他節(jié)點(diǎn)不相關(guān)，沒(méi)有輪與輪同步和節(jié)點(diǎn)的相互等待過(guò)程.各節(jié)點(diǎn)并行計(jì)算，當(dāng)本節(jié)點(diǎn)迭代1次之后，立即開(kāi)始下一輪迭代.在迭代過(guò)程中如果需要其他節(jié)點(diǎn)的數(shù)據(jù)，則請(qǐng)求獲得其他節(jié)點(diǎn)的最新數(shù)據(jù)即可.特別地，在一些條件約束下，為了異步迭代數(shù)據(jù)的一致性，請(qǐng)求其他節(jié)點(diǎn)的數(shù)據(jù)有可能不是即刻更新的值而是上一輪的值.

不考慮計(jì)算的串并行，單從同步和異步的角度看，雅可比迭代法是BSP類型的同步模式，而高斯-賽德?tīng)柕ㄒ延挟惒降乃枷?，即新?jì)算采用當(dāng)前最新的值，無(wú)論這個(gè)值是在當(dāng)前輪或是上一輪產(chǎn)生.

1.4.3 同步和異步的執(zhí)行過(guò)程

在執(zhí)行過(guò)程中，同步迭代下，劃分到同一個(gè)機(jī)器上的邊和點(diǎn)在1輪迭代中依次進(jìn)行計(jì)算，在2輪之間進(jìn)行同步和可能的合并計(jì)算.異步迭代時(shí)，每個(gè)機(jī)器上的子圖中各個(gè)點(diǎn)單獨(dú)計(jì)算，本節(jié)點(diǎn)1輪計(jì)算之后直接進(jìn)入下輪，不等待其他節(jié)點(diǎn)的計(jì)算進(jìn)度.

1.5 不同迭代的適用性

在圖計(jì)算的迭代算法中，同步執(zhí)行與異步執(zhí)行有不同的適用范圍.PageRank等基于隨機(jī)漫步的算法同步執(zhí)行比異步執(zhí)行效率更高.因?yàn)樵诿恳惠喌校總€(gè)節(jié)點(diǎn)都參與計(jì)算，且計(jì)算量相當(dāng)，各節(jié)點(diǎn)收斂的速率接近.異步執(zhí)行相較于同步執(zhí)行會(huì)引起更多的通信，各節(jié)點(diǎn)請(qǐng)求終止與綜合判斷的開(kāi)銷較大.而圖著色等遍歷算法異步執(zhí)行效率更高，因?yàn)槊總€(gè)節(jié)點(diǎn)雖然計(jì)算模式相同，但計(jì)算量有區(qū)別，同步迭代會(huì)面臨“落后者問(wèn)題”，此外，一些算法需要執(zhí)行的“異步性”來(lái)保證算法跳出不斷翻轉(zhuǎn)的死循環(huán).因此同步迭代較適用于隨機(jī)漫步類算法，異步迭代更適用于并行遍歷類算法.

2 迭代過(guò)程的理論建模

2.1 并行迭代描述

2.2 迭代執(zhí)行的收斂性

迭代過(guò)程中的計(jì)算可以用矩陣描述x(k+1)=x(k)T(f)+b，當(dāng)矩陣T的譜半徑小于1時(shí)，迭代過(guò)程收斂[17].譜半徑ρ(T)=maxλi，i=1,2,…,n，λi為矩陣的特征值.圖的迭代計(jì)算也可以用以上形式描述.求解每個(gè)xi的值不一定需要所有點(diǎn)上的值，大多數(shù)情況下只需要對(duì)應(yīng)圖鄰居節(jié)點(diǎn)的值，所以此時(shí)矩陣T中圖中各點(diǎn)對(duì)應(yīng)的非鄰居元素都為0.

另外一些圖算法對(duì)應(yīng)于圖的選擇問(wèn)題，每次計(jì)算會(huì)根據(jù)收到的信息(例如鄰居節(jié)點(diǎn)的值)對(duì)本節(jié)點(diǎn)進(jìn)行直接修改.由于修改對(duì)應(yīng)的矩陣每行只有一個(gè)元素為1，其余皆0，矩陣的譜半徑為1，此類算法的迭代收斂性不能保證[18].例如圖著色算法，節(jié)點(diǎn)可選顏色用自然數(shù)表示：如果采用同步迭代的方式，每次迭代當(dāng)前節(jié)點(diǎn)選擇與周圍所有鄰居顏色都不同的最小顏色編號(hào)的值，如果最后2個(gè)節(jié)點(diǎn)的顏色不斷交換跳變，圖著色算法不能收斂；如果采用異步迭代執(zhí)行，此種情況很有可能避免.另如標(biāo)簽傳播類的算法，每次節(jié)點(diǎn)會(huì)根據(jù)選取收到的所有鄰居節(jié)點(diǎn)值的其中一個(gè)作為本節(jié)點(diǎn)的值，當(dāng)節(jié)點(diǎn)信息保持穩(wěn)定時(shí)節(jié)點(diǎn)會(huì)請(qǐng)求終止，類似地，異步迭代相比于同步迭代執(zhí)行方式更容易收斂[19].

3 弱一致的異步迭代執(zhí)行方式

3.1 完全一致、邊一致、點(diǎn)一致

對(duì)于異步迭代，由于當(dāng)前節(jié)點(diǎn)可以隨時(shí)訪問(wèn)其他節(jié)點(diǎn)，而被訪問(wèn)的節(jié)點(diǎn)可能處于任何狀態(tài)，如果要使用最新的值，則需保證數(shù)據(jù)的一致性.然而由于異步迭代中不同節(jié)點(diǎn)間輪數(shù)可能會(huì)差異很大，所以即使沒(méi)有使用節(jié)點(diǎn)的最新值(比如該節(jié)點(diǎn)正在計(jì)算而拒絕訪問(wèn)其值)而使用其舊值也沒(méi)有影響，此時(shí)可以理解為該節(jié)點(diǎn)在請(qǐng)求節(jié)點(diǎn)的視角下還處于上一輪的狀態(tài).

Table 1 ReadabilityWriteability in Different AsynchronousConsistent Models

表1 不同異步一致性與計(jì)算時(shí)的可讀寫(xiě)性

Table 1 ReadabilityWriteability in Different AsynchronousConsistent Models

ConsistentModelLocalVertexNeighborEdgeNeighborVertexComplete ConsistentR WR WR WEdge ConsistentR WR WR WVertex ConsistentR WR WR W

以上異步執(zhí)行模式中，點(diǎn)一致即全異步可能出現(xiàn)寫(xiě)競(jìng)爭(zhēng)情況.一致性要求越高，異步執(zhí)行的并行性越低，執(zhí)行速度也會(huì)因此降低.但較高的一致性能有效減少競(jìng)爭(zhēng)情況，從而加快迭代后期的收斂速度，甚至使原本由于競(jìng)爭(zhēng)而不能收斂的算法收斂[20].

3.2 單一異步一致性執(zhí)行的不足

在異步執(zhí)行時(shí)，可采用統(tǒng)計(jì)活躍點(diǎn)的方式來(lái)判斷異步執(zhí)行的并行性(活躍點(diǎn)指同一時(shí)刻正在計(jì)算的點(diǎn)的數(shù)量).已有的異步迭代方式[9]只有單純的完全一致、邊一致和點(diǎn)一致，各有優(yōu)劣.

1) 完全一致的異步迭代執(zhí)行能夠有效避免競(jìng)爭(zhēng)，但是在同一時(shí)間段內(nèi)同時(shí)執(zhí)行的點(diǎn)數(shù)有限，并行效率較低.

2) 邊一致相對(duì)于完全一致約束較松，但在邊上沒(méi)有數(shù)據(jù)的條件下，邊一致和點(diǎn)一致相同(由于寫(xiě)鎖排斥讀鎖，而讀鎖之間不互相排斥.在異步執(zhí)行時(shí)，讀到的鄰居數(shù)據(jù)并不要求是最新值.所以在沒(méi)有邊數(shù)據(jù)時(shí)，點(diǎn)一致和邊一致都只維持本節(jié)點(diǎn)的范圍計(jì)算即可).

3) 點(diǎn)一致是完全異步的執(zhí)行模式，但是在迭代執(zhí)行的后期，對(duì)于一些算法會(huì)出現(xiàn)競(jìng)爭(zhēng)的情況而難以收斂.

3.3 弱一致的異步迭代執(zhí)行方式

針對(duì)已有異步迭代模型的不足，本文提出弱一致的異步迭代執(zhí)行模型：綜合已有的不同一致性約束條件，根據(jù)異步迭代的不同時(shí)間段的特征，選擇最合適的一致性模型.

在“以點(diǎn)為中心”的計(jì)算中，異步迭代執(zhí)行過(guò)程以活躍點(diǎn)的數(shù)目描述.例如，在圖著色算法(隨機(jī)漫步類算法)中，初始階段，活躍點(diǎn)逐漸增加；中間階段，活躍點(diǎn)在較高的范圍內(nèi)波動(dòng)；最后階段，活躍點(diǎn)開(kāi)始下降.并行遍歷算法和隨機(jī)漫步算法不同，在開(kāi)始時(shí)活躍點(diǎn)的個(gè)數(shù)較多，中間過(guò)程中活躍點(diǎn)在一定范圍內(nèi)波動(dòng)，最后活躍點(diǎn)數(shù)目逐漸下降.

不同的一致性適用于異步執(zhí)行的不同階段.完全一致和邊一致能夠有效避免數(shù)據(jù)一致性問(wèn)題引發(fā)的死鎖，同時(shí)能夠避免產(chǎn)生點(diǎn)一致中的競(jìng)爭(zhēng)危害.在異步執(zhí)行的開(kāi)始階段，較強(qiáng)的一致性限制會(huì)降低各點(diǎn)迭代的速度，因?yàn)榇藭r(shí)競(jìng)爭(zhēng)較少，而基于一致性要求，只有不到50%的節(jié)點(diǎn)在同時(shí)計(jì)算，較多的等待節(jié)點(diǎn)制約了執(zhí)行速度.而在異步執(zhí)行的后期，較高的一致性會(huì)加快收斂，而較低的一致性會(huì)引發(fā)競(jìng)爭(zhēng)，甚至難以收斂.一個(gè)恰當(dāng)?shù)慕鉀Q方式是在執(zhí)行的初期采用完全異步的方式進(jìn)行迭代，在中后期提高一致性約束加快收斂.

針對(duì)當(dāng)前節(jié)點(diǎn)，迭代的計(jì)算過(guò)程如算法1，執(zhí)行模型的流程如圖1.

算法1. 弱一致的異步迭代執(zhí)行.

① while (沒(méi)有收斂)

② [根據(jù)活躍點(diǎn)信息等條件選擇異步一致性模型]；

③ 檢查鄰居狀態(tài)，等待所有鄰居狀態(tài)滿足本節(jié)點(diǎn)的計(jì)算要求；

④ 修改本節(jié)點(diǎn)狀態(tài)；

⑤ 請(qǐng)求鄰居數(shù)據(jù)；

⑥ 接收數(shù)據(jù)；

⑦ 計(jì)算v←f(Γv,e(v))；

⑧ 修改本節(jié)點(diǎn)狀態(tài)；

⑨ end while

Fig. 1 Process of weakly consistent asynchronous iteration圖1 異步弱一致迭代的計(jì)算流程圖

3.3.1 選擇模型的時(shí)機(jī)

算法1行②表示異步迭代過(guò)程選擇一致性模型.一致性模型的選擇時(shí)機(jī)有很多：

1) 每輪迭代前選擇(如算法1描述).此方式的優(yōu)點(diǎn)是可以實(shí)時(shí)調(diào)整一致性模型的選擇；缺點(diǎn)是每輪檢查開(kāi)銷巨大，如果用活躍點(diǎn)檢查，需要全局的All-reduce操作，這會(huì)大大降低迭代速度.

2) 間隔一定輪數(shù)，需要每個(gè)節(jié)點(diǎn)保持1個(gè)計(jì)數(shù)器.此方法的優(yōu)點(diǎn)是避免了過(guò)多全局開(kāi)銷，但前提是間隔輪數(shù)設(shè)置合理；其缺點(diǎn)是需要權(quán)衡計(jì)數(shù)器的計(jì)算存儲(chǔ)開(kāi)銷與圖計(jì)算節(jié)點(diǎn)的計(jì)算開(kāi)銷.如果圖計(jì)算節(jié)點(diǎn)的計(jì)算簡(jiǎn)單(例如僅僅是選擇值)，此方法會(huì)使計(jì)算量加倍.此外，此方法在迭代中間階段會(huì)增加迭代一致性模型選擇的開(kāi)銷，因?yàn)樵摃r(shí)刻活躍點(diǎn)變化復(fù)雜，不同一致性模型下活躍點(diǎn)變化趨勢(shì)不同，可能會(huì)引起此階段選擇的一致性模型不斷跳變.

3) 間隔一定時(shí)間，需要計(jì)時(shí)器和時(shí)鐘響應(yīng).需要全局的時(shí)鐘開(kāi)銷和時(shí)鐘中斷響應(yīng)，在分布式條件下需要考慮其數(shù)據(jù)一致性.一個(gè)替代的方法是采用“master節(jié)點(diǎn)法”管理時(shí)鐘，但其缺點(diǎn)是該節(jié)點(diǎn)的IO開(kāi)銷巨大.

4) 活躍點(diǎn)閾值驅(qū)動(dòng)，需要在一定時(shí)刻檢查，例如每輪迭代開(kāi)始前.這會(huì)增大迭代開(kāi)銷.

5) 鄰居節(jié)點(diǎn)模型驅(qū)動(dòng)，根據(jù)鄰居節(jié)點(diǎn)更改一致性模型的情況決定本節(jié)點(diǎn)的一致性模型.此方法代價(jià)較小，只需要在每次節(jié)點(diǎn)請(qǐng)求鄰居節(jié)點(diǎn)數(shù)據(jù)的時(shí)候一同接受模型信息；缺點(diǎn)是需要與其他方式配合，否則無(wú)法開(kāi)始模型的更改.而引入其他方式的配合就會(huì)引入其缺點(diǎn).

以上選擇模型的時(shí)機(jī)并不是單一存在于異步迭代過(guò)程中，而是可以多種選擇方式相結(jié)合.這樣不僅可以融合各種模型選擇方法的優(yōu)勢(shì)，還可以避免單一選擇方法引發(fā)的單一方面開(kāi)銷巨大的問(wèn)題.

3.3.2 選擇的一致性模型

一致性模型的選擇是弱異步迭代的關(guān)鍵.3.1～3.2節(jié)已經(jīng)分析，完全一致、邊一致、點(diǎn)一致的競(jìng)爭(zhēng)性逐步加強(qiáng)，收斂性逐步減弱.

一個(gè)圖算法采用弱一致的方式執(zhí)行，一般會(huì)經(jīng)歷從點(diǎn)一致、邊一致，到完全一致的過(guò)程.如果在執(zhí)行過(guò)程中收斂和競(jìng)爭(zhēng)并重，可能會(huì)出現(xiàn)以上過(guò)程的重復(fù)或部分重復(fù).

從宏觀上可以判斷，活躍點(diǎn)數(shù)量越多，說(shuō)明競(jìng)爭(zhēng)占據(jù)更主要的地位；而活躍點(diǎn)數(shù)量越少，說(shuō)明算法執(zhí)行到更需要收斂的階段.如果以活躍點(diǎn)驅(qū)動(dòng)的算法，活躍點(diǎn)數(shù)量長(zhǎng)時(shí)間不變，需要適時(shí)檢查其計(jì)算情況，有時(shí)需要調(diào)整一致性模型(例如從點(diǎn)一致到邊一致甚至完全一致)增加收斂能力.

而采用固定間隔的方法切換一致性模型時(shí)，可以根據(jù)算法的經(jīng)驗(yàn)運(yùn)行輪數(shù)總時(shí)間，確定初步的切換時(shí)機(jī)，用小規(guī)模的圖運(yùn)行做測(cè)試、調(diào)整，最終確定運(yùn)行的模型選擇.

3.3.3 不同一致性共存

由于一致性模型可變，在分布式環(huán)境下，各個(gè)節(jié)點(diǎn)之間的模型變化時(shí)機(jī)可能不同.當(dāng)節(jié)點(diǎn)之間模型不一致時(shí)，多種一致性模型可在同一次圖計(jì)算中共存.

圖計(jì)算迭代中不同的一致性能夠適應(yīng)圖中不同節(jié)點(diǎn)迭代收斂速度不同的情況.有實(shí)驗(yàn)表明[9]，在完全異步(點(diǎn)一致)的模型下，圖著色計(jì)算最后1%的活躍點(diǎn)計(jì)算用到整體迭代時(shí)間的34%.如果采用不同一致性的模型，可以使較難收斂的點(diǎn)首先提高一致性約束，而其他的點(diǎn)仍保持原來(lái)較低的一致性約束.這樣在迭代過(guò)程中，較難收斂的點(diǎn)就能以更大的速度收斂，不會(huì)出現(xiàn)少量節(jié)點(diǎn)在迭代后期一直活躍的情況.

由于各個(gè)節(jié)點(diǎn)根據(jù)自身情況或者全局情況獨(dú)立地選擇異步迭代模型，本節(jié)提出的弱一致模型能夠自動(dòng)適應(yīng)不同一致性共存的情況，且各節(jié)點(diǎn)之間不會(huì)相互干擾.

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)設(shè)計(jì)

本實(shí)驗(yàn)的執(zhí)行流程如圖2所示.在實(shí)驗(yàn)過(guò)程中采用負(fù)載均衡的劃分策略進(jìn)行圖劃分，比較同步迭代策略和異步迭代策略在執(zhí)行PageRank，SSSP，Graph Coloring的結(jié)果.對(duì)于Graph Coloring的異步迭代，在不同一致性(完全一致，邊一致，點(diǎn)一致，以及三者綜合的弱一致)下執(zhí)行，以比較不同一致性的計(jì)算區(qū)別.

實(shí)驗(yàn)采用公開(kāi)數(shù)據(jù)集SNAP[21]中部分類別的圖和Kronecker生成器生成的圖(表2).

Fig. 2 Process of iterating experiment圖2 迭代執(zhí)行流程圖

CategoryGraphVerticesEdgesWebWeb-Google8757135105039Social NetworkTwitter813061768149RoadRoadNet-CA19652065533214GeneratedK.3351—K.23951903351—2395190130654—134212448

實(shí)驗(yàn)環(huán)境為8個(gè)節(jié)點(diǎn)組成的集群，通過(guò)千兆以太網(wǎng)連接.每個(gè)節(jié)點(diǎn)包含8個(gè)2.50 GHz Intel?Xeon?E5420 CPU，8 GB DDR2 RAM.

4.2 實(shí)驗(yàn)算法

選擇PageRank，SSSP，Graph Coloring這3種算法作為基本的實(shí)驗(yàn)算法分析迭代執(zhí)行的效果.

SSSP算法每輪迭代中單點(diǎn)的計(jì)算過(guò)程：收集所有入邊鄰居節(jié)點(diǎn)的值pi；計(jì)算本節(jié)點(diǎn)值p=min{p,(min{pi}+1)}；將本節(jié)點(diǎn)值發(fā)送給所有出邊鄰居.

4.3 同步迭代與異步迭代的比較

圖3和圖4是PageRank計(jì)算在同步和異步2種迭代方式下的執(zhí)行結(jié)果.本實(shí)驗(yàn)選擇了典型的2種圖——網(wǎng)頁(yè)鏈接圖(Web-Google)和社交網(wǎng)絡(luò)圖(Twitter)，這2種圖的大部分分析都會(huì)用到PageRank這種隨機(jī)漫步類算法.該類計(jì)算需要得到具體數(shù)值作為最終結(jié)果，故比較2種迭代方式計(jì)算結(jié)果的區(qū)別，如圖3(b)和圖4(b).

從圖3和圖4可以看出，PageRank的同步迭代執(zhí)行模式要優(yōu)于異步迭代執(zhí)行模式，執(zhí)行時(shí)間更短.這是因?yàn)镻ageRank算法每一輪的計(jì)算量接近，采用同步的方式能夠整合同一輪中的所有通信，在2輪之間的通信部分進(jìn)行整體通信，而異步的迭代方式每個(gè)點(diǎn)計(jì)算完成之后都要單獨(dú)通信，大量小消息帶來(lái)了巨大的通信開(kāi)銷.圖3(b)和圖4(b)表明，同步和異步執(zhí)行的計(jì)算結(jié)果基本一致，其誤差在1%以內(nèi)，也證明了異步迭代執(zhí)行的合理性和正確性.

Fig. 3 SynchronousAsynchronous iterations in PageRank algorithm (Web-Google graph)圖3 PageRank算法同步迭代與異步迭代比較(Web-Google圖)

圖5表示SSSP算法的同步和異步執(zhí)行結(jié)果.選擇了2種典型的圖——社交網(wǎng)絡(luò)圖(Twitter)和道路交通圖(RoadNet-CA)，它們?cè)趯?shí)際應(yīng)用中經(jīng)常需要遍歷類算法.例如用SSSP求2個(gè)人間的最短好友路徑和2個(gè)地點(diǎn)之間的最短路徑.該類型的計(jì)算同步迭代方式也優(yōu)于異步迭代方式，這是由于圖遍歷的最短路徑選擇依賴于圖的整體信息，采用同步的方式能夠在每一輪中都有效計(jì)算圖中每個(gè)點(diǎn)相對(duì)于源點(diǎn)的路徑長(zhǎng)，而采用異步的方式路徑長(zhǎng)度的變化更改更快，在相同的長(zhǎng)度下可能需要記錄更多的入節(jié)點(diǎn)信息.此外異步執(zhí)行最嚴(yán)重的缺點(diǎn)仍是大量小消息的通信開(kāi)銷.對(duì)于圖遍歷類算法SSSP，由于結(jié)果唯一，同步和異步迭代方式計(jì)算結(jié)果相同，都可以保證正確性.

Fig. 5 SynchronousAsynchronous iterations in SSSP algorithm圖5 SSSP算法同步迭代與異步迭代比較

表3表示圖著色算法的同步和異步迭代執(zhí)行結(jié)果.2幅圖由于結(jié)構(gòu)不同，需要的迭代次數(shù)有差異，其執(zhí)行時(shí)間增加的比例也不同.與理論分析一致：異步迭代下圖著色可以收斂，而同步迭代圖著色不能收斂.

Table 3 Execution Time of SynchronousAsynchronousMethods in Graph Coloring Algorithm

表3 圖著色算法同步迭代與異步迭代執(zhí)行時(shí)間比較

Table 3 Execution Time of SynchronousAsynchronousMethods in Graph Coloring Algorithm

ParallelNodesTwitter GraphRoadNet-CA GraphSyncAsyncSyncAsync2∞2.76973∞4.119174∞7.16003∞5.81978∞18.6696∞8.319616∞42.2898∞11.5532∞93.8981∞17.270364∞234.006∞34.8584

Fig. 6 Active vertices in synchronous SSSP algorithm圖6 SSSP的同步迭代執(zhí)行

同步迭代中的活躍節(jié)點(diǎn)分析：圖6和圖7分別表示同步迭代下SSSP和圖著色算法(RoadNet-CA圖)的活躍點(diǎn)數(shù)變化趨勢(shì).由于SSSP是單源開(kāi)始計(jì)算，故計(jì)算初始時(shí)只有源點(diǎn)為活躍點(diǎn)，隨著迭代的增加逐步向鄰居擴(kuò)展，到迭代結(jié)束時(shí)所有節(jié)點(diǎn)的值都已更新完畢達(dá)到穩(wěn)定值，活躍點(diǎn)降為0.圖著色的初始狀態(tài)下所有節(jié)點(diǎn)同時(shí)開(kāi)始著色，在同步迭代的每一輪中活躍點(diǎn)個(gè)數(shù)都為總節(jié)點(diǎn)數(shù)，迭代無(wú)法收斂.這是因?yàn)橄噜彽?個(gè)點(diǎn)會(huì)不斷同時(shí)變換顏色難以跳出此模式.

Fig. 7 Active vertices in synchronous graph coloring algorithm圖7 圖著色的同步迭代執(zhí)行

4.4 弱一致的異步迭代

表4是不同一致性模型下圖著色算法的執(zhí)行情況，以Kronecker生成器生成1 048 576點(diǎn)數(shù)的自然圖(K.1048576)，8個(gè)機(jī)器運(yùn)行為例.

Table 4 Graph Coloring in Different Consistent Models(K.1048576 Graph)

由于圖著色算法的信息只包含在點(diǎn)上，邊上沒(méi)有信息，故不存在修改邊數(shù)據(jù)的問(wèn)題，邊一致和完全一致相同.從表4可以看出，在點(diǎn)一致的異步迭代下，圖著色難以結(jié)束，這是因?yàn)辄c(diǎn)一致時(shí)各點(diǎn)計(jì)算獨(dú)立，當(dāng)請(qǐng)求其鄰邊的數(shù)據(jù)時(shí)，鄰邊可能也在計(jì)算，從而引發(fā)死鎖.而邊一致與完全一致的迭代下，圖著色能正常收斂結(jié)束.

異步迭代對(duì)于請(qǐng)求的鄰居節(jié)點(diǎn)值于何輪產(chǎn)生沒(méi)有要求.為了避免點(diǎn)一致下死鎖的問(wèn)題，可以采用更強(qiáng)的一致性策略.為了詳細(xì)分析不同一致性的執(zhí)行特點(diǎn)，可以統(tǒng)計(jì)執(zhí)行過(guò)程中活躍點(diǎn)的變化規(guī)律.

異步執(zhí)行時(shí)各節(jié)點(diǎn)的執(zhí)行狀態(tài)不同(有的在通信，有的在計(jì)算)，難以找到合適的時(shí)間點(diǎn)進(jìn)行統(tǒng)計(jì)，每次統(tǒng)計(jì)活躍點(diǎn)采用的All-gather操作又會(huì)影響其本身的迭代執(zhí)行(需要每個(gè)點(diǎn)的當(dāng)前輪計(jì)算結(jié)束，相當(dāng)于1次同步過(guò)程，只是各點(diǎn)執(zhí)行的輪數(shù)不同).因此對(duì)于異步執(zhí)行的分析僅抽樣執(zhí)行階段的指定時(shí)間步長(zhǎng).

圖著色計(jì)算過(guò)程不會(huì)用到邊上的數(shù)據(jù)，由于邊一致和完全一致在圖的邊上沒(méi)有數(shù)據(jù)時(shí)寫(xiě)鎖的范圍一致，故其執(zhí)行情況一樣.所以后文我們比較點(diǎn)一致和邊一致2種約束條件，以及對(duì)應(yīng)的弱一致策略.

圖8表示圖著色問(wèn)題分別用點(diǎn)一致的異步迭代和邊一致的異步迭代執(zhí)行時(shí)，相同時(shí)間步長(zhǎng)下活躍點(diǎn)數(shù)、總著色數(shù)、著色沖突數(shù)的變化情況.實(shí)驗(yàn)測(cè)得，點(diǎn)一致中的平均迭代輪數(shù)是邊一致中的2倍.

Fig. 8 Asynchronous iteration of graph coloring algorithm 圖8 圖著色的異步迭代執(zhí)行

圖著色的圖并行迭代方法采用近似的算法，當(dāng)著色沖突數(shù)(1條邊的2個(gè)端點(diǎn)顏色相同表示1次沖突，總沖突數(shù)是沖突邊數(shù))下降到閾值以內(nèi)，迭代結(jié)束.因此著色沖突數(shù)可以反映收斂速度.

從圖8可以看出，點(diǎn)一致下，著色數(shù)逐步減少，異步競(jìng)爭(zhēng)充分；實(shí)驗(yàn)中相同時(shí)間段內(nèi)，平均每個(gè)點(diǎn)迭代的輪數(shù)多于邊一致的條件下迭代輪數(shù)，迭代速度較快；而沖突數(shù)增加，收斂變差.邊一致下著色數(shù)變化不大，異步競(jìng)爭(zhēng)受到一致性條件的約束；而沖突數(shù)迅速減少，收斂變快.但是，沖突數(shù)到達(dá)一個(gè)略低的水平之后就會(huì)維持，有時(shí)難以達(dá)到設(shè)定的閾值.

圖9表示本文提出的弱一致異步迭代模型在標(biāo)簽傳播類著色算法上的執(zhí)行結(jié)果.我們先通過(guò)點(diǎn)一致的異步迭代維持較高的迭代速度(虛線左邊)，再切換到邊一致加速收斂(虛線右邊).橫軸表示近似迭代輪數(shù)，虛線左邊平均迭代了500輪，用時(shí)9.823 s，虛線右邊平均迭代了561輪，用時(shí)21.019 s；總用時(shí)30.842 s.

Fig. 9 Weakly consistent asynchronous iterating圖9 弱一致的異步迭代

Fig. 10 Convergence speed in weaklyedge consistent asynchronous iterating圖10 弱一致與邊一致的異步迭代下的收斂速度

可以看出，經(jīng)過(guò)一致性切換，著色沖突數(shù)逐步減少，使算法快速收斂并結(jié)束.

圖10表示弱一致(方塊)和邊一致(叉)的收斂情況，虛線仍表示弱一致下的切換.本實(shí)驗(yàn)用105邊數(shù)的圖做示意，設(shè)置收斂閾值(著色沖突數(shù))是20(總邊數(shù)的0.02%).可以看出雖然一直采用邊一致的策略能夠使著色沖突數(shù)快速降低，但其達(dá)到50左右就維持在附近小幅波動(dòng)，不能達(dá)到閾值要求.而采用弱一致的方式，在初期增加競(jìng)爭(zhēng)，后續(xù)切換至邊一致的策略后，著色沖突數(shù)能迅速下降，很快達(dá)到閾值20以下，經(jīng)過(guò)進(jìn)一步測(cè)試，本弱一致迭代著色沖突數(shù)會(huì)維持在15附近小幅波動(dòng).

可以看出，采用本文提出的弱一致方法.迭代初始狀態(tài)選擇點(diǎn)一致的迭代模式，能加快迭代速度，使著色迅速分散.達(dá)到切換條件(輪數(shù))后，采用邊一致的方式，能加快收斂.弱一致的異步迭代能達(dá)到更好的收斂效果，且用時(shí)較短；而同步或者點(diǎn)一致的異步迭代難以收斂，邊一致的異步迭代收斂效果有限.

5 總 結(jié)

迭代計(jì)算在數(shù)據(jù)計(jì)算中是有效的逼近方式，能夠擬合多種計(jì)算模型.在大數(shù)據(jù)分析領(lǐng)域尤其是圖計(jì)算中，迭代計(jì)算能夠抽象描述大部分圖算法，在結(jié)構(gòu)化數(shù)據(jù)挖據(jù)和關(guān)聯(lián)分析領(lǐng)域至關(guān)重要.

已有的異步模型都基于單一的一致性，本研究提出了弱一致的異步計(jì)算模型，將異步迭代中不同的一致性執(zhí)行方式在異步迭代的各個(gè)階段融合，自動(dòng)選擇適合的執(zhí)行方式.該方法能夠利用不同一致性的特征服務(wù)于迭代計(jì)算的不同階段，既可滿足迭代初期要求的迭代速度，也可滿足迭代后期要求的收斂速度.實(shí)驗(yàn)證明，在異步迭代開(kāi)始階段，選擇一致性較弱的執(zhí)行方式(點(diǎn)一致)能達(dá)到較快的迭代速度；在異步迭代的結(jié)束階段，采用一致性較強(qiáng)的執(zhí)行方式(完全一致)能達(dá)到較快的收斂速度.一致性模型的選擇代價(jià)較大，在實(shí)際實(shí)驗(yàn)中，采用較簡(jiǎn)單的方法，在迭代的中期切換已能達(dá)到綜合利用的效果.