基于FPGA的圖計算并行算法和體系結構研究.pdf

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

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

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

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

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

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