基于GPU的圖計(jì)算研究.pdf

1、圖算法一直是學(xué)術(shù)界和工業(yè)界的研究熱點(diǎn)。隨著社交網(wǎng)絡(luò)和大數(shù)據(jù)爆炸式增長，基于大圖數(shù)據(jù)的應(yīng)用逐漸增多。Google提出了Pregel圖計(jì)算系統(tǒng)，解決關(guān)于大圖數(shù)據(jù)的分布式計(jì)算問題。Pregel編程模型為用戶抽象分布式計(jì)算的實(shí)現(xiàn)細(xì)節(jié)，提供了簡明的API實(shí)現(xiàn)圖算法。隨著 GPU軟硬件技術(shù)的發(fā)展，與CPU相比，GPU逐漸演變成為高度并行的多線程及多核處理器，同時(shí)具有強(qiáng)大的計(jì)算能力和超高的內(nèi)存帶寬。越來越多的圖算法使用GPU來提升計(jì)算性能，并利用GP

2、U的硬件特性優(yōu)化圖算法。
　　但是目前大部分基于GPU的圖計(jì)算研究都是針對(duì)特定的圖算法，缺乏基于GPU的類Pregel系統(tǒng)，為圖算法提供基于GPU的通用圖計(jì)算系統(tǒng)。而且當(dāng)前的系統(tǒng)尚未根據(jù)圖算法特點(diǎn)和GPU硬件特性，對(duì)系統(tǒng)性能進(jìn)行優(yōu)化。因此，本文主要對(duì)基于GPU的圖計(jì)算進(jìn)行研究，以實(shí)現(xiàn)對(duì)基于GPU的Pregel編程模型進(jìn)行改進(jìn)，分析圖計(jì)算出現(xiàn)的性能瓶頸問題，提出相關(guān)的系統(tǒng)級(jí)優(yōu)化算法?；谝陨涎芯砍晒?，本文實(shí)現(xiàn)了基于GPU的圖計(jì)算系統(tǒng)

3、PregelGPU。論文的主要工作如下：
　　首先，討論GPU體系結(jié)構(gòu)的基礎(chǔ)知識(shí)，歸納圖計(jì)算的研究進(jìn)展。著重闡述圖計(jì)算系統(tǒng)的編程模型和執(zhí)行流程，并分析相關(guān)系統(tǒng)的不足。
　　其次，GPU線程具有細(xì)粒度并行的特點(diǎn)，改進(jìn)傳統(tǒng)的頂點(diǎn)編程模型，提出基于GPU的通用圖編程模型—Edge-Vertex編程模型，為圖算法提供類似Pregel的API。同時(shí)根據(jù)Edge-Vertex編程模型，設(shè)計(jì)圖系統(tǒng)的執(zhí)行流程，把整個(gè)系統(tǒng)執(zhí)行階段劃分成預(yù)處理

4、階段、EdgeCompute和VertexCompute，并闡述各個(gè)階段的執(zhí)行任務(wù)和邏輯操作。
　　最后，分析Edge-Vertex編程模型的性能瓶頸，提出相應(yīng)的解決方案。由于基于GPU的圖計(jì)算存在線程負(fù)載不均衡問題，提出基于GPU的近似排序算法，緩解線程任務(wù)分配不均衡的壓力。根據(jù)GPU合并訪問全局內(nèi)存的特性，提出應(yīng)用于消息緩存的數(shù)據(jù)重映射算法，減少非合并訪存次數(shù)，提高全局內(nèi)存的實(shí)際帶寬利用率。實(shí)驗(yàn)顯示在不同的數(shù)據(jù)集和圖算法下，和