GraphHP:一個(gè)圖迭代處理的混合平臺(tái)

蘇靜,索博,陳群,潘魏,李戰(zhàn)懷

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,西安710072)

GraphHP:一個(gè)圖迭代處理的混合平臺(tái)

蘇靜,索博,陳群,潘魏,李戰(zhàn)懷

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,西安710072)

BSP(Bulk Synchronous Parallel,BSP)計(jì)算模型是建立大規(guī)模迭代式圖處理分布式系統(tǒng)的重要基礎(chǔ).現(xiàn)有平臺(tái)(如Pregel、Giraph、Hama)雖然已經(jīng)實(shí)現(xiàn)了較高的可擴(kuò)展性,但主機(jī)之間高頻同步和通信負(fù)荷嚴(yán)重影響了并行計(jì)算的效率.為了解決這個(gè)關(guān)鍵性問(wèn)題,本文提出了一種基于混合式模型的執(zhí)行平臺(tái)GraphHP(Graph Hybrid Processing).它不僅繼承了以頂點(diǎn)為中心的BSP編程接口,而且能夠顯著減少同步和通信負(fù)荷.通過(guò)在圖分區(qū)內(nèi)部和分區(qū)之間建立混合執(zhí)行模型,GraphHP實(shí)現(xiàn)了偽超步迭代計(jì)算,把分區(qū)內(nèi)部計(jì)算從分布式同步和通信中分離出來(lái).這種混合執(zhí)行模型不需要繁重的調(diào)度算法或者以圖為中心的串行算法,就能有效減少同步和通信負(fù)荷.最后,本文評(píng)估了經(jīng)典的BSP應(yīng)用在GraphHP平臺(tái)的實(shí)現(xiàn)方式.實(shí)驗(yàn)表明它比現(xiàn)有的BSP實(shí)現(xiàn)平臺(tái)效率更高.本文提出的GraphHP平臺(tái)雖然是基于Hama實(shí)現(xiàn)的,但它很容易遷移到其他的BSP平臺(tái).

圖迭代;分布式計(jì)算;BSP;GraphHP

0 引言

目前越來(lái)越多的大數(shù)據(jù)應(yīng)用都聚焦于具有復(fù)雜數(shù)據(jù)依賴關(guān)系的圖模型,如各種社交網(wǎng)絡(luò)、Web圖、生物基因網(wǎng)絡(luò)等都需要利用圖模型進(jìn)行計(jì)算處理.圖模型的計(jì)算離不開(kāi)迭代,迭代的本質(zhì)就是對(duì)目前系統(tǒng)的一系列狀態(tài)進(jìn)行改變,特別是在大規(guī)模數(shù)據(jù)集中運(yùn)行這類算法時(shí),就需要一種快速執(zhí)行并行迭代的技術(shù).設(shè)計(jì)和實(shí)現(xiàn)大規(guī)模分布式并行處理系統(tǒng)面臨諸多挑戰(zhàn),它需要編程人員處理死鎖、數(shù)據(jù)競(jìng)爭(zhēng)、分布狀態(tài)和通信協(xié)議等問(wèn)題.現(xiàn)有的抽象并行編程模型如MapReduce和Dryad并不適合依賴分析,因此人們開(kāi)發(fā)了以頂點(diǎn)為中心的并行編程平臺(tái),如Pregel、Giraph和Hama等.這些平臺(tái)都基于BSP模型,其系統(tǒng)通過(guò)調(diào)用BSP程序中用戶自定義的超步進(jìn)行圖計(jì)算.BSP模型相對(duì)其他模型更適合于圖迭代計(jì)算,而且很容易推理圖語(yǔ)義.但目前這些平臺(tái)在進(jìn)行圖計(jì)算時(shí)收斂并不快,而且通信開(kāi)銷也較大.

為了解決上述問(wèn)題,人們開(kāi)始對(duì)BSP同步平臺(tái)進(jìn)行改進(jìn)和優(yōu)化,現(xiàn)有研究成果主要分成兩類:一類的典型代表是分布式GraphLab和Giraph++.GraphLab采用異步GAS計(jì)算模型,允許用戶直接讀取和修改鄰接點(diǎn)的數(shù)據(jù).它通過(guò)鎖機(jī)制保證數(shù)據(jù)一致性,調(diào)度代價(jià)比較高.Giraph++采用以圖為中心的編程接口,要求用戶為圖分區(qū)編寫復(fù)雜的調(diào)度算法.它的執(zhí)行效率嚴(yán)重受制于用戶編寫的程序.第二類主要是一些零碎的BSP系統(tǒng)優(yōu)化方案[1-4],盡管目前這些技術(shù)能夠減少同步和通信負(fù)荷,但它們或者是專門用于特定圖算法,具有有限的可用性,或者僅僅基于邊緣的優(yōu)化,并沒(méi)有改變BSP執(zhí)行模型低率的現(xiàn)狀.

隨著B(niǎo)SP平臺(tái)的廣泛使用,急需一種Q能解決BSP模型同步代價(jià)高和通信量大,又能保持以頂點(diǎn)為中心模型簡(jiǎn)潔性的通用平臺(tái).為此本文提出了一種新的分布式圖計(jì)算平臺(tái)GraphHP,它不僅能大幅減少同步和通信負(fù)荷,而且保留了BSP編程模型的簡(jiǎn)單性.該平臺(tái)在分區(qū)內(nèi)部執(zhí)行偽超步迭代計(jì)算,全局同步時(shí)執(zhí)行邊界點(diǎn)的迭代計(jì)算.這種混合執(zhí)行模型能有效減少同步和通信負(fù)荷,同時(shí)不需要繁重的調(diào)度開(kāi)銷.本文具體描述了此混合執(zhí)行模型,并說(shuō)明了它是如何在BSP模型上實(shí)現(xiàn)的.主要貢獻(xiàn)點(diǎn)是

·分析了現(xiàn)有BSP計(jì)算平臺(tái)的性能,總結(jié)了它們?cè)趯?shí)現(xiàn)圖迭代算法時(shí)的不足;

·建立了一個(gè)混合執(zhí)行模型.對(duì)比標(biāo)準(zhǔn)BSP執(zhí)行模型,該混合模型不僅具有較高的并行效率,而且具有較少的全局迭代次數(shù);

·設(shè)計(jì)和實(shí)現(xiàn)了混合迭代圖處理平臺(tái)GraphHP.GraphHP繼承了以頂點(diǎn)為中心的BSP編程接口,但具有不同的混合執(zhí)行模型.雖然它是基于Hama的實(shí)現(xiàn),但可以很容易地移植到其他的BSP平臺(tái);

·比較研究了經(jīng)典BSP上的算法在GraphHP的應(yīng)用,證明了GraphHP比目前BSP平臺(tái)在性能上有顯著提升.

本文組織結(jié)構(gòu)如下:第1節(jié)介紹相關(guān)工作;第2節(jié)描述BSP平臺(tái)及編程接口;第3節(jié)提出混合GraphHP執(zhí)行模型;第4節(jié)介紹GraphHP平臺(tái)的基本架構(gòu);第5節(jié)探討經(jīng)典BSP程序在GraphHP上的應(yīng)用和實(shí)驗(yàn)分析;第6節(jié)對(duì)本文進(jìn)行總結(jié),并概述未來(lái)研究的方向.

1 相關(guān)工作

盡管Google的Pregel有幾個(gè)通用的BSP實(shí)現(xiàn)庫(kù),如Green BSP庫(kù)[5]和BSPlib[6],但都沒(méi)有提供圖計(jì)算相關(guān)的應(yīng)用程序編程接口(Application Programming Interface,API),而且不涉及頂點(diǎn)為中心的編程接口.并行平臺(tái)BGL[7]和CGM[8]提供了多點(diǎn)接口(Multi Point Interface,MPI)上使用的圖計(jì)算API,但沒(méi)有提供頂點(diǎn)為中心的編程接口,同時(shí)也沒(méi)有處理關(guān)鍵性的容錯(cuò)問(wèn)題.除GraphLab之外,還有其他異步抽象平臺(tái);但這些平臺(tái)并不確?？纱行?或者提供足夠的從數(shù)據(jù)競(jìng)爭(zhēng)中恢復(fù)數(shù)據(jù)的機(jī)制.GRACE[9]是建立在單臺(tái)機(jī)器上的異步圖處理平臺(tái),采用類似以頂點(diǎn)為中心的編程接口,但使用用戶定義的頂點(diǎn)調(diào)度和消息選擇機(jī)制支持異步計(jì)算.盡管這些異步平臺(tái)能夠加速收斂計(jì)算,但仍需要大量的調(diào)度負(fù)荷.

還有其他混合平臺(tái)如Trinity[10]和Kineograph[11].Trinity在分布式內(nèi)存上存儲(chǔ)圖數(shù)據(jù),支持聯(lián)機(jī)圖處理,它使用類似于BSP平臺(tái)的執(zhí)行模型進(jìn)行脫機(jī)處理.Kineograph用于存儲(chǔ)連續(xù)變化圖的分布式系統(tǒng),也是以頂點(diǎn)為中心的計(jì)算模型,但在它上面的圖挖掘算法仍然在動(dòng)態(tài)圖的靜態(tài)快照上執(zhí)行.

2 BSP平臺(tái)和編程接口

由于BSP模型的可擴(kuò)展性、靈活性和以頂點(diǎn)為中心編程的易用性,出現(xiàn)了很多BSP平臺(tái)(如Pregel、Hama、Giraph),這些平臺(tái)都適合具有依賴的圖迭代計(jì)算.BSP同步模型不需要編程者指定迭代執(zhí)行順序,確保了系統(tǒng)中程序沒(méi)有死鎖和數(shù)據(jù)爭(zhēng)用.如果給定足夠的并行松弛,BSP程序的性能與異步程序相比是具有競(jìng)爭(zhēng)性的.Hama是開(kāi)源BSP的實(shí)現(xiàn),編程接口主要由頂點(diǎn)類(Vertex class)、聚合類(Aggregator class)和組合類(Combiner class)組成.Vertex class是最重要的類,負(fù)責(zé)構(gòu)建頂點(diǎn)的行為,并維護(hù)它們的狀態(tài).compute()(計(jì)算函數(shù))方法使用消息迭代器檢查接受到的消息,定義每個(gè)超步中活躍頂點(diǎn)的行為,同時(shí)sendMessage()(發(fā)送消息函數(shù)).Aggregator class是一種全局通信和檢測(cè)的機(jī)制,每個(gè)頂點(diǎn)在超步(S)提交一個(gè)值給聚合器(aggregator),aggregator合并接收到的值,并把合并后的新值在進(jìn)行超步(S+1)計(jì)算前發(fā)送給各個(gè)頂點(diǎn).Aggregator class提供的典型操作如min、max和sum.Combiner class用于減少通信負(fù)荷,聚合發(fā)送給同一個(gè)頂點(diǎn)的多個(gè)消息為一個(gè).這個(gè)優(yōu)化要求用戶在combiner()(組合函數(shù))中指定合并規(guī)則.集群上BSP程序由一個(gè)主機(jī)(master)和多個(gè)從機(jī)(worker)組成.master不參與具體的計(jì)算,主要負(fù)責(zé)worker之間的協(xié)調(diào).每個(gè)worker負(fù)責(zé)一個(gè)或多個(gè)分區(qū)的計(jì)算,給每一個(gè)分區(qū)啟動(dòng)一個(gè)BSPPeer計(jì)算進(jìn)程.使用BSP平臺(tái)實(shí)現(xiàn)某些標(biāo)準(zhǔn)的圖算法(如強(qiáng)關(guān)聯(lián)圖分量、最小生成森林和圖著色),尤其是許多機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法(如信念傳播和隨機(jī)優(yōu)化)可能導(dǎo)致較低的收斂率.

3 混合執(zhí)行模型

在詳細(xì)描述混合模型之前,先給出一些符號(hào)表示來(lái)簡(jiǎn)化表示.

定義1(本地頂點(diǎn)和邊界點(diǎn))一個(gè)圖分區(qū)內(nèi)部,如果頂點(diǎn)v與它入邊的所有頂點(diǎn)在同一個(gè)分區(qū),則該頂點(diǎn)被稱為本地頂點(diǎn).否則,v至少有一個(gè)入邊的頂點(diǎn)位于遠(yuǎn)程分區(qū)中,則被稱為邊界點(diǎn).

定義2(本地計(jì)算和邊界計(jì)算)一個(gè)本地頂點(diǎn)的compute()操作被稱為本地計(jì)算.邊界點(diǎn)操作被稱為邊界計(jì)算.

本文所提出的混合計(jì)算模型建立在傳統(tǒng)BSP基礎(chǔ)上,通過(guò)實(shí)現(xiàn)異步消息通信機(jī)制優(yōu)化性能.該混合計(jì)算模型由一系列的全局迭代組成,每個(gè)全局迭代由“計(jì)算-通信-同步”三階段組成,其中把計(jì)算分成全局計(jì)算和本地計(jì)算兩部分.本地計(jì)算由一系列連續(xù)的內(nèi)部迭代組成,并且在內(nèi)部迭代過(guò)程中支持異步操作.本地計(jì)算完成后,要把全局計(jì)算和本地計(jì)算階段中發(fā)送給臨界頂點(diǎn)的消息通過(guò)網(wǎng)絡(luò)傳輸給其他計(jì)算節(jié)點(diǎn),接著該混合執(zhí)行引擎進(jìn)行全局通信和同步過(guò)程,然后開(kāi)始下一次全局迭代的計(jì)算,直到算法終止.可以看出,本地計(jì)算并不需要直接與其他分區(qū)通信,邊界計(jì)算需要不同分區(qū)上的遠(yuǎn)程通信.

如圖1(b)所示,該混合執(zhí)行模型是抽象的.如標(biāo)準(zhǔn)的BSP模型一樣,混合模型需要同樣的初始化迭代.在第一次初始化迭代(迭代0)時(shí),所有的頂點(diǎn)都是積極活躍的(active),由用戶分配初始化值,并發(fā)送消息給鄰接點(diǎn).從迭代1開(kāi)始,重復(fù)性的調(diào)用全局階段和本地階段.在全局階段,每個(gè)active的邊界頂點(diǎn)使用之前超步中發(fā)送給它的消息作為輸入,執(zhí)行compute(),確保每個(gè)邊界點(diǎn)使用鄰接點(diǎn)最新的消息參與計(jì)算.

圖1 標(biāo)準(zhǔn)和混合計(jì)算模型對(duì)比圖Fig.1Standard calculation model and hybrid contrast figure

4 基本架構(gòu)

盡管是混合執(zhí)行模型,但本地和邊界頂點(diǎn)的行為都在Vertex class中被同一個(gè)compute()定義.頂點(diǎn)之間的通信通過(guò)Vertex class中的sendMessage()傳遞獲取.在標(biāo)準(zhǔn)的BSP平臺(tái)上,寫GraphHP程序涉及預(yù)先定義的Vertex class的子類,此外用戶可以指定邊界點(diǎn)是否參與本地階段計(jì)算.在迭代時(shí),一個(gè)邊界點(diǎn)可能收到另外一個(gè)頂點(diǎn)的多個(gè)消息,這時(shí)用戶通過(guò)指定combine()合并這些消息.GraphHP提供了一個(gè)額外的函數(shù)sourcecombine()(源端組合函數(shù)),合并同一個(gè)發(fā)送者發(fā)給一個(gè)頂點(diǎn)的所有消息,同時(shí)用戶可以自定義任何需要合并的規(guī)則.GraphHP的實(shí)現(xiàn)并沒(méi)有重新設(shè)計(jì)Hama的分布式架構(gòu)、通信和同步機(jī)制,僅僅涉及輕微的系統(tǒng)調(diào)整,所以它的實(shí)現(xiàn)可以很容易推廣到其他BSP平臺(tái).

GraphHP執(zhí)行初始化迭代跟Hama初始化方式一樣.第一次迭代后,master命令每一個(gè)worker重復(fù)地執(zhí)行全局階段和本地階段.worker在迭代中給每一個(gè)分區(qū)分配一個(gè)線程執(zhí)行全局和本地階段.全局階段循環(huán),通過(guò)調(diào)用active的邊界點(diǎn)執(zhí)行compute().本地階段迭代調(diào)用偽超步.在每一個(gè)偽超步中,線程循環(huán)通過(guò)active本地頂點(diǎn)和執(zhí)行compute().GraphHP利用基于Hama的超步機(jī)制實(shí)現(xiàn)全局迭代階段.worker首先定義是否接收者和發(fā)送者位于同一個(gè)分區(qū):如果是,消息直接放到目的頂點(diǎn)的入邊消息隊(duì)列;否則,消息將會(huì)暫時(shí)被緩存,之后會(huì)通過(guò)Hama上的RPC(Remote Procedure Call Protocol,遠(yuǎn)程過(guò)程調(diào)用協(xié)議)傳輸.由于不同分區(qū)之間傳輸?shù)南?huì)在下一個(gè)階段處理,所以僅僅要求在每個(gè)迭代開(kāi)始前傳輸.當(dāng)一個(gè)分區(qū)完成全局階段,它立刻進(jìn)入一個(gè)本地階段,不需要通知master去轉(zhuǎn)化.

GraphHP繼承了Hama的容錯(cuò)機(jī)制,通過(guò)設(shè)置檢查點(diǎn)來(lái)進(jìn)行容錯(cuò)處理.在全局或本地階段的開(kāi)始前,master通知所有worker保存每個(gè)分區(qū)的狀態(tài)信息到HDFS(Hadoop Distributed File System,Hadoop的文件系統(tǒng))上,包含頂點(diǎn)的值、邊值、頂點(diǎn)的狀態(tài)和接收到的消息隊(duì)列.由于一個(gè)分區(qū)中總是頻繁地執(zhí)行本地計(jì)算,因此GraphHP選擇在本地階段制定多個(gè)檢查點(diǎn).master周期性地發(fā)送“ping”消息給worker來(lái)檢測(cè)worker的健康狀態(tài),如果master沒(méi)有在指定的時(shí)間收到回應(yīng),將會(huì)標(biāo)記worker為不成功的、失敗的(failed).當(dāng)一個(gè)worker是failed時(shí),master把圖分區(qū)重新分配到健康的worker上,新的worker將從最近的檢查點(diǎn)重新加載分區(qū).

5 實(shí)驗(yàn)研究

這一部分分別評(píng)估3個(gè)算法,即最短路徑、PageRank和二分圖在GraphHP上的性能.使用傳統(tǒng)BSP平臺(tái)Hama和它的優(yōu)化版本AM-Hama.AM-Hama是像Hama一樣的執(zhí)行平臺(tái),即使用異步的方式處理消息.如果消息發(fā)送給遠(yuǎn)程分區(qū)上的頂點(diǎn),它通過(guò)Hama上的RPC分布式機(jī)制傳輸,這時(shí)消息會(huì)被下一個(gè)超步處理;否則,在內(nèi)存處理,直接放到目的頂點(diǎn)的入邊消息隊(duì)列.在GraphHP中,如果應(yīng)用需要的話,邊界點(diǎn)參與本地計(jì)算,異步消息機(jī)制被激活.

5.1 實(shí)驗(yàn)設(shè)置

表1中給出了測(cè)試數(shù)據(jù)的細(xì)節(jié),前5個(gè)數(shù)據(jù)集都是典型的長(zhǎng)尾分布圖,被用于評(píng)估算法性能,最后的Delaunay n24是一個(gè)Delaumay圖廣泛用于圖分區(qū)評(píng)估和聚類算法.最大匹配是圖分區(qū)和聚類的基本操作,本文使用Delaunay n24數(shù)據(jù)集評(píng)估BM算法.使用的集群是1個(gè)master和12個(gè)worker.每個(gè)機(jī)器運(yùn)行環(huán)境為Ubuntu Linux(10.04版本),16 G內(nèi)存,160G磁盤存儲(chǔ)和16核AMD Opteron(TM)處理器,具有2600 MHZ的頻率,通過(guò)1 Gbit以太網(wǎng)互聯(lián).

我們基于Hama平臺(tái)實(shí)現(xiàn)GraphHP.默認(rèn)Hama通過(guò)hash函數(shù)(hash(id)mod k)分配一個(gè)頂點(diǎn)給一個(gè)分區(qū),其中id是頂點(diǎn)標(biāo)識(shí)符,k是分區(qū)數(shù)量.很明顯,hash分區(qū)結(jié)果會(huì)導(dǎo)致大量跨分區(qū)的邊.好的分區(qū)應(yīng)該最小化跨分區(qū)的邊數(shù)量,減少分布式計(jì)算的通信負(fù)荷.使用圖分區(qū)啟發(fā)式Metis[14]可產(chǎn)生更好的分區(qū).當(dāng)輸入圖很大不能被單個(gè)機(jī)器處理時(shí),可以采用并行版本ParMetis[15]并行多層k-way圖分區(qū),它是一種基于圖粗化[16]的分區(qū)方法.本文中我們只是使用ParMetis分割測(cè)試圖,分配頂點(diǎn)產(chǎn)生分區(qū),從而評(píng)估不同分布式平臺(tái)的性能.關(guān)于不同分區(qū)方法的優(yōu)略問(wèn)題的研究不在本文討論的范疇之內(nèi).

表1 數(shù)據(jù)集信息Tab.1Dataset information

5.2 最短路徑

單源最短路徑(Single Source Shortest Path,SSSP)[17]算法用于搜索圖中源頂點(diǎn)到其他所有頂點(diǎn)的最短距離.在該算法中,初始源頂點(diǎn)的值是0,其他頂點(diǎn)的值設(shè)置為∞.初始源頂點(diǎn)廣播自己的值給直接鄰居,鄰居反過(guò)來(lái)更新自己值并發(fā)送消息給它的鄰居.在Hama上,一個(gè)超步僅僅傳播一個(gè)頂點(diǎn)距離的值.由于每個(gè)頂點(diǎn)僅僅關(guān)心最短距離,只有收到一個(gè)較小的距離時(shí)才進(jìn)行更新.

Hama、AM-Hama和GraphHP的性能采用3個(gè)度量標(biāo)準(zhǔn):全局迭代次數(shù);網(wǎng)絡(luò)通信數(shù)量;執(zhí)行時(shí)間.在USA-Road-Full上結(jié)果數(shù)據(jù)集很小,108個(gè)分區(qū)的詳細(xì)結(jié)果在表2中給出,其中,I代表迭代次數(shù),M代表網(wǎng)絡(luò)消息量,T代表執(zhí)行時(shí)間.與Hama相比,AM-Hama節(jié)省了較大的網(wǎng)絡(luò)消息量,但僅僅減少了很少的迭代次數(shù).GraphHP執(zhí)行效果遠(yuǎn)遠(yuǎn)超出另外兩個(gè).

表2 SSSP在USA-Road上的評(píng)估結(jié)果Tab.2SSSP evaluation results on USA-Road-Full

5.3 PageRank

PageRank[17]屬于典型的隨機(jī)游走算法.利用網(wǎng)頁(yè)相互鏈接關(guān)系對(duì)網(wǎng)頁(yè)進(jìn)行組織排名,確定出每個(gè)網(wǎng)頁(yè)的重要級(jí)別,用PageRank值表示.

算法1:The Compute()Function for Incremental PageRank //Δ is the user-defined convergence tolerance; if getSuperstepCount()==0 then setValue(0); updateValue=0.15; else updateValue=sum(Msg); if updateValue＞Δ then setValue(getValue()+updateValue); for u∈N(v)do sendMessage(u,updateValue/|N(v)|); voteToHalt();

算法1中給出了增量式PageRank的偽代碼.在該增量式PageRank算法中,把每次接收到的消息累加到頂點(diǎn)當(dāng)前的值,而且只是把中間更新值Δv按照計(jì)算公式計(jì)算后的值發(fā)送給鄰接頂點(diǎn),這樣重復(fù)迭代,直到每個(gè)頂點(diǎn)的值收斂到一個(gè)預(yù)定義的容忍度.對(duì)于增量式算法,邊界點(diǎn)可以參與本地階段的計(jì)算.具體而言,GraphHP上增量式PageRank算法的初始化迭代跟經(jīng)典式PageRank相同,接著進(jìn)入第二次迭代的全局超步,每個(gè)分區(qū)更新邊界點(diǎn)的PageRank值.然后執(zhí)行本地階段,參與頂點(diǎn)包括本地和邊界頂點(diǎn),通過(guò)偽超步迭代更新PageRank值,直到所有值收斂.迭代重復(fù)調(diào)用直到所有頂點(diǎn)不活躍,且沒(méi)有消息傳輸,標(biāo)志著頂點(diǎn)的PageRank值已經(jīng)收斂.在迭代時(shí),如果一個(gè)頂點(diǎn)發(fā)送多個(gè)消息給同一個(gè)頂點(diǎn),使用用戶定義的Combine()對(duì)在傳輸之前的所有更新值進(jìn)行合并.GraphHP有效地壓縮收斂計(jì)算到本地階段中一個(gè)分區(qū)內(nèi)部,減少了全局同步和通信的頻率.

圖2 PageRank的可擴(kuò)展性評(píng)估Fig.2Scalability evaluation of PageRank

圖2中分析了在Web-Google和UK-2002兩個(gè)數(shù)據(jù)集上,隨著同一數(shù)據(jù)分區(qū)數(shù)目的增加,系統(tǒng)的性能變化規(guī)律,收斂誤差值Δ設(shè)置為1 E-5.兩個(gè)數(shù)據(jù)集的最大分區(qū)數(shù)目分別設(shè)置為14和108.因?yàn)檫M(jìn)一步增加分區(qū)數(shù)目并不能提高并行性能,同時(shí)由于3個(gè)系統(tǒng)的通信消息量相差較大,所以圖中的消息量均取以10為底的對(duì)數(shù)(log)來(lái)表示.實(shí)驗(yàn)結(jié)果表明,GraphHP系統(tǒng)在迭代次數(shù)、通信消息量和執(zhí)行時(shí)間這3個(gè)方面都要明顯優(yōu)于Hama和AM-Hama.雖然異步消息傳遞機(jī)制在兩個(gè)數(shù)據(jù)集上均能有效減少全局迭代次數(shù)和通信消息量,使得AM-Hama的性能相比Hama具有一定的優(yōu)勢(shì),但是根據(jù)實(shí)驗(yàn)結(jié)果,GraphHP系統(tǒng)的性能比AM-Hama還要好,說(shuō)明GraphHP系統(tǒng)采用的混合計(jì)算模型能進(jìn)一步減少全局迭代次數(shù)和通信消息量,能有效減少全局分布式的通信和同步代價(jià).分析上圖的實(shí)驗(yàn)結(jié)果,可以發(fā)現(xiàn)隨著分區(qū)數(shù)目的增加,GraphHP系統(tǒng)的迭代次數(shù)和通信消息量只是稍有增長(zhǎng).因此,GraphHP系統(tǒng)具有良好的可擴(kuò)展性.

5.4 二分圖匹配

二分圖[18]由兩類不同的頂點(diǎn)集合組成,它們之間僅僅有連接不同集合的邊存在.二分圖匹配由沒(méi)有共同端點(diǎn)的邊子集組成.二分圖匹配問(wèn)題(Bipartite Matching,BM)是找到最大匹配,添加任何邊都可能導(dǎo)致至少兩條邊共享一個(gè)端點(diǎn).算法要求頂點(diǎn)在不同階段處理不同類型的消息.由于GraphHP是異步執(zhí)行模型,要求為握手機(jī)制建立左右端頂點(diǎn)的匹配.在算法實(shí)現(xiàn)中左端頂點(diǎn)有兩種狀態(tài):不相配的(unmatched)和相配的(matched).右邊頂點(diǎn)有3種狀態(tài):不準(zhǔn)許(ungranted);準(zhǔn)許(granted);matched.ungranted狀態(tài)指右端頂點(diǎn)沒(méi)有準(zhǔn)許(grant)該匹配的請(qǐng)求.granted狀態(tài)指右端頂點(diǎn)已經(jīng)grant一個(gè)匹配的請(qǐng)求,發(fā)送grant消息,但是沒(méi)有收到接受(accept)消息.granted狀態(tài)中的右邊頂點(diǎn)不能grant任何新的匹配請(qǐng)求,但是發(fā)送拒絕(deny)消息給每個(gè)需求者(requester).表3是二分圖匹配在2個(gè)數(shù)據(jù)集上的評(píng)估結(jié)果,即Cit-patent和Delaunay n24,分別分為18個(gè)和48個(gè)分區(qū).在Cit-patent上,Hama只要求20+次迭代,GraphHP減少了3倍的迭代次數(shù),只需要7次.同時(shí)執(zhí)行時(shí)間從原本需要42 s減少到13 s.與Hama相比,AM-Hama能夠減少通信負(fù)荷,但僅僅減少了少量的迭代次數(shù).從結(jié)果可以看到,GraphHP在每個(gè)指標(biāo)上超出AM-Hama較大的量.

表3 BM評(píng)估結(jié)果Tab.3BM evaluation results

6 總結(jié)和未來(lái)工作

目前在BSP平臺(tái)上實(shí)現(xiàn)大規(guī)模復(fù)雜圖迭代算法仍具有較大挑戰(zhàn),因?yàn)橥降旧砭哂械却屯ㄐ懦杀?本文中提出了一種新的圖計(jì)算混合執(zhí)行模型,通過(guò)在每個(gè)全局迭代中加入一系列基于本地迭代的偽超步,優(yōu)化同步等待和通信成本,并進(jìn)一步基于Hama建立了GraphHP混合平臺(tái),證明了該模型在BSP中具有可實(shí)現(xiàn)性.

未來(lái)的工作將集中在多個(gè)方面,圖中頂點(diǎn)由于在偽超步迭代過(guò)程中沒(méi)有和其他分區(qū)的頂點(diǎn)通信,在后面的全局迭代中會(huì)同時(shí)收到多個(gè)階段的消息,導(dǎo)致頂點(diǎn)在全局階段消耗過(guò)多計(jì)算時(shí)間.因此如何在加速偽超步迭代的同時(shí)不犧牲以頂點(diǎn)為中心編程的統(tǒng)一性成為一項(xiàng)有趣的研究.另一方面,負(fù)載均衡技術(shù)對(duì)BSP的高效處理也非常重要.現(xiàn)有的BSP負(fù)載均衡技術(shù)[4,19]都是標(biāo)準(zhǔn)的執(zhí)行引擎,因此另一個(gè)研究方向就是為GraphHP設(shè)計(jì)一個(gè)有效的負(fù)載均衡方法.

［1］SALIHOGLU S,WIDOM J.Optimizing graph algorithms on pregel-like systems[J].Proceedings of the VLDB Endowment,2014,7(7):577-588.

［2］SALIHOGLUS,WIDOMJ.GPS:Agraphprocessing system[C]//Proceedings ofthe25thInternational Conference on Scientific and Statistical Database Management.ACM,2013,Article No 22,doi: 10.1145/2484838.2484843.

［3］BAO N T,SUZUMURA T.Towards highly scalable pregel-based graph processing platform with x10 [C]//Proceedings of the 22nd International Conference on World Wide Web.ACM,2013:501-508.

［4］CHEN R S,YANG M,WENG X T,et al.Improving large graph processing on partitioned graphs in the cloud[C]//Proceedings of the 3rd ACM Symposium on Cloud Computing.ACM,2012,Article No 3,doi: 10.1145/2391229.2391232.

［5］GOUDREAU M W,LANG K,RAO S B,et al.Portable and efficient parallel computing using the bsp model [J].Computers IEEE Transactions on,1999,48(7):670-689.

［6］HILL J M D,MCCOL B,STEFANESCU D C,et al.BSPlib:The BSP programming library[J].Parallel Computing,1998,24(14):1947-1980.

［7］GREGOR D,LUMSDAINE A.The Parallel BGL:A generic library for distributed graph computations [C]//Proceedings of the Parallel Object-Oriented Scientific Computing(POOSC).2005:1-18.

［8］CHAN A,DEHNE F.CGMGRAPH/CGMLIB:Implementing and testing CGM graph algorithms on PC clusters and shared memory machines[J].Lecture Notes in Computer Science,2003,2840:117-125.

［9］WANGG Z,XIE W L,DEMERS A,et al.Asynchronous large-scale graph processing made easy [C]//Proceedings of the 6th Biennial Conference on Innovative Data Systems Research(CIDR).2013:58-70.

［10］SHAO B,WANG H,LI Y.Trinity:A distributed graph engine on a memory cloud[C]//Proceedings of the ACM-SIGMOD International Conference on Management of Data.ACM,2013:505-516.

［11］CHENG R,HONG J,KYROLA A,et al.Kineograph:Taking the pulse of a fast-changing and connected world [C]//Proceedings of the 7th ACM European Conference on Computer Systems.ACM,2012:85-98.

［12］DEMETRESCU C.USA road network[EB/OL].(2005-10-12)[2016-04-01].http://www.dis.uniroma1.it/ challenge9/download.shtml.

［13］DAVIST.TheUniversityofFloridasparsematrixcollection[EB/OL].(2011-10-13)[2016-04-01]. http://www.cise.ufl.edu/research/sparse/matrices/.

［14］KARYPIS G,KUMAR V.A fast and high quality multilevel scheme for partitioning irregular graphs[J].SIAM J Sci Comput,1998,20(1):359-392.

［15］KARYPIS G,KUMAR V.A coarse-grain parallel formulation of multilevel k-way graph partitioning algorithm [C]//Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing.1997:1-12.

［16］TIAN Y Y,BALMIN A,CORSTEN S A,et al.From“think like a vertex”to“think like a graph”[J].Proceedings of the VLDB Endowment,2013,7(3):193-204.

［17］CHERKASSKY B V,GOLDBERG A V,RADZIK T.Shortest paths algorithms:Theory and experimental evaluation[J].Mathematical Programming,1996,73(2):129-174.

［18］ANDERSON T,OWICKI S,SAXE J,et al.High-speed switch scheduling for local-area networks[J].ACM Sigplan Notices,1993,11(4):319-352.

［19］KHAYYAT Z,AWARA K,ALONAZI A,et al.Mizan:A system for dynamic load balancing in large-scale graph processing[C]//Proceedings of the 8th ACM European Conference on Computer Systems.ACM,2013:169-182.

(責(zé)任編輯:李藝)

GraphHP:A hybrid platform for iterative graph processing

SU Jing,SUO Bo,CHEN Qun,PAN Wei,LI Zhan-huai
(School of Computer,Northwestern Polytechnical University,Xi’an,710072,China)

BSP(Bulk Synchronous Parallel)computing model is an important foundation for the establishment of a large-scale iterative graph processing distributed system. Existing platforms(e.g.,Pregel,Giraph,and Hama)have achieved a high scalability, but the high frequency synchronization and communication load between the hosts have seriously affected the efficiency of parallel computing.In order to solve this key problem, this paper proposes a hybrid model based on GraphHP(Graph Hybrid Processing).It not only inherits the BSP programming interface with the vertex as the center,but also can significantly reduce the synchronization and communication load.By establishing the hybrid execution model between the interior and the interval partition of the graph, the GraphHP realizes the pseudo super step iteration calculation,and separates the internal computation from the distributed synchronization and communication.This hybrid execution model does not need heavy scheduling algorithm or the serial algorithmcan effectively reduce the synchronization and communication load.Finally,this paper evaluates the implementation of the classic BSP application in the GraphHP platform,and the experiment shows that it is more efficient than the existing BSP platform.Although the GraphHP platform proposed in this paper is based on Hama,it is easy to migrate to other BSP platforms.

graph iterative;distributed computation;BSP;GraphHP

TP311

A

10.3969/j.issn.1000-5641.2016.05.013

1000-5641(2016)05-0112-09

2016-05

國(guó)家973計(jì)劃項(xiàng)目(2012CB316203);國(guó)家863計(jì)劃項(xiàng)目(2015AA015307);國(guó)家自然科學(xué)基金(61332006,61472321,61502390).

蘇靜,女,博士研究生,研究方向?yàn)榇髷?shù)據(jù)處理技術(shù).E-mail:jinjin-su@163.com.