[發(fā)明專利]一種面向圖數(shù)據(jù)處理引擎的優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201810916036.2
• 申請日: 2018-08-13
• 公開（公告）號: CN109388733B
• 公開（公告）日: 2022-01-07
• 發(fā)明（設(shè)計）人: 王鋒華;錢仲文;夏洪濤;成敬周;陳婷;王政;張旭東;張建松;陳俊;黃敏;譚程文;琚小明;李博
• 申請（專利權(quán)）人: 國網(wǎng)浙江省電力有限公司;浙江華云信息科技有限公司;國網(wǎng)浙江仙居縣供電有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F9/448
• 代理公司: 北京中創(chuàng)陽光知識產(chǎn)權(quán)代理有限責(zé)任公司 11003
• 代理人: 尹振啟

本發(fā)明提出一種新的圖數(shù)據(jù)處理引擎優(yōu)化方法，其特征在于，采用本地迭代，全局通信的處理方式，所述處理方式首先在同一計算節(jié)點上開展計算，直到該計算節(jié)點上的所有圖節(jié)點的數(shù)據(jù)都完成更新則停止局部迭代；在同一計算節(jié)點上開展計算的同時，邊緣圖節(jié)點緩存并合并消息，待局部迭代停止后批量傳輸計算節(jié)點間發(fā)送的消息，所述邊緣圖節(jié)點為跨兩個或多個計算節(jié)點的圖節(jié)點。

技術(shù)領(lǐng)域

本發(fā)明涉及一種面向圖數(shù)據(jù)處理引擎的優(yōu)化方法，主要涉及到面向分布式圖數(shù)據(jù)處理引擎的優(yōu)化與性能提升、降低處理時間、減少通信開銷的方法。

背景技術(shù)

圖(Graph)是公認(rèn)的世界上最復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在數(shù)學(xué)和計算科學(xué)領(lǐng)域，圖論是專門研究圖的一門科學(xué)，其也可以認(rèn)為是研究事物及事物間關(guān)系的一門科學(xué)。近年來，圖算法及圖計算引擎的研究取得了較大的進(jìn)步，并在應(yīng)用領(lǐng)域取得了較好的進(jìn)展。以電網(wǎng)為例，電網(wǎng)可以認(rèn)為是最為復(fù)雜的人造網(wǎng)絡(luò)之一，學(xué)術(shù)界將電網(wǎng)看做一種特定類型的圖，并以其為研究對象，探索了電網(wǎng)的圖屬性和各種性質(zhì)，并研發(fā)了面向電網(wǎng)的圖計算算法和引擎，解決實際應(yīng)用中存在的各種問題。

然而，隨著圖規(guī)模的增大，圖算法運(yùn)行時間也不斷增加，且由于圖算法的復(fù)雜度通常較高，導(dǎo)致難以在單機(jī)上進(jìn)行計算。例如，龐大的圖數(shù)據(jù)結(jié)構(gòu)超出了內(nèi)存范圍，雖然可通過外存進(jìn)行中轉(zhuǎn)和緩存，但也使得計算時間變得不可接受。在這一背景下，分布式圖計算引擎應(yīng)用而生，通過多臺計算節(jié)點并行完成同一計算任務(wù)，從而大大節(jié)省了任務(wù)執(zhí)行時間。

雖然分布式圖計算引擎使得原本在單機(jī)上無法完成的圖計算任務(wù)在分布式環(huán)境中得以運(yùn)行，但仍然面臨著分布式節(jié)點間通信開銷過大以及多節(jié)點計算并行度較低的問題。例如，知名圖計算引擎Graphlab在運(yùn)行Pagerank算法時的并行加速比僅為0.45。這意味著該算法在Graphlab上并未能充分利用多節(jié)點的并行處理能力。其本質(zhì)原因在于圖計算任務(wù)難以在多計算節(jié)點實現(xiàn)橫向擴(kuò)展，以及圖節(jié)點間同步等待以及計算節(jié)點間的通信開銷過大問題。

發(fā)明內(nèi)容

針對以上問題，本發(fā)明提出了一種面向圖數(shù)據(jù)處理引擎的優(yōu)化方法，該方法適用于點中心模式的圖數(shù)據(jù)處理引擎。本發(fā)明中，單個計算節(jié)點中的多個圖節(jié)點通過多輪計算和通信后達(dá)到不動點，之后多計算節(jié)點間執(zhí)行批量信息交換，全局更新數(shù)據(jù)，然后再重復(fù)上述過程，直到獲得最終計算結(jié)果。與現(xiàn)有技術(shù)相比，本發(fā)明能有效提升圖數(shù)據(jù)處理引擎的并行度，減少通信開銷，因此大幅提高現(xiàn)有圖計算引擎的性能和計算效率。

附圖說明

圖1為本發(fā)明進(jìn)行圖數(shù)據(jù)處理的整體流程圖；

具體實施方式

為了使本發(fā)明的目的、技術(shù)方案及優(yōu)點更加清楚明白，以下結(jié)合附圖及實施例，對本發(fā)明進(jìn)行進(jìn)一步詳細(xì)說明。應(yīng)當(dāng)理解，此處所描述的具體實施例僅僅用以解釋本發(fā)明，并不用于限定本發(fā)明。此外，下面所描述的本發(fā)明各個實施方式中所涉及到的技術(shù)特征只要彼此之間未構(gòu)成沖突就可以相互組合。

本發(fā)明提出了一種新的圖數(shù)據(jù)處理引擎優(yōu)化方法，采用“本地迭代、全局通信”處理方法，當(dāng)前基于點中心方式的圖計算引擎，其計算任務(wù)在圖節(jié)點上執(zhí)行，圖節(jié)點間通過消息傳遞更新數(shù)據(jù)，并采用步長迭代(Step Iteration)方式獲得最終計算結(jié)果。執(zhí)行每一步，圖節(jié)點間都要傳遞消息，并根據(jù)消息更新圖節(jié)點上的數(shù)據(jù)。對于跨計算節(jié)點間的消息傳遞，涉及到大量的網(wǎng)絡(luò)傳輸開銷，顯著拖慢了計算效率。本發(fā)明提出的“本地迭代、全局通信”機(jī)制，首先在同一計算節(jié)點上開展計算，直到該計算節(jié)點上的所有圖節(jié)點的數(shù)據(jù)都完成更新則停止局部迭代，同時邊緣圖節(jié)點(跨兩個或多個計算節(jié)點的圖節(jié)點)緩存并合并消息，待局部迭代停止后批量傳輸計算節(jié)點間發(fā)送的消息，因此顯著降低了網(wǎng)絡(luò)數(shù)據(jù)傳輸量，提高了整體效率。

本發(fā)明在單計算節(jié)點內(nèi)進(jìn)行分區(qū)獨(dú)立迭代計算的方法，如圖1所示，具體方法如下：

步驟1，迭代計算開始：計算節(jié)點內(nèi)的圖節(jié)點開始執(zhí)行計算任務(wù)，計算任務(wù)完成后會生成中間計算結(jié)果，圖節(jié)點會根據(jù)預(yù)設(shè)的消息觸發(fā)條件將中間計算結(jié)果發(fā)送給相鄰圖節(jié)點。