發(fā)布時間：2021-06-15 11:05

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

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

【文章頁數】：58 頁

【學位級別】：碩士

【部分圖文】：

點劃分示意圖

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

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

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



本文編號：3230940