伴隨著圖處理的快速發(fā)展,包括數(shù)據(jù)規(guī)模、數(shù)據(jù)類型,以及圖應(yīng)用在內(nèi)的多方面因素,顯著影響著訪存特征。圖處理的過程一般分為多次迭代進(jìn)行,每一次迭代過程中同時存在著活躍數(shù)據(jù)和不活躍數(shù)據(jù),而當(dāng)前圖處理主要的研究方向是通過努力獲取訪問數(shù)據(jù)的局部性,減少隨機(jī)訪問請求以提高I/O速度,這主要是針對活躍數(shù)據(jù)的優(yōu)化工作,但是處理過程中暫不參與處理的數(shù)據(jù),也會給存儲系統(tǒng)造成負(fù)擔(dān),其同樣受圖處理訪存高隨機(jī)性的影響,很難在圖處理過程中削減,因此為了更好地優(yōu)化圖處理,在提高活躍數(shù)據(jù)訪問速度的同時,需要考慮減少不活躍數(shù)據(jù)的傳輸量。通過綜合分析活躍數(shù)據(jù)和不活躍數(shù)據(jù)的特征,基于頂點(diǎn)的活躍度提出一種通用的圖數(shù)據(jù)布局策略VAL。它同時兼顧活躍數(shù)據(jù)和不活躍數(shù)據(jù)的分布,使它們分別采用不同的方法組織,一方面高效緩存活躍數(shù)據(jù),另一方面有效調(diào)度不活躍數(shù)據(jù)。首先基于中介中心性劃分活躍和不活躍頂點(diǎn)集,接著對活躍頂點(diǎn)集集中編排,聚集存儲,提高局部性,然后根據(jù)度中心性和直接鄰接關(guān)系兩種數(shù)據(jù)特征重編排不活躍頂點(diǎn)集,提高不活躍數(shù)據(jù)的局部性,最后針對布局后的不活躍數(shù)據(jù)設(shè)計(jì)了一種新的篩選策略,使得CPU請求數(shù)據(jù)時不僅提高了數(shù)據(jù)訪問速度,也充分去除無...

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

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

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 研究背景及意義
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 主要工作和論文組織結(jié)構(gòu)
2 當(dāng)前圖處理數(shù)據(jù)組織的分析
    2.1 GraphChi的數(shù)據(jù)組織和訪問
    2.2 X-Stream的數(shù)據(jù)組織和訪問
    2.3 GridGraph的數(shù)據(jù)組織和訪問
    2.4 不活躍數(shù)據(jù)對圖處理的影響
    2.5 圖數(shù)據(jù)布局方法
    2.6 本章小結(jié)
3 基于活躍度的數(shù)據(jù)布局策略
    3.1 整體設(shè)計(jì)
    3.2 活躍頂點(diǎn)集的劃分
    3.3 不活躍頂點(diǎn)的布局
    3.4 對不活躍數(shù)據(jù)的篩選方法
    3.5 實(shí)現(xiàn)方案
    3.6 本章小結(jié)
4 測試與結(jié)果分析
    4.1 測試環(huán)境與方案
    4.2 測試與分析
    4.3 本章小結(jié)
5 總結(jié)與展望
    5.1 工作總結(jié)
    5.2 研究展望
致謝
參考文獻(xiàn)
附錄1 攻讀碩士學(xué)位期間發(fā)表的論文和專利
附錄2 攻讀碩士學(xué)位期間參與的科研項(xiàng)目



本文編號：3836192