項(xiàng)哲慧，秦小麟+，猶 鋒，劉 亮

1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

2.南瑞集團(tuán)有限公司，南京 210003

1 引言

近年來(lái)隨著數(shù)據(jù)規(guī)模的增大，優(yōu)化各種大數(shù)據(jù)處理平臺(tái)的性能已成為研究的熱點(diǎn)。圖計(jì)算平臺(tái)Pregel[1]和Giraph[2]等基于并行計(jì)算加快圖數(shù)據(jù)的處理，它們采用BSP[3]編程模型作為并行算法的基礎(chǔ)框架。Barrier（柵欄）同步是并行計(jì)算常采用的一種同步方法,用于BSP的兩個(gè)超步（super-step）之間的同步。一個(gè)線程調(diào)用Barrier意味著該線程需要在該點(diǎn)等待所有線程到達(dá)，控制線程的執(zhí)行進(jìn)度確保并行計(jì)算的正確性。在并行最小生成樹(shù)算法中[4]，對(duì)多個(gè)連通分量進(jìn)行合并需要先統(tǒng)計(jì)所有連通分量選擇的邊，再確定該邊是否同時(shí)被兩個(gè)連通分量選中，進(jìn)而合并連通分量。因此線程在計(jì)算完連通分量選擇的邊之后需要同步，否則會(huì)出現(xiàn)先計(jì)算完的線程無(wú)法判斷邊是否同時(shí)被兩個(gè)分量選中，因?yàn)檫x擇該邊的另一個(gè)連通分量可能由其他線程處理?？梢?jiàn)Barrier同步是保證并行計(jì)算正確性不可或缺的部分，它的效率直接影響并行計(jì)算的性能。

并行計(jì)算有兩種計(jì)算結(jié)構(gòu)：共享內(nèi)存結(jié)構(gòu)和消息傳遞結(jié)構(gòu)。后者在大數(shù)據(jù)處理平臺(tái)中更常見(jiàn)，如Pregel，Giraph的Barrier同步機(jī)制是通過(guò)消息傳遞實(shí)現(xiàn)線程之間的同步的。然而在網(wǎng)絡(luò)中，消息過(guò)量、消息重發(fā)以及消息的輸入速率超過(guò)輸出速率[5-6]等原因都能造成網(wǎng)絡(luò)擁堵或者網(wǎng)絡(luò)斷路。而現(xiàn)有的Barrier算法在遇到網(wǎng)絡(luò)擁堵或者網(wǎng)絡(luò)斷路時(shí)只能等待或者選擇一條更遠(yuǎn)的路由傳遞消息，降低了同步算法的效率。

造成上述問(wèn)題的主要原因是現(xiàn)有Barrier算法的通信模式[7](communication pattern)是固定的。如圖1（a）所示：在由節(jié)點(diǎn)a、b和c組成的網(wǎng)絡(luò)上進(jìn)行同步，3個(gè)節(jié)點(diǎn)兩兩之間有物理鏈路連接（雙向箭頭表示物理鏈路）。Barrier算法設(shè)定由a匯總3個(gè)節(jié)點(diǎn)的狀態(tài)，則節(jié)點(diǎn)b、c需分別向a傳送同步消息，此時(shí)，節(jié)點(diǎn)b、c消息傳遞分別只需1跳的距離（實(shí)線箭頭）。如果ab鏈路斷路，節(jié)點(diǎn)c向a傳送消息的路徑不變，但節(jié)點(diǎn)b與a通信時(shí)要通過(guò)節(jié)點(diǎn)c轉(zhuǎn)送消息，導(dǎo)致節(jié)點(diǎn)a、b的通信距離增加到2跳（虛線箭頭），且加重了ac鏈路上的擁堵?tīng)顩r。但如果能改變通信模式，由c來(lái)匯總消息，則節(jié)點(diǎn)a、b分別向c傳遞同步消息，均可1跳到達(dá)，避開(kāi)了斷掉的ab鏈路。然而直接修改通信模式代價(jià)較大，如調(diào)整最小生成樹(shù)結(jié)構(gòu)的Tree算法的通信模式時(shí)需重新構(gòu)建最小生成樹(shù)，調(diào)整過(guò)程依賴多個(gè)輪次的同步[4]、額外的消息來(lái)確認(rèn)節(jié)點(diǎn)間的通信關(guān)系以及額外的空間來(lái)存儲(chǔ)新的通信模式結(jié)構(gòu)，避免與調(diào)整過(guò)程中依賴的通信模式混淆。

Fig.1 Network topology圖1 網(wǎng)絡(luò)拓?fù)?/p>

此外，通信模式的結(jié)構(gòu)與網(wǎng)絡(luò)拓?fù)涞钠鹾隙葧?huì)影響算法效率?，F(xiàn)有的大數(shù)據(jù)平臺(tái)[1-2]使用的同步算法（如PUB[8]）的通信模式結(jié)構(gòu)為主從結(jié)構(gòu)(masterslave，MS)，而MS結(jié)構(gòu)僅適合星型拓?fù)涞木W(wǎng)絡(luò)結(jié)構(gòu)。如圖1（b）所示：由節(jié)點(diǎn)a、b和c組成的線型網(wǎng)絡(luò)由ab、bc兩條物理鏈路連通（雙向箭頭表示物理鏈路），設(shè)定由a匯總3個(gè)節(jié)點(diǎn)的狀態(tài)，在MS結(jié)構(gòu)中，節(jié)點(diǎn)b給a發(fā)送同步消息需要1跳，節(jié)點(diǎn)c給a發(fā)送同步消息需要2跳（實(shí)線箭頭）。在2層樹(shù)形結(jié)構(gòu)中，節(jié)點(diǎn)a為樹(shù)根，b為中間節(jié)點(diǎn)，c為葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)c給b發(fā)送同步消息，中間節(jié)點(diǎn)b匯總自身及子節(jié)點(diǎn)（節(jié)點(diǎn)b、c）的消息再發(fā)送給根節(jié)點(diǎn)a，節(jié)點(diǎn)b、c發(fā)送消息分別只需1跳距離（虛線箭頭）?？芍ㄐ拍Ｊ?jīng)Q定的需要通信的節(jié)點(diǎn)間的距離（跳數(shù)）越小越好（更契合網(wǎng)絡(luò)拓?fù)洌?/p>

針對(duì)上述問(wèn)題，本文在原來(lái)的Barrier算法基礎(chǔ)上提出一種新的同步算法，可調(diào)整通信模式，提高同步算法在網(wǎng)絡(luò)斷路下的效率。本文貢獻(xiàn)如下：

（1）引入節(jié)點(diǎn)編碼將通信模式與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分離開(kāi)，并提出一個(gè)異步調(diào)整算子（asynchronous adjustment operator，AAO）通過(guò)修改節(jié)點(diǎn)編碼的方式達(dá)到調(diào)整通信模式的目的，這種調(diào)整方式比直接調(diào)整通信模式的代價(jià)低。

（2）提出了局部連續(xù)樹(shù)（local continuous tree,LCT）結(jié)構(gòu)的通信模式，LCT結(jié)構(gòu)具有局部連續(xù)性，可以減小網(wǎng)絡(luò)中需要相互通信的節(jié)點(diǎn)之間的距離，提高通信效率。

（3）結(jié)合LCT結(jié)構(gòu)和AAO算子，提出了動(dòng)態(tài)局部連續(xù)樹(shù)(dynamic local continuous tree，DLCT)算法。并實(shí)驗(yàn)比較了DLCT算法與其他5種Barrier算法在網(wǎng)絡(luò)斷路情況下的效率，結(jié)果表明DLCT比其他算法的效率高30%到50%。

本文結(jié)構(gòu)如下：第2章介紹Barrier算法的相關(guān)工作以及現(xiàn)有算法在網(wǎng)絡(luò)斷路下的局限性；第3章介紹提出的DLCT算法；第4章實(shí)驗(yàn)評(píng)估DLCT在網(wǎng)絡(luò)斷路下的效率；第5章總結(jié)工作。

2 相關(guān)工作

Barrier算法可分為三類：?jiǎn)蜗?、雙相和多層。單相算法用消息散播的方式，使得各節(jié)點(diǎn)都獲得全局節(jié)點(diǎn)的同步狀態(tài)并進(jìn)行獨(dú)立判斷；雙相算法有個(gè)中心節(jié)點(diǎn)來(lái)獲取并判斷全局節(jié)點(diǎn)的同步狀態(tài)，在Gather階段中心節(jié)點(diǎn)匯總所有節(jié)點(diǎn)的同步消息，判斷全局的同步狀態(tài)，并在Release階段通知其他節(jié)點(diǎn)所有節(jié)點(diǎn)已到達(dá)同步狀態(tài)并結(jié)束同步；多層算法將網(wǎng)絡(luò)分層，每層應(yīng)用不同的Barrier算法，使得不同算法間進(jìn)行優(yōu)勢(shì)互補(bǔ)，并提高算法的拓展性。然而這些算法均不能很好地適應(yīng)網(wǎng)絡(luò)斷路狀況。

單相 Barrier算法有 All to All、Butterfly[9]、Dissemination[7]和Pairwise exchange[10]。其中后3種采用了Han等提出的消息散播模式[11]，把All to All的O(N2)的消息復(fù)雜度降低到O(NlbN)。此類算法適用于共享內(nèi)存的多核框架，可以減少鎖的使用。但是在網(wǎng)絡(luò)框架下，該類算法的消息量比雙相Barrier算法O(N)大，導(dǎo)致同步效率相對(duì)較差，且通信模式復(fù)雜，不易調(diào)整。

雙相Barrier算法有MS（master-slave）、combining tree[12]、tournament[7,13]、MSC（Mellor&Scott’s combining tree）[14]、BST（binominal structure tree）[15]和2層樹(shù)形結(jié)構(gòu)[16]。其中MS算法簡(jiǎn)單，很多大數(shù)據(jù)平臺(tái)的同步模型都使用MS算法[1-2]，但是master節(jié)點(diǎn)容易成為全局的熱點(diǎn)。Combining tree的k叉樹(shù)結(jié)構(gòu)、tournament的錦標(biāo)賽結(jié)構(gòu)和BST的二項(xiàng)樹(shù)結(jié)構(gòu)等都能緩解一定的熱點(diǎn)問(wèn)題。上述結(jié)構(gòu)都是不同形狀的樹(shù)形結(jié)構(gòu)，調(diào)整代價(jià)大，涉及到額外的同步、通信和存儲(chǔ)空間。

多層Barrier算法有 MLB（multi-layer barrier）[17]、TAB（tree-based all-to-all barrier）[18]和文獻(xiàn)[19]等。但是因?yàn)槎鄬铀惴ㄖ皇侨诤犀F(xiàn)有算法，其通信模式依然是固定的，且不易調(diào)整，同樣會(huì)出現(xiàn)斷路時(shí)效率大幅降低的問(wèn)題。

此外，文獻(xiàn)[20]研究了上述Barrier算法在負(fù)載不均衡的情況下的效率。文獻(xiàn)[21]在共享內(nèi)存結(jié)構(gòu)下研究Barrier算法的效率。

3 DLCT Barrier算法

3.1 LCT通信模式

因?yàn)殡p相Barrier算法消息復(fù)雜度低，比較適合在網(wǎng)絡(luò)中同步線程，所以本文在雙相Barrier算法的基礎(chǔ)上改進(jìn)。本文采用的通信模式為二項(xiàng)樹(shù)結(jié)構(gòu)。如圖2（a）所示，在LCT結(jié)構(gòu)中，ID=x的節(jié)點(diǎn)的父節(jié)點(diǎn)為ID=x&(x-1)，比如節(jié)點(diǎn)6的父節(jié)點(diǎn)為6&(6-1)=4，相當(dāng)于將子節(jié)點(diǎn)的最低非0位置0。根節(jié)點(diǎn)0的父節(jié)點(diǎn)為null。通信模式結(jié)構(gòu)中相連的節(jié)點(diǎn)間需要通信。

Fig.2 Structures of LCT&BST圖2 LCT和BST的結(jié)構(gòu)

本文給出通信模式的形式化定義，用一對(duì)映射G，R:{ID}→p({ID})分別表示節(jié)點(diǎn)x在Gather階段和Release階段的通信對(duì)象的集合，p({ID})表示節(jié)點(diǎn)集合的冪集（ID與節(jié)點(diǎn)一一對(duì)應(yīng)）。在Gather階段每個(gè)節(jié)點(diǎn)需要與父節(jié)點(diǎn)通信，從而逐步將同步信息匯總到根節(jié)點(diǎn)，計(jì)算父節(jié)點(diǎn)的過(guò)程對(duì)應(yīng)通信模式中的G映射：G(ID)={(ID-1)&ID}，相當(dāng)于將二進(jìn)制形式的ID的最低非0比特位置0。在Release階段每個(gè)節(jié)點(diǎn)需要與子節(jié)點(diǎn)通信，逐步廣播同步結(jié)束消息到葉子節(jié)點(diǎn)，計(jì)算孩子節(jié)點(diǎn)的過(guò)程對(duì)應(yīng)R映射，R(ID)的計(jì)算見(jiàn)算法1，即將二進(jìn)制形式的ID的最低非0位之后的比特位逐個(gè)置1。

算法1 R(ID)LCT Release階段的目標(biāo)節(jié)點(diǎn)集合計(jì)算

通過(guò)引入節(jié)點(diǎn)編碼以簡(jiǎn)化通信模式的調(diào)整：將網(wǎng)絡(luò)中各節(jié)點(diǎn)的位置映射到全局唯一的ID值，使其與LCT結(jié)構(gòu)中相同ID的節(jié)點(diǎn)對(duì)應(yīng)，用映射num:{(x，y)}→[0，N)表示。其中，(x，y)表示節(jié)點(diǎn)位置，N表示網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)。num映射用ID值將通信模式LCT結(jié)構(gòu)中的節(jié)點(diǎn)與網(wǎng)絡(luò)節(jié)點(diǎn)聯(lián)系起來(lái)，網(wǎng)絡(luò)節(jié)點(diǎn)先通過(guò)num映射得到相應(yīng)的ID，再通過(guò)LCT的G、R映射計(jì)算出在Gather和Release階段的通信對(duì)象。如在Gather階段，位置為(x，y)的非根節(jié)點(diǎn)需要發(fā)送同步消息給位置為num-1(G(num(x，y)))的節(jié)點(diǎn)，其中num-1為num的反函數(shù)。在節(jié)點(diǎn)編號(hào)的基礎(chǔ)上僅改變網(wǎng)絡(luò)節(jié)點(diǎn)的ID值就能達(dá)到調(diào)整通信模式的目的，具體調(diào)整過(guò)程在3.2節(jié)闡述。

LCT與同為二項(xiàng)樹(shù)的BST結(jié)構(gòu)比較有兩點(diǎn)優(yōu)勢(shì)：（1）簡(jiǎn)化節(jié)點(diǎn)編碼；（2）易于更新鏈路集合。其中第（2）點(diǎn)在3.2節(jié)具體闡述。

LCT能簡(jiǎn)化節(jié)點(diǎn)編碼：節(jié)點(diǎn)編碼傾向于將需要通信的兩個(gè)ID賦值給相互靠近的兩個(gè)物理節(jié)點(diǎn)以減小通信距離，提高算法效率。如圖2（a）、（b）所示，分別為L(zhǎng)CT和BST的結(jié)構(gòu)圖，容易看出LCT的子樹(shù)中的節(jié)點(diǎn)是連續(xù)編號(hào)的，而B(niǎo)ST的編號(hào)是跳躍的，可知LCT結(jié)構(gòu)中需要相互通信的節(jié)點(diǎn)編號(hào)相近。節(jié)點(diǎn)編碼時(shí)只需根據(jù)節(jié)點(diǎn)距離依次編碼，即可滿足減少通信距離的需求，此類編碼方式有S-order curve、Z-order curve[22]、Hilbert curve[23]等。本文采用的編碼方式就是S-order curve，其num映射為num(x，y)=x×size+y+(x%2)×(size-1-2y)，其中size為網(wǎng)格型網(wǎng)絡(luò)的長(zhǎng)寬。用s-curve的編碼方式將圖2中虛線框內(nèi)的節(jié)點(diǎn)映射到網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)（參考圖3（a）或（c）），LCT結(jié)構(gòu)中的節(jié)點(diǎn)12～15映射在一條直線上，而B(niǎo)ST中的節(jié)點(diǎn)3、7、11、15卻分別在置于網(wǎng)絡(luò)中相距最遠(yuǎn)的4個(gè)位置形成一個(gè)波浪形。在相同的簡(jiǎn)單的節(jié)點(diǎn)編碼方式下LCT結(jié)構(gòu)在網(wǎng)絡(luò)中的通信效率更高，即（在保證高效通信的情況下）LCT能夠簡(jiǎn)化節(jié)點(diǎn)編碼。

3.2 異步調(diào)整算子(AAO）

調(diào)整通信模式即改變節(jié)點(diǎn)的通信對(duì)象，從而改變使用的鏈路集合，起到避開(kāi)斷路的作用。通信模式調(diào)整主要有兩種方式，改變節(jié)點(diǎn)編碼num映射或者改變G、R映射。而改變G、R映射相當(dāng)于改變邏輯上的樹(shù)型連接，調(diào)整方式復(fù)雜，代價(jià)大。本文采用改變num映射的方式調(diào)整通信模式。異步調(diào)整算子round(K)的作用是更新網(wǎng)絡(luò)節(jié)點(diǎn)的ID，即ID′=ID+KmodN，因?yàn)镮D=num(x，y)，所以改變ID本質(zhì)上即改變num映射：num′(x，y)=num(x，y)+KmodN。該調(diào)整過(guò)程僅對(duì)num映射進(jìn)行模加運(yùn)算，調(diào)整的計(jì)算代價(jià)很低。

Fig.3 Link set in use of BST&LCT before and after adjustment圖3 BST和LCT調(diào)整前后使用的鏈路集合

UQ的值域?yàn)閇0，1]：當(dāng)A=B時(shí)UQ=0，無(wú)更新量；當(dāng)A?B=? 時(shí)UQ=1，更新量最大。

LCT易于更新鏈路集合：如圖3所示，分別為BST和LCT采用s-curve的方式映射到4×4的網(wǎng)絡(luò)中，并調(diào)用round(1)更新通信模式。圖中粗實(shí)線表示網(wǎng)絡(luò)使用的鏈路集合，可看出通過(guò)調(diào)整，LCT和BST使用的鏈路集合都發(fā)生變化。根據(jù)LCT結(jié)構(gòu)（圖2）可知節(jié)點(diǎn)4、5之間需要通信，在圖3（c）中為（2,3）和（2,4）節(jié)點(diǎn)通信，調(diào)整之后如圖3（d）變?yōu)椋?,4）和（2,4）節(jié)點(diǎn)通信，更換了使用的鏈路。LCT結(jié)構(gòu)調(diào)整前后使用的鏈路集合的交集大小為7，并集大小為26，計(jì)算LCT的更新量UQ(LCT)=1-7/26=73.1%。同理根據(jù)圖3（a）、（b）計(jì)算BST調(diào)整之后的更新量UQ(BST)=18.2%。LCT的更新量顯著大于BST，即LCT更容易更新鏈路集合（在實(shí)驗(yàn)4.2節(jié)會(huì)給出BST和LCT完整的更新量的比較，說(shuō)明在整體上LCT結(jié)構(gòu)的更新量大于BST，上述例子并非特例）。

異步調(diào)整過(guò)程在Release階段進(jìn)行，其調(diào)整信息K值（round（K）的參數(shù)值）存放在同步消息結(jié)構(gòu)中。同步消息結(jié)構(gòu)如圖4所示：G/R標(biāo)志該消息的類型：Gather和Release；content在不同類型消息中的含義不同：在Gather消息中，content保存消息經(jīng)過(guò)的路徑的實(shí)際長(zhǎng)度，該內(nèi)容會(huì)被消息經(jīng)過(guò)的每個(gè)節(jié)點(diǎn)更新，根節(jié)點(diǎn)根據(jù)Gather消息的content判斷是否存在斷路；在Release消息中，content表示調(diào)整算子的K值，收到Release消息的節(jié)點(diǎn)先轉(zhuǎn)發(fā)消息給子節(jié)點(diǎn)，然后根據(jù)K值改變num映射，調(diào)整結(jié)構(gòu)。調(diào)整信息借助同步消息進(jìn)行傳遞，無(wú)須增加額外的消息量，且每個(gè)節(jié)點(diǎn)獨(dú)立更新自己的num映射，異步調(diào)整結(jié)構(gòu)。

本文定義了更新量UQ（update quantity）來(lái)量化AAO更新鏈路集合的效果，更新量越大說(shuō)明結(jié)構(gòu)越易于更新，從而越容易避開(kāi)斷路。

定義1（更新量UQ）在AAO的作用下鏈路集合從A變?yōu)锽，則更新量為：

Fig.4 Structure of synchronous message圖4 同步消息結(jié)構(gòu)

此外，異步調(diào)整過(guò)程不會(huì)破壞同步過(guò)程的正確性。調(diào)整過(guò)程中只存在3種消息傳遞：舊節(jié)點(diǎn)給舊節(jié)點(diǎn)發(fā)送本次同步的Release消息，新節(jié)點(diǎn)給新節(jié)點(diǎn)發(fā)送下次同步的Gather消息，新節(jié)點(diǎn)給舊節(jié)點(diǎn)發(fā)送下一次的Gather消息。每個(gè)節(jié)點(diǎn)更新完num映射就結(jié)束本次同步過(guò)程，且如果節(jié)點(diǎn)未更新，它的子節(jié)點(diǎn)也一定未更新，所以不存在舊節(jié)點(diǎn)給新節(jié)點(diǎn)發(fā)送Release消息的情況。其中前兩種情況相當(dāng)于通信模式固定時(shí)的同步消息傳送，不會(huì)破壞同步過(guò)程。在第3種情況中，因?yàn)榕f節(jié)點(diǎn)處于本次同步過(guò)程的Release階段，只要保證在Release階段時(shí)本次的Gather消息已經(jīng)清空，則下次的Gather消息與本次的Gather消息不會(huì)混在一起，隔離了兩次同步中的消息就能保證兩次同步過(guò)程正確。如何保證在Release階段Gather消息已清空會(huì)在3.3節(jié)解釋。

由調(diào)整過(guò)程可知，AAO有以下3個(gè)優(yōu)點(diǎn)：（1）各節(jié)點(diǎn)異步調(diào)整num映射，不需要依賴額外的同步過(guò)程，或者額外的空間暫存新值；（2）斷路的判定信息以及調(diào)整值K存放在同步消息中，不會(huì)增加消息量；（3）每次更新通信模式僅僅對(duì)節(jié)點(diǎn)num進(jìn)行模加，計(jì)算量極低。降低通信模式調(diào)整對(duì)同步算法效率的影響。

3.3 DLCT Barrier同步過(guò)程

DLCTBarrier同步過(guò)程分為3階段，分別為Gather、Release和調(diào)整階段。相比原來(lái)的雙相Barrier過(guò)程多了調(diào)整階段。算法2為DLCT算法的具體過(guò)程。步驟1、2，初始化當(dāng)前節(jié)點(diǎn)的ID和子節(jié)點(diǎn)的數(shù)量（需要接收的Gather消息數(shù)量）。Gather階段：步驟3、4，節(jié)點(diǎn)等待接收所有子節(jié)點(diǎn)的Gather消息；步驟5，匯總子節(jié)點(diǎn)消息的路徑長(zhǎng)度；步驟6，清空Gather消息；步驟7、8，發(fā)送Gather消息給父節(jié)點(diǎn)。注意這里需要先清空消息隊(duì)列再發(fā)送消息，確保節(jié)點(diǎn)不會(huì)在進(jìn)入Release階段之后還存有本次的Gather消息。因?yàn)槿绻劝l(fā)送消息給父節(jié)點(diǎn)，可能出現(xiàn)還未清空消息時(shí)，就收到父節(jié)的Release消息的情況。Release階段：步驟9、10，非根節(jié)點(diǎn)等待來(lái)自父節(jié)點(diǎn)的Release消息；步驟12，根節(jié)點(diǎn)匯總Gather消息，判斷是否存在較大影響的斷路，決定是否需要調(diào)整通信模式；步驟14，非根節(jié)點(diǎn)從Release消息中獲取K值；步驟15、16，發(fā)送Release消息給子節(jié)點(diǎn)。異步調(diào)整階段：步驟17、18，各節(jié)點(diǎn)根據(jù)K值調(diào)整通信模式；步驟19，最后結(jié)束同步過(guò)程，各節(jié)點(diǎn)恢復(fù)計(jì)算任務(wù)。

算法2DLCT Barrier同步過(guò)程

以4個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)為例，節(jié)點(diǎn)0的子節(jié)點(diǎn)為1、2，節(jié)點(diǎn)1的子節(jié)點(diǎn)為3。假設(shè)節(jié)點(diǎn)0、2之間的鏈路中斷，則在Gather階段根節(jié)點(diǎn)0收到所有子節(jié)點(diǎn)的消息之后，根據(jù)消息的跳數(shù)判斷網(wǎng)絡(luò)出現(xiàn)斷路情況，然后調(diào)用round(1)做出調(diào)整，并在Release階段將調(diào)整參數(shù)K=1通過(guò)Release消息傳遞給子節(jié)點(diǎn)。根節(jié)點(diǎn)0調(diào)整之后節(jié)點(diǎn)編號(hào)變?yōu)?（成為葉子節(jié)點(diǎn)），標(biāo)記該節(jié)點(diǎn)為x，假設(shè)當(dāng)其他3個(gè)節(jié)點(diǎn)還處于Release階段時(shí)，節(jié)點(diǎn)x已進(jìn)入下一階段的同步過(guò)程，并發(fā)送Gather消息給節(jié)點(diǎn)0（原節(jié)點(diǎn)3），節(jié)點(diǎn)3在Release階段已清空Gather消息隊(duì)列，此時(shí)節(jié)點(diǎn)x給原節(jié)點(diǎn)3發(fā)送消息可以安全緩存到隊(duì)列中而不會(huì)與上一次的Gather消息混合，直到原節(jié)點(diǎn)3調(diào)整節(jié)點(diǎn)編號(hào)為0并進(jìn)入下一次同步之后才會(huì)處理緩存的Gather消息，因此調(diào)整通信模式的過(guò)程是安全的。

4 實(shí)驗(yàn)與分析

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

實(shí)驗(yàn)在JADE[24]4.4.0平臺(tái)提供的通信基礎(chǔ)上搭建模擬的網(wǎng)格型網(wǎng)絡(luò)：每個(gè)節(jié)點(diǎn)都有唯一的位置信息(x，y)，并根據(jù)位置信息確定其鄰居節(jié)點(diǎn)（可以直接發(fā)送消息的節(jié)點(diǎn)），在發(fā)送消息給目標(biāo)節(jié)點(diǎn)的過(guò)程中，先將消息發(fā)送給離目標(biāo)節(jié)點(diǎn)最近的鄰居節(jié)點(diǎn)，如果接收到消息的節(jié)點(diǎn)非目標(biāo)節(jié)點(diǎn)則繼續(xù)選取離目標(biāo)節(jié)點(diǎn)最近的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息。斷路情況通過(guò)刪除鄰居節(jié)點(diǎn)來(lái)實(shí)現(xiàn)，比如設(shè)定相鄰的a、b節(jié)點(diǎn)之間的鏈路中斷，則節(jié)點(diǎn)a刪除鄰居節(jié)點(diǎn)b，節(jié)點(diǎn)b刪除鄰居節(jié)點(diǎn)a。網(wǎng)絡(luò)層封裝消息的路由過(guò)程，保留send、receive接口供Barrier算法傳送同步消息。實(shí)驗(yàn)采用一個(gè)簡(jiǎn)單的同步測(cè)試程序測(cè)試各Barrier算法的效率，測(cè)試程序調(diào)用3次Barrier進(jìn)行同步，每?jī)纱瓮街gsleep 0.5 s（無(wú)同步情況下的單個(gè)線程運(yùn)行時(shí)間為1 s）。各Barrier算法都給同步測(cè)試程序提供統(tǒng)一的Barrier()接口用于各個(gè)節(jié)點(diǎn)的同步。

實(shí)驗(yàn)選取現(xiàn)有的5種Barrier算法進(jìn)行實(shí)驗(yàn)，雙相算法采用MS、Tree、Tournament，分別代表不同的結(jié)構(gòu)，其中MS為單層樹(shù)狀結(jié)構(gòu)，Tree為最小生成樹(shù)結(jié)構(gòu)，Tournament為錦標(biāo)賽結(jié)構(gòu)（混合二項(xiàng)樹(shù)與單層樹(shù)結(jié)構(gòu)）。單相算法選取dissemination作為代表，因?yàn)樵撍惴ㄔ趩蜗嗨惴ㄖ行首罡撸篈2A（all-to-all）算法消息量大，butterfly、pairwise exchange在節(jié)點(diǎn)數(shù)量非2的冪次方時(shí)效率驟降。多層算法由單相和雙相算法中效率最高的dissemination+Tree構(gòu)成。在實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn)單純的DLCT算法擴(kuò)展性不好，因此實(shí)驗(yàn)采用了雙層算法ID1：DLCT+MS和ID2：DLCT+Tree。ID1和ID2的結(jié)構(gòu)依然是樹(shù)狀結(jié)構(gòu)，通信模式的調(diào)整過(guò)程只作用于DLCT層。

實(shí)驗(yàn)結(jié)果有兩個(gè)指標(biāo)分別為更新量UQ和同步程序運(yùn)行時(shí)間。采用更新量來(lái)量化LCT結(jié)構(gòu)在AAO調(diào)整下避開(kāi)斷路的能力，更新量越大則越容易避開(kāi)斷路。用同步程序運(yùn)行時(shí)間來(lái)比較各Barrier算法的同步效率，因?yàn)橛糜跍y(cè)試Barrier算法效率的程序是相同的，程序的運(yùn)行時(shí)間可以側(cè)面反映出Barrier算法的效率，程序運(yùn)行時(shí)間越短則Barrier算法效率越高。此外，實(shí)驗(yàn)設(shè)定了不同比例的斷路狀況來(lái)測(cè)試Barrier算法在斷路情況下的效率，并設(shè)定了不同的網(wǎng)絡(luò)規(guī)模，測(cè)試Barrier算法的拓展性。

4.2 LCT結(jié)構(gòu)避開(kāi)斷路的能力

為證明LCT避開(kāi)斷路的能力，實(shí)驗(yàn)在大小為4×4的網(wǎng)格型網(wǎng)絡(luò)上計(jì)算LCT的更新量。在16節(jié)點(diǎn)的網(wǎng)絡(luò)中，共有16種s-curve型的節(jié)點(diǎn)編號(hào)（確定了其中一個(gè)節(jié)點(diǎn)的編號(hào)就可以根據(jù)s-curve確定網(wǎng)絡(luò)中所有節(jié)點(diǎn)的編號(hào)），每種編號(hào)可以通過(guò)調(diào)用異步調(diào)整算子round(K)轉(zhuǎn)化成其他編號(hào)，一共有16×16種轉(zhuǎn)化。分別計(jì)算出這256種情況下的UQ(LCT)，其平均更新量為0.552 7，即平均每次調(diào)整結(jié)構(gòu)都能更新一半的鏈路。

此外實(shí)驗(yàn)比較了LCT和BST結(jié)構(gòu)的更新量，計(jì)算BST在256種轉(zhuǎn)化下的相應(yīng)的更新量UQ(BST)，取LCT與BST更新量的差值UQ(LCT)-UQ(BST)作直方圖，結(jié)果如圖5所示。當(dāng)LCT的更新量大于BST時(shí)，豎條為正，出現(xiàn)在x軸上方，反之則出現(xiàn)在下方。由圖可知x軸上方的豎條比較密集，可見(jiàn)在絕大部分的轉(zhuǎn)化中LCT通信模式的更新量比BST大，從而可知LCT比BST更易更新鏈路。因?yàn)镈LCT可通過(guò)雙層Barrier算法拓展，實(shí)驗(yàn)只考慮算法在4×4大小的網(wǎng)絡(luò)中的更新量。

4.3 DLCT算法的拓展性

如圖6所示（a）、（b）、（c）分別為各Barrier算法在網(wǎng)絡(luò)鏈路完好、存在10%的網(wǎng)絡(luò)斷路和存在20%的網(wǎng)絡(luò)斷路的情況下，以及在不同網(wǎng)絡(luò)規(guī)模下（網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)不同）的運(yùn)行時(shí)間。

Fig.5 Update quantity of LCT&BST圖5 LCT和BST結(jié)構(gòu)的更新量

除ID1、ID2和Tree外，其他算法的拓展性都比較差。Dissemination算法的消息量為NlbN，隨著網(wǎng)絡(luò)規(guī)模的增大，其消息量與其他算法的消息量的差值增大，雙層算法Dissemination+Tree有同樣的問(wèn)題。Tournament和MS中的通信模式不契合網(wǎng)絡(luò)拓?fù)洌瑢?dǎo)致通信距離比較長(zhǎng)，網(wǎng)絡(luò)規(guī)模的增長(zhǎng)，越發(fā)加劇了這種現(xiàn)象。ID1、ID2和Tree的通信模式比較契合網(wǎng)絡(luò)拓?fù)?，其中Tree是依據(jù)實(shí)際網(wǎng)絡(luò)建立的最小生成樹(shù)，從圖6（a）可以看出無(wú)斷路情況下，隨著網(wǎng)絡(luò)規(guī)模的增大Tree算法的效率基本保持不變。DLCT在較大規(guī)模的網(wǎng)絡(luò)中的效率略低于Tree算法。網(wǎng)絡(luò)斷路使得每種算法的效率都有不同程度的降低，從圖6（b）、（c）可以看出在網(wǎng)絡(luò)斷路情況下，DLCT的斜率比Tree低，更適應(yīng)斷路情況。

Fig.6 Delay of Barrier algorithms in different break rates of link圖6 Barrier算法在不同斷路率下的延時(shí)

4.4 DLCT在網(wǎng)絡(luò)斷路下的效率

從圖6可以看出雙層DLCT與Tree算法的效率比較高。實(shí)驗(yàn)進(jìn)一步比較斷路情況對(duì)DLCT與Tree的效率的影響。如圖7所示的橫向5組實(shí)驗(yàn)分別是3種算法在不同網(wǎng)絡(luò)規(guī)模下的運(yùn)行時(shí)間，每組中的3條豎線分別為對(duì)應(yīng)算法在斷路率為[0%，50%]的網(wǎng)絡(luò)中運(yùn)行時(shí)間的范圍，線上的黑點(diǎn)為算法在不同斷路率下對(duì)應(yīng)的運(yùn)行時(shí)間?？梢钥闯鰞煞N結(jié)構(gòu)的DLCT的兩種算法ID和ID2都比Tree算法效率高，能達(dá)到30%到50%的效率提升。比較線段最低點(diǎn)（斷路率為0的情況）Tree算法跟DLCT算法的效率相差不大，但是在斷路情況下Tree算法效率急劇下降，圖7所示的Tree算法的線條長(zhǎng)度最長(zhǎng)便可說(shuō)明該算法受斷路影響最大。本實(shí)驗(yàn)說(shuō)明了DLCT算法能在一定程度上提高Barrier算法在網(wǎng)絡(luò)斷路情況下的效率，從而表現(xiàn)得比其他算法優(yōu)異。

Fig.7 Delay of DLCT&Tree in different break rates of link圖7 DLCT與Tree在不同斷路率下的延時(shí)

5 結(jié)束語(yǔ)

本文針對(duì)網(wǎng)絡(luò)斷路情況下同步算法效率急劇下降的問(wèn)題，提出了DLCT Barrier算法，采用高效的LCT通信模式和低代價(jià)的AAO調(diào)整算子，用動(dòng)態(tài)調(diào)整通信模式的方式避開(kāi)網(wǎng)絡(luò)斷路提高算法效率。與現(xiàn)有的Barrier算法比較，DLCT在不同網(wǎng)絡(luò)斷路情況下算法效率提高30%到50%。

除了網(wǎng)格型網(wǎng)絡(luò)，DLCT還可以應(yīng)用于其他網(wǎng)絡(luò)拓?fù)?，如?jié)點(diǎn)隨機(jī)分布的傳感網(wǎng)絡(luò)，根據(jù)節(jié)點(diǎn)距離依次編號(hào)(x，y)位置形成num映射表就能完成到傳感器網(wǎng)絡(luò)的應(yīng)用。此外后續(xù)工作還可以通過(guò)對(duì)judge函數(shù)進(jìn)行優(yōu)化，更有效調(diào)整通信模式。