GPU上圖處理并行框架的設計與實現(xiàn).pdf

1、圖是一種強大的數(shù)據(jù)結(jié)構(gòu)，它可以表達現(xiàn)實世界中事物之間錯綜復雜的關(guān)系，如城市之間道路的連接關(guān)系，網(wǎng)頁之間的引用關(guān)系，人與人之間的社交關(guān)系。近年來GPU體系結(jié)構(gòu)的蓬勃發(fā)展讓人們看到了用GPU來進行通用計算的可能性。由于GPU能夠提供大量并行線程，于是很自然地想到用它來處理圖這種蘊含海量數(shù)據(jù)并行性的數(shù)據(jù)。但在GPU上實現(xiàn)一個高效的圖應用程序仍舊面臨著許多方面的挑戰(zhàn)，其中包括串行化與工作量之間的矛盾，規(guī)則與不規(guī)則之間的矛盾，以及GPU并行編程本

2、身的復雜度。為了解決這些問題，本文提出了一個輕量級GPU圖處理框架。本文的研究工作和成果包括以下兩點:
　　(1)設計并實現(xiàn)了輕量級GPU圖編程并行框架——Olive。Olive向用戶提供了vertexSubset（頂點子集）數(shù)據(jù)類型和兩組計算函數(shù):用來進行邊計算的edgeFilter和edgeMap，以及用來進行頂點計算的vertexFilter和vertexMap。使用Olive編程框架進行圖編程就是對一系列的vertexSu

3、bset調(diào)用這兩組函數(shù)的過程。所有的底層細節(jié)都被隱藏在了系統(tǒng)背后，用戶只需要關(guān)注發(fā)生在邊和頂點上的計算即可，而不需要關(guān)心和GPU有關(guān)的任何編程細節(jié)。vertexSubset在底層使用了兩種不同的物理實現(xiàn):基于隊列的緊湊型表示和基于布爾數(shù)組的松散型表示。使用緊湊型表示作為edgeFilter的輸入可以最小化工作量，使用松散型表示作為edgeFilter的輸出則可以提高系統(tǒng)的并行性。為了證明Olive的實用性和有效性，本文基于Olive實現(xiàn)

4、了三種常用的圖算法（BFS、PageRank和Bellman-Ford單源最短路徑），并通過實驗評測了Olive系統(tǒng)的性能。實驗表明，Olive的實現(xiàn)對串行版本的加速比最高可以達到20倍。
　　(2)研究了圖不規(guī)則性和GPU執(zhí)行模型之間的關(guān)系。由于GPU中的線程以SIMD的方式執(zhí)行，在邊計算（edgeFilter和edgeMap）過程中，輸入數(shù)據(jù)的不規(guī)則性會對性能產(chǎn)生很大的影響。為了理解輸入數(shù)據(jù)對硬件利用率的影響，本文分析了15個