發(fā)布時間：2021-01-18 05:16

　　圖計算能夠挖掘事物之間潛在不易洞察的行為和聯(lián)系,廣泛應(yīng)用于服務(wù)推薦、欺詐檢測、風(fēng)投分析、市場營銷、疾病建模等領(lǐng)域。隨著互聯(lián)網(wǎng)等領(lǐng)域的發(fā)展,圖數(shù)據(jù)規(guī)模爆炸增長的同時,各種圖分析算法不斷涌現(xiàn)。在圖處理平臺上,大量圖算法并發(fā)地對共享的圖結(jié)構(gòu)進(jìn)行處理,形成了并發(fā)圖分析任務(wù)。與CPU相比,GPU具有更強(qiáng)的并行計算能力,因此由CPU和GPU組成的異構(gòu)環(huán)境更適合大規(guī)模圖處理。然而,在當(dāng)前的GPU圖計算系統(tǒng)中,并發(fā)圖分析任務(wù)獨(dú)立地沿著不同的路徑訪問共享圖,由于嚴(yán)重的數(shù)據(jù)帶寬競爭和緩存干擾,導(dǎo)致較高的訪存計算比,降低系統(tǒng)吞吐率。為解決上述問題,實(shí)現(xiàn)了數(shù)據(jù)驅(qū)動的并發(fā)圖分析任務(wù)執(zhí)行機(jī)制,支持高效的并發(fā)圖計算。首先,為多GPU節(jié)點(diǎn)建立異步通信機(jī)制,實(shí)現(xiàn)圖算法的異步執(zhí)行模型,避免同步編程模型的大量同步開銷;其次,在GPU的本地計算階段實(shí)現(xiàn)數(shù)據(jù)驅(qū)動的并發(fā)圖分析任務(wù)執(zhí)行機(jī)制,將圖數(shù)據(jù)劃分成大小合適的塊,按照一定的順序載入緩存中,然后觸發(fā)多個相關(guān)任務(wù)并發(fā)處理,減少總的數(shù)據(jù)訪問需求;最后,實(shí)現(xiàn)了一個圖劃分塊調(diào)度器,最大化并發(fā)圖分析任務(wù)數(shù)據(jù)訪問的關(guān)聯(lián)性;此外,通過給待處理的頂點(diǎn)賦予優(yōu)先級解決異步編程模型可能導(dǎo)致的冗余計算... 

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

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

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

【部分圖文】：

同步（上）和異步（下）編程模型比較

理一個共享圖，由圖劃分塊 1 和圖劃分塊 2 組成。用現(xiàn)存的解決方案，SSSP 能先訪問劃分塊 1，接著訪問劃分塊 2，而 PageRank 任務(wù)可能先訪問劃分塊訪問劃分塊 1。而且不同任務(wù)對每個劃分塊的處理是不同的，使得數(shù)據(jù)訪問更規(guī)律性。結(jié)果，劃分塊 1 和 2 需要被重復(fù)地載入緩存，這導(dǎo)致嚴(yán)重的數(shù)據(jù)訪競爭和緩存干擾。如圖 2.3 是在某社交網(wǎng)路上對不同數(shù)目并發(fā)任務(wù)共享圖的比例隨時間進(jìn)行采從圖 2.3 可以發(fā)現(xiàn)，由于重復(fù)遍歷共享圖并發(fā)任務(wù)的數(shù)據(jù)訪問有很強(qiáng)的空間和聯(lián)性。這意味著并發(fā)圖分析任務(wù)存在冗余訪問，很多緩存空間被浪費(fèi)于在不間存儲相同圖數(shù)據(jù)的拷貝。如圖 2.3 展示的，每輪迭代中不同任務(wù)處理的圖劃分塊的交集很大（平均超的所有活躍劃分塊），這叫做空間關(guān)聯(lián)性。然而，在現(xiàn)存的系統(tǒng)中并發(fā)圖分析不同的順序訪問共享圖劃分塊。理想情況下，并發(fā)任務(wù)應(yīng)該合并對共享圖結(jié)問，在緩存中存儲一份共享數(shù)據(jù)同時服務(wù)多個任務(wù)。

華 中 科 技 大 學(xué) 碩 士 學(xué) 位 論 文載進(jìn)去。每載入一個圖劃分塊，然后觸發(fā)并發(fā)任務(wù)進(jìn)行處理，避免各圖別加載它。當(dāng)一個圖劃分塊被對應(yīng)所有任務(wù)處理完之后才能載入下一個并發(fā)處理模塊給待處理的圖劃分塊設(shè)置優(yōu)先級，每次調(diào)度最多圖分析任的、擁有最高平均頂點(diǎn)度數(shù)的圖劃分塊，從而最大化并發(fā)圖分析任務(wù)數(shù)關(guān)性。

【參考文獻(xiàn)】：
期刊論文
[1]并行原型系統(tǒng)上BFS算法設(shè)計實(shí)現(xiàn)與測試分析[J]. 衡冬冬,唐玉華,易曉東,劉向陽,周侗.  計算機(jī)工程與科學(xué). 2017(01)
[2]工業(yè)控制系統(tǒng)信息安全審計系統(tǒng)分析與設(shè)計[J]. 陳莊,黃勇,鄒航.  計算機(jī)科學(xué). 2013(S1)
[3]相關(guān)任務(wù)圖的均衡動態(tài)關(guān)鍵路徑調(diào)度算法[J]. 石威,鄭緯民.  計算機(jī)學(xué)報. 2001(09)

博士論文
[1]眾核GPU體系結(jié)構(gòu)相關(guān)技術(shù)研究[D]. 陳鋼.復(fù)旦大學(xué) 2011



本文編號：2984347