基于GPU的圖計算研究.pdf

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

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

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

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