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

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

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

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

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

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