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

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

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

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

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