基于FPGA的圖計(jì)算并行算法和體系結(jié)構(gòu)研究.pdf

1、近年來，隨著現(xiàn)場可編程門陣列（FPGA）在計(jì)算、存儲(chǔ)和邏輯等資源方面的急劇增長，基于FPGA的可重構(gòu)計(jì)算成為高性能計(jì)算領(lǐng)域的一個(gè)重要分支，越來越凸顯其重要的研究和應(yīng)用價(jià)值。圖計(jì)算是大數(shù)據(jù)分析領(lǐng)域的一種關(guān)鍵應(yīng)用，在大數(shù)據(jù)分析方面具有重要作用，F(xiàn)PGA定制計(jì)算在加速圖計(jì)算方面具有巨大的潛力。然而，現(xiàn)有FPGA圖計(jì)算存在并行算法設(shè)計(jì)、并行度開發(fā)和支持圖計(jì)算規(guī)模有限等挑戰(zhàn)。為應(yīng)對(duì)這些挑戰(zhàn)，本文對(duì)大規(guī)模圖計(jì)算的FPGA實(shí)現(xiàn)技術(shù)進(jìn)行了深入研究，本文

2、的主要工作和創(chuàng)新點(diǎn)如下：
　　（1）提出了面向大規(guī)模圖最短路徑計(jì)算的FPGA并行算法和硬件實(shí)現(xiàn)結(jié)構(gòu)。針對(duì)現(xiàn)有單源路徑問題的FPGA實(shí)現(xiàn)采用片內(nèi)存儲(chǔ)資源來保存圖數(shù)據(jù)和計(jì)算結(jié)果，難以高效處理大規(guī)模圖數(shù)據(jù)處理的問題，提出了基于Eager Dijkstra算法變種的FPGA并行單源最短路徑算法，每次迭代從優(yōu)先隊(duì)列移除多個(gè)元素進(jìn)行并行處理，開發(fā)了并行性。為了實(shí)現(xiàn)大規(guī)模優(yōu)先隊(duì)列的處理，提出了基于片外存儲(chǔ)的大規(guī)模優(yōu)先隊(duì)列實(shí)現(xiàn)方法，利用片外DRA

3、M存儲(chǔ)器保存溢出隊(duì)列元素，并設(shè)計(jì)合理策略將片外元素重新放回片內(nèi)，從而保證了大規(guī)模優(yōu)先隊(duì)列處理的正確性。選取真實(shí)的公路網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行測試，實(shí)驗(yàn)結(jié)果表明基于FPGA的并行單源最短路徑算法和通用微處理器上的軟件實(shí)現(xiàn)相比可以獲得5倍的加速效果，并且功耗僅為通用微處理器的1/4。
　?。?）提出了面向大規(guī)模圖最小生成樹計(jì)算的FPGA并行算法和硬件實(shí)現(xiàn)結(jié)構(gòu)。針對(duì)現(xiàn)有最小生成樹計(jì)算的FPGA實(shí)現(xiàn)并行度開發(fā)不夠和不能處理大規(guī)模圖的問題，提出了一種基

4、于Prim算法的FPGA最小生成樹并行算法。該算法選取多個(gè)起始結(jié)點(diǎn)并行執(zhí)行Prim算法生成多個(gè)子樹，當(dāng)檢測到子樹間沖突時(shí)，停止當(dāng)前子樹生成，選擇其它的未訪問結(jié)點(diǎn)繼續(xù)生成新的子樹，當(dāng)所有結(jié)點(diǎn)都被訪問時(shí)，對(duì)所有的子樹進(jìn)行合并。對(duì)于單個(gè)子樹的Prim計(jì)算，提出了基于線性陣列優(yōu)先隊(duì)列的實(shí)現(xiàn)方法，當(dāng)優(yōu)先隊(duì)列溢出時(shí)，采用DRAM存儲(chǔ)溢出隊(duì)列元素，實(shí)現(xiàn)了大規(guī)模子樹生成。選取隨機(jī)生成圖進(jìn)行測試，實(shí)驗(yàn)結(jié)果表明基于FPGA的并行最小生成樹算法和通用微處理器

5、上的軟件實(shí)現(xiàn)相比可以獲得2.58倍到6.88倍的加速比。
　?。?）提出了面向大規(guī)模圖寬度優(yōu)先搜索（BFS）的FPGA消息傳遞并行算法和硬件實(shí)現(xiàn)結(jié)構(gòu)。針對(duì)大規(guī)模并行寬度優(yōu)先搜索通信延遲大的問題，首次提出了一種新穎的基于二維消息傳遞陣列結(jié)構(gòu)的并行寬度優(yōu)先搜索算法，利用片上存儲(chǔ)減少了處理單元之間的通信延遲。與相關(guān)工作相比，該結(jié)構(gòu)顯著減少了片上存儲(chǔ)資源的消耗，并且具備良好的可擴(kuò)展性，能夠映射到多FPGA系統(tǒng)。此外，提出了一種基于片上位圖

6、存儲(chǔ)的分布式隊(duì)列實(shí)現(xiàn)方法，該方法避免了為判斷頂點(diǎn)是否為當(dāng)前層待搜索頂點(diǎn)而引入的片外訪存開銷。使用不同類型的圖進(jìn)行了測試，并與相關(guān)工作進(jìn)行了比較。由于隨機(jī)訪存的延遲較大，單片F(xiàn)PGA上的BFS算法實(shí)測性能低于相關(guān)工作的性能。盡管如此，本文提出的FPGA并行BFS算法和硬件結(jié)構(gòu)在理論上能夠擴(kuò)展到任意數(shù)量FPGA構(gòu)成的計(jì)算系統(tǒng)。
　?。?）提出了面向大規(guī)模圖匹配的FPGA并行算法和硬件實(shí)現(xiàn)結(jié)構(gòu)。針對(duì)現(xiàn)有二部圖圖匹配計(jì)算的FPGA實(shí)現(xiàn)基于