面向高性能圖計(jì)算的高效高層次綜合方法

湯嘉武 鄭 龍 廖小飛 金 海

(華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 武漢 430074) (大數(shù)據(jù)技術(shù)與系統(tǒng)國(guó)家地方聯(lián)合工程研究中心(華中科技大學(xué)) 武漢 430074) (服務(wù)計(jì)算技術(shù)與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室(華中科技大學(xué)) 武漢 430074) (集群與網(wǎng)格計(jì)算湖北省重點(diǎn)實(shí)驗(yàn)室(華中科技大學(xué)) 武漢 430074)

(jiawut@hust.edu.cn)

最近10年來(lái)隨著生物信息網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、網(wǎng)頁(yè)圖等大數(shù)據(jù)分析問(wèn)題的出現(xiàn)，圖應(yīng)用變得越來(lái)越重要，圖是大數(shù)據(jù)關(guān)聯(lián)屬性的最佳表達(dá)方式，圖計(jì)算則是基于圖模式進(jìn)行巨量、稀疏、超維關(guān)聯(lián)的挖掘和分析過(guò)程，當(dāng)前大數(shù)據(jù)的機(jī)器學(xué)習(xí)和深度學(xué)習(xí)都依賴(lài)于圖計(jì)算，圖計(jì)算已經(jīng)成為大數(shù)據(jù)處理的主流模式之一.

圖計(jì)算的復(fù)雜特性對(duì)當(dāng)前硬件提出了新的挑戰(zhàn)，CPU和面向吞吐量的架構(gòu)都有各自的局限性[1].對(duì)于通用的CPU，大量研究表明,即使對(duì)于最優(yōu)的圖算法實(shí)現(xiàn)其指令級(jí)并行度仍然異常的低，絕大多數(shù)低于1.0，許多低于0.5[2].對(duì)于面向吞吐量的架構(gòu)，比如GPU，按照單指令多數(shù)據(jù)(single-instruction multiple-data, SIMD)的方式執(zhí)行，通過(guò)調(diào)度數(shù)以千計(jì)的線程來(lái)掩蓋耗時(shí)的內(nèi)存訪問(wèn)[3]，雖然性能較高但是功耗巨大，圖數(shù)據(jù)的冪律分布和圖算法的不規(guī)則性天然對(duì)SIMD模式不友好，存在負(fù)載不均和低帶寬利用率問(wèn)題，研究表明只有低于16%的時(shí)間GPU得到完全利用，主要性能瓶頸在于訪存單元在流水線中的停滯[4].

對(duì)于可重構(gòu)硬件，例如現(xiàn)場(chǎng)可編程門(mén)陣列(field-programmable gate array， FPGA)，由于其低功耗和可重構(gòu)特性得到很大關(guān)注，研究人員在FPGA上針對(duì)圖計(jì)算設(shè)計(jì)了諸多高效的處理架構(gòu)[5-8]，體現(xiàn)了FPGA在圖計(jì)算領(lǐng)域的巨大潛力，而即使對(duì)于專(zhuān)業(yè)的研究人員，編寫(xiě)完整的圖計(jì)算硬件代碼也是十分耗時(shí)的事情，一方面是圖計(jì)算自身的復(fù)雜性，另一方面是硬件編程過(guò)高的壁壘，表面上算法優(yōu)化和架構(gòu)設(shè)計(jì)是工作核心，實(shí)際上硬件語(yǔ)言的仿真測(cè)試、調(diào)試以及上板所必須的其他工作占了大量時(shí)間，因特爾公司指出1名資深的硬件工程師實(shí)現(xiàn)1個(gè)完整的最短路徑算法也需要幾個(gè)月的時(shí)間.

為了使FPGA開(kāi)發(fā)人員從繁瑣的硬件細(xì)節(jié)中解脫出來(lái)，專(zhuān)心于算法本身和架構(gòu)的設(shè)計(jì)，許多HLS系統(tǒng)被提出，大部分都采用CC++作為輸入并輸出寄存器傳輸級(jí)(register-transfer level, RTL)代碼，這極大地降低了硬件編程門(mén)檻并縮短了開(kāi)發(fā)時(shí)間，HLS系統(tǒng)還提供了各種優(yōu)化方法使得開(kāi)發(fā)人員可以從高級(jí)語(yǔ)言層面對(duì)硬件結(jié)構(gòu)進(jìn)行優(yōu)化，部分還提供了可視化的視圖方便對(duì)每個(gè)時(shí)鐘周期的電路行為進(jìn)行分析，進(jìn)一步提高了生成RTL的性能，但是目前與手動(dòng)最優(yōu)的RTL在面積和性能等多個(gè)方面有較大差距，特別地，針對(duì)圖計(jì)算這種不規(guī)則的復(fù)雜關(guān)聯(lián)應(yīng)用，這一些現(xiàn)象尤為嚴(yán)重，這是由于HLS系統(tǒng)自身的結(jié)構(gòu)特性造成的，具體而言：

1) 采用C或類(lèi)C語(yǔ)言作為輸入，從這種命令式語(yǔ)言中很難提取到結(jié)構(gòu)信息和并行特性，難以發(fā)掘其中的優(yōu)化機(jī)會(huì).

2) 優(yōu)化指令和算法雜糅在一起，如果要進(jìn)行算法結(jié)構(gòu)上的變更必須修改大量代碼，編程效率低下，無(wú)法快速找到較好的算法結(jié)構(gòu)和優(yōu)化方案.

3) 優(yōu)化指令不友好，由于輸入語(yǔ)言的原因，只有開(kāi)發(fā)人員對(duì)硬件底層細(xì)節(jié)十分了解才能寫(xiě)好優(yōu)化指令，比如某一段程序想要并行執(zhí)行，開(kāi)發(fā)人員得自己設(shè)計(jì)好數(shù)據(jù)存儲(chǔ)和劃分，否則HLS系統(tǒng)會(huì)大量復(fù)制數(shù)據(jù)占用稀缺的片上存儲(chǔ)或者因?yàn)榇鎯?chǔ)空間不夠而自動(dòng)取消并行，但是這些對(duì)開(kāi)發(fā)人員是隱藏的，只能在生成RTL后通過(guò)硬件代碼或者資源利用情況判斷.

4) 中間表示(intermediate representation， IR)粒度太細(xì)，輸入的上層代碼編譯為最基本的操作，完全喪失了結(jié)構(gòu)特性，底層硬件模板也是基本操作的簡(jiǎn)單實(shí)現(xiàn)，會(huì)造成電路邏輯的大量冗余和關(guān)鍵路徑的延長(zhǎng)，降低可讀性，同時(shí)與手寫(xiě)代碼相比也要遜色許多.

5) 調(diào)度算法不高效，系統(tǒng)最耗時(shí)的部分就是調(diào)度部分，由于FPGA的天然并行特性，沒(méi)有依賴(lài)的邏輯是可以并行執(zhí)行的，為了縮短關(guān)鍵路徑提高系統(tǒng)頻率，組合邏輯不應(yīng)該過(guò)長(zhǎng)，這要求可以并行的盡量放到同一個(gè)時(shí)鐘周期中執(zhí)行，由于IR粒度太細(xì)，指令數(shù)目巨大，現(xiàn)有調(diào)度算法只能在可接受時(shí)間內(nèi)找到次優(yōu)解，或者直接采用簡(jiǎn)單的啟發(fā)式算法，面對(duì)潛在的依賴(lài)關(guān)系沒(méi)有很好的方法解決或者直接串行執(zhí)行，特別是圖計(jì)算這類(lèi)不規(guī)則應(yīng)用，對(duì)優(yōu)化指令也沒(méi)有特定的支撐，這也是片上存儲(chǔ)資源被不必要地大量消耗和表面并行實(shí)則串行的原因.

6) 不支持片外數(shù)據(jù)傳輸，HLS系統(tǒng)不能自動(dòng)生成存儲(chǔ)控制器和與主機(jī)端以及DRAM數(shù)據(jù)傳輸?shù)慕涌冢荒苌蛇壿嬰娐泛笫謩?dòng)編寫(xiě)添加相應(yīng)模塊，對(duì)于上板需求而言十分不便，同樣要求開(kāi)發(fā)人員對(duì)底層內(nèi)存系統(tǒng)細(xì)節(jié)十分了解，沒(méi)有從根本上提高硬件設(shè)計(jì)的抽象層次.

HLS系統(tǒng)整體流程也導(dǎo)致了編譯和綜合流程對(duì)開(kāi)發(fā)人員不透明，難以通過(guò)在上層調(diào)整高級(jí)語(yǔ)言代碼從而在底層實(shí)現(xiàn)特定硬件架構(gòu)，底層低效的硬件模板既無(wú)法靈活表達(dá)上層需求，也不能達(dá)到高效性能，特別是對(duì)現(xiàn)在一些復(fù)雜的特定應(yīng)用，HLS系統(tǒng)的作用非常有限.因此出現(xiàn)了一些領(lǐng)域特定語(yǔ)言(domain-specific language, DSL)，對(duì)特定領(lǐng)域需求作了相應(yīng)的優(yōu)化，從上層編程語(yǔ)言到底層硬件模塊都作了對(duì)應(yīng)修改，取得了很好的效果，但是對(duì)于圖計(jì)算這類(lèi)非規(guī)則的復(fù)雜應(yīng)用還沒(méi)有很好的支撐，與其特性不能很好地契合，目前還沒(méi)有一個(gè)專(zhuān)門(mén)面向圖計(jì)算的HLS系統(tǒng).

為了解決HLS系統(tǒng)缺乏對(duì)圖計(jì)算有效支撐的根本問(wèn)題，提出了一種面向圖計(jì)算的高效HLS方法，通用自定義的編程原語(yǔ)編寫(xiě)圖算法作為輸入，自動(dòng)輸出RTL代碼.本文主要貢獻(xiàn)有4個(gè)方面：

1) 提出了一種面向圖計(jì)算的高效HLS方法，采用數(shù)據(jù)流架構(gòu)實(shí)現(xiàn)高效的并行流水執(zhí)行.

2) 提出了面向圖計(jì)算的函數(shù)式編程原語(yǔ)和對(duì)應(yīng)的優(yōu)化指令，可簡(jiǎn)潔高效地表達(dá)各類(lèi)圖算法.

3) 提出了模塊化的數(shù)據(jù)流IR，細(xì)粒度地暴露出圖算法中的點(diǎn)邊不規(guī)則并行性.

4) 提供參數(shù)化硬件模板，生成了BFS和PageRank算法的硬件實(shí)現(xiàn)，通過(guò)在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了方法的正確性和高效性.

1 相關(guān)工作

當(dāng)前的FPGA設(shè)計(jì)工具支持相對(duì)原始的編程接口，需要大量的手動(dòng)工作[9],Verilog和VHDL等硬件描述語(yǔ)言專(zhuān)為任意電路描述而設(shè)計(jì).時(shí)序、控制信號(hào)和內(nèi)存均由用戶(hù)處理.而Chisel[10]，MyHDL[11]，VeriScala[12]這樣的語(yǔ)言通過(guò)在軟件語(yǔ)言(例如Scala或Python)中使用硬件描述語(yǔ)言來(lái)簡(jiǎn)化程序生成電路.Genesis2[13]為SystemVerilog添加了Perl腳本支持，以幫助推動(dòng)程序生成.雖然與Verilog生成語(yǔ)句相比，這些改進(jìn)允許更強(qiáng)大的元編程，但用戶(hù)仍然在時(shí)序電路級(jí)別編寫(xiě)程序.

HLS系統(tǒng)提高了設(shè)計(jì)層級(jí)[14]，比如LegUp[15]，Lime[16]，Vivado HLS[17]，OpenCL[18]，SDAccel[19],允許用戶(hù)用類(lèi)C語(yǔ)言或者OpenCL進(jìn)行FPGA設(shè)計(jì)，存儲(chǔ)單元用數(shù)組表示，整個(gè)應(yīng)用不包含時(shí)序.但是對(duì)于圖算法中的嵌套循環(huán)，使用這些工具進(jìn)行內(nèi)層循環(huán)流水執(zhí)行、循環(huán)展開(kāi)、內(nèi)存劃分、內(nèi)存復(fù)制和建立緩沖區(qū)時(shí)，由于這些工作均由編譯器完成，命令式的設(shè)計(jì)描述給編譯器發(fā)現(xiàn)并行性、流水結(jié)構(gòu)和內(nèi)存訪問(wèn)模式帶來(lái)了很大的困難，因此要求用戶(hù)進(jìn)行顯示地標(biāo)注，對(duì)用戶(hù)提出了很高的要求，而且數(shù)組很難映射到圖計(jì)算所需要的各種硬件存儲(chǔ)單元.

有工作采用多面體工具在單循環(huán)嵌套中自動(dòng)對(duì)仿射訪問(wèn)進(jìn)行內(nèi)存劃分[20]，但是不能解決圖計(jì)算中非仿射訪問(wèn)的情況和多循環(huán)嵌套中訪問(wèn)相同存儲(chǔ)單元的情況.也有工作可以輔助對(duì)HLS程序中的編譯指示進(jìn)行自動(dòng)調(diào)整，但仍需要手動(dòng)硬件優(yōu)化.總而言之，HLS工具不能很好地挖掘粗粒度流水執(zhí)行和嵌套循環(huán)并行的機(jī)會(huì)，同樣簡(jiǎn)單的存儲(chǔ)模型對(duì)高并行流水的支持也不足.

DSL在提高設(shè)計(jì)層級(jí)的同時(shí)對(duì)特定領(lǐng)域進(jìn)行了相應(yīng)優(yōu)化，DHDL[21]可以描述無(wú)時(shí)序嵌套并行的流水結(jié)構(gòu)并將其轉(zhuǎn)化到硬件模塊，Spatial[22]是DHDL的改良版本，可以支持有數(shù)據(jù)依賴(lài)的控制流和豐富的存儲(chǔ)單元表達(dá).但是對(duì)于圖計(jì)算這種非規(guī)則的應(yīng)用，當(dāng)并行執(zhí)行時(shí)產(chǎn)生大量數(shù)據(jù)沖突，Spatial的內(nèi)存劃分機(jī)制對(duì)其支撐不足，會(huì)簡(jiǎn)單地對(duì)片上存儲(chǔ)單元進(jìn)行復(fù)制操作，快速用完稀缺的存儲(chǔ)資源，無(wú)法實(shí)現(xiàn)高并行度.

在HLS系統(tǒng)中使用動(dòng)態(tài)調(diào)度可以實(shí)現(xiàn)更高效的流水結(jié)構(gòu)，ElasticFlow[23]可以對(duì)一類(lèi)特定的不規(guī)則循環(huán)進(jìn)行循環(huán)流水化，Dai等人[24]通過(guò)調(diào)度流水結(jié)構(gòu)的多個(gè)啟動(dòng)間隔實(shí)現(xiàn)流水線沖刷，他們后來(lái)開(kāi)發(fā)了應(yīng)用特定的動(dòng)態(tài)沖突檢測(cè)電路，但是有嚴(yán)格的約束.Nurvitadhi等人[25]通過(guò)假定數(shù)據(jù)通路已經(jīng)劃分到了流水線各個(gè)階段來(lái)實(shí)現(xiàn)自動(dòng)流水化.這些方法還是基于傳統(tǒng)HLS系統(tǒng)中的靜態(tài)調(diào)度，引入了一些動(dòng)態(tài)行為，只能在特定的情況下得到性能提升.

目前還沒(méi)有HLS工具可以從上層高級(jí)語(yǔ)言為圖算法直接生成高并行度的高效流水結(jié)構(gòu)，一方面因?yàn)槠浔磉_(dá)能力有限，用戶(hù)很難準(zhǔn)確描述所要的架構(gòu)并指定微架構(gòu)參數(shù)，另一方面對(duì)圖算法指定高并行度后會(huì)產(chǎn)生大量數(shù)據(jù)依賴(lài)和沖突，沒(méi)有足夠的底層優(yōu)化去實(shí)現(xiàn)高并行度所需的存儲(chǔ)和計(jì)算結(jié)構(gòu)，導(dǎo)致最后生成的硬件電路實(shí)際串行執(zhí)行或者資源耗盡無(wú)法生成.

本文通過(guò)底層采用特定于圖算法的優(yōu)化數(shù)據(jù)流架構(gòu)和定制的存儲(chǔ)層級(jí)結(jié)構(gòu)針對(duì)上述HLS工具中難以對(duì)圖算法高并行度執(zhí)行和存儲(chǔ)模型低效的問(wèn)題提出了解決方法，為從上層語(yǔ)言生成圖應(yīng)用RTL提供有效支撐.

2 系統(tǒng)設(shè)計(jì)

本節(jié)中主要包含3個(gè)部分，分別是上層編程模型、模塊化數(shù)據(jù)流IR和底層參數(shù)化硬件模板與RTL代碼生成，對(duì)應(yīng)整個(gè)方法的執(zhí)行流程.

2.1 上層編程模型

編程模型使用的是以點(diǎn)為中心的模型，圖算法通過(guò)描述每個(gè)節(jié)點(diǎn)的計(jì)算行為描述整個(gè)算法邏輯，有較高的兼容性，在執(zhí)行模型方面，圖計(jì)算中常見(jiàn)的執(zhí)行模型有push和pull這2種.本文選擇pull作為執(zhí)行模型.在pull模型中，圖算法每輪迭代會(huì)調(diào)度所有節(jié)點(diǎn)，并處理其所有入邊數(shù)據(jù).選擇它的主要原因是：1)PageRank類(lèi)算法更適合采用pull[26]；2)基于push的BFS需要同時(shí)獲取源點(diǎn)和目標(biāo)點(diǎn)數(shù)據(jù)，增加硬件開(kāi)銷(xiāo)；3)基于notify-pullpull和pushpull的BFS的性能差距較低.

算法1給出了基于以點(diǎn)為中心的命令式圖算法偽代碼,在詳細(xì)解釋之前先給出圖術(shù)語(yǔ)，由于從數(shù)學(xué)到計(jì)算科學(xué)以及其他各個(gè)領(lǐng)域?qū)D的研究非常廣泛，標(biāo)準(zhǔn)的術(shù)語(yǔ)尚未確定，本文只簡(jiǎn)單介紹此處使用的描述.

算法1.基于以點(diǎn)為中心的命令式圖計(jì)算偽代碼.

輸入：點(diǎn)數(shù)據(jù)VertexValue、邊數(shù)據(jù)Edge、邊偏移量EdgeOffsetTable；

輸出：迭代收斂后的點(diǎn)數(shù)據(jù)VertexValue.

① for (inti=0;i

② Vertexv=ActiveVertex[i];

③ EdgeOffseteoff=EdgeOffsetTable[v.id];

④ for (intj=eoff.l;j

⑤ Edgee=Edge[j];

⑥ Valueu.val=VertexValue[e.uid];

⑦ Valuetmp=Process(e.weight,v.val,u.val);

⑧ Valuenewval=Reduce(tmp,newval);

⑨ endfor

⑩ UpdateVertex(v.val,newval);

圖數(shù)據(jù)結(jié)構(gòu)建立在反映現(xiàn)實(shí)世界的基元上，包括頂點(diǎn)(vertex)、連接不同頂點(diǎn)的邊(edge)和屬性(property)，節(jié)點(diǎn)和邊均有自己的屬性，屬性可以是任意類(lèi)型的任意數(shù)據(jù).編程模型要求輸入格式為壓縮稀疏行(compressed sparse row, CSR)，引入了Offset的概念，即當(dāng)前頂點(diǎn)對(duì)應(yīng)邊在邊表中的偏移量，在具體算法實(shí)現(xiàn)中一般還會(huì)建立1個(gè)活躍點(diǎn)集(ActiveVertex),目標(biāo)節(jié)點(diǎn)表示為u，屬性值表示為Value.

對(duì)算法1中的圖計(jì)算偽代碼，行①的循環(huán)代表依次處理所有活躍頂點(diǎn)，行④的循環(huán)代表依次處理當(dāng)前活躍頂點(diǎn)的所有邊.首先考慮對(duì)嵌套循環(huán)進(jìn)行粗粒度流水，即行②③作為1個(gè)流水階段，行④～⑨的循環(huán)整體作為1個(gè)流水階段(目前只有Spatial可以實(shí)現(xiàn)任意位置的粗粒度流水)，接著對(duì)行④～⑨代表的循環(huán)整體進(jìn)行細(xì)粒度流水，即使達(dá)到了HLS工具最大的流水能力，高并行度情況下依然會(huì)有嚴(yán)重的流水停滯.之后考慮添加并行指令，分為點(diǎn)間并行和點(diǎn)內(nèi)并行，分別對(duì)應(yīng)于行①的循環(huán)并行和行④的循環(huán)并行，兩者可同時(shí)添加.

首先考慮點(diǎn)內(nèi)并行，對(duì)于高并行度的點(diǎn)內(nèi)并行(圖加速器可達(dá)到并行度為16或32)，在頂點(diǎn)度數(shù)較小時(shí)每個(gè)周期都有許多計(jì)算資源空閑.首先分析行⑤，邊數(shù)據(jù)存放在Edge數(shù)組中，因?yàn)椴捎肅SR輸入格式，此處邊是連續(xù)的，可以通過(guò)劃分支持高并行訪問(wèn)，第1節(jié)提到有HLS工具對(duì)這類(lèi)訪存行為可以自動(dòng)進(jìn)行內(nèi)存劃分，許多也支持手動(dòng)劃分.之后行⑥通過(guò)邊數(shù)據(jù)訪問(wèn)目標(biāo)點(diǎn)屬性，由于每個(gè)頂點(diǎn)所連結(jié)的目標(biāo)節(jié)點(diǎn)是不可預(yù)測(cè)的，此處會(huì)存在大量的數(shù)據(jù)沖突，對(duì)于這種訪問(wèn)模式現(xiàn)有工具不能進(jìn)行自動(dòng)劃分，由于圖數(shù)據(jù)的冪律分布，少量頂點(diǎn)會(huì)連接大量的邊，這些頂點(diǎn)的訪問(wèn)會(huì)尤其頻繁，Spatial不允許手動(dòng)的內(nèi)存劃分，其自動(dòng)劃分機(jī)制此處支持有限，從而選擇簡(jiǎn)單的內(nèi)存復(fù)制導(dǎo)致片上稀缺的存儲(chǔ)資源大量消耗.行⑦是特定于圖算法的處理操作，行⑧計(jì)算得到更新值，此處由于每條并行的流水線都會(huì)讀同一個(gè)變量然后向其中寫(xiě)入，有的HLS工具為保證結(jié)果正確性會(huì)串行執(zhí)行，有的沒(méi)有檢測(cè)到這個(gè)依賴(lài)問(wèn)題會(huì)產(chǎn)生錯(cuò)誤的結(jié)果(多條流水同時(shí)往同一個(gè)地址寫(xiě)入時(shí)只會(huì)寫(xiě)入第1條流水的數(shù)據(jù)).

點(diǎn)間并行情況與點(diǎn)內(nèi)并行類(lèi)似，由于圖數(shù)據(jù)的冪律分布特性，并行流水線間存在負(fù)載不均的問(wèn)題.在行②讀活躍點(diǎn)數(shù)據(jù)和行③讀邊偏移量以及后面的操作沖突同樣很?chē)?yán)重.當(dāng)邊數(shù)量太大無(wú)法存放在片上時(shí)會(huì)將其存放到片外動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器(dynamic random access memory， DRAM)中，一般在行③和行④之間增加1個(gè)通過(guò)Offset去片外取邊的操作，不改變行⑤取邊數(shù)據(jù)的沖突本質(zhì).

現(xiàn)有HLS系統(tǒng)雖然可以實(shí)現(xiàn)圖算法的粗細(xì)粒度流水結(jié)構(gòu)，但是在指定高并行度時(shí)缺乏訪存和并行更新操作的支持，其生成的硬件邏輯依賴(lài)于用戶(hù)的輸入，但是高級(jí)語(yǔ)言對(duì)硬件描述能力有限，即使用戶(hù)熟悉底層硬件也很難在上層描述出特定的硬件結(jié)構(gòu)，對(duì)算法1的分析可以發(fā)現(xiàn)在整個(gè)遍歷過(guò)程中可以將圖算法的操作分為讀活躍點(diǎn)集合、讀邊偏移量、讀邊數(shù)據(jù)、讀目標(biāo)點(diǎn)數(shù)據(jù)、邊數(shù)據(jù)計(jì)算、合并計(jì)算結(jié)果和更新節(jié)點(diǎn)和活躍點(diǎn)集7個(gè)主要操作，但是針對(duì)于循環(huán)而展開(kāi)的各種優(yōu)化手段無(wú)法針對(duì)性地切實(shí)地解決這些操作中存在的依賴(lài)和沖突問(wèn)題，其作用于循環(huán)內(nèi)包含的多種操作，無(wú)法為每個(gè)操作生成特定的支持.

本文提出的編程模型突出了7個(gè)主要的圖操作，允許用戶(hù)直接在每個(gè)操作上添加特定的架構(gòu)和微架構(gòu)參數(shù)，包括并行度、數(shù)據(jù)位寬、數(shù)據(jù)類(lèi)型和格式調(diào)整.如算法2所示的偽代碼.

算法2.基于以點(diǎn)為中心的函數(shù)式圖計(jì)算偽代碼.

輸入：點(diǎn)數(shù)據(jù)VertexValue、邊數(shù)據(jù)Edge、邊偏移量EdgeOffsetTable；

輸出：迭代收斂后的點(diǎn)數(shù)據(jù)VertexValue.

①ReadGraph(address);

② Foreach (ActiveVertex){i=>

③v=GetVertex(i);

④off=GetOffset(v);

⑤ Foreach (off){j=>

⑥e=GetEdge(j);

⑦u=GetNeighbor(e);

⑧tmp=Process(v,e,u);

⑨newval=Reduce(tmp,newval);

⑩ }

2.2 模塊化數(shù)據(jù)流IR

根據(jù)圖計(jì)算的依賴(lài)關(guān)系，算法2的數(shù)據(jù)流圖如圖1所示，算法2中行①由用戶(hù)指定輸入的CSR格式圖數(shù)據(jù)的地址，讀入圖數(shù)據(jù)，將根據(jù)后面的代碼自動(dòng)決定數(shù)據(jù)的存放方式和地址；行②③對(duì)應(yīng)圖1中讀活躍點(diǎn)數(shù)據(jù)，由于是pull執(zhí)行，所有點(diǎn)都是活躍點(diǎn)，其中行②實(shí)際上作為本輪迭代是否完成的信號(hào)，此處可以選擇讀點(diǎn)的并行度；行④對(duì)應(yīng)圖1中讀邊偏移量，同樣可以指定并行度，默認(rèn)和點(diǎn)并行度保持一致；行⑤無(wú)實(shí)際作用，如2.1節(jié)所述此模型不依賴(lài)循環(huán)驅(qū)動(dòng)執(zhí)行；行⑥對(duì)應(yīng)圖1中讀邊數(shù)據(jù)，可以指定邊并行度，由于是順序讀邊不依賴(lài)于源點(diǎn)數(shù)據(jù)，當(dāng)頂點(diǎn)度數(shù)較大時(shí)相當(dāng)于點(diǎn)內(nèi)并行，頂點(diǎn)度數(shù)較小時(shí)相當(dāng)于點(diǎn)間并行，保證了硬件資源的持續(xù)運(yùn)行和解決了點(diǎn)間度數(shù)不均勻帶來(lái)的負(fù)載均衡問(wèn)題；行⑦對(duì)應(yīng)圖1中讀目標(biāo)點(diǎn)數(shù)據(jù)，由于此處存在大量隨機(jī)訪存，將根據(jù)讀邊并行度生成對(duì)應(yīng)數(shù)量的緩沖區(qū)，對(duì)片上點(diǎn)數(shù)據(jù)劃分的同時(shí)也對(duì)訪存請(qǐng)求實(shí)施調(diào)度保證較高的吞吐量.行⑧對(duì)應(yīng)圖1中的邊計(jì)算，可以指定數(shù)據(jù)位寬和數(shù)據(jù)類(lèi)型；行⑨對(duì)應(yīng)圖1中合并計(jì)算結(jié)果，用戶(hù)只需編輯合并的邏輯操作，具體架構(gòu)根據(jù)讀邊并行度按照文獻(xiàn)[5]中并行累加架構(gòu)產(chǎn)生；行對(duì)應(yīng)圖1中更新結(jié)果和活躍點(diǎn)集，同樣用戶(hù)只需在行編輯合并的邏輯操作即可，此處更新結(jié)果操作并行度不大于讀點(diǎn)并行度，且會(huì)對(duì)片上點(diǎn)數(shù)據(jù)存儲(chǔ)作相應(yīng)設(shè)置，不會(huì)產(chǎn)生讀寫(xiě)沖突問(wèn)題.

Fig. 1 The data flow diagram of algorithm 2圖1 算法2的數(shù)據(jù)流圖表示

基于圖1所示的數(shù)據(jù)流圖，本文設(shè)計(jì)了如圖2所示的模塊化數(shù)據(jù)流IR用以高效支撐圖1中的各個(gè)操作高并行度流水實(shí)現(xiàn).IR分為17個(gè)模塊，每個(gè)模塊對(duì)應(yīng)圖2中的1個(gè)節(jié)點(diǎn)，編號(hào)和數(shù)據(jù)流動(dòng)方向如圖2所示，不同于將上層語(yǔ)言編譯為細(xì)粒度的中間表示后再去挖掘其中的并行機(jī)會(huì)，模塊化的IR通過(guò)更高抽象層次的表達(dá)將圖算法中如2.1節(jié)提到的關(guān)鍵點(diǎn)針對(duì)性地用特定的模塊顯式表達(dá)，精準(zhǔn)地提供了優(yōu)化支持，避免了大部分?jǐn)?shù)據(jù)沖突.其中每個(gè)模塊都有2種緩沖區(qū)，其一接收上一模塊傳遞的數(shù)據(jù)并指示溢出情況，另外還有緩沖區(qū)存入本模塊產(chǎn)生的結(jié)果供下一模塊讀取，根據(jù)緩沖區(qū)的溢出信號(hào)產(chǎn)生控制信號(hào).接下來(lái)按照?qǐng)D1各個(gè)圖操作的連接順序依次說(shuō)明IR中的對(duì)應(yīng)模塊在每個(gè)時(shí)鐘周期的操作是如何進(jìn)行支撐的，還會(huì)說(shuō)明IR中各個(gè)模塊的實(shí)現(xiàn)細(xì)節(jié).

Fig. 2 Modular data flow IR圖2 模塊化數(shù)據(jù)流IR

1) 讀活躍點(diǎn)數(shù)據(jù)

模塊①對(duì)應(yīng)讀活躍點(diǎn)數(shù)據(jù).由于pull模型所有頂點(diǎn)都是活躍點(diǎn)因此可以順序讀取源節(jié)點(diǎn)，實(shí)現(xiàn)邏輯為1個(gè)源節(jié)點(diǎn)計(jì)數(shù)器按照讀點(diǎn)并行度每個(gè)周期生成對(duì)應(yīng)數(shù)量的源節(jié)點(diǎn)編號(hào)存入輸出緩沖區(qū)，輸出緩沖區(qū)有溢出信號(hào)控制源節(jié)點(diǎn)計(jì)數(shù)器，輸出緩沖區(qū)的大小根據(jù)指定的位寬和點(diǎn)并行度實(shí)例化.假設(shè)點(diǎn)并行度指定為n.

2) 讀邊偏移量

模塊②③對(duì)應(yīng)讀邊偏移量.模塊②從模塊①的輸出緩沖區(qū)讀取n個(gè)點(diǎn)，傳遞源節(jié)點(diǎn)信息，同時(shí)順序生成節(jié)點(diǎn)邊偏移量的訪存請(qǐng)求，同樣受到溢出信息的控制.模塊③處理邊偏移量的訪存請(qǐng)求和邊數(shù)據(jù)訪存請(qǐng)求，各有對(duì)應(yīng)的訪存請(qǐng)求輸入緩沖區(qū)和數(shù)據(jù)輸出緩沖區(qū)，大小由訪存請(qǐng)求并行度和讀邊數(shù)據(jù)并行度決定.

3) 讀邊數(shù)據(jù)

模塊③～⑧對(duì)應(yīng)讀邊數(shù)據(jù).模塊④從模塊③中邊偏移量輸出緩沖區(qū)接收邊偏移量，同時(shí)從模塊②中讀取n個(gè)點(diǎn)信息繼續(xù)傳遞.模塊⑤從模塊④中讀取邊偏移量和源點(diǎn)數(shù)據(jù)并進(jìn)行匹配，在節(jié)點(diǎn)信息中添加其對(duì)應(yīng)的邊偏移量.

模塊⑥按照讀邊并行度順序生成邊訪問(wèn)請(qǐng)求，假設(shè)讀邊并行度為m，不同于根據(jù)源節(jié)點(diǎn)對(duì)應(yīng)的邊偏移量來(lái)生成邊訪存請(qǐng)求，模塊內(nèi)有讀邊計(jì)數(shù)器，此處需要做1個(gè)調(diào)度.首先從緩沖區(qū)中取n個(gè)源節(jié)點(diǎn)，由于源節(jié)點(diǎn)是連續(xù)的，所以其對(duì)應(yīng)的邊偏移量也是連續(xù)的，若讀邊計(jì)數(shù)器的值加上m大于最大的邊偏移量，即將取的m條邊包含了n個(gè)源節(jié)點(diǎn)的所有鄰邊，還存在不屬于這n個(gè)點(diǎn)的邊，那么此次時(shí)鐘周期傳遞n個(gè)源節(jié)點(diǎn)和m個(gè)邊訪存請(qǐng)求，但是邊計(jì)算器不增加，即下一時(shí)鐘周期依然生成這m條邊的訪存請(qǐng)求.若恰好相等，則傳遞n個(gè)源節(jié)點(diǎn)和m個(gè)邊訪存請(qǐng)求，邊計(jì)數(shù)器增加m；若小于，說(shuō)明將取的m條邊不能完全包含這n個(gè)點(diǎn)的所有邊，根據(jù)源節(jié)點(diǎn)信息中包含的邊偏移量計(jì)算出哪些源節(jié)點(diǎn)的邊完全包含在這m條邊中，傳遞這些源節(jié)點(diǎn)并用無(wú)效點(diǎn)補(bǔ)充為n個(gè)，其余的源節(jié)點(diǎn)存入緩沖區(qū)中等待下個(gè)時(shí)鐘周期處理，傳遞m個(gè)邊訪存請(qǐng)求，邊計(jì)數(shù)器增加m.即此模塊根據(jù)實(shí)際節(jié)點(diǎn)度數(shù)可以處理大度數(shù)節(jié)點(diǎn)的多條邊，相當(dāng)于點(diǎn)內(nèi)并行，也可以處理多個(gè)小度數(shù)節(jié)點(diǎn)的所有邊，相當(dāng)于點(diǎn)間并行.

模塊⑦對(duì)邊數(shù)據(jù)產(chǎn)生控制信息，即當(dāng)點(diǎn)度數(shù)較小時(shí)m條邊中存在邊不屬于這n個(gè)源節(jié)點(diǎn)，需要標(biāo)記這些無(wú)效邊，同時(shí)需要給邊加上標(biāo)記指示屬于的源節(jié)點(diǎn)編號(hào)，向后傳遞節(jié)點(diǎn)信息和邊控制信息.模塊⑧從模塊③接收邊數(shù)據(jù)，從模塊⑦接收節(jié)點(diǎn)信息和邊控制信息，根據(jù)控制信號(hào)傳遞這3類(lèi)信息.

4) 讀目標(biāo)點(diǎn)數(shù)據(jù)

Fig. 3 Hardware architecture of graph processing accelerate圖3 圖計(jì)算加速器的硬件架構(gòu)

5) 邊計(jì)算

6) 合并計(jì)算結(jié)果

7) 更新結(jié)果和活躍點(diǎn)集模塊

2.3 底層參數(shù)化硬件模板和代碼生成

基于圖1的數(shù)據(jù)流圖，硬件架構(gòu)如圖3所示，片上流水主要包括讀活躍點(diǎn)集合、讀邊數(shù)據(jù)、讀目標(biāo)點(diǎn)數(shù)據(jù)、任務(wù)調(diào)度、邊計(jì)算、合并計(jì)算結(jié)果和更新節(jié)點(diǎn)和活躍點(diǎn)集.實(shí)際流水按照IR分為17個(gè)模塊，每個(gè)模塊有參數(shù)化的硬件模板支撐，按照2.2節(jié)所述各個(gè)模塊完成的功能不同，對(duì)應(yīng)硬件模板內(nèi)部結(jié)構(gòu)包括外層接口也不相同，但是2個(gè)確定的硬件模板間傳遞的數(shù)據(jù)類(lèi)型是確定的，主要包括源節(jié)點(diǎn)有效性信號(hào)、源節(jié)點(diǎn)編號(hào)、后續(xù)流水級(jí)溢出信號(hào)、內(nèi)存控制器溢出信號(hào)、邊偏移量數(shù)據(jù)、邊數(shù)據(jù)、邊數(shù)據(jù)有效性、邊數(shù)據(jù)屬于的節(jié)點(diǎn)編號(hào)、目標(biāo)點(diǎn)數(shù)據(jù)等等.而對(duì)于源節(jié)點(diǎn)編號(hào)、邊偏移量這類(lèi)非控制性數(shù)據(jù)可以根據(jù)指令生成多個(gè)并行連線.硬件模板內(nèi)部參數(shù)主要包括各類(lèi)數(shù)據(jù)的位寬、緩沖區(qū)大小、點(diǎn)邊流水線個(gè)數(shù)等.

以模塊④和模塊⑤對(duì)應(yīng)的硬件模板之間的連接為例(省略時(shí)鐘信號(hào)和重置信號(hào))，如圖4所示.模塊④輸出n個(gè)源節(jié)點(diǎn)有效性信號(hào)、源節(jié)點(diǎn)編號(hào)、n+1個(gè)邊偏移量、1個(gè)緩沖區(qū)溢出信號(hào)，其中源節(jié)點(diǎn)有效性信號(hào)和溢出信號(hào)位寬默認(rèn)為1，源節(jié)點(diǎn)編號(hào)和邊偏移量位寬根據(jù)指令設(shè)置；模塊⑤接收對(duì)應(yīng)數(shù)據(jù)并從下一流水級(jí)接收緩沖區(qū)溢出信號(hào).

對(duì)于圖算法無(wú)關(guān)的模塊，其對(duì)應(yīng)的硬件模板基本功能完備，只需根據(jù)用戶(hù)指定的并行度和數(shù)據(jù)位寬類(lèi)型等要求實(shí)例化對(duì)應(yīng)的點(diǎn)傳遞流水線、邊傳遞流水線、邊控制信號(hào)傳遞流水線和緩沖區(qū)的大小以及各個(gè)模塊內(nèi)部控制信號(hào)的參數(shù).對(duì)于圖算法相關(guān)的模塊，包括圖2中模塊，以邊計(jì)算對(duì)應(yīng)的硬件模板為例(省略時(shí)鐘信號(hào)和重置信號(hào))，如圖5所示.圖5中輸入接口包括源節(jié)點(diǎn)有效性信號(hào)、源節(jié)點(diǎn)編號(hào)、邊控制信號(hào)、邊屬性等；內(nèi)部結(jié)構(gòu)包括單個(gè)點(diǎn)傳遞流水線和多邊操作模塊，源節(jié)點(diǎn)信息和邊控制信息通過(guò)單個(gè)點(diǎn)傳遞流水線向后續(xù)流水級(jí)傳遞，邊屬性進(jìn)入多邊操作模塊處理得到更新值；輸出接口包括源節(jié)點(diǎn)有效性信號(hào)、源節(jié)點(diǎn)編號(hào)、邊控制信號(hào)、更新值等.

Fig. 4 The connection diagram of edge offset reading hardware template ④ and ⑤圖4 邊偏移量讀取的硬件模板④和⑤連接示意圖

Fig. 5 The diagram of edge process hardware template圖5 邊計(jì)算硬件模板示意圖

除了多邊操作模塊內(nèi)部與圖算法相關(guān)的部分外，輸入輸出接口和單個(gè)點(diǎn)傳遞流水適用于不同圖算法，同樣只需按照用戶(hù)指令參數(shù)實(shí)例化，包括各類(lèi)數(shù)據(jù)的位寬以及單個(gè)點(diǎn)傳遞流水線的個(gè)數(shù)等，邊屬性數(shù)據(jù)中包含多條邊，根據(jù)邊并行度決定，依照相應(yīng)的位數(shù)在多邊操作中并行處理.由于用戶(hù)只需編寫(xiě)計(jì)算操作，不包含控制和訪存操作，根據(jù)其計(jì)算操作生成相應(yīng)的基本硬件計(jì)算器在多邊操作模塊內(nèi)連接即可.完成各個(gè)硬件模板的實(shí)例化和相應(yīng)的連接后生成最終的Verilog代碼.

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

圖算法根據(jù)計(jì)算特點(diǎn)被分為2類(lèi)：遍歷為中心和計(jì)算為中心，其中BFS和PageRank分別是這2類(lèi)圖算法中最常用并且最具代表性的圖算法.在本節(jié)中，我們使用本文提出的方法生成了BFS和PageRank硬件實(shí)現(xiàn)，并且在4個(gè)不同類(lèi)型的數(shù)據(jù)集上測(cè)試了硬件實(shí)現(xiàn)的性能，我們還使用特定于并行模式優(yōu)化的DSL Spatial生成了手動(dòng)調(diào)優(yōu)的BFS和PageRank硬件實(shí)現(xiàn)，在相同數(shù)據(jù)集上進(jìn)行了比較，驗(yàn)證了本文中面向圖計(jì)算的HLS方法的有效性.

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文從SNAP網(wǎng)站上下載了4個(gè)不同類(lèi)型的數(shù)據(jù)集，均為自然圖，如表1所示.按照邊數(shù)目大小分別為email-Eu-core，wiki-Vote，soc-Epinions1，soc-Slashdot0922，平均度數(shù)區(qū)分明顯，可以驗(yàn)證硬件實(shí)現(xiàn)在不同度數(shù)下的表現(xiàn)，平均度數(shù)最大的email-Eu-core達(dá)到了25.4，平均度數(shù)最小的soc-Epinions1為6.7.將所有數(shù)據(jù)集預(yù)處理為圖計(jì)算中流行的CSR格式，包括邊偏移量文件(Offset)和邊表(edge).本方法和Spatial生成的硬件實(shí)現(xiàn)使用完全相同的輸入，包括格式和數(shù)據(jù).

Table 1 Datasets Used in Our Experiments表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2 實(shí)驗(yàn)評(píng)估方法

本文按照Graph500的計(jì)算標(biāo)準(zhǔn)測(cè)試BFS硬件實(shí)現(xiàn)的性能，計(jì)算方法為：圖的邊數(shù)除以BFS運(yùn)行時(shí)間，由于采用pull執(zhí)行模式，BFS需要多輪迭代才能收斂，此處采用圖的邊數(shù)進(jìn)行計(jì)算而不是多輪迭代的總邊數(shù)，剔除了迭代中無(wú)效的吞吐量.由于PageRank在每輪迭代中所有邊均為有效邊，因此通用的PageRank性能計(jì)算方法為：圖的邊數(shù)除以PageRank 1輪迭代時(shí)間，所有硬件實(shí)現(xiàn)使用Xilinx Virtex UltraScale+XCVU9P進(jìn)行驗(yàn)證.

本方法的優(yōu)化參數(shù)設(shè)置為讀點(diǎn)并行度為4，讀邊并行度為16，其余各模塊并行度與其匹配，數(shù)據(jù)位寬設(shè)置為32 b，邊偏移量預(yù)處理模塊輸出的邊偏移量數(shù)據(jù)位寬為4 b，設(shè)置時(shí)鐘頻率為200 MHz.

Spatial優(yōu)化參數(shù)按照2.1節(jié)中描述的流水方式，首先將內(nèi)層循環(huán)當(dāng)做整體放到外層循環(huán)的粗粒度流水中，然后對(duì)內(nèi)層循環(huán)內(nèi)部進(jìn)行細(xì)粒度流水，考慮到片上存儲(chǔ)資源的數(shù)量，設(shè)置內(nèi)層循環(huán)并行度為2，即點(diǎn)間流水并行度為2，按照其默認(rèn)的150 MHz時(shí)鐘頻率運(yùn)行.

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

根據(jù)FPGA上運(yùn)行時(shí)間按照評(píng)估方法分別計(jì)算2類(lèi)硬件實(shí)現(xiàn)在4個(gè)數(shù)據(jù)集上的吞吐量，通用指標(biāo)為每秒遍歷百萬(wàn)條邊數(shù)(million traversed edges per second， MTEPS)，PageRank性能如表2所示，BFS性能如表3所示，本方法硬件實(shí)現(xiàn)和Spatial硬件實(shí)現(xiàn)分別簡(jiǎn)稱(chēng)為Ours和Spatial.為了更直觀地體現(xiàn)性能優(yōu)勢(shì)，圖6和圖7中以Spatial實(shí)現(xiàn)的性能為基準(zhǔn)分別給出了PageRank和BFS性能加速比圖.

Table 2 Performance Comparison of PageRank 表2 PageRank性能比較

Table 3 Performance Comparison of BFS表3 BFS性能比較

Fig. 6 Performance speedup of PageRank圖6 PageRank性能加速比

Fig. 7 Performance speedup of BFS圖7 BFS性能加速比

Spatial非常適合挖掘出深度學(xué)習(xí)、矩陣相乘這類(lèi)規(guī)則訪存應(yīng)用中的并行性，其自動(dòng)內(nèi)存劃分機(jī)制在其中發(fā)揮巨大作用，但是如2.1節(jié)中提到的原因，在圖算法中不規(guī)則訪存使其自動(dòng)劃分不能發(fā)揮太大作用，大量復(fù)制存儲(chǔ)單元導(dǎo)致其并行度難以提升.

我們的實(shí)驗(yàn)結(jié)果相比于Spatial有很大的性能優(yōu)勢(shì)，BFS在不同數(shù)據(jù)集上有7.9～16.1倍的性能提升.對(duì)于以遍歷為中心的圖算法而言，由于底層優(yōu)化后的架構(gòu)各個(gè)模塊的時(shí)序約束較為寬裕，主要問(wèn)題集中在圖2中的模塊邊處理模塊，因?yàn)檫@類(lèi)圖算法邊處理模塊內(nèi)的邏輯相對(duì)簡(jiǎn)單，實(shí)際上整個(gè)設(shè)計(jì)可以采用更高的時(shí)鐘頻率，給性能帶來(lái)進(jìn)一步提升.

另一個(gè)重要影響因素即圖數(shù)據(jù)，圖7中實(shí)驗(yàn)結(jié)果表明對(duì)不同的圖數(shù)據(jù)性能差別較大，主要與圖2中的模塊⑥生成邊數(shù)據(jù)訪存請(qǐng)求和模塊片上數(shù)據(jù)緩存有關(guān)，當(dāng)節(jié)點(diǎn)平均度數(shù)較大時(shí)，模塊⑥訪存的全是有效邊，性能較好，email-Eu-core，wiki-Vote，soc-Slashdot0922節(jié)點(diǎn)平均度數(shù)都大于11；而節(jié)點(diǎn)平均度數(shù)較小時(shí)，受限于讀點(diǎn)并行度，會(huì)產(chǎn)生許多無(wú)效邊導(dǎo)致性能較差.此外雖然在模塊⑩中做了調(diào)度允許不同時(shí)鐘周期到來(lái)的鄰點(diǎn)訪存請(qǐng)求同時(shí)執(zhí)行，但是如果鄰點(diǎn)訪存行為不規(guī)則程度較大，對(duì)性能也會(huì)造成影響.

本文采用的pull編程模型最適合PageRank類(lèi)型的圖算法，其在不同數(shù)據(jù)集上有26.19～30.57倍的性能提升，因?yàn)镻ageRank 1輪迭代里面所有邊都是有效邊，而B(niǎo)FS這類(lèi)圖算法1輪迭代里面只有很少一部分是有效邊，由于我們是按照有效邊進(jìn)行計(jì)算，剔除了遍歷的無(wú)效邊，因此PageRank性能會(huì)比BFS好很多.

2.2節(jié)提到邊處理模塊會(huì)影響時(shí)鐘頻率，因?yàn)镻ageRank需要復(fù)雜的浮點(diǎn)計(jì)算，頻率很難進(jìn)一步提升，雖然可以采用流水線方式進(jìn)行浮點(diǎn)計(jì)算，使得其啟動(dòng)間隔為1個(gè)時(shí)鐘周期，即和BFS的邊處理模塊達(dá)到同樣的處理速度，但是由于流水線長(zhǎng)度更長(zhǎng)，當(dāng)模塊停頓時(shí)，需要更多的時(shí)鐘周期才能重新啟動(dòng).類(lèi)似地，圖數(shù)據(jù)也會(huì)對(duì)PageRank性能產(chǎn)生影響，由于邊處理并行度設(shè)置為16，當(dāng)平均度數(shù)低于16時(shí)，由實(shí)驗(yàn)結(jié)果可知更高平均度數(shù)的圖數(shù)據(jù)會(huì)有更高的性能.

4 總 結(jié)

針對(duì)通用HLS系統(tǒng)缺乏對(duì)不規(guī)則圖算法有效支撐的問(wèn)題，提出了一種面向圖計(jì)算的高效HLS方法.結(jié)合圖算法固有的嵌套循環(huán)、大量隨機(jī)訪存、數(shù)據(jù)沖突以及圖數(shù)據(jù)冪律分布等特性，設(shè)計(jì)了數(shù)據(jù)流驅(qū)動(dòng)的處理架構(gòu)，實(shí)現(xiàn)高效的并行流水執(zhí)行，保證了處理單元的負(fù)載均衡.通過(guò)自定義的編程原語(yǔ)，可快速定制現(xiàn)有圖算法，并將其轉(zhuǎn)化為模塊化的數(shù)據(jù)流中間表示，進(jìn)而映射到參數(shù)化的硬件模板，最后生成RTL.

未來(lái)計(jì)劃考慮提供更豐富的編程原語(yǔ)和編譯支持，使得用戶(hù)可以在上層表達(dá)出現(xiàn)有各主流圖計(jì)算加速器的底層架構(gòu)特性.