互聯(lián)網(wǎng)的迅速發(fā)展使得網(wǎng)絡(luò)圖成為了研究和分析的熱點,而機器學(xué)習(xí)和數(shù)據(jù)挖掘等面向圖數(shù)據(jù)結(jié)構(gòu)的技術(shù)也已經(jīng)在社交網(wǎng)絡(luò)分析、網(wǎng)絡(luò)搜索、自然語言處理和推薦系統(tǒng)等領(lǐng)域得到了廣泛的應(yīng)用。PowerGraph提出了GAS（Gather Apply Scatter）抽象以及點切割的圖分區(qū)算法。本論文分析了圖算法執(zhí)行過程中消息傳輸模型及數(shù)據(jù)緩存機制的網(wǎng)絡(luò)通信行為,發(fā)現(xiàn)PowerGraph中原有的消息傳輸模型僅采用推送模式,可能導(dǎo)致Master副本無法及時從Mirror副本獲取到最新消息,或者Mirror副本可能會傳送多條消息給Master副本;除此之外,在PowerGraph點切割分區(qū)方法下原本的數(shù)據(jù)緩存機制只能夠減少計算開銷,卻無法減少網(wǎng)絡(luò)開銷,而且開發(fā)人員必須自己實現(xiàn)緩存相關(guān)的代碼,導(dǎo)致開發(fā)人員的使用成本也有所增高。針對上述問題,本文做了詳盡的分析調(diào)研并提出了相應(yīng)的解決方案,主要內(nèi)容包括以下兩個方面。為了解決PowerGraph消息傳輸模型的問題,本文提出了一種新的模型:首先,由Mirror副本接收的消息總是存儲在本地,并且將與新接收到的消息合并,直到Mirror副本被調(diào)度后才將合并后的消息發(fā)送給Mas... 

【文章來源】：電子科技大學(xué)四川省 211工程院校 985工程院校 教育部直屬院校

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

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

【文章目錄】：
摘要
ABSTRACT
第一章 緒論
    1.1 研究工作的背景
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 主要研究內(nèi)容
    1.4 論文組織結(jié)構(gòu)
第二章 圖計算框架概述
    2.1 單機圖計算系統(tǒng)
        2.1.1 GraphChi
        2.1.2 X-stream
        2.1.3 Grid Graph
    2.2 分布式圖計算系統(tǒng)
        2.2.1 Pregel
        2.2.2 Giraph
        2.2.3 GPS
        2.2.4 Pregel+
        2.2.5 GraphX
    2.3 PowerGraph及其優(yōu)化
        2.3.1 PowerGraph架構(gòu)簡介
            2.3.1.1 GAS模型
            2.3.1.2 執(zhí)行引擎
            2.3.1.3 點切割圖分區(qū)
        2.3.2 PowerGraph相關(guān)優(yōu)化
    2.4 本章小結(jié)
第三章 消息傳輸機制中的拉取模型
    3.1 現(xiàn)有機制存在的問題
    3.2 系統(tǒng)設(shè)計
        3.2.1 消息傳輸
        3.2.2 迭代流程
        3.2.3 模型設(shè)計
    3.3 系統(tǒng)實現(xiàn)
    3.4 本章小結(jié)
第四章 基于單副本集中式緩存的迭代加速技術(shù)
    4.1 原系統(tǒng)中的分布式緩存機制
    4.2 分布式緩存機制的不足
    4.3 緩存機制的設(shè)計
        4.3.1 多副本緩存機制
        4.3.2 單副本緩存機制
        4.3.3 緩存機制的空間影響
    4.4 緩存機制的適用范圍
        4.4.1 圖著色應(yīng)用
        4.4.2 消息傳遞應(yīng)用
        4.4.3 其它應(yīng)用
    4.5 數(shù)據(jù)緩存機制與消息拉取模型的合并
    4.6 本章小結(jié)
第五章 實驗評估
    5.1 實驗配置
        5.1.1 實驗使用的集群環(huán)境
        5.1.2 實驗使用的圖應(yīng)用
        5.1.3 實驗使用的數(shù)據(jù)集
    5.2 實驗結(jié)果
        5.2.1 不同應(yīng)用的實驗結(jié)果
            5.2.1.1 消息拉取模型與原系統(tǒng)的比較
            5.2.1.2 數(shù)據(jù)緩存機制與原系統(tǒng)的比較
            5.2.1.3 合并后的系統(tǒng)與原系統(tǒng)的比較
        5.2.2 不同數(shù)據(jù)集的實驗結(jié)果
            5.2.2.1 消息拉取模型與原系統(tǒng)的比較
            5.2.2.2 數(shù)據(jù)緩存機制與原系統(tǒng)的比較
            5.2.2.3 合并后的系統(tǒng)與原系統(tǒng)的比較
        5.2.3 不同機器數(shù)的實驗結(jié)果
            5.2.3.1 消息拉取模型與原系統(tǒng)的比較
            5.2.3.2 數(shù)據(jù)緩存機制與原系統(tǒng)的比較
            5.2.3.3 合并后的系統(tǒng)與原系統(tǒng)的比較
    5.3 本章小結(jié)
第六章 總結(jié)與展望
    6.1 全文總結(jié)
    6.2 后續(xù)工作展望
致謝
參考文獻
攻碩期間取得的研究成果



本文編號：3375301