【摘要】：圖是一種很重要的非結(jié)構(gòu)化數(shù)據(jù),可以用于建模現(xiàn)實世界中的各種問題,被廣泛應(yīng)用到交通運輸、金融、社交網(wǎng)絡(luò)等重要領(lǐng)域。但由于圖計算過程中嚴重的結(jié)構(gòu)依賴性,導(dǎo)致應(yīng)用執(zhí)行時內(nèi)存隨機訪問嚴重,內(nèi)存帶寬成為限制圖計算系統(tǒng)性能的重要因素。并且不同類型圖算法的內(nèi)存訪問特征差異明顯,單一的內(nèi)存圖數(shù)據(jù)組織不足以應(yīng)對各種圖算法多樣化的內(nèi)存訪問需求。針對上述問題,分析了常見圖算法的動態(tài)運行特征和內(nèi)存數(shù)據(jù)訪問特點,將圖算法分為遍歷式和迭代式兩類,研究不同運行特征下的高效的圖數(shù)據(jù)組織策略。對于遍歷式圖算法,通過分析其運行過程,發(fā)現(xiàn)同一個頂點和不同鄰居節(jié)點之間存在關(guān)聯(lián)度的大小差異,對鄰居節(jié)點的訪問順序是影響算法運行過程中緩存命中率的重要因素。基于此提出了基于關(guān)聯(lián)度的圖頂點重映射算法GDL-VC,并采用滑動窗口模型SW實現(xiàn)了內(nèi)存圖數(shù)據(jù)的合理布局。該布局結(jié)果能夠體現(xiàn)出圖的結(jié)構(gòu)特性,使相關(guān)聯(lián)的頂點ID分布呈現(xiàn)局部有序,減少圖算法運行過程中的內(nèi)存隨機訪問。對于迭代式圖算法,通過分析其算法收斂特性,發(fā)現(xiàn)圖結(jié)構(gòu)中“超級頂點”長時間不能達到收斂狀態(tài)而造成了迭代式圖應(yīng)用的長尾現(xiàn)象。針對于此,提出了基于影響力的圖頂點重映射算法GDL-DR,該布局算法根據(jù)頂點的影響力(頂點度)完成圖數(shù)據(jù)的布局。這樣在圖算法迭代后期,活躍頂點集執(zhí)行狀態(tài)更新時,與之相關(guān)聯(lián)的鄰居節(jié)點緊湊分布,可以減少內(nèi)存隨機訪問,使頂點更快的達到收斂狀態(tài),縮短應(yīng)用執(zhí)行時間。測試結(jié)果表明:GDL-VC布局算法能夠給遍歷式圖應(yīng)用(連通分量、單源點最短路徑)帶來25.4%、27.5%的平均內(nèi)存訪問效率提升,部分數(shù)據(jù)集超過50%;GDL-DR布局算法能夠給迭代式圖應(yīng)用(網(wǎng)頁排名、標簽傳播)帶來23.9%、17.1%的平均內(nèi)存訪問效率提升,最大提升百分比為42.9%。對于GraphChi測試平臺,兩種布局算法帶來的系統(tǒng)加速比均達到1.5×以上,部分圖數(shù)據(jù)超過2×;Cache命中率提高到90%以上。
【圖文】：

圖 1.4 典型圖應(yīng)用活躍頂點比例變化曲線可以看出，對于 BFS 遍歷式圖算法，其按照順序?qū)哟伪闅v圖結(jié)構(gòu)，前期活例逐漸增大，隨著大多數(shù)頂點都被訪問，后續(xù)活躍頂點比例下降；但是整個過程活躍頂點比例整體上都維持在一個比較低的水平。而對于 PageRank 迭法，初始時由于所有頂點都要執(zhí)行更新，因此活躍頂點比例很高；但是經(jīng)過

圖 1.6 圖社區(qū)結(jié)構(gòu)在對圖數(shù)據(jù)重新布局的時候，如果能夠預(yù)先準確的檢測出圖社一個社區(qū)單獨執(zhí)行頂點重映射。這樣在分布式環(huán)境下，能夠大大減量，，保持系統(tǒng)復(fù)雜均衡；而在單機環(huán)境下，亦可以保證內(nèi)存中頂點體上呈現(xiàn)局部有序性。當(dāng)前存在眾多的圖社區(qū)檢測算法，如 M
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP311.12

【相似文獻】

相關(guān)期刊論文 前10條

1 孫宏放;彭秀艷;趙希人;;改進周期圖算法及在船舶運動預(yù)報中的應(yīng)用[J];哈爾濱工程大學(xué)學(xué)報;2008年11期

2 徐耀東;楊華;魏大名;;計算機體表電位作圖方法的研究[J];醫(yī)療器械;1987年04期

3 孫重春;;快速計算煙道尺寸的圖算法[J];化肥設(shè)計;1988年02期

4 傅鐘鵬;;建筑工人實用數(shù)學(xué) 第三十八講 圖算法[J];建筑工人;1988年02期

5 劉鮮京;;中醫(yī)椎拿力學(xué)信息的處理方法[J];山東省科學(xué)院院刊;1988年02期

6 周庚生;;推件力、卸件力和頂件力的圖算法[J];鍛壓技術(shù);1988年02期

7 萬新光;;一個面向邊的圖算法通用數(shù)據(jù)結(jié)構(gòu)[J];哈爾濱科學(xué)技術(shù)大學(xué)學(xué)報;1988年02期

8 朱柏石,石維明,馬云東;用圖算法確定井巷工程的具體優(yōu)化安排[J];阜新礦業(yè)學(xué)院學(xué)報;1989年02期

9 張亞光;圖算法應(yīng)用初探[J];中國環(huán)境監(jiān)測;1989年02期

10 劉廣寬,劉美輪;上界可控的門矩陣布圖算法[J];計算機學(xué)報;1989年07期

相關(guān)會議論文 前9條

1 雷凱茹;趙海;朱宏博;樸春鶴;;基于導(dǎo)向半徑參數(shù)自適應(yīng)的數(shù)字摳圖算法[A];第十二屆沈陽科學(xué)學(xué)術(shù)年會論文集（理工農(nóng)醫(yī)）[C];2015年

2 朱更新;鄭大鐘;;一類離散事件系統(tǒng)的穩(wěn)態(tài)控制與圖算法[A];1995年中國控制會議論文集（下）[C];1995年

3 梁繼;張新煥;王建;楊燕明;;基于NDVI背景場的雪蓋制圖算法探索[A];第十五屆全國遙感技術(shù)學(xué)術(shù)交流會論文摘要集[C];2005年

4 王宇君;胡美琛;施伯樂;;外部閉包和3NF合成的快速圖算法[A];第十一屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集[C];1993年

5 蔣長輝;陳帥;薄煜明;陳育偉;;基于因子圖算法的慣性/衛(wèi)星組合導(dǎo)航系統(tǒng)可行性研究[A];2018慣性技術(shù)發(fā)展動態(tài)發(fā)展方向研討會文集[C];2018年

6 來永芳;;地下核爆炸沉降預(yù)報方法研究[A];第7屆全國核電子學(xué)與核探測技術(shù)學(xué)術(shù)年會論文集（三）[C];1994年

7 宋鴻陟;區(qū)兆明;劉超彪;傅熠;;多焦點的魚眼視圖算法的研究與應(yīng)用[A];第七屆和諧人機環(huán)境聯(lián)合學(xué)術(shù)會議（HHME2011)論文集【oral】[C];2011年

8 劉建;閻迪;官文濤;;基于模糊認知圖算法的遙測智能推送平臺設(shè)計[A];第九屆中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會論文集——S08 測試評估技術(shù)[C];2018年

9 何正焱;王厚峰;;商品品牌名稱挖掘[A];中國計算語言學(xué)研究前沿進展（2009-2011）[C];2011年

相關(guān)重要報紙文章 前1條

1 本報編輯部 整理;2018，科技將怎樣改變世界？[N];中國經(jīng)濟導(dǎo)報;2018年

相關(guān)博士學(xué)位論文 前5條

1 孫巍;視覺感知特性指導(dǎo)下的自然圖像摳圖算法研究[D];北京交通大學(xué);2015年

2 王強;頻譜管理關(guān)鍵技術(shù)[D];北京交通大學(xué);2009年

3 李一明;基于傳導(dǎo)閉包圖結(jié)構(gòu)的布圖算法研究[D];電子科技大學(xué);2011年

4 杜文俊;基于幾何的實時繪制反走樣[D];浙江大學(xué);2015年

5 張濤;高性能低能耗GPGPU計算技術(shù)研究[D];上海交通大學(xué);2015年

相關(guān)碩士學(xué)位論文 前10條

1 易前旭;基于應(yīng)用運行特征的圖數(shù)據(jù)布局與訪問優(yōu)化研究[D];華中科技大學(xué);2018年

2 肖軍;基于GPU的圖計算研究[D];湖南大學(xué);2015年

3 李平凡;GPGPU上圖處理算法的實現(xiàn)與優(yōu)化[D];國防科學(xué)技術(shù)大學(xué);2016年

4 梅珍杰;面向圖計算的優(yōu)化方法研究[D];華中科技大學(xué);2017年

5 戚駿;自然圖像摳圖算法研究與優(yōu)化[D];湖南大學(xué);2015年

6 逄瀟;基于概率圖的最小獨立圖算法研究[D];青島大學(xué);2018年

7 駱名樊;概率路標圖算法的無人機三維路徑規(guī)劃研究[D];華中科技大學(xué);2016年

8 孫國星;全自動摳圖技術(shù)的研究[D];山東師范大學(xué);2017年

9 費炳超;數(shù)字圖像摳圖算法研究[D];電子科技大學(xué);2012年

10 程賓洋;高光譜遙感蝕變礦物填圖算法并行設(shè)計與實現(xiàn)[D];成都理工大學(xué);2013年

本文編號：2689668