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

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

GraphHP:一個圖迭代處理的混合平臺

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

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

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

圖迭代;分布式計算;BSP;GraphHP

0 引言

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

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

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

·分析了現(xiàn)有BSP計算平臺的性能,總結(jié)了它們在實現(xiàn)圖迭代算法時的不足;

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

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

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

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

1 相關(guān)工作

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

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

2 BSP平臺和編程接口

由于BSP模型的可擴(kuò)展性、靈活性和以頂點為中心編程的易用性,出現(xiàn)了很多BSP平臺(如Pregel、Hama、Giraph),這些平臺都適合具有依賴的圖迭代計算.BSP同步模型不需要編程者指定迭代執(zhí)行順序,確保了系統(tǒng)中程序沒有死鎖和數(shù)據(jù)爭用.如果給定足夠的并行松弛,BSP程序的性能與異步程序相比是具有競爭性的.Hama是開源BSP的實現(xiàn),編程接口主要由頂點類(Vertex class)、聚合類(Aggregator class)和組合類(Combiner class)組成.Vertex class是最重要的類,負(fù)責(zé)構(gòu)建頂點的行為,并維護(hù)它們的狀態(tài).compute()(計算函數(shù))方法使用消息迭代器檢查接受到的消息,定義每個超步中活躍頂點的行為,同時sendMessage()(發(fā)送消息函數(shù)).Aggregator class是一種全局通信和檢測的機(jī)制,每個頂點在超步(S)提交一個值給聚合器(aggregator),aggregator合并接收到的值,并把合并后的新值在進(jìn)行超步(S+1)計算前發(fā)送給各個頂點.Aggregator class提供的典型操作如min、max和sum.Combiner class用于減少通信負(fù)荷,聚合發(fā)送給同一個頂點的多個消息為一個.這個優(yōu)化要求用戶在combiner()(組合函數(shù))中指定合并規(guī)則.集群上BSP程序由一個主機(jī)(master)和多個從機(jī)(worker)組成.master不參與具體的計算,主要負(fù)責(zé)worker之間的協(xié)調(diào).每個worker負(fù)責(zé)一個或多個分區(qū)的計算,給每一個分區(qū)啟動一個BSPPeer計算進(jìn)程.使用BSP平臺實現(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ì)描述混合模型之前,先給出一些符號表示來簡化表示.

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

定義2(本地計算和邊界計算)一個本地頂點的compute()操作被稱為本地計算.邊界點操作被稱為邊界計算.

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

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

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

4 基本架構(gòu)

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

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

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

5 實驗研究

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

5.1 實驗設(shè)置

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

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

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

5.2 最短路徑

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

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

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

5.3 PageRank

PageRank[17]屬于典型的隨機(jī)游走算法.利用網(wǎng)頁相互鏈接關(guān)系對網(wǎng)頁進(jìn)行組織排名,確定出每個網(wǎng)頁的重要級別,用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算法中,把每次接收到的消息累加到頂點當(dāng)前的值,而且只是把中間更新值Δv按照計算公式計算后的值發(fā)送給鄰接頂點,這樣重復(fù)迭代,直到每個頂點的值收斂到一個預(yù)定義的容忍度.對于增量式算法,邊界點可以參與本地階段的計算.具體而言,GraphHP上增量式PageRank算法的初始化迭代跟經(jīng)典式PageRank相同,接著進(jìn)入第二次迭代的全局超步,每個分區(qū)更新邊界點的PageRank值.然后執(zhí)行本地階段,參與頂點包括本地和邊界頂點,通過偽超步迭代更新PageRank值,直到所有值收斂.迭代重復(fù)調(diào)用直到所有頂點不活躍,且沒有消息傳輸,標(biāo)志著頂點的PageRank值已經(jīng)收斂.在迭代時,如果一個頂點發(fā)送多個消息給同一個頂點,使用用戶定義的Combine()對在傳輸之前的所有更新值進(jìn)行合并.GraphHP有效地壓縮收斂計算到本地階段中一個分區(qū)內(nèi)部,減少了全局同步和通信的頻率.

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

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

5.4 二分圖匹配

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

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

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

目前在BSP平臺上實現(xiàn)大規(guī)模復(fù)雜圖迭代算法仍具有較大挑戰(zhàn),因為同步迭代本身具有等待和通信成本.本文中提出了一種新的圖計算混合執(zhí)行模型,通過在每個全局迭代中加入一系列基于本地迭代的偽超步,優(yōu)化同步等待和通信成本,并進(jìn)一步基于Hama建立了GraphHP混合平臺,證明了該模型在BSP中具有可實現(xiàn)性.

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

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

蘇靜,女,博士研究生,研究方向為大數(shù)據(jù)處理技術(shù).E-mail:jinjin-su@163.com.