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

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

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

【文章目錄】：
摘要
Abstract
符號(hào)使用說(shuō)明
第一章 緒論
    1.1 課題背景
        1.1.1 圖數(shù)據(jù)存儲(chǔ)與計(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)評(píng)測(cè)工作
    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)盤性能評(píng)測(cè)
        2.3.1 裸設(shè)備性能
        2.3.2 文件系統(tǒng)下設(shè)備性能
    2.4 閃存陣列性能評(píng)測(cè)
        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)存訪問(wèn)特性
        3.2.3 閃存陣列
    3.3 整體設(shè)計(jì)
        3.3.1 編程模型
        3.3.2 基于NUMA特性的數(shù)據(jù)布局和訪問(wèn)模式
        3.3.3 細(xì)粒度的edge_block過(guò)濾策略
        3.3.4 其它優(yōu)化
    3.4 實(shí)驗(yàn)與分析
        3.4.1 測(cè)試算法和數(shù)據(jù)集
        3.4.2 預(yù)處理開銷
        3.4.3 整體性能評(píng)估
        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 測(cè)試算法和數(shù)據(jù)集
        4.5.2 不同互聯(lián)模式性能比較
        4.5.3 整體性能評(píng)估
        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 問(wèn)題描述
        5.2.1 定義
        5.2.2 典型Truss分解算法
    5.3 動(dòng)機(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 整體性能評(píng)估
        5.6.3 并行化處理效果
        5.6.4 IO優(yōu)化效果
    5.7 本章小結(jié)
第六章 總結(jié)與展望
    6.1 工作總結(jié)
    6.2 未來(lái)研究工作展望
致謝
參考文獻(xiàn)
作者在學(xué)期間取得的學(xué)術(shù)成果



本文編號(hào)：3997361