盧 罡,徐勤良,許南山,郭俊霞
(北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院,北京100029)
復(fù)雜網(wǎng)絡(luò)松耦合分布式計(jì)算框架的設(shè)計(jì)與實(shí)現(xiàn)
盧 罡,徐勤良,許南山,郭俊霞
(北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院,北京100029)
為更快地計(jì)算大尺度復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的相關(guān)參數(shù),設(shè)計(jì)并實(shí)現(xiàn)一種松耦合分布式計(jì)算框架。將分散于網(wǎng)絡(luò)中的松耦合計(jì)算節(jié)點(diǎn)匯集起來(lái),通過(guò)任務(wù)隊(duì)列使各計(jì)算節(jié)點(diǎn)共同參與復(fù)雜網(wǎng)絡(luò)的相關(guān)分布式計(jì)算,并能隨時(shí)加入或者退出計(jì)算,利用分散于網(wǎng)絡(luò)中松耦合的計(jì)算節(jié)點(diǎn)提高復(fù)雜網(wǎng)絡(luò)相關(guān)分析的計(jì)算速度。基于該框架,實(shí)現(xiàn)對(duì)大尺度復(fù)雜網(wǎng)絡(luò)的平均最短路徑長(zhǎng)度、網(wǎng)絡(luò)直徑和網(wǎng)絡(luò)效率的分布式計(jì)算。實(shí)驗(yàn)結(jié)果表明,在保證計(jì)算結(jié)果正確的前提下,該框架可充分利用網(wǎng)絡(luò)中閑散的計(jì)算資源,提高運(yùn)算效率。
復(fù)雜網(wǎng)絡(luò);分布式計(jì)算;因特網(wǎng)通信引擎;松耦合;M/S模式
近年來(lái),復(fù)雜網(wǎng)絡(luò)在各個(gè)領(lǐng)域的應(yīng)用越來(lái)越廣泛,人們頻繁利用網(wǎng)絡(luò)科學(xué)的概念及方法思考和解決各領(lǐng)域的相關(guān)科學(xué)問(wèn)題。而隨著所研究網(wǎng)絡(luò)的規(guī)模越來(lái)越大,針對(duì)大尺度網(wǎng)絡(luò)分析的圖計(jì)算、圖挖掘問(wèn)題也日顯突出。2013年在杭州舉行的“大數(shù)據(jù)時(shí)代下復(fù)雜網(wǎng)絡(luò)的機(jī)遇與挑戰(zhàn)”研討會(huì)中提出了目前復(fù)雜網(wǎng)絡(luò)研究面臨的最主要的10個(gè)挑戰(zhàn),其中就有在大數(shù)據(jù)的背景下如何快速準(zhǔn)確地處理包含數(shù)千萬(wàn)甚至數(shù)億節(jié)點(diǎn)大尺度網(wǎng)絡(luò)的問(wèn)題[1]。
隨著多核計(jì)算技術(shù)、Hadoop技術(shù)、GPGPU技術(shù)的發(fā)展,基于這些技術(shù)的大尺度網(wǎng)絡(luò)的并行分析與計(jì)算研究也正廣泛地開(kāi)展。比如基于多核CPU[2-4]、GPU[5-6]以及異構(gòu)系統(tǒng)[7-8]上的最短路徑、節(jié)點(diǎn)介數(shù)的計(jì)算[9]。卡內(nèi)基梅隆大學(xué)開(kāi)發(fā)的GraphChi框架[10]以及后續(xù)的GraphCT框架[11]通過(guò)精心設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)和算法,充分利用了單機(jī)的并行計(jì)算資源。此外,卡耐基梅隆大學(xué)開(kāi)發(fā)的Pegasus[12]以及最近研發(fā)的HADI[13],均是基于Hadoop平臺(tái)的圖算法引擎。但基于Hadoop的實(shí)現(xiàn)要求基于高速網(wǎng)絡(luò)對(duì)可用的集群環(huán)境先做好規(guī)劃,而且一旦計(jì)算開(kāi)始,不易動(dòng)態(tài)調(diào)整計(jì)算節(jié)點(diǎn)的負(fù)載和數(shù)量。而建立松耦合計(jì)算網(wǎng)絡(luò)框架,將網(wǎng)絡(luò)中閑置的各種不同的操作系統(tǒng)下和不同配置的計(jì)算機(jī)聯(lián)合起來(lái),共同處理復(fù)雜網(wǎng)絡(luò)的相關(guān)分布式計(jì)算,可以大大提高計(jì)算效率。參與者可以隨時(shí)加入或退出計(jì)算,并隨時(shí)動(dòng)態(tài)調(diào)整負(fù)載,從而將散落于網(wǎng)絡(luò)中的計(jì)算資源低成本、靈活動(dòng)態(tài)地利用起來(lái),節(jié)省了管理服務(wù)器集群的成本。這種機(jī)制稱(chēng)為“志愿計(jì)算”,最早由加州伯克利大學(xué)的BOINC[14-15]項(xiàng)目提出。BOINC是目前最著名、使用最廣泛的志愿計(jì)算平臺(tái),并且在平臺(tái)上活躍著近百個(gè)分布式計(jì)算項(xiàng)目,涵蓋了多個(gè)科學(xué)領(lǐng)域,但是還未見(jiàn)有復(fù)雜網(wǎng)絡(luò)分析、模擬方面的項(xiàng)目,并且BOINC框架式通過(guò)設(shè)定為每個(gè)計(jì)算節(jié)點(diǎn)的任務(wù)預(yù)期完成時(shí)間來(lái)進(jìn)行容錯(cuò)處理,但是復(fù)雜網(wǎng)絡(luò)的計(jì)算由于計(jì)算時(shí)間同網(wǎng)絡(luò)規(guī)模有關(guān),所以不能很好地預(yù)測(cè)任務(wù)完成時(shí)間,BOINC的結(jié)果驗(yàn)證機(jī)制是通過(guò)分配相同任務(wù)給不同的計(jì)算節(jié)點(diǎn)比較最終結(jié)果。
由于復(fù)雜網(wǎng)絡(luò)的相關(guān)分析與計(jì)算以節(jié)點(diǎn)或邊為中心,因此可以由與節(jié)點(diǎn)或邊相關(guān)的計(jì)算構(gòu)成任務(wù)隊(duì)列。這種基于任務(wù)隊(duì)列的架構(gòu)有利于負(fù)載均衡和容錯(cuò)機(jī)制的實(shí)現(xiàn)。本文基于該任務(wù)隊(duì)列的計(jì)算模式以及志愿計(jì)算的基本思想,設(shè)計(jì)針對(duì)大尺度復(fù)雜網(wǎng)絡(luò)分析計(jì)算的松耦合分布式計(jì)算框架,并基于該框架實(shí)現(xiàn)大尺度復(fù)雜網(wǎng)絡(luò)的平均最短路徑長(zhǎng)度、網(wǎng)絡(luò)直徑和網(wǎng)絡(luò)效率[16]的分布式計(jì)算。由ZeroC開(kāi)發(fā)的中間件因特網(wǎng)通信引擎(Internet Communica-tions Engine,ICE)具有通信負(fù)載低、與平臺(tái)和語(yǔ)言無(wú)關(guān)等優(yōu)點(diǎn)[17-18],因此在計(jì)算框架的具體實(shí)現(xiàn)上,本文采用ICE作為網(wǎng)絡(luò)通信中間件,通過(guò)局域網(wǎng)或者互聯(lián)網(wǎng)將松耦合的計(jì)算節(jié)點(diǎn)以M aster-Slave模式共同參與復(fù)雜網(wǎng)絡(luò)的相關(guān)分布式計(jì)算。
本文提出的針對(duì)大尺度網(wǎng)絡(luò)的松耦合分布式計(jì)算框架與BOINC不同,主要針對(duì)復(fù)雜網(wǎng)絡(luò)的計(jì)算特點(diǎn)進(jìn)行設(shè)計(jì),采用心跳信號(hào)的機(jī)制進(jìn)行錯(cuò)誤判斷而不是通過(guò)預(yù)判時(shí)間,旨在將框架抽取通用接口,將其用到復(fù)雜網(wǎng)絡(luò)的其他計(jì)算中。本文框架采用通用的M aster-Slave模式,不同配置的Slave節(jié)點(diǎn)都可以通過(guò)局域網(wǎng)或廣域網(wǎng)與M aster節(jié)點(diǎn)通信,共同完成計(jì)算任務(wù)。
本文框架的主要設(shè)計(jì)思想為:外部應(yīng)用程序接收計(jì)算需求,M aster節(jié)點(diǎn)將任務(wù)均勻的分成若干個(gè)任務(wù)集,Slave節(jié)點(diǎn)申請(qǐng)加入計(jì)算,由M aster節(jié)點(diǎn)根據(jù)其系統(tǒng)配置動(dòng)態(tài)分配不同個(gè)數(shù)任務(wù)集交由相應(yīng)的Slave節(jié)點(diǎn)計(jì)算,Slave節(jié)點(diǎn)計(jì)算完成后回傳計(jì)算結(jié)果,最終由M aster節(jié)點(diǎn)進(jìn)行運(yùn)算結(jié)果匯總統(tǒng)計(jì)?;谌蝿?wù)隊(duì)列的分布式計(jì)算框架的架構(gòu)如圖1所示。該框架至少需要一個(gè)M aster節(jié)點(diǎn)和Slave節(jié)點(diǎn),理論上可同時(shí)存在成百上千個(gè)Slave節(jié)點(diǎn)參與計(jì)算,實(shí)際最大可運(yùn)行數(shù)量取決于M aster節(jié)點(diǎn)性能,任務(wù)隊(duì)列管理性能以及網(wǎng)絡(luò)通信速率等指標(biāo)來(lái)決定。
圖1 基于任務(wù)隊(duì)列的分布式計(jì)算框架
2.1 M aster節(jié)點(diǎn)
M aster節(jié)點(diǎn)是本文分布式框架的核心,主要任務(wù)包括:分解任務(wù)并維護(hù)任務(wù)隊(duì)列,接收Slave節(jié)點(diǎn)的計(jì)算請(qǐng)求,實(shí)時(shí)監(jiān)控Slave節(jié)點(diǎn)的運(yùn)行狀態(tài),實(shí)時(shí)監(jiān)控任務(wù)運(yùn)行狀態(tài),為Slave節(jié)點(diǎn)分配計(jì)算任務(wù),接收子任務(wù)計(jì)算結(jié)果,匯總?cè)孔尤蝿?wù)結(jié)果集。
根據(jù)不同的算法,大尺度復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)或邊被組織成計(jì)算任務(wù)隊(duì)列。M aster節(jié)點(diǎn)負(fù)責(zé)根據(jù)需要將任務(wù)隊(duì)列分割為細(xì)粒度的任務(wù)集分配給申請(qǐng)參與運(yùn)算的Slave節(jié)點(diǎn)。M aster節(jié)點(diǎn)通過(guò)維護(hù)狀態(tài)信息列表實(shí)時(shí)監(jiān)控Salve節(jié)點(diǎn)的狀態(tài),該列表主要包含Slave節(jié)點(diǎn)唯一標(biāo)識(shí)、心跳信號(hào)時(shí)間戳以及分配的任務(wù)集。Slave節(jié)點(diǎn)每隔一段時(shí)間向M aster節(jié)點(diǎn)發(fā)送心跳信號(hào),由M aster節(jié)點(diǎn)更新?tīng)顟B(tài)信息列表中相應(yīng)時(shí)間戳。該框架的容錯(cuò)機(jī)制主要是M aster節(jié)點(diǎn)通過(guò)判斷時(shí)間戳間接判斷Slave節(jié)點(diǎn)的在線(xiàn)或離線(xiàn)狀態(tài),所以,框架允許Slave節(jié)點(diǎn)隨時(shí)加入或退出計(jì)算。
不同計(jì)算能力的Slave節(jié)點(diǎn),完成任務(wù)集計(jì)算的速度不同。計(jì)算能力越強(qiáng),申請(qǐng)的任務(wù)集個(gè)數(shù)越多,完成單個(gè)任務(wù)計(jì)算的速度越快,Master節(jié)點(diǎn)為其分配更多地任務(wù)集。因此,基于任務(wù)隊(duì)列的機(jī)制可以解決計(jì)算節(jié)點(diǎn)間的負(fù)載均衡問(wèn)題。
M aster節(jié)點(diǎn)從各Slave節(jié)點(diǎn)收集各個(gè)任務(wù)集相應(yīng)的計(jì)算結(jié)果,最終將所有任務(wù)集的計(jì)算結(jié)果通過(guò)指定計(jì)算匯總成最終結(jié)果。
2.2 Slave節(jié)點(diǎn)
Slave節(jié)點(diǎn)的主要任務(wù)包括:申請(qǐng)加入計(jì)算,評(píng)價(jià)自身性能并接收計(jì)算子任務(wù)和計(jì)算數(shù)據(jù),完成對(duì)子任務(wù)的計(jì)算,向M aster節(jié)點(diǎn)返回計(jì)算結(jié)果集以及定時(shí)向M aster節(jié)點(diǎn)發(fā)送心跳信號(hào)。
Slave節(jié)點(diǎn)申請(qǐng)加入計(jì)算,則先由M aster節(jié)點(diǎn)發(fā)送計(jì)算所需的網(wǎng)絡(luò)拓?fù)涞认嚓P(guān)數(shù)據(jù),通過(guò)Slave節(jié)點(diǎn)主機(jī)的計(jì)算性能指標(biāo)申請(qǐng)任務(wù)個(gè)數(shù),性能指標(biāo)主要包括可提供的CPU核心數(shù)、內(nèi)存大小以及是否有GPU參與計(jì)算等。由M aster節(jié)點(diǎn)為其分配相應(yīng)的任務(wù)個(gè)數(shù)。Slave節(jié)點(diǎn)可以在計(jì)算過(guò)程中動(dòng)態(tài)調(diào)整分配計(jì)算的CPU核心數(shù)以實(shí)現(xiàn)本地多線(xiàn)程之間的負(fù)載均衡,所以,完成任務(wù)并回傳結(jié)果后,重新評(píng)測(cè)計(jì)算性能申請(qǐng)任務(wù)。
Slave節(jié)點(diǎn)每隔一段時(shí)間發(fā)送心跳信號(hào),便于M aster節(jié)點(diǎn)及時(shí)了解其狀態(tài)。
平均最短路徑是復(fù)雜網(wǎng)絡(luò)的一個(gè)基本拓?fù)涮卣髦笜?biāo),它能夠體現(xiàn)網(wǎng)絡(luò)是否具有小世界性質(zhì),全局效率則反映了網(wǎng)絡(luò)之間節(jié)點(diǎn)發(fā)送消息的平均效率。有向網(wǎng)絡(luò)和無(wú)向網(wǎng)絡(luò)的平均最短路徑計(jì)算公式和全局效率計(jì)算公式分別如式(1)~式(4)所示,其中,N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù);dij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短路徑長(zhǎng)度。而這些指標(biāo)要求計(jì)算網(wǎng)絡(luò)中每一對(duì)節(jié)點(diǎn)間的最短路徑長(zhǎng)度,這對(duì)于大尺度的復(fù)雜網(wǎng)絡(luò)來(lái)說(shuō)是一個(gè)很耗時(shí)的過(guò)程。本文基于上述針對(duì)大尺度網(wǎng)絡(luò)分析的志愿計(jì)算框架的設(shè)計(jì),實(shí)現(xiàn)了該框架下的大尺度網(wǎng)絡(luò)平均最短路徑長(zhǎng)度及全局效率的分布式計(jì)算。在具體實(shí)現(xiàn)中,采用了ICE中間件作為網(wǎng)絡(luò)通信組件,該中間件具有實(shí)現(xiàn)簡(jiǎn)單、與平臺(tái)和語(yǔ)言無(wú)關(guān)的優(yōu)點(diǎn)。
為了在分布式的志愿計(jì)算框架下實(shí)現(xiàn)平均最短路徑和全局效率的計(jì)算,首先要實(shí)現(xiàn)算法的并行化。這里只需對(duì)每個(gè)節(jié)點(diǎn)調(diào)用經(jīng)典的單源最短路徑算法即可,然后根據(jù)式(1)或式(2)求得平均最短路徑長(zhǎng)度,根據(jù)式(3)或式(4)求得全局效率。由于每個(gè)節(jié)點(diǎn)間計(jì)算單源最短路徑是相互獨(dú)立的,很容易基于每個(gè)節(jié)點(diǎn)將算法并行化。
基于分布式的志愿計(jì)算框架實(shí)現(xiàn)了大尺度網(wǎng)絡(luò)的平均最短路徑和全局效率算法后,實(shí)驗(yàn)選用1臺(tái)服務(wù)器作為M aster節(jié)點(diǎn),8臺(tái)不同配置、位于不同網(wǎng)段的計(jì)算機(jī)作為Slave節(jié)點(diǎn)共同參與計(jì)算,通過(guò)多組實(shí)驗(yàn)對(duì)框架進(jìn)行測(cè)試和評(píng)估。各臺(tái)計(jì)算機(jī)的硬件、軟件配置情況如表1所示,其中,M表示Master節(jié)點(diǎn);S表示Slave節(jié)點(diǎn)。
表1 實(shí)驗(yàn)環(huán)境配置
3.1 任務(wù)規(guī)模的影響
本節(jié)測(cè)試任務(wù)規(guī)模與計(jì)算時(shí)間之間的關(guān)系。實(shí)驗(yàn)測(cè)試數(shù)據(jù)為一個(gè)具有158 378個(gè)節(jié)點(diǎn)、851 968條邊的無(wú)向網(wǎng)絡(luò),實(shí)驗(yàn)環(huán)境為8個(gè)Slave節(jié)點(diǎn)同時(shí)參與計(jì)算。通過(guò)遞增任務(wù)規(guī)模(單個(gè)任務(wù)包含節(jié)點(diǎn)個(gè)數(shù))的方式得到計(jì)算時(shí)間。經(jīng)一組實(shí)驗(yàn),得到的計(jì)算時(shí)間如表2所示。
表2 不同任務(wù)規(guī)模下的計(jì)算時(shí)間s
由表2可知,隨著任務(wù)規(guī)模的增加,計(jì)算時(shí)間相對(duì)有一定減少,但是相對(duì)于整個(gè)任務(wù)的計(jì)算來(lái)看并不是很明顯,并且任務(wù)規(guī)模到一定程度,計(jì)算時(shí)間幾乎不變,由此設(shè)定任務(wù)規(guī)模為500,即每500個(gè)節(jié)點(diǎn)作為一個(gè)任務(wù)集。
3.2 Slave節(jié)點(diǎn)個(gè)數(shù)的影響
本節(jié)測(cè)試在任務(wù)規(guī)模一定的情況下,Slave節(jié)點(diǎn)的個(gè)數(shù)對(duì)計(jì)算時(shí)間的影響。采用5組數(shù)據(jù)作為基礎(chǔ)數(shù)據(jù),每組數(shù)據(jù)的基本信息如表3所示。
表3 實(shí)驗(yàn)數(shù)據(jù)
表4 不同節(jié)點(diǎn)個(gè)數(shù)下的計(jì)算時(shí)間s
由圖2也可以看出,對(duì)同一個(gè)復(fù)雜網(wǎng)絡(luò)的數(shù)據(jù)來(lái)說(shuō),當(dāng)增加Slave節(jié)點(diǎn)的個(gè)數(shù),計(jì)算時(shí)間逐漸減小,但是時(shí)間減小的幅度也越來(lái)越小。同時(shí),對(duì)不同數(shù)據(jù)來(lái)說(shuō),數(shù)據(jù)量越大計(jì)算時(shí)間減小幅度越明顯??傮w計(jì)算時(shí)間是由節(jié)點(diǎn)計(jì)算時(shí)間和網(wǎng)絡(luò)通信等額外時(shí)間共同組成,數(shù)據(jù)量越小,任務(wù)分配越頻繁,通信額外時(shí)間越多,所以,減小幅度越不明顯。
圖2 同一網(wǎng)絡(luò)中Slave個(gè)數(shù)與計(jì)算時(shí)間的關(guān)系
經(jīng)過(guò)實(shí)驗(yàn)證明,本文設(shè)計(jì)的針對(duì)復(fù)雜網(wǎng)絡(luò)計(jì)算的分布式框架是有效的,可以有效利用分散于網(wǎng)絡(luò)中的計(jì)算資源,使其共同參與到處理含有上千萬(wàn)甚至上億個(gè)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò)計(jì)算中。
針對(duì)大尺度復(fù)雜網(wǎng)絡(luò)的高性能分析計(jì)算問(wèn)題,本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于志愿計(jì)算思想的松耦合分布式計(jì)算框架。實(shí)驗(yàn)結(jié)果表明,該框架可以將網(wǎng)絡(luò)中多臺(tái)不同硬件配置、不同操作系統(tǒng)的計(jì)算機(jī)閑置資源通過(guò)局域網(wǎng)或廣域網(wǎng)連接起來(lái),在保證計(jì)算結(jié)果正確的前提下,共同參與大尺度復(fù)雜網(wǎng)絡(luò)的快速分析與計(jì)算。
在下一步的工作中,主要擬解決以下3個(gè)問(wèn)題:(1)將計(jì)算功能從服務(wù)端剝離,并進(jìn)一步抽象框架的接口,實(shí)現(xiàn)不同算法的插件化選擇和配置;(2)實(shí)現(xiàn)客戶(hù)端異構(gòu)計(jì)算資源的匹配和調(diào)用,如GPU計(jì)算;(3)實(shí)現(xiàn)大尺度復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)的P2P傳輸,從而降低服務(wù)端在數(shù)據(jù)傳輸方面的負(fù)載。
[1] 周 濤,張子柯,陳觀榮,等.復(fù)雜網(wǎng)絡(luò)研究的機(jī)遇與挑戰(zhàn)[J].電子科技大學(xué)學(xué)報(bào),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的單源最短路徑算法設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(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,F(xiàn)edak 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中間件技術(shù)及其應(yīng)用研究[J].計(jì)算機(jī)與現(xiàn)代化,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
盧 罡,徐勤良,許南山,等.復(fù)雜網(wǎng)絡(luò)松耦合分布式計(jì)算框架的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(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
北京高等學(xué)校青年英才計(jì)劃基金資助項(xiàng)目(YETP0506)。
盧 罡(1981-),男,講師,主研方向:高性能計(jì)算,復(fù)雜網(wǎng)絡(luò);徐勤良,碩士研究生;許南山,副教授;郭俊霞(通訊作者),講師。
2014-10-15
2014-12-11 E-m ail:guojx@mail.buct.edu.cn