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

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

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

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

【部分圖文】：

點(diǎn)劃分示意圖

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

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

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



本文編號(hào)：3230940