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

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

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

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



本文編號(hào)：3852171