FPGA圖計算的編程與開發環境：綜述和探索

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

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

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

Fig.1 The organization of programming enviornment圖1 編程與開發環境部分的組織結構

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

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

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

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

圖1是第2～5節關于FPGA圖計算編程與開發環境部分的組織結構.

1 背景介紹

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

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

1.1 圖計算的簡介

圖是一種由頂點以及連接它們的邊所構成的特殊數據結構，可以表示為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.

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

1.2 通用處理器上的圖計算

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

2) 基于GPU的圖計算.由于GPU具有數據并行能力，因此很多相關工作采用GPU來追求圖計算的高性能.許多基于GPU系統[39-41]都被設計用來進行高性能圖計算.對BFS,CC,BC以及SSSP等常用算法性能優化的工作也被大量展開.圖計算領域專用框架領域也被用于提高GPU應用的開發效率.為了支持大規模的圖數據，CPU-GPU異構系統、多GPU系統和片外內存系統也被陸續提出.

1.3 FPGA的圖計算加速器

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

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

1) 編程靈活性.與ASIC在制造過程中僅“配置”一次不同，FPGA可以根據需要進行多次重新配置.這樣可以調節和改進體系結構，應用錯誤修復或使用FPGA快速原型化硬件設計，然后可以將其設計為ASIC.FPGA還允許即時重新配置以解決不同的任務[47].

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

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

1.4 FPGA上常用圖算法

本節我們將對已在FPGA上實現的主要代表性圖算法進行分類.表2是FPGA上常用的圖算法及分類.FPGA上常用的算法主要包括：廣度優先搜索(BFS)、連通分量(CC)、可達性證明算法、單源最短路徑(SSSP)、全對最短路徑(APSP)、PageRank(PR)、圖形計數(GC)、三角形計數(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 相關編程與開發環境

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

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

2 編程模型

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

2.1 圖計算專用編程模型

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

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

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

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

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

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

2.1.2 其他類型的編程模型

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

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

2.2 通用編程模型

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

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

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

3 高層次綜合

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

3.1 針對圖計算的HLS優化

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

3.1.1 HLS的并行優化

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

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

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

3.1.2 HLS的訪存優化

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

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

3.1.3 HLS的其他優化

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

3.2 通用HLS的能力評估

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

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

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

Spatial適合挖掘出深度學習及矩陣相乘這類規則訪存應用中的并行性，其自動內存劃分機制能發揮巨大作用.但在面臨BFS等圖計算問題時，由于訪存的不規則性，其內存自動劃分機制難以發揮作用，并且會導致大量的存儲單元復制，阻止并行度的提升.

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

4 編程語言

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

4.1 HDL

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

SystemVerilog[3]是對Verilog的擴展，擴充了新的數據類型、壓縮和非壓縮數組、接口、斷言等內容.SystemVerilog結合了硬件描述語言和硬件驗證語言(HVL)，具有測試平臺開發和基于斷言的形式驗證的功能，并且具有面向對象編程的特點.這些特點使得SystemVerilog具有更強的抽象能力，適合于設計可重用的、可用于綜合和驗證的IP，以及特大型基于IP的系統級設計和驗證.

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

4.2 DSL

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

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

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

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

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

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

5 用戶程序接口

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

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

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

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

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

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

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

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

5.2 指令集架構(ISA)方式

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

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

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

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

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

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

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

6 國內外研究進展分析

Fig.3 Running environment and design module of JGraph圖3 JGraph系統運行環境介紹與系統設計模塊圖

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

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

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

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

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

Table 5 FPGA-based Graph Processing Programming Development Environment表5 基于FPGA的圖計算編程與開發環境

7 開放問題與挑戰

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

7.1 支持復雜環境的大圖處理

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

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

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

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

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

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

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

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

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

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

根據一些已有的工具[18,89]，將機器學習引入到HLS工具中將是一個有意思的嘗試.Spatial[18]使用了一種基于機器學習的內存劃分機制，而FlexTensor[89]提出了一種自動探索調度空間與優化的框架.

8 總 結

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