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

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

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

【學位級別】：博士

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



本文編號：3997361