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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：2689668