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

1(數(shù)學工程與先進計算國家重點實驗室 江蘇無錫 214125)2 (國家并行計算機工程技術研究中心 北京 100190)

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

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

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

1 背 景

1.1 相關工作

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

串行的迭代方法有雅可比(Jacobi)和高斯-賽德爾(Gauss-Seidel)方法[1].迭代計算可以轉(zhuǎn)化為矩陣乘法，迭代的收斂性可以用矩陣的特征值對應：當矩陣的譜小于1時，迭代問題收斂[2].

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

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

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

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

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

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

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

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

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

而高斯-賽德爾法每次的迭代可以被描述為

雅可比法和高斯-賽德爾法都直觀地描述了迭代的串行執(zhí)行過程.在串行迭代時，每輪迭代依次進行，1輪迭代中圖中的點按照編號依次更新值.雅可比迭代每一輪中計算的參數(shù)是上一輪的值，而高斯-賽德爾迭代每一輪匯總計算的參數(shù)是最近產(chǎn)生的值(包括本輪之前產(chǎn)生的值和上一輪產(chǎn)生而在本輪還未更新的值).

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

1.4.1 同步迭代

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

1.4.2 異步迭代

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

不考慮計算的串并行，單從同步和異步的角度看，雅可比迭代法是BSP類型的同步模式，而高斯-賽德爾迭代法已有異步的思想，即新計算采用當前最新的值，無論這個值是在當前輪或是上一輪產(chǎn)生.

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

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

1.5 不同迭代的適用性

在圖計算的迭代算法中，同步執(zhí)行與異步執(zhí)行有不同的適用范圍.PageRank等基于隨機漫步的算法同步執(zhí)行比異步執(zhí)行效率更高.因為在每一輪迭代中，每個節(jié)點都參與計算，且計算量相當，各節(jié)點收斂的速率接近.異步執(zhí)行相較于同步執(zhí)行會引起更多的通信，各節(jié)點請求終止與綜合判斷的開銷較大.而圖著色等遍歷算法異步執(zhí)行效率更高，因為每個節(jié)點雖然計算模式相同，但計算量有區(qū)別，同步迭代會面臨“落后者問題”，此外，一些算法需要執(zhí)行的“異步性”來保證算法跳出不斷翻轉(zhuǎn)的死循環(huán).因此同步迭代較適用于隨機漫步類算法，異步迭代更適用于并行遍歷類算法.

2 迭代過程的理論建模

2.1 并行迭代描述

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

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

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

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

3.1 完全一致、邊一致、點一致

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

Table 1 ReadabilityWriteability in Different AsynchronousConsistent Models

表1 不同異步一致性與計算時的可讀寫性

Table 1 ReadabilityWriteability in Different AsynchronousConsistent Models

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

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

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

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

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

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

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

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

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

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

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

針對當前節(jié)點，迭代的計算過程如算法1，執(zhí)行模型的流程如圖1.

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

① while (沒有收斂)

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

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

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

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

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

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

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

⑨ end while

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

3.3.1 選擇模型的時機

算法1行②表示異步迭代過程選擇一致性模型.一致性模型的選擇時機有很多：

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

2) 間隔一定輪數(shù)，需要每個節(jié)點保持1個計數(shù)器.此方法的優(yōu)點是避免了過多全局開銷，但前提是間隔輪數(shù)設置合理；其缺點是需要權衡計數(shù)器的計算存儲開銷與圖計算節(jié)點的計算開銷.如果圖計算節(jié)點的計算簡單(例如僅僅是選擇值)，此方法會使計算量加倍.此外，此方法在迭代中間階段會增加迭代一致性模型選擇的開銷，因為該時刻活躍點變化復雜，不同一致性模型下活躍點變化趨勢不同，可能會引起此階段選擇的一致性模型不斷跳變.

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

4) 活躍點閾值驅(qū)動，需要在一定時刻檢查，例如每輪迭代開始前.這會增大迭代開銷.

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

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

3.3.2 選擇的一致性模型

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

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

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

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

3.3.3 不同一致性共存

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

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

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

4 實 驗

4.1 實驗設計

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

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

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

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

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

4.2 實驗算法

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

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

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

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

從圖3和圖4可以看出，PageRank的同步迭代執(zhí)行模式要優(yōu)于異步迭代執(zhí)行模式，執(zhí)行時間更短.這是因為PageRank算法每一輪的計算量接近，采用同步的方式能夠整合同一輪中的所有通信，在2輪之間的通信部分進行整體通信，而異步的迭代方式每個點計算完成之后都要單獨通信，大量小消息帶來了巨大的通信開銷.圖3(b)和圖4(b)表明，同步和異步執(zhí)行的計算結(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)絡圖(Twitter)和道路交通圖(RoadNet-CA)，它們在實際應用中經(jīng)常需要遍歷類算法.例如用SSSP求2個人間的最短好友路徑和2個地點之間的最短路徑.該類型的計算同步迭代方式也優(yōu)于異步迭代方式，這是由于圖遍歷的最短路徑選擇依賴于圖的整體信息，采用同步的方式能夠在每一輪中都有效計算圖中每個點相對于源點的路徑長，而采用異步的方式路徑長度的變化更改更快，在相同的長度下可能需要記錄更多的入節(jié)點信息.此外異步執(zhí)行最嚴重的缺點仍是大量小消息的通信開銷.對于圖遍歷類算法SSSP，由于結(jié)果唯一，同步和異步迭代方式計算結(jié)果相同，都可以保證正確性.

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

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

Table 3 Execution Time of SynchronousAsynchronousMethods in Graph Coloring Algorithm

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

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

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

4.4 弱一致的異步迭代

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總 結(jié)

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

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