基于BFS 和FPGA-CPU 的混合加速器設(shè)計(jì)*

郭小波，楊光露

（1.河南工程學(xué)院計(jì)算機(jī)學(xué)院，鄭州 451191；2.糧食信息處理與控制教育部重點(diǎn)實(shí)驗(yàn)室，鄭州 450002；3.河南中煙工業(yè)有限責(zé)任公司南陽卷煙廠，河南 南陽 473007）

0 引言

圖作為數(shù)據(jù)表示和處理圖的算法普遍存在于許多科學(xué)領(lǐng)域。廣度優(yōu)先搜索（Breadth-First Search，BFS）是研究圖的一個(gè)關(guān)鍵構(gòu)建模塊，也是各種圖指標(biāo)如計(jì)算連接組件、計(jì)算圖的直徑和半徑的基礎(chǔ)。BFS 以及許多其他圖算法的2 個(gè)主要特性是由圖頂點(diǎn)和邊結(jié)構(gòu)上的數(shù)據(jù)驅(qū)動(dòng)計(jì)算引起的不規(guī)則的存儲(chǔ)訪問和較低的計(jì)算-存儲(chǔ)比［1］。

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

近年來，隨著人們對(duì)節(jié)能計(jì)算系統(tǒng)的關(guān)注，采用可重構(gòu)邏輯和FPGAs 的異構(gòu)處理越來越流行，包括采用數(shù)據(jù)中心［10］；文獻(xiàn)［11］提出的CPU-GPU 混合方法采用的是一種切換方法；文獻(xiàn)［12］強(qiáng)調(diào)了順序模式對(duì)于采用圖算法獲得高存儲(chǔ)設(shè)備帶寬有明顯的優(yōu)勢(shì)，并提出了一種采用流分割的以邊沿為中心的分散-聚集框架，但這種方法是以犧牲某些效率（如隨機(jī)訪問節(jié)點(diǎn)）來實(shí)現(xiàn)通用性的圖存儲(chǔ)，其效率對(duì)于BFS 是有限的。

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

1 背景知識(shí)

1.1 廣度優(yōu)先搜索

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

1.2 稀疏性與小世界特性

一個(gè)小世界圖就是一個(gè)直徑很小的圖，如“六度分離”，而對(duì)于社會(huì)圖如臉譜網(wǎng)來說，已被證明低至四度。小世界圖一般表現(xiàn)為無標(biāo)度分布形式y(tǒng)=xa，即由極少數(shù)高度中心“樞紐”和形成外圍的許多低度節(jié)點(diǎn)構(gòu)成。這意味著當(dāng)BFS 開始時(shí)，存在根節(jié)點(diǎn)僅被連接到幾個(gè)相鄰節(jié)點(diǎn)的一個(gè)高概率，而且那些相鄰節(jié)點(diǎn)連接到少數(shù)節(jié)點(diǎn)，等等。因此，BFS 的第一次迭代訪問一小部分圖。但隨著越來越多的邊被遍歷，前沿規(guī)模急劇增大，就構(gòu)成了很大的網(wǎng)絡(luò)。

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

2.1 采用線性代數(shù)語言的BFS

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

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

2.2 解耦距離生成及布爾BFS 算法實(shí)現(xiàn)

在2.1 節(jié)中給出的BFS 布爾環(huán)矩陣-向量表示在存儲(chǔ)需求方面是非常簡(jiǎn)潔的，這使得它適合于硬件加速器的實(shí)現(xiàn)。具體來說，對(duì)于每個(gè)圖節(jié)點(diǎn)，x 和y向量僅需要1 位存儲(chǔ)。由于矩陣稀疏性，y 將被隨機(jī)訪問，保持被隨機(jī)訪問數(shù)據(jù)的范圍和容量最小，對(duì)于性能是有利的。遺憾的是，迭代調(diào)用?對(duì)于BFS是不夠的，因?yàn)樗簧杀辉L問節(jié)點(diǎn)的狀態(tài)而不是dist 數(shù)組。

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

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

2.3 帶寬和冗余計(jì)算之間的權(quán)衡

由于稀疏圖的遍歷涉及很少的實(shí)際計(jì)算，而且被視為是一個(gè)內(nèi)存約束問題，故用高帶寬傳送圖數(shù)據(jù)對(duì)于加速器性能來說是至關(guān)重要的。因此，對(duì)于設(shè)計(jì)BFS 硬件加速器來說，存儲(chǔ)訪問模式的分析是一個(gè)關(guān)鍵步驟。在本文設(shè)計(jì)的加速器中，BFS 的輸入存儲(chǔ)在動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器中，而且訪問也從DRAM 中進(jìn)行。

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

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

圖1 稀疏xt 的內(nèi)存請(qǐng)求結(jié)構(gòu)

2.4 處理單元結(jié)構(gòu)

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

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

圖2 密集xt 處理單元的體系結(jié)構(gòu)

2）稀疏x 變量：根據(jù)整體架構(gòu)，稀疏xt變量與密集xt變量是相同的，除了它不需要輸入向量FIFO（因?yàn)橄∈杼幚硪馕吨縳t值是1）部分。圖3 所示為稀疏xt后端的內(nèi)部結(jié)構(gòu)，與密集xt變量本質(zhì)上是不同的。稀疏輸入向量是通過前沿濾波器內(nèi)部生成，它掃描距離數(shù)組的值，并發(fā)送索引值，全部值被寫入在先前的BFS 步驟中。之后，每個(gè)生成索引的開始和結(jié)束指針被請(qǐng)求，這兩個(gè)指針用于請(qǐng)求該節(jié)點(diǎn)的邊數(shù)據(jù)，并生成前端的邊計(jì)數(shù)信息。

圖3 稀疏xt 變量的后端結(jié)構(gòu)

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

4）距離生成器：在每個(gè)BFS 步驟完成后，調(diào)用距離生成器來執(zhí)行DistGen。這涉及到比較輸入和結(jié)果向量，并找到從未被訪問過的節(jié)點(diǎn)到訪問過的節(jié)點(diǎn)。這些節(jié)點(diǎn)的索引被傳遞給后端作為實(shí)際寫當(dāng)前BFS 距離到對(duì)應(yīng)的存儲(chǔ)位置，并為密集變量的下一個(gè)BFS 步驟更新x 向量。

2.5 一個(gè)實(shí)際加速器系統(tǒng)的構(gòu)建

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

式中，β 是利用的帶寬部分。FPGA 繼續(xù)執(zhí)行直至前沿尺寸下降到低于全部圖節(jié)點(diǎn)的θ%。之后，軟件BFS 接管直到搜索終止。β，θ 憑經(jīng)驗(yàn)確定。

3 實(shí)驗(yàn)結(jié)果

為了評(píng)價(jià)本文提出的加速器系統(tǒng)，采用Graph500 基準(zhǔn)參數(shù)（A=0.57，B=0.19，C=0.19）［1，4］綜合生成的RMAT 圖，把一個(gè)具有規(guī)模S（2S個(gè)節(jié)點(diǎn)）和邊因子E（E×2s 條邊）的RMAT 圖稱為RMATS-E。

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

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

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

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

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

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

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

現(xiàn)在來比較在一個(gè)RMAT 圖上僅采用BFS 軟件算法、僅采用密集變量前沿加速器和混合BFS 方案的性能。根據(jù)經(jīng)驗(yàn)取β=0.78 和θ=5%來執(zhí)行接近理想的切換。性能指標(biāo)采用每秒遍歷邊的百萬條數(shù)（MTEPS），結(jié)果是對(duì)16 個(gè)BFS 操作求平均值。

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

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

3.3 不同算法的性能比較

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

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

4 結(jié)論

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