基于GPU的并行圖算法研究.pdf

1、圖形處理器（GPU：Graphics Processing Unit）傳統(tǒng)上是作為一種外設(shè)用來加速3D圖形渲染，但隨著其功能和性能的逐步加強，如今它已經(jīng)成為一種流行的通用計算設(shè)備。隨著CPU單核心性能的進化陷入瓶頸，同時多核CPU正在蓬勃發(fā)展，需要把注意力從單線程程序轉(zhuǎn)移到多線程程序上，才能從多核CPU中獲益。這就要求開發(fā)者必須設(shè)計相應(yīng)的并行算法來代替串行算法?，F(xiàn)代GPU將多核處理器的設(shè)計思路推向了極致，在一塊芯片上集成了成百上千個核心

2、。與CPU相比，GPU具有高性能、高能耗比、低成本等優(yōu)勢，因此利用GPU來提升算法性能得到了廣泛的關(guān)注。
　　然而，GPU有自己獨特的編程方式和算法設(shè)計思想，讓習慣編寫CPU程序的人很容易犯錯，寫出低效的GPU程序。因此需要深入研究GPU全新的編程模型，包括硬件結(jié)構(gòu)、編程環(huán)境、程序執(zhí)行方式以及性能優(yōu)化方法等，對它們的深入研究和理解是設(shè)計高性能GPU算法的基礎(chǔ)。在此基礎(chǔ)上，高效實現(xiàn)了需要在后續(xù)算法中使用到的reduce、scan等原

3、語操作，這些操作對于所提出算法的性能表現(xiàn)有至關(guān)重要的影響。
　　圖算法的大數(shù)據(jù)量、高并發(fā)度和高性能要求的特點使其很適合利用GPU進行處理，因此近幾年來基于GPU的圖算法研究成為了一個熱點。廣度優(yōu)先搜索（BFS：Breadth-First Search）是最底層最基礎(chǔ)的圖算法之一，它一般作為其他復(fù)雜算法的構(gòu)成單元，其性能對整個算法會產(chǎn)生重大影響，因此值得進行深入研究?，F(xiàn)有的GPU BFS算法均存在較大的負載不均問題，導(dǎo)致算法的性能受

4、圖結(jié)構(gòu)的影響較大，表現(xiàn)不夠穩(wěn)定。針對此問題提出了一個新的BFS算法，第一次實現(xiàn)了完全的負載均衡。該算法將每一輪BFS循環(huán)分解為兩個階段：工作重分配與鄰接頂點獲取。工作重分配階段使用一個并行化的expand操作來從全局范圍內(nèi)重新組織輸入的工作負載，然后鄰接頂點獲取階段以負載均衡的方式實現(xiàn)對鄰接頂點的并行訪問。實驗結(jié)果表明，對比CPU上的串行BFS實現(xiàn)與現(xiàn)有最高效的GPU BFS實現(xiàn)，所提出的算法分別能夠取得最高39倍和1.42倍的性能提升

5、。
　　強連通分量（SCC：Strongly Connected Component）分解是另一個基礎(chǔ)圖算法。現(xiàn)有的GPU SCC分解算法基本上是CPU算法的直接移植，沒有充分考慮GPU的架構(gòu)特性，性能表現(xiàn)受到很大局限。針對這一問題，提出了一個新的SCC分解算法。它完全基于GPU架構(gòu)，以前向和反向可達集合查詢?yōu)榛A(chǔ)，通過一種迭代形式的分治策略來識別每一個SCC。算法中引入了很多專門針對GPU架構(gòu)所設(shè)計的優(yōu)化方法，如基于BFS的高效