發(fā)布時(shí)間：2024-06-29 07:24

　　圖結(jié)構(gòu)具有很強(qiáng)的表達(dá)能力,現(xiàn)實(shí)世界中諸多實(shí)體以及實(shí)體之間的聯(lián)系可以抽象成圖中的頂點(diǎn)和邊,通過分析圖數(shù)據(jù)來挖掘有價(jià)值的信息,具有重要的現(xiàn)實(shí)意義。近幾年來,圖數(shù)據(jù)迅速增長,網(wǎng)頁搜索、社交網(wǎng)絡(luò)、生物信息等領(lǐng)域圖建模早已達(dá)十億甚至千億規(guī)模。并且,圖本身呈現(xiàn)的冪律分布和隨機(jī)訪問等特性,使得在圖數(shù)據(jù)處理過程中很難利用時(shí)間和空間局部性。以上問題為設(shè)計(jì)高效的圖計(jì)算框架帶來了嚴(yán)峻挑戰(zhàn)。單機(jī)圖計(jì)算框架以其能夠充分利用計(jì)算和存儲資源、線程間通信更加高效以及編程簡潔易懂等優(yōu)勢,逐漸成為研究熱點(diǎn)。本文圍繞圖計(jì)算面臨的諸多難題,針對單機(jī)上高效圖計(jì)算框架的設(shè)計(jì)與實(shí)現(xiàn)開展了深入研究,主要工作和創(chuàng)新點(diǎn)如下:1.基于閃存的冗余陣列構(gòu)建方法。閃存相對磁盤具有高帶寬、低延遲、隨機(jī)讀寫性能好等優(yōu)勢,為了進(jìn)一步縮短與內(nèi)存之間的性能差距,為圖計(jì)算提供高速外部存儲,我們探究了高速閃存陣列的構(gòu)建方法。我們分別選用SATA和PCIe兩種接口的固態(tài)盤,組成了RAIS0,5和6三種模式下的閃存陣列。然后,分析了隊(duì)列深度和請求粒度對單塊固態(tài)盤和閃存陣列性能發(fā)揮的影響,測試了掛載四種主流文件系統(tǒng)XFS、EXT4、F2FS和Btr FS后單盤和閃...

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

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

【文章目錄】：
摘要
Abstract
符號使用說明
第一章 緒論
    1.1 課題背景
        1.1.1 圖數(shù)據(jù)存儲與計(jì)算
        1.1.2 圖計(jì)算面臨的挑戰(zhàn)
    1.2 相關(guān)工作
        1.2.1 基于外存的圖計(jì)算框架
        1.2.2 基于內(nèi)存的圖計(jì)算框架
        1.2.3 基于異構(gòu)的圖計(jì)算框架
        1.2.4 圖計(jì)算相關(guān)評測工作
    1.3 本文研究的主要內(nèi)容和貢獻(xiàn)
    1.4 論文組織結(jié)構(gòu)
第二章 基于閃存的冗余陣列構(gòu)建方法
    2.1 引言
    2.2 背景
        2.2.1 固態(tài)盤
        2.2.2 閃存陣列
        2.2.3 文件系統(tǒng)
    2.3 單塊固態(tài)盤性能評測
        2.3.1 裸設(shè)備性能
        2.3.2 文件系統(tǒng)下設(shè)備性能
    2.4 閃存陣列性能評測
        2.4.1 裸設(shè)備性能
        2.4.2 文件系統(tǒng)下設(shè)備性能
    2.5 閃存陣列構(gòu)建方法討論
    2.6 本章小結(jié)
第三章 基于NUMA架構(gòu)的外存圖計(jì)算框架HPGraph
    3.1 引言
    3.2 背景
        3.2.1 圖計(jì)算編程模型
        3.2.2 非統(tǒng)一內(nèi)存訪問特性
        3.2.3 閃存陣列
    3.3 整體設(shè)計(jì)
        3.3.1 編程模型
        3.3.2 基于NUMA特性的數(shù)據(jù)布局和訪問模式
        3.3.3 細(xì)粒度的edge_block過濾策略
        3.3.4 其它優(yōu)化
    3.4 實(shí)驗(yàn)與分析
        3.4.1 測試算法和數(shù)據(jù)集
        3.4.2 預(yù)處理開銷
        3.4.3 整體性能評估
        3.4.4 相關(guān)優(yōu)化效果
        3.4.5 閃存陣列帶寬和處理器資源使用情況
    3.5 本章小結(jié)
第四章 基于眾核處理器的內(nèi)存圖計(jì)算框架Ants
    4.1 引言
    4.2 背景
        4.2.1 圖結(jié)構(gòu)特性
        4.2.2 圖數(shù)據(jù)分析
        4.2.3 眾核處理器架構(gòu)
    4.3 挑戰(zhàn)
        4.3.1 異構(gòu)內(nèi)存和數(shù)據(jù)布局
        4.3.2 緩存一致性和任務(wù)調(diào)度
    4.4 整體設(shè)計(jì)
        4.4.1 編程模型
        4.4.2 基于異構(gòu)內(nèi)存的數(shù)據(jù)布局策略
        4.4.3 基于Mesh互聯(lián)的任務(wù)調(diào)度機(jī)制
        4.4.4 其它優(yōu)化
    4.5 實(shí)驗(yàn)與分析
        4.5.1 測試算法和數(shù)據(jù)集
        4.5.2 不同互聯(lián)模式性能比較
        4.5.3 整體性能評估
        4.5.4 數(shù)據(jù)布局優(yōu)化效果
        4.5.5 任務(wù)調(diào)度優(yōu)化效果
        4.5.6 Open MP實(shí)現(xiàn)
        4.5.7 多核體系結(jié)構(gòu)上優(yōu)化效果
    4.6 本章小結(jié)
第五章 基于內(nèi)存的快速Truss分解算法p TD
    5.1 引言
    5.2 問題描述
        5.2.1 定義
        5.2.2 典型Truss分解算法
    5.3 動機(jī)
    5.4 快速Truss分解算法
    5.5 并行及IO相關(guān)優(yōu)化
    5.6 實(shí)驗(yàn)與分析
        5.6.1 實(shí)驗(yàn)環(huán)境
        5.6.2 整體性能評估
        5.6.3 并行化處理效果
        5.6.4 IO優(yōu)化效果
    5.7 本章小結(jié)
第六章 總結(jié)與展望
    6.1 工作總結(jié)
    6.2 未來研究工作展望
致謝
參考文獻(xiàn)
作者在學(xué)期間取得的學(xué)術(shù)成果



本文編號：3997361