郭進陽 邵傳明 王 靖 李 超 朱浩瑾 過敏意

(上海交通大學(xué)電子信息與電氣工程學(xué)院 上海 200240)

如今，工業(yè)界和學(xué)術(shù)界嘗試設(shè)計專用加速器來提升圖計算的性能與能效.有多種硬件架構(gòu)在可選范圍之列，比如圖形處理器(GPU)、現(xiàn)場可編程門陣列(FPGA)、專用集成電路(ASIC)等.其中，F(xiàn)PGA有多方面優(yōu)勢.與通用架構(gòu)相比，F(xiàn)PGA能夠提供高度的編程靈活性和較高的性能，這為圖計算加速器的設(shè)計提供了便利.同時，F(xiàn)PGA的開發(fā)模式是數(shù)據(jù)驅(qū)動的，少去了譯碼過程，使得基于FPGA的圖計算加速器能夠?qū)崿F(xiàn)更高的能效.

Fig.1 The organization of programming enviornment圖1 編程與開發(fā)環(huán)境部分的組織結(jié)構(gòu)

基于FPGA的圖計算加速是國內(nèi)外熱門話題.中國計算機學(xué)會有關(guān)專委會于2014年在面向新型計算模型的系統(tǒng)軟件方面展開了探索，其中對圖計算的相關(guān)性質(zhì)做出了詳細描述[1]；2017年，該學(xué)會有關(guān)研究人員在可重構(gòu)加速器領(lǐng)域也做了進一步討論，指出了FPGA存在的編程墻問題[2].從上述研究可以看到，利用FPGA進行圖計算加速需要首先解決FPGA開發(fā)存在的固有編程挑戰(zhàn).目前國內(nèi)外存在許多面向FPGA圖計算的編程語言[3-12]、編程工具[13-19]與一些圖計算框架[20-24].

編程與開發(fā)環(huán)境是一個開放的概念，本文中FPGA圖計算編程與開發(fā)環(huán)境包括：1)編程模型；2)高層次綜合工具；3)編程語言；4)便于加速器開發(fā)的應(yīng)用程序接口，包含圖計算應(yīng)用開發(fā)過程中所涉及到的各個環(huán)節(jié).傳統(tǒng)FPGA開發(fā)方式依賴于硬件描述語言，缺乏軟件開發(fā)的高層視角，導(dǎo)致開發(fā)過程十分耗時.學(xué)術(shù)界和工業(yè)界寄希望于高層次綜合工具，以獲取更高的開發(fā)效率，然而通用的高層次工具在圖計算應(yīng)用上面臨性能不佳的問題.同時，一些加速器被設(shè)計出來，針對某些特定算法，缺乏靈活性，阻礙了其廣泛應(yīng)用.

近年來，雖然有一些關(guān)于FPGA編程與開發(fā)環(huán)境的相關(guān)探索，也有一些綜述文章，但是這些綜述通常只關(guān)注了FPGA圖計算加速器設(shè)計過程中涉及到的某一部分.以2016年的一篇綜述為例[25]，雖然其涵蓋了諸多HLS工具，但是并沒有對常用的成熟工具作出重點介紹，也未談及圖計算的相關(guān)優(yōu)化技術(shù).許多綜述對圖計算中的可選方案和優(yōu)化技術(shù)進行介紹，這其中包含對某一特定技術(shù)的介紹，如對圖計算中內(nèi)存系統(tǒng)的優(yōu)化技術(shù)[26]、對頂點為中心的編程模型進行了介紹[27]，以及關(guān)于圖計算框架的涉及到的一系列技術(shù)的介紹[28].其他一些綜述[29-30]關(guān)注點在于總結(jié)圖計算中使用的技術(shù)和優(yōu)化策略，而沒有以這些框架蘊含的應(yīng)用程序接口(為方便圖計算加速器的開發(fā)而提供)作為主要的關(guān)注點.為此，本文將對基于FPGA圖計算所涉及到的編程與開發(fā)環(huán)境進行介紹與探索.

簡單來講，編程模型提供高級抽象，使編程人員從底層細節(jié)解放.高層次綜合通過高級程序語言的支持，能夠允許用戶快速探索設(shè)計空間，降低了所需的硬件知識門檻.精心設(shè)計的編程語言能更好地聯(lián)系底層硬件模塊.高度集成的用戶接口能便利開發(fā)過程.

圖1是第2～5節(jié)關(guān)于FPGA圖計算編程與開發(fā)環(huán)境部分的組織結(jié)構(gòu).

1 背景介紹

本節(jié)分為2個部分：1)介紹圖計算相關(guān)概念，并對FPGA上流行的圖算法做簡單分類；2)概述FPGA圖專用加速器以及與通用架構(gòu)的對比.表1對本文中用到的圖計算概念和關(guān)鍵符號做簡要總結(jié).

Table 1 The Key Symbols Used in This Article表1 本文中使用的重要符號

1.1 圖計算的簡介

圖是一種由頂點以及連接它們的邊所構(gòu)成的特殊數(shù)據(jù)結(jié)構(gòu)，可以表示為G=(V,E)，頂點集合V={v1,v2,…,vn}，邊集合E={e1,e2,…,em},且EV×V.e(u→v)表示從頂點vi到vj的一條邊，是有向或無向的.對e∈E，有vi和vj是鄰居.子圖定義：若圖G存在一個子圖G′，則有G′=(V′,E′),V′V且E′E.

圖計算技術(shù)可以被應(yīng)用于各領(lǐng)域，如社交網(wǎng)絡(luò)、計算機網(wǎng)絡(luò)、電子交易等.自然圖具有稀疏性、冪律性以及小世界性的特征[26].圖數(shù)據(jù)的稀疏性將會導(dǎo)致較差的局部性；冪律性將導(dǎo)致圖計算面臨嚴重的負載不均衡問題；小世界性為大圖數(shù)據(jù)分割帶來挑戰(zhàn).這些特性使得圖計算技術(shù)不適宜使用現(xiàn)有的數(shù)據(jù)處理方法，而且在并行處理上也存在著效率低下的問題[31].

1.2 通用處理器上的圖計算

1) 基于CPU的圖計算.為了提升CPU上圖計算的性能，大量關(guān)于構(gòu)建高效系統(tǒng)的工作已經(jīng)展開.這些工作整體上可以分成2個類別：分布式系統(tǒng)[32-33]和單機系統(tǒng).分布式系統(tǒng)利用集群來支持大規(guī)模數(shù)據(jù)處理，但是面臨通信開銷、同步開銷、一致性以及負載不均衡的困擾[34-35].新興服務(wù)器往往配備了大內(nèi)存，可以將大部分圖數(shù)據(jù)存儲其中，因此大量關(guān)于開發(fā)單機潛力的工作正在開展[36-38].

2) 基于GPU的圖計算.由于GPU具有數(shù)據(jù)并行能力，因此很多相關(guān)工作采用GPU來追求圖計算的高性能.許多基于GPU系統(tǒng)[39-41]都被設(shè)計用來進行高性能圖計算.對BFS,CC,BC以及SSSP等常用算法性能優(yōu)化的工作也被大量展開.圖計算領(lǐng)域?qū)Ｓ每蚣茴I(lǐng)域也被用于提高GPU應(yīng)用的開發(fā)效率.為了支持大規(guī)模的圖數(shù)據(jù)，CPU-GPU異構(gòu)系統(tǒng)、多GPU系統(tǒng)和片外內(nèi)存系統(tǒng)也被陸續(xù)提出.

1.3 FPGA的圖計算加速器

由于圖數(shù)據(jù)的特性，現(xiàn)有的圖計算系統(tǒng)無法充分發(fā)揮通用處理器的硬件潛力[42-43].自然圖通常為冪律分布(大多數(shù)頂點都只和少數(shù)幾條邊相關(guān)聯(lián))，導(dǎo)致在通用處理器上內(nèi)存訪問開銷大且效率低下[44-45],圖計算中的數(shù)據(jù)不規(guī)則性決定了在利用傳統(tǒng)處理器上的內(nèi)存級及指令級并行方面存在著固有缺陷.現(xiàn)有的商用多核體系結(jié)構(gòu)對于圖計算而言，大量的內(nèi)存帶寬實際上沒有得到充分利用[43,45].

現(xiàn)場可編程門陣列(FPGA)是可重配置的計算設(shè)備[46]，其中包含大量可用于解決特定計算問題的可編程單元.這些處理單元包括用于實現(xiàn)組合邏輯的查找表(LUT)、用于實現(xiàn)寄存器的觸發(fā)器(FF)，以及可編程的互連大容量存儲Block RAM(BRAM).將FPGA用于圖計算加速有3個優(yōu)點：

1) 編程靈活性.與ASIC在制造過程中僅“配置”一次不同，F(xiàn)PGA可以根據(jù)需要進行多次重新配置.這樣可以調(diào)節(jié)和改進體系結(jié)構(gòu)，應(yīng)用錯誤修復(fù)或使用FPGA快速原型化硬件設(shè)計，然后可以將其設(shè)計為ASIC.FPGA還允許即時重新配置以解決不同的任務(wù)[47].

2) 高性能.經(jīng)過精心設(shè)計的FPGA系統(tǒng)可以通過利用大規(guī)模并行(通常以深層流水線的形式)獲得高于CPU的性能.同時，某些不屬于CPU指令集的特定于應(yīng)用程序的指令可以在FPGA上實現(xiàn)需要在單個周期完成計算，而在CPU上實現(xiàn)可能需要更長周期.

3) 高能效.CPU和GPU是指令驅(qū)動的，而FPGA設(shè)計通常是數(shù)據(jù)驅(qū)動的，這意味著FPGA可以直接處理數(shù)據(jù)而無需先解碼指令.此外，F(xiàn)PGA也無需訪問集中式寄存器文件或任何緩存層次結(jié)構(gòu).由于指令譯碼、寄存器和高速緩存查詢占據(jù)了基于指令的體系結(jié)構(gòu)所消耗功率的大部分[48]，因此使用FPGA開發(fā)往往可以獲得更高的性能功耗比.

1.4 FPGA上常用圖算法

本節(jié)我們將對已在FPGA上實現(xiàn)的主要代表性圖算法進行分類.表2是FPGA上常用的圖算法及分類.FPGA上常用的算法主要包括：廣度優(yōu)先搜索(BFS)、連通分量(CC)、可達性證明算法、單源最短路徑(SSSP)、全對最短路徑(APSP)、PageRank(PR)、圖形計數(shù)(GC)、三角形計數(shù)(TC)、中介中心度(BC)、最大匹配(MM)等算法.

Table 2 Classification of Representative Graph Algorithms Being Deployed on FPGAs表2 FPGA上部署的常見圖算法及其分類

Notes: CI represents computational intensity; H/L represents high/low; RH/RL represents relatively high/relatively low.

1.5 相關(guān)編程與開發(fā)環(huán)境

基于FPGA加速器的圖計算應(yīng)用開發(fā)面臨著2方面的編程挑戰(zhàn)：1)因為FPGA的傳統(tǒng)開發(fā)方式效率低下；2)因為圖算法多樣，涉及的操作也十分繁多，編程人員難以設(shè)計完備的操作集成庫以提高編程效率.因此需要很好地進行編程與開發(fā)環(huán)境設(shè)計以獲取更高的開發(fā)效率.

關(guān)于探究FPGA圖計算加速器高效編程與開發(fā)環(huán)境設(shè)計的工作早已開展，然而這些工作僅僅關(guān)注了編程與開發(fā)環(huán)境的某一方面.諸如FPGA圖計算編程框架、并行高效的HLS工具設(shè)計等都是常見的改進FPGA圖計算開發(fā)的途徑.

2 編程模型

圖計算涉及的算法多樣，各種算法的設(shè)計思維迥異，對不同圖算法可能要設(shè)計不同的數(shù)據(jù)分區(qū)以及通信機制.編程模型能夠提供一種高級抽象，使編程人員從底層細節(jié)中解放出來，專注于算法邏輯，以提高編程效率，也是高效的圖計算編程與開發(fā)環(huán)境中重要的一環(huán)，本節(jié)主要將就2類編程模型進行簡介.

2.1 圖計算專用編程模型

傳統(tǒng)的圖計算編程模型按照圖元素中心可以劃分為：以頂點為中心和以邊為中心.前者能夠提供高度并行性，在部分圖算法上能有很好的性能，但是可能存在大量隨機訪問從而導(dǎo)致高昂訪存開銷.后者能夠提供較好的空間局限性，但由于數(shù)據(jù)輸入順序受限，會導(dǎo)致額外的時間開銷.在此基礎(chǔ)上，GAS模型和混合中心模型被提出，用來優(yōu)化某些圖算法的性能.同時，最近的研究關(guān)注到一種新興的子流模型，能夠很好地適配FPGA的某些特性.表3對這些常見的圖計算專用編程模型進行分類并總結(jié)了相關(guān)特性.

Table 3 Classification and Characteristics of Common Graphprocessing Programming Models表3 常用圖計算編程模型分類及特性

2.1.1 以圖元素為中心的編程模型

1) 以頂點為中心的模型.在以頂點為中心[49-51]的模型中，需要獨立處理每個頂點的任務(wù)，通過對邊和鄰接點進行計算以及數(shù)據(jù)傳輸.每個頂點都可以被單獨處理，因此可以通過調(diào)度來保證高并行度.但由于相鄰點可能存儲在存儲器的不同位置，所以會導(dǎo)致大量的存儲器隨機訪問，從而導(dǎo)致高昂的內(nèi)存訪問開銷.

2) 以邊為中心的模型.在以邊為中心的模型[52-53]中，邊數(shù)據(jù)以它們在圖數(shù)據(jù)結(jié)構(gòu)中所存儲的順序傳輸?shù)教幚砥?此處，邊由其成員點的標(biāo)簽以及對應(yīng)的邊權(quán)重構(gòu)成.處理器順序地處理邊數(shù)據(jù)并在必要時更新關(guān)聯(lián)邊的數(shù)據(jù).因此這種順序訪問的方式能夠改善空間局部性.但是，由于該模型限制了加載順序，部分算法存在性能低下的問題，例如BFS算法，使用邊為中心模型的過程中會造成額外的時間開銷[56].

3) 頂點為中心和邊為中心相結(jié)合的模型.頂點為中心的編程模型適合處理活躍節(jié)點占比大的情形，而邊為中心的編程模型適合處理活躍節(jié)點占比低的情形.可以將頂點為中心和邊為中心的模型相結(jié)合以獲取更大的優(yōu)勢[32].

2.1.2 其他類型的編程模型

1) 集聚散射(GAS)模型.GAS模型[54]與以頂點為中心的方法相似.它提供了關(guān)于圖算法的以頂點為中心的視圖.不同的的是它將每次迭代分為3個部分：聚集(gather)、應(yīng)用(apply)和分散(scatter).在聚集階段，頂點收集有關(guān)其相鄰頂點或邊的信息，并可選地將其減小為單個值σ.在應(yīng)用階段，將根據(jù)先前計算的σ以及頂點的鄰居的屬性來更新頂點的狀態(tài).最終，在分散階段，每個頂點將其新狀態(tài)傳播到其鄰居.然后，將在下一次迭代的收集階段再次收集該值.

2) 以子流為中心的模型.在子流為中心模型[55]中，需要首先將數(shù)據(jù)流劃分為子流，然后單獨對每個子流進行處理，以提高并行度和降低通信開銷.這種模型能夠更好地適配FPGA特性，可以利用有限的存儲器資源來達到高能效、高性能和高精度的要求.

2.2 通用編程模型

除去圖計算專用編程框架，也有一些通用的分布式/并行計算框架，可以用于圖計算，批量同步并行模型和異步執(zhí)行模型是其中的典型代表.然而這些通用框架卻存在一些問題，批量同步并行(BSP)模型需要特殊的硬件支持以實現(xiàn)全局障礙同步;異步執(zhí)行(asynchronous execution)模型需要額外的設(shè)計，以實現(xiàn)復(fù)雜的同步機制.

1) 批量同步并行(BSP)模型.批量同步并行[57]模型中的每個迭代稱為超步(super step).在每個超步之后，并行過程將使用障礙進行同步.每個迭代都分為3個階段:在第1階段，每個過程都會進行任何所需的本地計算;在下一階段，進程將發(fā)送和接收消息;最后障礙同步保證了僅在當(dāng)前超步中的所有本地計算完成，并且交換完該超步中的所有消息，才開始下一個超步.

2) 異步執(zhí)行(asynchronous execution)模型.異步執(zhí)行模型[58]不同于批量同步模型，它允許部分節(jié)點先一步開始下一步迭代，在PageRank這種應(yīng)用下，能夠允許部分節(jié)點更頻繁地向其鄰居節(jié)點傳播信息，從而達到更快的首先速度.但是相應(yīng)地，它需要復(fù)雜的同步機制來支持這種異步過程.

3 高層次綜合

高層次綜合(HLS)通常指的是將高層次語言描述的邏輯結(jié)構(gòu)，自動轉(zhuǎn)換成低抽象級語言描述的電路模型的過程.已有研究證明，HLS可以生成性能高效的代碼[59].HLS工具能降低軟件開發(fā)人員利用FPGA進行硬件加速的知識門檻.對于硬件開發(fā)人員，HLS工具能夠提高相應(yīng)系統(tǒng)的開發(fā)速度，并且允許用戶更快地探索設(shè)計空間[60].

3.1 針對圖計算的HLS優(yōu)化

HLS工具雖然能夠提高設(shè)計的抽象等級，但不能簡單應(yīng)用到圖計算環(huán)境中來.由于自然圖的特性[26]，圖計算面臨著數(shù)據(jù)訪問不規(guī)則、工作負載不均衡以及嚴重的數(shù)據(jù)依賴等挑戰(zhàn).若要利用HLS進行硬件設(shè)計，則需要針對這些問題進行大量的手工批注，以適配圖計算這種特殊的計算任務(wù).而通用HLS工具缺乏對不規(guī)則圖算法的有效支撐，需要針對圖算法固有數(shù)據(jù)不規(guī)則性問題進行針對性的優(yōu)化.

3.1.1 HLS的并行優(yōu)化

早期HLS工具[13-15]支持靜態(tài)并發(fā)的設(shè)計，基于C語言的HLS工具通常分析循環(huán)并采用展開和流水線化等技術(shù).Intel[13]和Xilinx[15]的HLS工具都致力于實現(xiàn)數(shù)據(jù)并行性.LegUp[14]通過支持OpenMP和pthread API以實現(xiàn)線程級并行性.IBM的Liquid Metal[16]支持流內(nèi)核并行性，這些工具都采用靜態(tài)并發(fā)模式，并行結(jié)構(gòu)在硬件生成期間無法更改.

而TAPAS[17]構(gòu)建于并行編譯器的中間表示之上，關(guān)注程序中隱式表達的細粒度的并行.借助于動態(tài)并行模式，TAPAS使任務(wù)可以在運行時動態(tài)產(chǎn)生，并與其他任務(wù)同步.TAPAS的最大優(yōu)勢是能夠解決使用靜態(tài)并行模式下HLS工具難以實現(xiàn)的軟件開發(fā)，例如嵌套并行、條件循環(huán)、流水線并行、遞歸并行.Spatial[18]工具也支持動態(tài)并行，支持循環(huán)嵌套，可以實現(xiàn)任意位置的粗粒度流水線.

康奈爾大學(xué)的研究工作提出了多線程流水線[61]和彈性工作流[62]的概念，用于解決靜態(tài)流水線技術(shù)無法發(fā)現(xiàn)與利用潛在的數(shù)據(jù)局部性和并行性的問題，以提升動態(tài)并行能力.他們還提出了一種預(yù)測流水線HRU[63]以獲得更好的并行設(shè)計.

3.1.2 HLS的訪存優(yōu)化

有文獻提出了3種粒度的片上內(nèi)存優(yōu)化策略[64]：1)細粒度優(yōu)化，通過聲明局部數(shù)組并將其作用于較大位寬度的存儲空間獲得高數(shù)據(jù)傳輸帶寬，是典型的利用LUT和BRAM資源消耗換取大帶寬；2)粗粒度優(yōu)化，主要是通過額外的局部緩沖區(qū)以增加帶寬，但是需要在計算前后額外地進行數(shù)據(jù)復(fù)制；3)混合粒度則允許綜合2種策略的優(yōu)點.

一些新興HLS工具針對動態(tài)內(nèi)存管理進行了設(shè)計優(yōu)化.例如，DMM-HLS[65]關(guān)注到FPGA上可能的資源匱乏問題，將動態(tài)內(nèi)存管理的想法借鑒到HLS中.該工作研究了堆深度、堆字長以及分配對齊等約束條件，為解決內(nèi)存碎片、內(nèi)存一致性以及內(nèi)存訪問沖突等問題提供了可行方案，同時也為支持新興的多加速系統(tǒng)提供了支持.另外，Spatial[18]則提出了一種基于機器學(xué)習(xí)的內(nèi)存分配策略，允許自動進行內(nèi)存劃分.

3.1.3 HLS的其他優(yōu)化

由于生成RTL代碼的過程與具體的圖數(shù)據(jù)耦合，因此在對另一組圖數(shù)據(jù)作計算時，需要按此過程再次編譯.解耦數(shù)據(jù)結(jié)構(gòu)[66]可以提升HLS的綜合能力，通過訪問器和突變體方法2種方式，使得HLS能夠支持除原始數(shù)據(jù)結(jié)構(gòu)之外的新興結(jié)構(gòu)，同時也能避免重復(fù)編譯的問題.

3.2 通用HLS的能力評估

本節(jié)將對一些早期HLS工具[13-15]:TAPAS[17]，Spatial[18]和Bluespec[19],進行簡單的評估，主要從能否支持動態(tài)并發(fā)以及相應(yīng)的流水線優(yōu)化技術(shù)支持進行評估，表4是對其基本能力的評估結(jié)果.

Table 4 Evaluation of Some HLS Tools表4 HLS工具評估

Bluespec[19]是一種使用Bluespec System Verilog(BSV)的高層次綜合工具.BSV是一種基于Verilog，并受到Haskell啟發(fā)的函數(shù)式硬件描述語言.BSV語言基于一種新的硬件計算模型，其中所有行為都描述為一組重寫規(guī)則或“受保護的原子操作”.與Verilog的進程/線程模型、C/C++的順序模型不同，BSV程序通過并行協(xié)作的FSM表達行為，并且所有行為都可以通過原子規(guī)則觸發(fā).

Spatial適合挖掘出深度學(xué)習(xí)及矩陣相乘這類規(guī)則訪存應(yīng)用中的并行性，其自動內(nèi)存劃分機制能發(fā)揮巨大作用.但在面臨BFS等圖計算問題時，由于訪存的不規(guī)則性，其內(nèi)存自動劃分機制難以發(fā)揮作用，并且會導(dǎo)致大量的存儲單元復(fù)制，阻止并行度的提升.

當(dāng)前通用HLS工具對圖計算開發(fā)的支持有限.使用這些通用工具，用戶難以直接通過高級編程語言為圖算法生成高效的并行流水結(jié)構(gòu)，這是由于這些通用語言通常缺乏硬件細節(jié)、難以對架構(gòu)準確進行描述.同時，由于圖算法的高數(shù)據(jù)依賴性，如果沒有足夠的底層優(yōu)化，在指定高并行度后會產(chǎn)生數(shù)據(jù)沖突，導(dǎo)致無法生成硬件電路或者生成效果差.因此，有效支撐圖計算的HLS工具是未來FPGA圖計算加速的編程與開發(fā)環(huán)境相關(guān)探索的重要方向.

4 編程語言

本節(jié)將對FPGA的硬件開發(fā)所用的編程語言進行介紹，按照硬件描述語言(HDL)和領(lǐng)域特定語言(DSL).在基于FPGA的圖計算加速器的編程與開發(fā)環(huán)境中，編程語言是其中關(guān)鍵一環(huán)，設(shè)計出高效且能結(jié)合軟硬件特點的DSL是編程人員的目標(biāo)，也是未來圖計算加速器編程與開發(fā)環(huán)境的探索方向.

4.1 HDL

Verilog和VHDL是2種符合IEEE標(biāo)準的硬件描述語言(HDL)，它們有許多共同點.首先，2種語言的程序結(jié)構(gòu)類似，并都支持使用門級原語描述邏輯電路的結(jié)構(gòu).此外，它們也支持使用過程性語句描述電路的行為.相比VHDL，Verilog程序更加簡短，并且許多語言結(jié)構(gòu)和C語言很類似.VHDL是一門強類型的語言，語法更為嚴謹，具有更強的確定性.

SystemVerilog[3]是對Verilog的擴展，擴充了新的數(shù)據(jù)類型、壓縮和非壓縮數(shù)組、接口、斷言等內(nèi)容.SystemVerilog結(jié)合了硬件描述語言和硬件驗證語言(HVL)，具有測試平臺開發(fā)和基于斷言的形式驗證的功能，并且具有面向?qū)ο缶幊痰奶攸c.這些特點使得SystemVerilog具有更強的抽象能力，適合于設(shè)計可重用的、可用于綜合和驗證的IP，以及特大型基于IP的系統(tǒng)級設(shè)計和驗證.

除此之外，也有運用某種語言作為宏語言生成底層的HDL代碼的策略.例如Verischemelog[4]采用Scheme語言的語法，用一種與Verilog相似的方式定義硬件模塊.JHDL[5]將Java的類與硬件模塊相對應(yīng).HML[6]使用標(biāo)準的ML函數(shù)表示電路的連接.這些語言使用簡單的方式將硬件描述語言與現(xiàn)有的編程語言聯(lián)系起來，允許用戶使用熟悉的編程語言描述電路結(jié)構(gòu)和行為.但是這些語言需要使用底層的HDL描述一些底層部件，但由于這樣一些HDL過于底層的限制，這些語言無法進一步提高抽象能力.

4.2 DSL

當(dāng)前FPGA的設(shè)計工具支持相對原始的編程接口[7]，傳統(tǒng)HDL缺乏軟件編程高級概念，需要設(shè)計人員提供時序、控制信號以及內(nèi)存處理的相關(guān)支持，領(lǐng)域特定語言(DSL)對特定領(lǐng)域需求進行了相應(yīng)的優(yōu)化，能夠讓編程人員擺脫體系結(jié)構(gòu)細節(jié)的限制，便于版本維護和代碼移植[8].

一些DSL是通過元編程的方式實現(xiàn)的.通過將HDL嵌入一種軟件編程語言中引進新的編程語言特性，從而獲得更高的抽象能力和設(shè)計空間探索能力.以下是一些典型例子：

Chisel[9]是嵌入在高級編程語言Scala中的硬件描述語言.借助于Scala的元編程能力，Chisel定義了硬件相關(guān)的數(shù)據(jù)類型和一系列的過程語句，允許用戶使用與Scala相近的語法編寫程序.同時，它還允許用戶定義抽象的數(shù)據(jù)類型和接口，以及參數(shù)化的函數(shù)和類，這樣可以提高代碼的重用性以及支持高度參數(shù)化的電路生成.此外，Chisel還可以生成C++代碼用于快速、周期精確的軟件模擬測試，也可以生成Verilog代碼用于FPGA仿真.

VeriScala[10]提供的便捷硬件通信API減少了集成難度，同時在硬件設(shè)計中構(gòu)建了一個填充層用以處理通信協(xié)議，提高了用戶的開發(fā)效率.SysPy[11]基于Python語言,利用了Python腳本語言的優(yōu)勢,將Python語言作為HDL、即用型VHDL組件和可編程處理器軟IP內(nèi)核之間的聯(lián)系.

還有一些對高級語言進行擴展來形成的DSL,如Pyverilog[12]擴展了Python語言,提供了4個關(guān)鍵庫：解析庫、數(shù)據(jù)流分析庫、控制流分析庫和Verilogcode生成庫,用于支持快速原型開發(fā).

總體來說,目前已有的硬件編程語言在實際應(yīng)用中有代碼的功能性強且代碼運行高效的優(yōu)勢,利于細粒度的底層元件和邏輯設(shè)計.與此同時，它們的缺點在于學(xué)習(xí)成本高、開發(fā)周期長、所需的專業(yè)知識強,在特定領(lǐng)域很難發(fā)揮自身優(yōu)勢.這也是當(dāng)前業(yè)界對于高層次編程與開發(fā)環(huán)境封裝的探索的重要原因之一.領(lǐng)域特定語言(DSL)的興起提高了領(lǐng)域?qū)Ｓ脝栴}的描述與解決能力,它幫助開發(fā)者在專業(yè)領(lǐng)域知識不深的情況下,使用簡單的語法和部分直接可用的接口來實現(xiàn),搭建快速有效的面向?qū)Ｓ脩?yīng)用的設(shè)計平臺.但它的問題在于編程標(biāo)準不夠明晰,設(shè)計實現(xiàn)需要額外的編譯或翻譯工具,并且這種方式實現(xiàn)的加速器通常無法提供高層邏輯抽象與底層具體實現(xiàn)的嚴格對應(yīng).將二者融匯結(jié)合,能夠提供高效的底層代碼，同時也能夠提高編程效率,是加速器編程與開發(fā)環(huán)境的未來主要研究方向.

5 用戶程序接口

Fig.2 Classification of the interfaces and programming models of the graph processing frameworks圖2 圖計算編程框架提供的接口及編程模型分類

現(xiàn)有的在FPGA上實現(xiàn)圖計算加速的架構(gòu)很多,但是很大一部分工作[20-22]只專注實現(xiàn)一種圖算法(例如SSSP或BFS等),而不能輕易地將其擴展以支持其他圖算法.除此之外,許多硬件架構(gòu)支持多種圖算法,這些架構(gòu)統(tǒng)稱為圖計算框架(graph processing framework).然而很多框架[23-24]沒有給出明確的的應(yīng)用程序接口,使得其他開發(fā)者無法將這些框架用于自己的圖計算系統(tǒng)中,因此它們不在編程與開發(fā)環(huán)境的討論范疇.在本節(jié)中，我們將從3種不同的策略來介紹這些應(yīng)用程序接口，以提取出便于用戶進行加速器開發(fā)的邏輯抽象.這些接口可以使用戶可以專注于圖算法的設(shè)計,而無需關(guān)心系統(tǒng)底層的實現(xiàn)與優(yōu)化細節(jié).

通常,這些框架內(nèi)部采用某一編程模型實現(xiàn),而編程模型對部分算法的適配性，會限制這些框架能夠進行計算的圖算法的種類.因此,我們將對文中提到的圖計算編程框架按照其提供的接口類型與編程模型分類,如圖2所示.下面,我們按照框架提供的用戶接口的類型對它們進行分類介紹.

5.1 封裝核函數(shù)(kernel function)方式

在第2節(jié)中，我們介紹了圖計算的編程模型.按照特定的編程模型，用戶只需要設(shè)計出相應(yīng)的核函數(shù)，就可以表達出某種圖算法.大部分的圖計算編程框架都是按照某種編程模型設(shè)計的，只要求用戶按照規(guī)定的I/O接口定義設(shè)計出相應(yīng)的核函數(shù)，就可以結(jié)合框架中的其他固定的模塊生成圖算法的加速器.

由于不同框架采用的編程模型的不同，用戶需要定義的核函數(shù)的數(shù)目也不同.GraphGen[49]采用頂點中心的編程模型，要求用戶定義頂點更新函數(shù)update-function(v).GraVF[51]同樣采用頂點中心的編程模型，但是頂點更新函數(shù)的定義要分成apply和scatter兩部分(分別稱為apply核和scatter核)，并最終實現(xiàn)為2個硬件模塊.而GraVF-M[54]采用GAS模型，要求用戶將核函數(shù)分為3個硬件模塊：Gather(對每條消息，更新頂點狀態(tài))、Apply(在一個超步的最后，根據(jù)頂點狀態(tài)生成消息)、Scatter(將生成的消息發(fā)送到目標(biāo)頂點).

在不同的框架中，定義核函數(shù)的方式也各有不同.由于GraVF和GraVF-M使用基于Python的元編程語言Migen[67]生成硬件實現(xiàn)，用戶在定義函數(shù)時只需要使用Migen的語法編寫即可.而GraphGen設(shè)計了一套用于定義頂點更新函數(shù)的語法，其中包含定義臨時變量、對頂點v的鄰邊進行遍歷、對頂點和邊關(guān)聯(lián)的數(shù)據(jù)進行計算和更新等語法結(jié)構(gòu)，其中也可以包含一些用戶自定義指令.

考慮到最終的硬件實現(xiàn)需要以RTL代碼的形式給出，因此框架需要提供從核函數(shù)到RTL代碼(如Verilog)的編譯器.對于GraVF和GraVF-M，由于核函數(shù)和系統(tǒng)其他部分都采用Migen實現(xiàn)，因此RTL代碼可以通過Migen的編譯器生成.GraphGen的編譯過程分為3步:1)需要將圖數(shù)據(jù)分割成適宜的大小并分配到FPGA的各個BRAM上，這一過程既可以采用手動分割的方式，也可由GraphGen自動分割;2)編譯器根據(jù)用戶編寫的頂點更新函數(shù)和用戶自定義指令，結(jié)合具體的圖分割方式，產(chǎn)生針對每個子圖的程序以及FPGA的存儲器映像(memory image);3)編譯器產(chǎn)生可用于綜合的Verilog代碼.由于生成RTL代碼的過程與具體的圖數(shù)據(jù)耦合，因此在對另一組圖數(shù)據(jù)作計算時需要按此過程再次編譯.

5.2 指令集架構(gòu)(ISA)方式

GraphSoC[68]針對圖計算的特點，設(shè)計了一個圖計算專用的指令集架構(gòu).與普通的CPU的架構(gòu)不同，GraphSoC中包含了用于保存頂點和邊的信息的專用寄存器，而不包含通用寄存器.GraphSoC的指令集中包含了專為圖計算設(shè)計的指令，這些指令可以直接操作專用寄存器.例如，指令RCV的功能是將邊數(shù)據(jù)從存儲器中取出，指令A(yù)CCU的功能是對一個頂點的入邊進行聚合操作，指令UPD的功能是將聚合操作的結(jié)果對頂點的值更新.使用GraphSoC的指令編寫的圖計算程序，可以運行于實現(xiàn)了GraphSoC架構(gòu)的FPGA上.

為了簡化圖計算加速器的設(shè)計，GraphSoC支持采用BSP編程模型進行圖計算.與編程模型的階段對應(yīng)，GraphSoC的指令集中包含了4種指令，分別為receive，accum，update，send.由于對不同的圖算法，這些指令對應(yīng)的操作不同，因此這些指令須由用戶定義產(chǎn)生.用戶首先采用C++ API調(diào)用的方式對這4個指令作出定義，通過編譯器編譯后，再通過GraphSoC提供的匯編器生成相應(yīng)的微指令代碼.

GraphSoC的處理器流水線架構(gòu)使用Vivado HLS設(shè)計編寫，雖然需要經(jīng)過耗時的CAD流程才能編譯為RTL代碼，但是由于這部分對于所有的圖計算任務(wù)都固定不變，因此只需編譯一次即可.編譯、綜合后的處理器與用戶定義的指令共同構(gòu)成圖計算的運行時系統(tǒng).

5.3 硬件模塊庫(hardware module)方式

許多圖計算框架提供設(shè)計好的硬件模塊，其中既包括提供圖操作通用的運算符模塊的框架[57]，也包括將常用圖算法封裝為硬件模塊的框架[53,69].

GraphOps[57]包含許多針對圖計算的模塊，這些模塊接收流式的圖數(shù)據(jù)輸入，經(jīng)過計算并將計算結(jié)果流式地輸出.通過將這些模塊進行組合，可以描述一系列圖分析算法.這些模塊以MaxJ的函數(shù)庫的形式提供，可以通過在MaxJ程序中調(diào)用，也可通過高層次綜合系統(tǒng)編譯為RTL代碼的方式使用.GraphOps硬件庫從各種圖算法的硬件實現(xiàn)過程的實際需要出發(fā)，提供3類硬件模塊，分別為數(shù)據(jù)模塊(data block)、控制模塊(control block)、工具模塊(utility block).數(shù)據(jù)模塊是GraphOps硬件庫中的主要組成部分，主要功能是接收數(shù)據(jù)輸入進行算術(shù)運算，然后將結(jié)果輸出到存儲器或者后續(xù)的模塊中.控制模塊包含一些反饋控制邏輯，用于表達狀態(tài)機.工具模塊包含一些與內(nèi)存系統(tǒng)與主機平臺交互的工具.為了使用GraphOps實現(xiàn)一個特定的圖計算加速器，用戶首先根據(jù)算法的特點選擇需要的模塊，之后通過修改模塊的參數(shù)對模塊進行的計算過程進行配置，最后將這些模塊的輸入、輸出流相連，組合形成滿足特定功能的圖計算系統(tǒng).

HitGraph[53]可以根據(jù)用戶設(shè)置的硬件參數(shù)等信息直接生成FPGA圖算法加速器的RTL實現(xiàn).HitGraph提供了設(shè)計空間探索和硬件生成器的軟件工具.用戶首先將圖算法的名稱、圖數(shù)據(jù)的具體信息(頂點和邊的數(shù)據(jù)寬度等)、FPGA設(shè)備的硬件條件約束(BRAM的大小等)信息作為參數(shù)運行設(shè)計空間探索工具.設(shè)計空間探索以最大化系統(tǒng)的帶寬為目標(biāo)，計算得到最佳的架構(gòu)參數(shù)(處理單元個數(shù)等).之后，用戶將算法名稱和架構(gòu)參數(shù)信息輸入硬件生成器中，生成圖加速器的Verilog代碼.使用HitGraph生成加速器的過程隱藏了加速器內(nèi)部的設(shè)計細節(jié)，具有極大的用戶友好和易用性.目前，HitGraph支持的算法包括SpMV,PR,SSSP,WCC這4種.由于HitGraph底層使用以邊為中心的編程模型，只需要定義Process_edge和Apply_update兩個函數(shù)就可將其拓展支持其他圖算法，而不需要改動其他部件.

6 國內(nèi)外研究進展分析

Fig.3 Running environment and design module of JGraph圖3 JGraph系統(tǒng)運行環(huán)境介紹與系統(tǒng)設(shè)計模塊圖

面向FPGA圖計算的編程與開發(fā)環(huán)境研究工程量大、技術(shù)挑戰(zhàn)高，目前在國內(nèi)研究工作局限在少數(shù)高校院所.在由上海交通大學(xué)與華中科技大學(xué)共同進行的FPGA圖計算加速器項目中，探索了簡單易用的編程與開發(fā)環(huán)境設(shè)計.如圖3所示，①②③④描述的是Host與FPGA加速卡的體系架構(gòu)與通信、控制等模塊，圖數(shù)據(jù)從CPU經(jīng)過PCIe接口傳遞到主存中，即主要存儲在主存上，在運算時會被加載到PE上計算.

該團隊設(shè)計了如圖3中⑤所示的面向圖計算系統(tǒng)的FPGA編程與開發(fā)環(huán)境系統(tǒng)，暫命名為JGraph，以及相關(guān)的軟件系統(tǒng)設(shè)計模塊圖.圖3中JGraph會經(jīng)過⑥設(shè)計的圖專用語言編寫程序，經(jīng)過高度優(yōu)化與凝練的⑦高層次綜合系統(tǒng)，生成⑧能夠高效運行的代碼，一部分在CPU上執(zhí)行，主要包括數(shù)據(jù)傳輸與運行控制部分，算法主體在FPGA板卡上執(zhí)行，其中會經(jīng)歷從Chisel硬件語言轉(zhuǎn)換為FPGA可用的Verilog語言，共同完成算法的布局與運行.

JGraph能夠支持多種圖計算編程模型，其中囊括多種經(jīng)典圖操作算子的提取與封裝，上層為用戶提供簡潔易用的程序編寫語言和靈活多層次的圖計算庫函數(shù)，設(shè)計高效的高層次綜合技術(shù)，系統(tǒng)能夠在保證易用性的前提下生成高性能的硬件代碼.

由于FPGA具有高性能高能效計算的潛力，國內(nèi)外各種基于FPGA的計算硬件加速器層出不窮，諸如Xilinx,Intel等硬件公司推出了各類新型板卡，Amazon以及Facebook等互聯(lián)網(wǎng)巨頭也開發(fā)了相應(yīng)加速器，而國內(nèi)的浪潮和百度、阿里等互聯(lián)網(wǎng)公司也在FPGA加速技術(shù)上做出探索.作為新興技術(shù)，深鑒科技和美圖影像實驗室也分別將它們應(yīng)用于深度學(xué)習(xí)以及圖像處理.

使用FPGA為代表的專用加速器進行圖計算已經(jīng)成為了廣泛趨勢.Google公司率先開展了大規(guī)模圖數(shù)據(jù)的研究，國內(nèi)外各大企業(yè)與高校也開展了相應(yīng)圖計算研究工作.2012年華為和阿里巴巴也進軍了該領(lǐng)域.將FPGA應(yīng)用于圖計算加速，學(xué)術(shù)界已經(jīng)做出了很多探索，以追求更高的性能和能效，而工業(yè)界關(guān)于二者的結(jié)合探索尚少.FPGA圖計算加速的相關(guān)工作具體結(jié)果如表5所示:

Table 5 FPGA-based Graph Processing Programming Development Environment表5 基于FPGA的圖計算編程與開發(fā)環(huán)境

7 開放問題與挑戰(zhàn)

圖計算具備廣泛的應(yīng)用前景.在今天，智能電網(wǎng)、醫(yī)療保險金融欺詐等應(yīng)用場景將使得它更加重要，基于FPGA的圖計算加速器主要面臨著硬件和軟件2方面的挑戰(zhàn).在圖數(shù)據(jù)規(guī)模日益增加的今天，大圖支持是圖計算加速器的重要訴求，面向大圖的編程與開發(fā)環(huán)境也是以后圖計算開發(fā)的重要探索方向.在可編程性的探索中，高效易用且能兼顧軟硬件特性的DSL也是有趣的嘗試.同時，如何設(shè)計出能高效支撐圖計算的HLS工具也是重要的探索方向.

7.1 支持復(fù)雜環(huán)境的大圖處理

FPGA片上存儲器(BRAM)具有高速隨機存取的能力，但是相比于DRAM，BRAM的容量很小，無法存儲較大的圖數(shù)據(jù)集.許多圖計算加速器，將圖數(shù)據(jù)集存儲于單個FPGA的BRAM中，因此在處理大規(guī)模圖數(shù)據(jù)的問題上，F(xiàn)PGA開發(fā)還面臨挑戰(zhàn).在面向大圖問題上，使用新興的內(nèi)存技術(shù)或者支持多FPGA是有效的解決方案，這也為編程開發(fā)帶來了新的挑戰(zhàn).

1) 新興內(nèi)存技術(shù)的引入.解決方法之一是在FPGA上增加一塊大容量的DRAM.然而由于圖計算具有高訪存比、隨機訪存的特點，DRAM的帶寬成為系統(tǒng)的瓶頸.改善帶寬瓶頸的方式包括使用HMC[21,74-75]或者ReRAM[85]等新型的存儲技術(shù)，或者通過優(yōu)化的圖存儲方式減少隨機訪存的次數(shù)，從而節(jié)省帶寬，圖計算提升性能.

設(shè)計有效的語言以支持這些新興的內(nèi)存技術(shù)，在高級語言層面提供相應(yīng)的設(shè)計支持，以在底層模塊提供更好的對應(yīng)，或者引入相關(guān)內(nèi)存機制優(yōu)化訪存過程，減小開銷，這些都是重要的研究課題.

2) 多FPGA架構(gòu)的引入.采用多FPGA架構(gòu)是解決問題的第2個方案.使用多個FPGA不僅能夠獲得更大的片上存儲空間，也同時使系統(tǒng)具有更大的帶寬和更高的并行計算能力.這種方法的缺點是圖數(shù)據(jù)分布在多個FPGA上，導(dǎo)致計算過程中FPGA之間需要頻繁交換數(shù)據(jù)，跨芯片的通信延遲成為了計算的關(guān)鍵路徑.通常的改進方式為使用更為優(yōu)化的圖分割方式，或者對算法的執(zhí)行流程進行優(yōu)化，以減少消息的發(fā)送量.

在采用多FPGA架構(gòu)時，高效且開銷小的通信機制是未來的重要探索方向之一.為了使用這一特殊架構(gòu)，將高效的通信機制引入相應(yīng)的編程與開發(fā)環(huán)境將是一個有趣的探索.

7.2 支持底層友好的高層編程

雖然FPGA硬件開發(fā)人員可選的開發(fā)工具(例如硬件描述語言、高層次綜合工具，以及圖計算框架等)種類繁多，但是開發(fā)方式之間各有優(yōu)勢與不足，需要開發(fā)者作出權(quán)衡.

1) 易用的DSL訴求.現(xiàn)有的FPGA圖計算框架只允許用戶通過修改硬件架構(gòu)中的部分模塊的方式更改加速器的行為，而架構(gòu)中其他的模塊以及圖的存儲方式都是固定的，這限制了框架的應(yīng)用場景.當(dāng)前，F(xiàn)PGA圖計算領(lǐng)域還沒有出現(xiàn)像CPU上的圖計算DSL那樣的具有細粒度圖計算算法描述能力的語言，這一方面是由于FPGA在運行方式上與CPU的巨大差異，另一方面是由于FPGA設(shè)備的型號與支持的硬件設(shè)備的多樣性.盡管許多新興的DSL通過元編程等方式嵌入高級編程語言，降低了編程難度，但是由于相關(guān)工具鏈不夠成熟、文檔描述不夠全面、支持的FPGA設(shè)備有限等原因，還沒有得到廣泛的應(yīng)用.因此，針對FPGA圖計算領(lǐng)域，設(shè)計出一種通用的高效易用的DSL仍然是一項巨大的挑戰(zhàn).

2) 高效的HLS支持.傳統(tǒng)的硬件描述語言(如Verilog,VHDL)專為硬件開發(fā)設(shè)計，運行效率較高.但是要求開發(fā)人員掌握底層的時序電路等硬件知識，并且相比于計算機編程語言，缺乏足夠的抽象能力.因此具有開發(fā)周期長、編程難度大的缺點.

HLS工具種類繁多[25]，并且各種HLS工具采用的優(yōu)化策略不同，因此對于不同類型的應(yīng)用，不同的HLS工具生成的加速器效率可能不同.高效的DSL支持、友好的指令優(yōu)化、可控的IR表示粒度以及高效的調(diào)度算法，都能使得HLS工具有效地支撐圖計算，是未來FPGA圖計算的編程的探索方向.

根據(jù)一些已有的工具[18,89]，將機器學(xué)習(xí)引入到HLS工具中將是一個有意思的嘗試.Spatial[18]使用了一種基于機器學(xué)習(xí)的內(nèi)存劃分機制，而FlexTensor[89]提出了一種自動探索調(diào)度空間與優(yōu)化的框架.

8 總 結(jié)

對于FPGA這種特殊的硬件架構(gòu)，高效的編程與開發(fā)環(huán)境是提高開發(fā)效率的關(guān)鍵要素.我們對FPGA圖計算加速器設(shè)計過程設(shè)計的編程和開發(fā)環(huán)境做了綜述，為了系統(tǒng)地說明編程與開發(fā)環(huán)境的特性，我們從編程模型、高層次綜合、編程語言以及用戶接口這4個方面做出了詳細介紹.本文對一些關(guān)鍵技術(shù)進行說明，能夠為以后基于FPGA圖計算加速器的開發(fā)提供思路與方向.同時，我們還介紹了國內(nèi)外FPGA圖計算加速器的工作進展.最后，本文還總結(jié)出了FPGA圖計算編程與開發(fā)環(huán)境的相關(guān)挑戰(zhàn)，并對FPGA圖計算編程與開發(fā)環(huán)境的有關(guān)探索方向進行了展望.