復雜網絡松耦合分布式計算框架的設計與實現

盧 罡，徐勤良，許南山，郭俊霞

（北京化工大學信息科學與技術學院，北京100029）

復雜網絡松耦合分布式計算框架的設計與實現

盧 罡，徐勤良，許南山，郭俊霞

（北京化工大學信息科學與技術學院，北京100029）

為更快地計算大尺度復雜網絡結構的相關參數，設計并實現一種松耦合分布式計算框架。將分散于網絡中的松耦合計算節點匯集起來，通過任務隊列使各計算節點共同參與復雜網絡的相關分布式計算，并能隨時加入或者退出計算，利用分散于網絡中松耦合的計算節點提高復雜網絡相關分析的計算速度。基于該框架，實現對大尺度復雜網絡的平均最短路徑長度、網絡直徑和網絡效率的分布式計算。實驗結果表明，在保證計算結果正確的前提下，該框架可充分利用網絡中閑散的計算資源，提高運算效率。

復雜網絡；分布式計算；因特網通信引擎；松耦合；M/S模式

1 概述

近年來，復雜網絡在各個領域的應用越來越廣泛，人們頻繁利用網絡科學的概念及方法思考和解決各領域的相關科學問題。而隨著所研究網絡的規模越來越大，針對大尺度網絡分析的圖計算、圖挖掘問題也日顯突出。2013年在杭州舉行的“大數據時代下復雜網絡的機遇與挑戰”研討會中提出了目前復雜網絡研究面臨的最主要的10個挑戰，其中就有在大數據的背景下如何快速準確地處理包含數千萬甚至數億節點大尺度網絡的問題［1］。

隨著多核計算技術、Hadoop技術、GPGPU技術的發展，基于這些技術的大尺度網絡的并行分析與計算研究也正廣泛地開展。比如基于多核CPU［2-4］、GPU［5-6］以及異構系統［7-8］上的最短路徑、節點介數的計算［9］。卡內基梅隆大學開發的GraphChi框架［10］以及后續的GraphCT框架［11］通過精心設計的存儲結構和算法，充分利用了單機的并行計算資源。此外，卡耐基梅隆大學開發的Pegasus［12］以及最近研發的HADI［13］，均是基于Hadoop平臺的圖算法引擎。但基于Hadoop的實現要求基于高速網絡對可用的集群環境先做好規劃，而且一旦計算開始，不易動態調整計算節點的負載和數量。而建立松耦合計算網絡框架，將網絡中閑置的各種不同的操作系統下和不同配置的計算機聯合起來，共同處理復雜網絡的相關分布式計算，可以大大提高計算效率。參與者可以隨時加入或退出計算，并隨時動態調整負載，從而將散落于網絡中的計算資源低成本、靈活動態地利用起來，節省了管理服務器集群的成本。這種機制稱為“志愿計算”，最早由加州伯克利大學的BOINC［14-15］項目提出。BOINC是目前最著名、使用最廣泛的志愿計算平臺，并且在平臺上活躍著近百個分布式計算項目，涵蓋了多個科學領域，但是還未見有復雜網絡分析、模擬方面的項目，并且BOINC框架式通過設定為每個計算節點的任務預期完成時間來進行容錯處理，但是復雜網絡的計算由于計算時間同網絡規模有關，所以不能很好地預測任務完成時間，BOINC的結果驗證機制是通過分配相同任務給不同的計算節點比較最終結果。

由于復雜網絡的相關分析與計算以節點或邊為中心，因此可以由與節點或邊相關的計算構成任務隊列。這種基于任務隊列的架構有利于負載均衡和容錯機制的實現。本文基于該任務隊列的計算模式以及志愿計算的基本思想，設計針對大尺度復雜網絡分析計算的松耦合分布式計算框架，并基于該框架實現大尺度復雜網絡的平均最短路徑長度、網絡直徑和網絡效率［16］的分布式計算。由ZeroC開發的中間件因特網通信引擎（Internet Communica-tions Engine，ICE）具有通信負載低、與平臺和語言無關等優點［17-18］，因此在計算框架的具體實現上，本文采用ICE作為網絡通信中間件，通過局域網或者互聯網將松耦合的計算節點以M aster-Slave模式共同參與復雜網絡的相關分布式計算。

2 復雜網絡的松耦合分布式計算框架

本文提出的針對大尺度網絡的松耦合分布式計算框架與BOINC不同，主要針對復雜網絡的計算特點進行設計，采用心跳信號的機制進行錯誤判斷而不是通過預判時間，旨在將框架抽取通用接口，將其用到復雜網絡的其他計算中。本文框架采用通用的M aster-Slave模式，不同配置的Slave節點都可以通過局域網或廣域網與M aster節點通信，共同完成計算任務。

本文框架的主要設計思想為：外部應用程序接收計算需求，M aster節點將任務均勻的分成若干個任務集，Slave節點申請加入計算，由M aster節點根據其系統配置動態分配不同個數任務集交由相應的Slave節點計算，Slave節點計算完成后回傳計算結果，最終由M aster節點進行運算結果匯總統計。基于任務隊列的分布式計算框架的架構如圖1所示。該框架至少需要一個M aster節點和Slave節點，理論上可同時存在成百上千個Slave節點參與計算，實際最大可運行數量取決于M aster節點性能，任務隊列管理性能以及網絡通信速率等指標來決定。

圖1 基于任務隊列的分布式計算框架

2.1 M aster節點

M aster節點是本文分布式框架的核心，主要任務包括：分解任務并維護任務隊列，接收Slave節點的計算請求，實時監控Slave節點的運行狀態，實時監控任務運行狀態，為Slave節點分配計算任務，接收子任務計算結果，匯總全部子任務結果集。

根據不同的算法，大尺度復雜網絡的節點或邊被組織成計算任務隊列。M aster節點負責根據需要將任務隊列分割為細粒度的任務集分配給申請參與運算的Slave節點。M aster節點通過維護狀態信息列表實時監控Salve節點的狀態，該列表主要包含Slave節點唯一標識、心跳信號時間戳以及分配的任務集。Slave節點每隔一段時間向M aster節點發送心跳信號，由M aster節點更新狀態信息列表中相應時間戳。該框架的容錯機制主要是M aster節點通過判斷時間戳間接判斷Slave節點的在線或離線狀態，所以，框架允許Slave節點隨時加入或退出計算。

不同計算能力的Slave節點，完成任務集計算的速度不同。計算能力越強，申請的任務集個數越多，完成單個任務計算的速度越快，Master節點為其分配更多地任務集。因此，基于任務隊列的機制可以解決計算節點間的負載均衡問題。

M aster節點從各Slave節點收集各個任務集相應的計算結果，最終將所有任務集的計算結果通過指定計算匯總成最終結果。

2.2 Slave節點

Slave節點的主要任務包括：申請加入計算，評價自身性能并接收計算子任務和計算數據，完成對子任務的計算，向M aster節點返回計算結果集以及定時向M aster節點發送心跳信號。

Slave節點申請加入計算，則先由M aster節點發送計算所需的網絡拓撲等相關數據，通過Slave節點主機的計算性能指標申請任務個數，性能指標主要包括可提供的CPU核心數、內存大小以及是否有GPU參與計算等。由M aster節點為其分配相應的任務個數。Slave節點可以在計算過程中動態調整分配計算的CPU核心數以實現本地多線程之間的負載均衡，所以，完成任務并回傳結果后，重新評測計算性能申請任務。

Slave節點每隔一段時間發送心跳信號，便于M aster節點及時了解其狀態。

3 計算框架的實現及評估

平均最短路徑是復雜網絡的一個基本拓撲特征指標，它能夠體現網絡是否具有小世界性質，全局效率則反映了網絡之間節點發送消息的平均效率。有向網絡和無向網絡的平均最短路徑計算公式和全局效率計算公式分別如式（1）～式（4）所示，其中，N為網絡節點數；dij表示節點i和節點j之間的最短路徑長度。而這些指標要求計算網絡中每一對節點間的最短路徑長度，這對于大尺度的復雜網絡來說是一個很耗時的過程。本文基于上述針對大尺度網絡分析的志愿計算框架的設計，實現了該框架下的大尺度網絡平均最短路徑長度及全局效率的分布式計算。在具體實現中，采用了ICE中間件作為網絡通信組件，該中間件具有實現簡單、與平臺和語言無關的優點。

為了在分布式的志愿計算框架下實現平均最短路徑和全局效率的計算，首先要實現算法的并行化。這里只需對每個節點調用經典的單源最短路徑算法即可，然后根據式（1）或式（2）求得平均最短路徑長度，根據式（3）或式（4）求得全局效率。由于每個節點間計算單源最短路徑是相互獨立的，很容易基于每個節點將算法并行化。

基于分布式的志愿計算框架實現了大尺度網絡的平均最短路徑和全局效率算法后，實驗選用1臺服務器作為M aster節點，8臺不同配置、位于不同網段的計算機作為Slave節點共同參與計算，通過多組實驗對框架進行測試和評估。各臺計算機的硬件、軟件配置情況如表1所示，其中，M表示Master節點；S表示Slave節點。

表1 實驗環境配置

3.1 任務規模的影響

本節測試任務規模與計算時間之間的關系。實驗測試數據為一個具有158 378個節點、851 968條邊的無向網絡，實驗環境為8個Slave節點同時參與計算。通過遞增任務規模（單個任務包含節點個數）的方式得到計算時間。經一組實驗，得到的計算時間如表2所示。

表2 不同任務規模下的計算時間s

由表2可知，隨著任務規模的增加，計算時間相對有一定減少，但是相對于整個任務的計算來看并不是很明顯，并且任務規模到一定程度，計算時間幾乎不變，由此設定任務規模為500，即每500個節點作為一個任務集。

3.2 Slave節點個數的影響

本節測試在任務規模一定的情況下，Slave節點的個數對計算時間的影響。采用5組數據作為基礎數據，每組數據的基本信息如表3所示。

表3 實驗數據

表4 不同節點個數下的計算時間s

由圖2也可以看出，對同一個復雜網絡的數據來說，當增加Slave節點的個數，計算時間逐漸減小，但是時間減小的幅度也越來越小。同時，對不同數據來說，數據量越大計算時間減小幅度越明顯。總體計算時間是由節點計算時間和網絡通信等額外時間共同組成，數據量越小，任務分配越頻繁，通信額外時間越多，所以，減小幅度越不明顯。

圖2 同一網絡中Slave個數與計算時間的關系

經過實驗證明，本文設計的針對復雜網絡計算的分布式框架是有效的，可以有效利用分散于網絡中的計算資源，使其共同參與到處理含有上千萬甚至上億個節點的復雜網絡計算中。

4 結束語

針對大尺度復雜網絡的高性能分析計算問題，本文設計并實現了一個基于志愿計算思想的松耦合分布式計算框架。實驗結果表明，該框架可以將網絡中多臺不同硬件配置、不同操作系統的計算機閑置資源通過局域網或廣域網連接起來，在保證計算結果正確的前提下，共同參與大尺度復雜網絡的快速分析與計算。

在下一步的工作中，主要擬解決以下3個問題：（1）將計算功能從服務端剝離，并進一步抽象框架的接口，實現不同算法的插件化選擇和配置；（2）實現客戶端異構計算資源的匹配和調用，如GPU計算；（3）實現大尺度復雜網絡數據的P2P傳輸，從而降低服務端在數據傳輸方面的負載。

［1］ 周 濤，張子柯，陳觀榮，等.復雜網絡研究的機遇與挑戰［J］.電子科技大學學報，2014，43（1）：1-5.

［2］ Bader D A，Madduri K.Designing Multithreaded Algorithm s for Breadth-first Search and st-connectivity on the Cray MTA-2［C］//Proceedings of ICPP'06. Washington D.C.，USA：IEEE Press，2006：523-530.

［3］ Bader D A，Madduri K.Parallel Algorithm s for Evaluating Centrality Indices in Real-world Networks［C］// Proceedings of ICPP'06.Washington D.C.，USA：IEEE Press，2006：539-550.

［4］ Zhao Xiaohan，Sala A，Zheng Haitao，et al.Efficient Shortest Paths on Massive Social Graphs［C］// Proceedings of the 7th International Conference on Collaborative Computing：Networking，Applications and Worksharing.Orlando，USA：［s.n.］，2011：77-86.

［5］ Hardin D S，Hardin S S.ACL2 Meets the GPU：Formalizing a CUDA-based Parallelizable A ll-pairs Shortest Path Algorithm in ACL2［C］//Proceedings of ACL2'13.［S.l.］：EPTCS，2013：127-142.

［6］ 郭紹忠，王 偉，周 剛，等.基于GPU的單源最短路徑算法設計與實現［J］.計算機工程，2012，38（2）：42-44.

［7］ Pandey M，Pandey H，Sharma S.In-place Recursive Approach for A ll-pairs Shortest-path Problem Using OPENCL［C］//Proceedings of ICIT'13.Washington D.C.，USA：IEEE Press，2013.

［8］ Ortega-Arranz H，Torres Y，Llanos D R，et al.The Allpair Shortest-path Problem in Shared-memory Heterogeneous Systems［EB/OL］.（2013-01-03）.http：//www. infor.uva.es/～yuri.torres/docs/hector-Complex-2013.pdf.

［9］ Sariyüce A E.Betweenness Centrality on GPUs and Heterogeneous Architectures［C］//Proceedings of the 6 th Workshop on General Purpose Processor Using Graphics Processing Units.New York，USA：ACM Press，2013.

［10］ Aapo K，B lelloch G E，Guestrin C.GraphChi：Largescale Graph Computation on Just a PC［C］// Proceedings of OSDI'12.Washington D.C.，USA：IEEE Press，2012：31-46.

［11］ Ediger D，Jiang K，Riedy J，et al.GraphCT：Multithreaded Algorithm s for Massive Graph Analysis［J］. IEEE Transactions on Parallel and Distributed System s，2013，24（11）：2220-2229.

［12］ Kang U，Tsourakakis C E.PEGASUS：A Peta-scale Graph Mining System Implementation and Observations［C］//Proceedings of ICDM'09.Washington D.C.，USA：IEEE Press，2009：229-238.

［13］ Kang U，Tsourakakis C E，Appel A P，et al.HADI：Mining Radii of Large Graphs［J］.ACM Transactions on Know ledge Discovery from Data，2011，5（8）：1-8.

［14］ Anderson D P.BOINC：A System for Public-resource Computing and Storage［C］//Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing. Washington D.C.，USA：IEEE Press，2004：4-10.

［15］ Anderson D P，Fedak G.The Computational and Storage Potential of Volunteer Computing［C］//Proceedings of the 6th IEEE International Symposium on Cluster Computing and the Grid.Washington D.C.，USA：IEEE Press，2006：73-80.

［16］ Latora V，Marchiori M.Efficient Behavior of Small world Networks［J］.Physical Review Letters，2001，87（19）：1-4.

［17］ Marquezan C，Righi R，Schnorr L M，et al.ICE：A Service Oriented Approach to Uniform the Access and Management of Cluster Environments［C］//Proceedings of Conference on Cluster Computing and the Grid. Washington D.C.，USA：IEEE Press，2006：54.

［18］ 張俊軍，章 旋.ICE中間件技術及其應用研究［J］.計算機與現代化，2012，（5）：192-194.

編輯 金胡考

Design and Implementation of Loose Coup ling Distributed Computing Framework for Com p lex Network

LU Gang，XU Qinliang，XU Nanshan，GUO Junxia
（College of Information Science and Technology，Beijing University of Chemical Technology，Beijing 100029，China）

In order to calculate the topological characteristics of large-scale com plex networks faster，a distributed computing framework for analyzing large-scale complex networks is designed and implemented in this paper.It collects loose coupling computing nodes distributed in the local network or the Internet.By using a task queue，Computing nodes can join or quit during Computing at any time.By fully leveraging the loose coupling Computing resources distributed in a network，the framework makes the speed of analyzing large-scale complex networks enhanced greatly.Based on this framework，the distributed computing of average length of the shortest paths and the efficiency of large-scale comp lex networks is implemented.Experimental results show that this framework can make full use of the idle Computing resources in the network，and greatly improves the Computing performance，on the premise of ensuring the correctness of computational results.

complex network；distributed Computing；Internet Communications Engine（ICE）；loose coupling；M/S mode

盧 罡，徐勤良，許南山，等.復雜網絡松耦合分布式計算框架的設計與實現［J］.計算機工程，2015，41（11）：73-76，93.

英文引用格式：Lu Gang，Xu Qinliang，Xu Nanshan，et al.Design and Implementation of Loose Coupling Distributed Computing Framework for Complex Network［J］.Computer Engineering，2015，41（11）：73-76，93.

1000-3428（2015）11-0073-04

A

TP391

10.3969/j.issn.1000-3428.2015.11.013

北京高等學校青年英才計劃基金資助項目（YETP0506）。

盧 罡（1981-），男，講師，主研方向：高性能計算，復雜網絡；徐勤良，碩士研究生；許南山，副教授；郭俊霞（通訊作者），講師。

2014-10-15

2014-12-11 E-m ail：guojx@mail.buct.edu.cn