基于FPGA的圖數(shù)據(jù)處理系統(tǒng)的研究與實現(xiàn).pdf

1、圖無處不在，它是用來表示實體之間關(guān)系的數(shù)據(jù)結(jié)構(gòu)，社交網(wǎng)絡(luò)，公路網(wǎng)絡(luò)和生物網(wǎng)絡(luò)等常見的信息都可以抽象成圖來表示。近年來，圖數(shù)據(jù)的處理已經(jīng)成為了數(shù)據(jù)挖掘，機器學(xué)習(xí)等新興領(lǐng)域的基礎(chǔ)技術(shù)?，F(xiàn)有的圖數(shù)據(jù)處理系統(tǒng)大都實現(xiàn)在通用處理器或者通用處理器集群上，但是由于圖數(shù)據(jù)處理的不規(guī)則訪存特性，使得其在基于通用處理器的計算平臺上的實現(xiàn)面臨著嚴(yán)重的“存儲墻”問題。
　　本文針對圖數(shù)據(jù)處理的不規(guī)則訪存特性，設(shè)計并實現(xiàn)了一個基于FPGA的圖數(shù)據(jù)處理系統(tǒng)。

2、該系統(tǒng)采用了深度流水和高度并行化的設(shè)計方法學(xué)，充分利用了FPGA片上的計算資源和片外存儲器的帶寬。系統(tǒng)主要由基本處理單元，邊緩存仲裁器和實時洗牌網(wǎng)絡(luò)等功能模塊組成。
　　本文的主要研究成果如下：
　　1.本文深入分析了由圖數(shù)據(jù)處理的不規(guī)則訪存特性而造成的“存儲墻”問題是圖數(shù)據(jù)處理系統(tǒng)的瓶頸，并針對該問題在FPGA的圖數(shù)據(jù)處理領(lǐng)域中引入了邊流式訪問模型，該模型可以充分利用FPGA的片外存儲帶寬；
　　2.為了最大化地利用

3、FPGA片上豐富的并行計算資源和節(jié)省片上存儲資源，本文基于邊流式訪問的圖數(shù)據(jù)處理模型提出了片上分布式處理單元共享片外存儲的圖數(shù)據(jù)處理系統(tǒng)架構(gòu)，該架構(gòu)可適用于多類圖數(shù)據(jù)處理問題；
　　3.本文在Xilinx ML605開發(fā)板上對文中提出的架構(gòu)進行了實現(xiàn)，并以網(wǎng)頁排名，Bellman-Ford單源最短路徑和Hash-Min連通分量計算為測試圖算法，對系統(tǒng)的正確性和有效性進行了驗證。以單位時間內(nèi)系統(tǒng)處理的邊數(shù)（GTEPs）和性能帶寬比（