隨著大數(shù)據(jù)時代的來臨,越來越多大數(shù)據(jù)應(yīng)用需要以圖的形式描述數(shù)據(jù),進(jìn)而通過迭代方式對其加以處理。如何高效利用圖結(jié)構(gòu)特性加速圖處理,降低大規(guī)模圖計算系統(tǒng)開銷,成為圖計算領(lǐng)域亟待解決的問題。然而,現(xiàn)有圖處理系統(tǒng)對頂點(diǎn)活躍程度差異缺乏考慮,將活躍頂點(diǎn)（即熱頂點(diǎn)）和非熱頂點(diǎn)（即冷頂點(diǎn)）混合劃分在同一分區(qū),導(dǎo)致加載包含熱頂點(diǎn)的分區(qū)時,增加不必要的冷頂點(diǎn)加載開銷,延長圖處理時間,降低圖處理系統(tǒng)性能。針對上述缺陷,提出了圖結(jié)構(gòu)感知的圖處理算法,并基于目前最先進(jìn)的圖處理系統(tǒng)Gemini實(shí)現(xiàn)了該算法（新系統(tǒng)為GGraph）。提出了圖結(jié)構(gòu)感知的圖劃分算法,該算法考慮了圖結(jié)構(gòu)的冪律特性,使用具有低開銷的邏輯重劃分方案,根據(jù)迭代過程中頂點(diǎn)間數(shù)據(jù)依賴的變化自適應(yīng)劃分冷/熱圖劃分片（即含有大量熱頂點(diǎn)的分區(qū)）,使得熱頂點(diǎn)能夠得到優(yōu)先處理,同時降低冷頂點(diǎn)的計算頻次,減少不必要的數(shù)據(jù)訪問開銷。為進(jìn)一步提高收斂速度,還提出了基于熱圖劃分片的調(diào)度算法,將熱圖劃分片賦予更高的處理優(yōu)先級,使得熱頂點(diǎn)能夠優(yōu)先計算,并且得到足夠的迭代處理次數(shù),既減少了頂點(diǎn)收斂所需的更新輪次,又降低了每輪迭代所需的計算時間,加速圖算法的收斂。實(shí)驗結(jié)果... 

【文章來源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：58 頁

【學(xué)位級別】：碩士

【部分圖文】：

點(diǎn)劃分示意圖

數(shù)頂點(diǎn)連接大部分邊，點(diǎn)劃，更新這些頂點(diǎn)時會產(chǎn)生跨部分的鄰接頂點(diǎn)，對于這些低系統(tǒng)性能。圖，該劃分方式平均分配各個降低邊跨越計算節(jié)點(diǎn)的數(shù)量結(jié)構(gòu)和頂點(diǎn)間的依賴關(guān)系。中，邊跨越多個分區(qū)。如圖2， 5和 6被劃分在分區(qū) 3，在低度數(shù)頂點(diǎn)較多的圖中，消息的傳播，降低跨節(jié)點(diǎn)通信

華 中 科 技 大 學(xué) 碩 士 學(xué) 位 論 文下，熱頂點(diǎn)較多的計算節(jié)點(diǎn)需要更多時間遍歷所有邊，產(chǎn)生“木桶效的收斂時間。點(diǎn)邊混合劃分方式werLyra[11]提出了一種混合圖劃分方法 Hybrid-Cut，即對度數(shù)高的頂，對度數(shù)低的頂點(diǎn)采用邊劃分方式。如圖 1.3 所示，Hybrid-Cut 圖度數(shù)的不同選取差異化的處理策略，將度數(shù)較低的頂點(diǎn)（如 2， 3，放置在一起，以保證數(shù)據(jù)局部性，同時將度數(shù)較高的頂點(diǎn)（如 1），以充分利用圖計算框架并行計算的能力。通過按頂點(diǎn)度數(shù)對頂點(diǎn)，Hybrid-Cut 算法在局部性和算法并行性上達(dá)到了較好的均衡。

【參考文獻(xiàn)】：
期刊論文
[1]內(nèi)存計算技術(shù)研究綜述[J]. 羅樂,劉軼,錢德沛.  軟件學(xué)報. 2016(08)
[2]從系統(tǒng)角度審視大圖計算[J]. 吳城文,張廣艷,鄭緯民.  大數(shù)據(jù). 2015(03)
[3]醫(yī)療健康大數(shù)據(jù):應(yīng)用實(shí)例與系統(tǒng)分析[J]. 董誠,林立,金海,廖小飛.  大數(shù)據(jù). 2015(02)



本文編號：3230940