基于BFS 和FPGA-CPU 的混合加速器設計*

郭小波，楊光露

（1.河南工程學院計算機學院，鄭州 451191；2.糧食信息處理與控制教育部重點實驗室，鄭州 450002；3.河南中煙工業有限責任公司南陽卷煙廠，河南 南陽 473007）

0 引言

圖作為數據表示和處理圖的算法普遍存在于許多科學領域。廣度優先搜索（Breadth-First Search，BFS）是研究圖的一個關鍵構建模塊，也是各種圖指標如計算連接組件、計算圖的直徑和半徑的基礎。BFS 以及許多其他圖算法的2 個主要特性是由圖頂點和邊結構上的數據驅動計算引起的不規則的存儲訪問和較低的計算-存儲比［1］。

關于快速圖遍歷已經提出了一系列研究方法，從采用并行機制的通用CPU 和多核/超級計算方法到圖形處理單元（GPUs）、從混合CPU-GPU 方法到利用可重構硬件的方法［2］。最近在現場可編程門陣列（FPGAs）中的多軟核處理器上實現了BFS和其他不規則應用的優化［3］；已有研究探索高度并行處理單元（PEs）和解耦計算內存［1，4］，發現小世界網絡上的BFS 的執行時間受中間級的控制。文獻［1］解耦FPGAs 中的通信和計算單元，以保持不規則存儲訪問的吞吐量；文獻［4］提出了優化BFS，本質上是融合最先的2 個請求響應向量，得到了較少內存需求的改進性能；文獻［5-7］提出了在GPU上實現并行的BFS，即在水平同步［5］或定點方法［6］，以及采用高效的緩存數據結構［7］；文獻［8］提出在一個4 倍Socket 系統上局部最優化來減少內存流量，并提出采用一個壓縮格式（每個節點1 位）的位圖來跟蹤被訪問的節點；文獻［9］提出通過一種方向優化方法來減少遍歷的邊的數量，該方法在父-子和子-父遍歷之間切換，它依賴于邊沿啟發式思想。

近年來，隨著人們對節能計算系統的關注，采用可重構邏輯和FPGAs 的異構處理越來越流行，包括采用數據中心［10］；文獻［11］提出的CPU-GPU 混合方法采用的是一種切換方法；文獻［12］強調了順序模式對于采用圖算法獲得高存儲設備帶寬有明顯的優勢，并提出了一種采用流分割的以邊沿為中心的分散-聚集框架，但這種方法是以犧牲某些效率（如隨機訪問節點）來實現通用性的圖存儲，其效率對于BFS 是有限的。

本文通過對BFS 的布爾矩陣向量表示式的觀察，提出了一種無失速數據通路的FPGA-CPU 異構處理器的混合BFS 加速器結構，系統采用BFS的冗余工作-帶寬權衡算法，把BFS 前沿處理成密集的，以使得冗余計算可換取帶寬并提高BFS在混合加速器執行中的性能，總體上更接近硬件角度的思想。

1 背景知識

1.1 廣度優先搜索

考慮無向、無加權圖G=（V，E），具有|V|個頂點（節點）集V 和|E|個邊集E。BFS 從根節點vr開始，vr包含于最大連通分量vr∈Vc，Vc?V，而且遍歷相鄰vj的每條邊erj，這樣，圖就是按級遍歷的，每級的全部節點在下一級處理之前都被搜索。與其他研究搜索BFS 性能［1，4，11］的算法一樣，本文考慮得到距離數組的關鍵變量，即dist，它是根據BFS 步驟得到的每個被訪問節點與根節點的距離。

1.2 稀疏性與小世界特性

一個小世界圖就是一個直徑很小的圖，如“六度分離”，而對于社會圖如臉譜網來說，已被證明低至四度。小世界圖一般表現為無標度分布形式y=xa，即由極少數高度中心“樞紐”和形成外圍的許多低度節點構成。這意味著當BFS 開始時，存在根節點僅被連接到幾個相鄰節點的一個高概率，而且那些相鄰節點連接到少數節點，等等。因此，BFS 的第一次迭代訪問一小部分圖。但隨著越來越多的邊被遍歷，前沿規模急劇增大，就構成了很大的網絡。

2 基于BFS 和FPGA-CPU 的加速器

2.1 采用線性代數語言的BFS

本文采用“半環上矩陣”的概念［13］把BFS 表示為一個線性代數運算。核心思想是用線性代數來代替數字數據類型以及乘法和加法算子，把各種算法表示為矩陣-向量運算。

具體來說，就是在布爾半環上利用矩陣乘向量運算來實現BFS。在實際中，這個運算“乘以”一個二進制矩陣和一個二進制向量，分別用布爾與（AND）和或（OR）運算代替正規的乘法和加法運算。為了避免與實數上正規的矩陣-向量“相乘”相混淆，這里用“?”表示“相乘”運算符。每個yt=A?xt運算對應一個廣度優先步驟，而且每個結果向量yt是步驟t后圖中被訪問節點的表示。矩陣A 是圖的鄰接矩陣，同時初始輸入向量x0被初始化為全零，除了在根節點位置上的1 外。結果向量yt作為下一步的輸入向量xt+1，這反過來在它的結果向量中又得到更多的訪問節點，直至結果收斂。

2.2 解耦距離生成及布爾BFS 算法實現

在2.1 節中給出的BFS 布爾環矩陣-向量表示在存儲需求方面是非常簡潔的，這使得它適合于硬件加速器的實現。具體來說，對于每個圖節點，x 和y向量僅需要1 位存儲。由于矩陣稀疏性，y 將被隨機訪問，保持被隨機訪問數據的范圍和容量最小，對于性能是有利的。遺憾的是，迭代調用?對于BFS是不夠的，因為它只生成被訪問節點的狀態而不是dist 數組。

為此，通過在每個?調用之后，引入一個單獨的距離生成（DistGen）步驟來解決這個問題。如果一個節點i 在BFS 步驟t 的過程中被訪問，則它有距離t，而且我們知道，一個節點不能從被訪問到不被訪問。因此，如果該節點在xt中未被訪問，而在yt中被訪問，則它有距離t，或dist［i］=t?（xt［i］==0∧yt［i］==1）。為了得到距離信息，在每一步驟完成后，必須檢查每個BFS 步驟的輸入和輸出向量。這個數組比較操作來自于正規BFS 步驟被解耦，而且可以很容易并行化或用硬件實現來降低其性能開銷。采用?和DistGen 的完整BFS 算法實現如算法1。

算法1 采用?和DistGen 的BFS 算法偽代碼

2.3 帶寬和冗余計算之間的權衡

由于稀疏圖的遍歷涉及很少的實際計算，而且被視為是一個內存約束問題，故用高帶寬傳送圖數據對于加速器性能來說是至關重要的。因此，對于設計BFS 硬件加速器來說，存儲訪問模式的分析是一個關鍵步驟。在本文設計的加速器中，BFS 的輸入存儲在動態隨機存取存儲器中，而且訪問也從DRAM 中進行。

前文分析表明，輸入向量xt可以被處理為稀疏來避免冗余工作。但線性代數符號告訴我們，又可以把xt處理為密集的，而且仍然得到正確的BFS 結果。在一個混合加速器中，把BFS 輸入前沿處理為密集的看似非正常的想法和執行冗余工作對整體性能來說實際上是有利的，因為有更簡單的DRAM訪問模式。如何處理xt向量直接影響矩陣A 的數據將如何被訪問，反過來說，就是使用多少帶寬。

圖1 描述了把xt處理為稀疏如何影響矩陣數據的內存請求。加速器必須首先獲得一個節點索引，這個索引是通過讀dist 的前沿的一個成員，然后得到這個節點的開始和結束指針，并最終使用這些指針獲得相鄰邊的列表。可見，當前的請求依賴于對先前請求的響應，這是典型的間接訪問應用，而且xt的稀疏處理導致二級間接尋址。首先是請求速率受響應速率的限制，其次是elems 數組的讀脈沖的長度受節點中邊數量的限制，最后，雖然讀elems數組是按次序的，但在使用的數組部分之間可能存在較大的差距，因為前沿節點離得更遠，導致部分DRAM 行緩沖區不被使用；相反，如果把xt視為密集的，并考慮圖的每個節點，則A 的訪問模式變得非常簡單。特別地，可以簡單地讀出整個矩陣，即可以采用最大長度脈沖讀操作來完成，而無需等待來自先前請求的響應。這對于獲得高DRAM 帶寬來說，是一種更簡單和更合適的訪問模式；通過把xt視為密集的所要做的冗余工作的數量與前沿有關，前沿越小，要做的冗余工作越多。然而，由于本文構建的是一種混合CPU-FPGA 系統，加速器能處理大前沿的BFS 步驟，故冗余工作的開銷就不重要了。

圖1 稀疏xt 的內存請求結構

2.4 處理單元結構

基于2.1、2.2 和2.3 的思想，現在來描述BFS 的硬件結構。為了比較2.3 所描述的稀疏和密集xt處理的效果，考慮2 個處理單元（PE）變量。

1）密集x 變量：密集xt處理單元的體系結構如下頁圖2 所示。該體系結構以數據流方式組織，并模塊化成3 個主要組成部分：一個后端，它通過系統互連到DRAM，一個前端，用于執行?運算，以及一個距離生成器。后端負責與主存儲器的全部交互，包括讀出矩陣和向量數據，并寫入更新到距離向量。矩陣和向量數據由后端請求并提供給前端使用，前端執行BFS 步驟操作并更新結果向量存儲器。具體來說，每當輸入向量為1 時，前端僅寫1 s結果到由邊顯示的存儲地址。邊計數數據用于確定何時讀取新的輸入向量元素。一個為0 的輸入向量值意味著邊來自于一個還未被訪問過的節點，而且這個數據被簡單地丟棄而無需進一步運算。加速器的控制和狀態接口通過內存映射寄存器提供。

圖2 密集xt 處理單元的體系結構

2）稀疏x 變量：根據整體架構，稀疏xt變量與密集xt變量是相同的，除了它不需要輸入向量FIFO（因為稀疏處理意味著全部xt值是1）部分。圖3 所示為稀疏xt后端的內部結構，與密集xt變量本質上是不同的。稀疏輸入向量是通過前沿濾波器內部生成，它掃描距離數組的值，并發送索引值，全部值被寫入在先前的BFS 步驟中。之后，每個生成索引的開始和結束指針被請求，這兩個指針用于請求該節點的邊數據，并生成前端的邊計數信息。

圖3 稀疏xt 變量的后端結構

3）失速y 寫入：為了保持加速器運行而無停頓，前端能夠如后端生成數據一樣快地消耗數據是很重要的，因此，可以抽取出前端的功能作為處理一個流寫入到隨機地址。如果結果向量被存儲在DRAM 中，則連接的寫請求緩存器和存儲控制器可能填滿并暫停整個加速器。為了避免這種情況，解決方案是利用向量表示的稀疏性。由于本文的方法要求僅保留每個圖節點的1 位，故可以有效地利用片上RAM 的雙端口FPGA，在每個周期提供2 個非常快的隨機訪問。

4）距離生成器：在每個BFS 步驟完成后，調用距離生成器來執行DistGen。這涉及到比較輸入和結果向量，并找到從未被訪問過的節點到訪問過的節點。這些節點的索引被傳遞給后端作為實際寫當前BFS 距離到對應的存儲位置，并為密集變量的下一個BFS 步驟更新x 向量。

2.5 一個實際加速器系統的構建

本文構建的加速器系統采用Xilinx Zynq Z7020 FPGA-CPU 混合結構，部署在ZedBoard 平臺上［14］；加速器組件首先采用Chisel［15］構建，然后采用Verilog 后端生成Verilog 描述，并導入到Vivado 中作為IP 模塊；隨后采用Vivado IP 集成器（2014.4 版）來構建加速器系統，包括Xilinx 提供的IP 模塊作為結果存儲模塊RAM（BRAM）和AXI 的互連。64 位AXI高性能（HP）從端口可利用DRAM 帶寬的約80%（3.2 GB/s），用于提供數據給加速器；構建中還需要考慮并行性和速率平衡的實現，以及軟件BFS 的實現和FPGA-CPU 切換。前者采用并行PEs 來搜索圖，并采用FPGA 稀疏矩陣-向量乘法速率平衡思想［16］來估計平臺上需要消耗可用DRAM 帶寬的PE 數量。后者通過加入一個簡單的硬件加速器來保持來自于切換的性能開銷達到最小化。至于方法切換，在每個BFS 步驟完成后，軟件使用一個簡單的模型來決定下一步應該使用哪一種方法。BFS 開始執行軟件，當預測的BFS 步長時間對于FPGA 更短時，就切換到FPGA 執行。利用密集變量的可預測性來建模它的執行時鐘周期如下：

式中，β 是利用的帶寬部分。FPGA 繼續執行直至前沿尺寸下降到低于全部圖節點的θ%。之后，軟件BFS 接管直到搜索終止。β，θ 憑經驗確定。

3 實驗結果

為了評價本文提出的加速器系統，采用Graph500 基準參數（A=0.57，B=0.19，C=0.19）［1，4］綜合生成的RMAT 圖，把一個具有規模S（2S個節點）和邊因子E（E×2s 條邊）的RMAT 圖稱為RMATS-E。

3.1 軟件BFS 和基于BFS 的稀疏和密集變量加速器性能比較

圖4 RMAT-19-32 上加速器和軟件BFS 每步執行時間

先比較基于BFS 的稀疏和密集變量加速器與BFS 軟件算法的性能。對于2 種加速器變量，在有相等數目（4）的PE 和時鐘頻率（100 MHz）的RMAT-19-32 上執行BFS，得到的每個BFS 步驟（包括距離生成）所花的時鐘周期數如圖4 所示。從圖4 可以看到，步驟1 和2 采用CPU 即軟件BFS 搜索，步驟3 和4 切換到密集x 加速器，步驟5 和步驟6 又切換回到CPU，從而實現最快執行；密集變量加速器優于稀疏意味著從DRAM 帶寬增加帶來的好處要大于中間步驟冗余數據獲取的代價。

為了更好地理解為什么密集變量加速器在大前沿的步驟過程中優于稀疏變量加速器，實驗得到了對于BFS 的步驟3 和4 的2 種變量加速器的總的讀帶寬利用率，如圖5 所示。對于稀疏變量加速器，實際上觀察到在步驟4 中，特別低的帶寬利用率是由比步驟3 更大的前沿引起的，導致并行PE請求全部邊數組，從而導致許多DRAM 內存沖突和行緩沖失誤；另一方面，密集變量加速器的帶寬利用率遠遠高于稀疏變量加速器，在4 個PE 時峰值達到78%，而且在2 步之間沒有變化。

從圖4、圖5 可見，采用BFS 算法的軟件解決方案對于開始和結束是最好的，密集變量加速器對于中間步驟總是優于稀疏變量加速器。因此，在下面的性能評價中將省去稀疏變量加速器的結果。

圖5 RMAT-19-32 的步驟3 和4 的總讀帶寬利用率比較

3.2 單一方法和混合BFS 的性能比較

現在來比較在一個RMAT 圖上僅采用BFS 軟件算法、僅采用密集變量前沿加速器和混合BFS 方案的性能。根據經驗取β=0.78 和θ=5%來執行接近理想的切換。性能指標采用每秒遍歷邊的百萬條數（MTEPS），結果是對16 個BFS 操作求平均值。

圖6 所示為得到的關于一系列RMAT 圖的3種方法的性能與圖的規模-邊因子的關系。可見，僅采用BFS 軟件算法有一個22 MTEPS 的平均性能。由于這些圖都不適合CPU 的高速緩存，故大量的數據高速緩存未被使用，降低了性能；而僅采用密集變量前沿加速器是僅采用BFS 軟件算法的3.9倍。這是由于CPU 的頻率優勢和大量冗余數據量獲取以及通過加速器執行運算，這種加速進一步支持了慢時鐘，而且并行FPGA 加速器適合于不規則的、內存受限的應用；最后，混合BFS 方案結合了二者的優勢，所以優于僅采用加速器和僅采用軟件的BFS，分別是它們的2 倍和7.8 倍的加速性能。

圖6 RMAT 系列圖上的性能比較

3.3 不同算法的性能比較

由于算法的性能隨著更多的帶寬可用而成比例增加，故在不同硬件平臺上關于相同RMAT 圖的搜索比較就不能采用MTEPS 性能指標，所以采用每單位帶寬的遍歷數作為性能指標，即用MTEPS 遍歷速度除以各自的外部存儲器帶寬（GB/s）來得到。表1 所示為得到的采用本文的密集變量BFS 算法與目前比較先進的混合BFS 算法［1，4，11］的性能結果。從表1 可見，本文所采用的密集變量BFS 算法相比于其中最好的解決方案［4］，在有效每帶寬遍歷數方面也是其2 倍以上。

表1 不同混合BFS 算法的性能比較

4 結論

本文針對FPGA-CPU 混合硬件系統提出了一種加速的BFS 體系結構，它可以有效利用小世界圖中不同程度的并行性，把BFS 視為在布爾環上的一個矩陣-向量運算，把輸入向量處理為密集，使得能夠在冗余計算和增加DRAM 帶寬之間進行交換；在ZedBoard 平臺上的實驗結果表明，本文提出的混合系統加速器性能能夠隨著增加的帶寬按比例提高，而且在每帶寬遍歷數性能方面優于其他的技術。