隨著互聯(lián)網(wǎng)的發(fā)展和大數(shù)據(jù)時代的到來,對海量大規(guī)模數(shù)據(jù)進行快速分析的需求變得更加迫切,圖作為一種抽象數(shù)據(jù)結(jié)構(gòu),許多實際應用中的大數(shù)據(jù)都是以圖的形式呈現(xiàn),使用圖數(shù)據(jù)結(jié)構(gòu)來描述數(shù)據(jù)間的關系,如社交網(wǎng)絡關系挖掘、電子商務推薦系統(tǒng)、交通事故對路網(wǎng)的影響等大規(guī)模圖計算問題。此外,許多非圖數(shù)據(jù)結(jié)構(gòu)的大數(shù)據(jù),也常常會被轉(zhuǎn)換為圖模型后再進行處理和分析,面向大規(guī)模圖數(shù)據(jù)處理的研究正成為學術(shù)界和工業(yè)界廣泛關注的焦點。為適應圖數(shù)據(jù)規(guī)模巨大、動態(tài)變化等特點,實現(xiàn)大規(guī)模圖數(shù)據(jù)的高效分析計算,近年來在計算模型和運行時優(yōu)化方面(包括分布式系統(tǒng)、異構(gòu)系統(tǒng)等)涌現(xiàn)出許多具有前瞻性的技術(shù)和圖計算系統(tǒng)�；诖�,設計實現(xiàn)高性能圖計算系統(tǒng)具有理論研究和實際應用的重要意義。本文針對異構(gòu)多核架構(gòu)的圖計算系統(tǒng)進行了深入的研究,主要工作如下:第一,目前GPU圖計算的研究分為專用的圖計算系統(tǒng)和通用的圖計算框架,前者使用GPU加速某一種特定的圖算法,如廣度優(yōu)先搜索算法,后者側(cè)重于設計適用于各種不同的圖算法的通用計算架構(gòu)。這兩類系統(tǒng)都取得了很好的研究成果,但它們之間在設計、實現(xiàn)、優(yōu)化等方面存在哪些異同點,仍然缺乏清晰的認識。通用圖計算框架可以...

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

【學位級別】：博士

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 異構(gòu)圖計算系統(tǒng)概要
    1.2 國內(nèi)外研究現(xiàn)狀
        1.2.1 單機圖計算系統(tǒng)
        1.2.2 GPU加速的圖計算系統(tǒng)
        1.2.3 分布式圖計算系統(tǒng)
    1.3 本文主要工作
    1.4 本文組織結(jié)構(gòu)
第2章 相關技術(shù)背景介紹
    2.1 大規(guī)模圖計算模型
        2.1.1 以頂點為中心的計算模型
        2.1.2 GAS計算模型
        2.1.3 以邊為中心的計算模型
    2.2 GPU體系結(jié)構(gòu)
        2.2.1 GPU和CUDA
        2.2.2 GPU線程調(diào)度機制
    2.3 圖的相關概念與常見的圖算法
        2.3.1 圖的基本概念
        2.3.2 圖的存儲
        2.3.3 常見的圖算法
    2.4 本章小結(jié)
第3章 專用和通用GPU圖計算系統(tǒng)分析
    3.1 通用圖計算系統(tǒng)Gunrock
    3.2 專用圖計算系統(tǒng)Enterprise
    3.3 評估與分析
        3.3.1 總體性能
        3.3.2 負載均衡
        3.3.3 同步操作
        3.3.4 內(nèi)存子系統(tǒng)
        3.3.5 討論分析
    3.4 本章小結(jié)
第4章 GPU圖計算系統(tǒng)設計與優(yōu)化
    4.1 引言
    4.2 Pregel圖計算系統(tǒng)簡介
    4.3 Medusa圖計算系統(tǒng)
        4.3.1 Medusa編程模型
        4.3.2 Medusa消息緩存
        4.3.3 Medusa存在的問題
    4.4 系統(tǒng)設計與實現(xiàn)
        4.4.1 執(zhí)行流程介紹
        4.4.2 編程接口
        4.4.3 運行時系統(tǒng)
        4.4.4 示例圖算法
        4.4.5 系統(tǒng)性能分析
    4.5 優(yōu)化方法
        4.5.1 負載均衡優(yōu)化策略
        4.5.2 消息緩存存儲結(jié)構(gòu)優(yōu)化策略
    4.6 實驗評估
        4.6.1 整體性能
        4.6.2 近似排序算法性能分析
        4.6.3 數(shù)據(jù)重映射策略性能評估
    4.7 本章小結(jié)
第5章 多核圖計算系統(tǒng)設計
    5.1 引言
    5.2 系統(tǒng)設計與實現(xiàn)
        5.2.1 基于協(xié)程的編程模型
        5.2.2 消息傳遞機制
        5.2.3 圖編程模型
        5.2.4 數(shù)據(jù)存儲
        5.2.5 數(shù)據(jù)訪問模式
        5.2.6 I/O優(yōu)化策略
        5.2.7 系統(tǒng)執(zhí)行流程
    5.3 實驗分析
        5.3.1 圖數(shù)據(jù)集
        5.3.2 實驗平臺介紹
        5.3.3 實驗過程介紹
        5.3.4 性能分析
    5.4 本章小結(jié)
結(jié)論
參考文獻
附錄A 讀學位期間所發(fā)表的學術(shù)論文
附錄B 讀學位期間所參加的科研項目
致謝



本文編號：3852171