基于動(dòng)態(tài)再劃分的分布式圖系統(tǒng)負(fù)載優(yōu)化機(jī)制研究.pdf

1、隨著計(jì)算機(jī)及網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，越來越多的應(yīng)用領(lǐng)域需要對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行處理。傳統(tǒng)的單機(jī)處理模式不能有效地適應(yīng)大規(guī)模圖數(shù)據(jù)計(jì)算，因此出現(xiàn)了許多分布式環(huán)境下的圖處理框架，如Pregel、Giraph、Graphlab等。圖劃分是分布式圖處理過程中的關(guān)鍵步驟，現(xiàn)有的分布式圖處理系統(tǒng)大多采用一次性靜態(tài)圖劃分技術(shù)來平衡各個(gè)計(jì)算節(jié)點(diǎn)的工作負(fù)載。由于在分布式圖處理的迭代過程中，不同特性的圖算法每次迭代計(jì)算所訪問的圖頂點(diǎn)數(shù)可能不同，其執(zhí)行過程中的運(yùn)行

2、時(shí)負(fù)載是隨圖算法執(zhí)行行為而變化的。一次靜態(tài)圖劃分未考慮這種圖算法行為所產(chǎn)生的運(yùn)行時(shí)負(fù)載不均衡對(duì)計(jì)算性能的影響，無(wú)法保證圖算法整個(gè)計(jì)算過程中的負(fù)載均衡，從而降低了圖處理的效率。
　　基于動(dòng)態(tài)再劃分的負(fù)載優(yōu)化方法采用動(dòng)態(tài)負(fù)載平衡技術(shù)，依據(jù)圖計(jì)算的行為特性監(jiān)測(cè)負(fù)載的運(yùn)行時(shí)狀態(tài)，動(dòng)態(tài)地將超載計(jì)算節(jié)點(diǎn)的負(fù)載轉(zhuǎn)移到未超載計(jì)算節(jié)點(diǎn)，從而減少圖算法行為對(duì)負(fù)載的不均衡影響，提高分布式圖處理的效率。主要研究?jī)?nèi)容包括：提出基于圖算法行為特征的節(jié)點(diǎn)負(fù)載計(jì)

3、算方法，建立以活躍頂點(diǎn)、傳入消息數(shù)及遠(yuǎn)程傳出消息為量化參數(shù)的節(jié)點(diǎn)負(fù)載計(jì)算模型；提出以局部節(jié)點(diǎn)負(fù)載為基礎(chǔ)，根據(jù)圖計(jì)算的行為變化平衡全局負(fù)載的兩階段負(fù)載動(dòng)態(tài)再劃分方法；設(shè)計(jì)實(shí)現(xiàn)節(jié)點(diǎn)監(jiān)控程序以及以頂點(diǎn)為中心的負(fù)載遷移機(jī)制，在每次迭代最后階段將監(jiān)控到的節(jié)點(diǎn)負(fù)載發(fā)送到其它計(jì)算節(jié)點(diǎn)，由各節(jié)點(diǎn)協(xié)同地進(jìn)行超載判定，確定負(fù)載并進(jìn)行遷移。
　　針對(duì)多種圖算法，在大量數(shù)據(jù)集上對(duì)所提出的動(dòng)態(tài)再劃分機(jī)制進(jìn)行測(cè)試。測(cè)試結(jié)果表明，相比未采用動(dòng)態(tài)再劃分機(jī)制的圖計(jì)