嘗試通過(guò)算法重構和Vivado HLS生成高效的處理流水線(xiàn)

通過(guò)用于重構高級算法描述的簡(jiǎn)單流程，就可以利用高層次綜合功能生成更高效的處理流水線(xiàn)。

如果您正在努力開(kāi)發(fā)計算內核，而且采用常規內存訪(fǎng)問(wèn)模式，并且循環(huán)迭代間的并行性比較容易提取，這時(shí)，Vivado設計套件高層次綜合(HLS)工具是創(chuàng )建高性能加速器的極好資源。通過(guò)向C語(yǔ)言高級算法描述中添加一些編譯指示，就可以在賽靈思FPGA上快速實(shí)現高吞吐量的處理引擎。結合使用軟件管理的DMA機制，就可以比通用處理器提速數十倍。

然而，實(shí)際應用中經(jīng)常會(huì )遇到難以處理的復雜內存訪(fǎng)問(wèn)問(wèn)題，尤其是當突破科學(xué)計算和信號處理算法領(lǐng)域時(shí)更是如此。我們設計出了一種簡(jiǎn)單方法，可供您在此類(lèi)情況下生成高效的處理流水線(xiàn)。在詳細介紹之前，我們首先了解一下Vivado HLS的工作原理，更重要的是了解它何時(shí)不起作用。

HLS工具如何起作用?

高層次綜合功能試圖獲取由高級語(yǔ)言描述的控制數據流圖 (CDFG)中的并行性。對計算操作和內存訪(fǎng)問(wèn)進(jìn)行分配和調度時(shí)，應根據它們之間的依賴(lài)約束和目標平臺的資源約束來(lái)執行。電路中特定操作的激活與某個(gè)時(shí)鐘周期相關(guān)，同時(shí)，沿數據路徑綜合的中央控制器協(xié)調整個(gè)CDFG的執行。

單純在內核上應用HLS可以建立一條具有眾多指令級并行性的數據路徑。但是當它被激活時(shí)，就需要頻繁停下來(lái)等待數據送入。

由于調度工作是在靜態(tài)下完成的， 因此加速器運行時(shí)間的行為相當簡(jiǎn)單。所生成電路的不同部分相互之間以相同步調運行;并不需要動(dòng)態(tài)的相關(guān)性檢查機制，例如高性能CPU上出現的那種。例如，在圖1(a) 所示的函數中，循環(huán)索引添加和curInd的加載可以并行處理。此外，下次迭代可以在當前迭代完成前開(kāi)始。

同時(shí)，由于浮點(diǎn)乘法通常使用上次迭代的乘法結果

因此可以開(kāi)始新迭代的最短間隔受到浮點(diǎn)乘法器時(shí)延的限制。該函數的執行調度如圖2(a)所示。

該方案何時(shí)達不到理想效果?

這種方案的問(wèn)題在于整個(gè)數據流圖嚴格按調度運行。片外通信產(chǎn)生的拖延會(huì )傳播到整個(gè)處理引擎，從而導致性能大幅下降。當內存訪(fǎng)問(wèn)模式已知，數據能在需要使用之前移動(dòng)到芯片上，或者如果數據集足夠小，則可完全高速緩存在FPGA上，這類(lèi)情況下不會(huì )有問(wèn)題。然而，就很多有趣的算法而言，數據訪(fǎng)問(wèn)取決于計算結果，而且內存占用決定了需要使用片外RAM?，F在，在內核上單純應用HLS可建立一條具有眾多指令級并行性的數據路徑。但是，當它被激活時(shí)，就需要頻繁停下來(lái)等待數據送入。

圖1 – 設計實(shí)例：(a) 包含不規則內存訪(fǎng)問(wèn)模式的函數;(b) 重構得到的流水線(xiàn)結構

圖2 – 不同情形下的執行調度：(a) 當所有數據都在片上高速緩存;

(b) 動(dòng)態(tài)取數據;(c) 解耦運算

圖2(b)給出了針對實(shí)例函數生成的硬件模塊的執行情況，此時(shí)數據集太大，需要動(dòng)態(tài)送入片上高速緩存。注意減速程度如何反映所有高速緩存缺失時(shí)延的綜合影響。不過(guò)，情況并非一定如此，因為計算圖中有些部分的進(jìn)展不需要立即提供內存數據。這些部分應該可以向前移動(dòng)。執行調度中這點(diǎn)額外自由度有可能產(chǎn)生顯著(zhù)影響，就像我們看到的那樣。

重構/解耦實(shí)例

我們看一下剛才的實(shí)例函數。假設浮點(diǎn)乘法的執行和數據訪(fǎng)問(wèn)沒(méi)有全部由統一的安排聯(lián)系在一起。當一個(gè)負載運算符等待數據返回時(shí)，另一個(gè)負載運算符可以開(kāi)始新的內存請求，乘法器的執行也能向前移動(dòng)。為達到此目的，每項內存訪(fǎng)問(wèn)都應該由一個(gè)模塊來(lái)負責，并按各自的調度運行。此外，乘法器單元應該與所有內存操作異步執行。

不同模塊間的數據相關(guān)性

通過(guò)硬件FIFO來(lái)通信。對于我們的實(shí)例而言，可能的重構形式如圖1(b)所示。用于各階段之間通信的硬件隊列可以緩沖已經(jīng)取回但尚未使用的數據。當內存訪(fǎng)問(wèn)部件因高速緩存缺失而出現拖延時(shí)，當前已產(chǎn)生的積壓數據還可以繼續供乘法器單元使用。在經(jīng)歷較長(cháng)時(shí)間后，形成的拖延時(shí)間會(huì )被浮點(diǎn)乘法的長(cháng)時(shí)延掩蓋。

圖2(c)給出了使用解耦處理流水線(xiàn)時(shí)的執行調度。這里，通過(guò)FIFO的時(shí)延沒(méi)有考慮在內，不過(guò)如果迭代量很大，該時(shí)延的影響會(huì )達到最小。

我們如何進(jìn)行重構?

為了給解耦處理模塊生成流水線(xiàn)，首先需要將初始CDFG中的指令進(jìn)行組合以構成子圖。為使所得的實(shí)現方案性能最大化，聚類(lèi)方法必須滿(mǎn)足幾個(gè)要求。

首先，正如我們之前所見(jiàn)，Vivado HLS工具在前面的迭代完成之前使用軟件流水線(xiàn)發(fā)起新的迭代。CDFG中最長(cháng)循環(huán)依賴(lài)的時(shí)延決定可發(fā)起新迭代的最小間隔，最終會(huì )限制加速器所能實(shí)現的總吞吐量。因此，很重要的一點(diǎn)在于這些依賴(lài)循環(huán)不能遍歷多個(gè)子圖，例如用于模塊間通信的FIFO總是會(huì )增加時(shí)延。

其次，應該將內存操作與涉及長(cháng)時(shí)延計算的依賴(lài)循環(huán)分開(kāi)，這樣高速緩存缺失就會(huì )被慢速的數據處理所“掩蓋”。在這里，“長(cháng)時(shí)延”是指操作需要一個(gè)周期以上的時(shí)間才能完成;在這里，我們使用Vivado HLS調度來(lái)獲取這一指標。例如，乘法是長(cháng)時(shí)延操作，而整數加法不是。

最后，為了將高速緩存缺失引起的拖延影響限定在局部范圍內，您需要將每個(gè)子圖中的內存操作數量減至最少，尤其是在需要尋址存儲空間中的不同部分時(shí)更是如此。

第一個(gè)要求——防止依賴(lài)循環(huán)遍歷多個(gè)子圖——很容易滿(mǎn)足，只需要找到原始數據流圖中的強連通分量(SCC)，并在將它們分為不同集群之前將其打開(kāi)變成節點(diǎn)。這樣，我們就得到一個(gè)有向的非循環(huán)圖，其中有些節點(diǎn)是簡(jiǎn)單指令，其它則為一組相關(guān)的操作。

要滿(mǎn)足第二和第三個(gè)要求，即分離內存操作和局部化拖延的影響，我們可以對這些節點(diǎn)進(jìn)行拓撲排序，然后將它們分區。最簡(jiǎn)單的分區方法是在每個(gè)內存操作或長(cháng)時(shí)延SCC節點(diǎn)后畫(huà)一條“邊界”。圖3展示了如何將此方案應用于我們的實(shí)例。集群與圖1中流水線(xiàn)結構之間的對應關(guān)系應該做到顯而易見(jiàn)。每個(gè)子圖都是一個(gè)新的C函數，可獨立通過(guò)HLS推送。這些子圖在執行時(shí)相互間的步調并不一致。

我們構建了一個(gè)簡(jiǎn)單的源到源轉換工具，用以執行重構。

我們使用賽靈思IP核，支持FIFO，以連接所生成的獨立模塊。當然，重構給定計算內核的方法不止一種，而且設計空間探索仍在進(jìn)行中。

流水線(xiàn)化內存訪(fǎng)問(wèn)

有了解耦處理流水線(xiàn)的初步實(shí)施方案后，我們就可以對其執行幾項優(yōu)化，以提高其效率。正如我們所見(jiàn)，當使用HLS映射C函數時(shí)，內存讀取出現阻塞。這個(gè)問(wèn)題也出現在流水線(xiàn)中的個(gè)別階段。例如，負責加載x[curInd]的模塊在等待數據時(shí)可能會(huì )產(chǎn)生拖延，即使在下個(gè)curInd已經(jīng)就緒而且FIFO下游有足夠空間的情況下亦是如此。

為了解決這個(gè)問(wèn)題，我們可以做一下轉變以簡(jiǎn)化內存訪(fǎng)問(wèn)。對于某個(gè)特定階段，我們不在C函數中執行簡(jiǎn)單的內存加載，而是將地址推送到新的FIFO。然后，單獨實(shí)例化一個(gè)新的硬件模塊，以讀取地址FIFO送出的地址，并將它們發(fā)送到內存子系統。返回的數據被直接推送到下游FIFO?，F在，內存訪(fǎng)問(wèn)得到了有效的流水線(xiàn)化。

地址的推送操作可在Vivado HLS中通過(guò)向FIFO接口的內存存儲來(lái)代表，AXI總線(xiàn)協(xié)議允許您指定突發(fā)長(cháng)度;而且，通過(guò)對解耦C函數進(jìn)行一些小的修改，并利用流水線(xiàn)化的內存訪(fǎng)問(wèn)模塊，我們就可利用該功能。

圖3 – 對子圖的重構

圖4 – 背包問(wèn)題

除了生成地址以外，解耦C函數中每個(gè)內存操作符還要在連續存儲塊被訪(fǎng)問(wèn)時(shí)計算突發(fā)長(cháng)度。循環(huán)計數器的復制還有助于突發(fā)訪(fǎng)問(wèn)的生成，因為被訪(fǎng)問(wèn)的字數量可以在每個(gè)解耦函數中本地確定。

不過(guò)，用以監測下游FIFO和發(fā)送內存請求的硬件模塊則采用Verilog實(shí)現。這是因為在由Vivado HLS綜合的內存接口中，外發(fā)地址和響應數據沒(méi)有捆綁在一起。不過(guò)這是一個(gè)簡(jiǎn)單模塊，能在不同基準測試中重用很多次，因此設計工作就被攤銷(xiāo)了。

復制或通信?

在重構內核并生成解耦處理流水線(xiàn)的過(guò)程中，用來(lái)在不同階段移動(dòng)數據的FIFO會(huì )形成很大開(kāi)銷(xiāo)。通過(guò)復制少量計算指令可以去除一些FIFO，這樣通常很有好處，因為即使是最小深度的FIFO也會(huì )占用不少FPGA資源。

一般而言，在權衡利弊以探究最佳設計點(diǎn)的過(guò)程中，您可以使用成本模型和規范的優(yōu)化技術(shù)。但在大多數基準測試中，僅僅為它的每個(gè)用戶(hù)復制簡(jiǎn)單的循環(huán)計數器就可以節省很多面積，這也正是我們所做的。在這個(gè)引導性實(shí)例中， 該優(yōu)化是指復制i的整數加法器，因此存儲結果 i時(shí)不需要從其它模塊獲得索引。

內存的突發(fā)訪(fǎng)問(wèn)

第三項優(yōu)化是內存的突發(fā)訪(fǎng)問(wèn)(burst-memory access)。為了更高效地利用內存帶寬，我們希望通過(guò)一次內存事務(wù)處理攜帶多個(gè)數據字。

實(shí)驗評估

我們應用上述方案做了幾個(gè)案例研究。 為評估這種方法的優(yōu)勢，我們將使用該方案生成的解耦處理流水線(xiàn) (DPP)與單純使用HLS生成的加速器進(jìn)行比較。當為單純或DPP實(shí)現方案調用Vivado HLS時(shí)，我們將目標時(shí)鐘頻率設置到150MHz，并在布局布線(xiàn)后使用所能達到的最高時(shí)鐘速率。此外，我們針對加速器和內存子系統之間的交互嘗試了不同的機制。所用的端口為ACP和HP。我們?yōu)槊總€(gè)端口在可重配置陣列上實(shí)例化一個(gè)64KB高速緩存。

本實(shí)驗所用的物理器件是賽靈思的Zynq®-7000 XC7Z020全可編程SoC，安裝在ZedBoard評估平臺上。

我們還在Zynq SoC 的ARM®處理器上運行應用的軟件版本，并將其性能作為實(shí)驗的基準。生成的所有加速器功能齊全，無(wú)需任何DMA機制將數據移入和移出可重配置架構。

圖5 – 針對背包問(wèn)題的運行時(shí)間比較

案例研究1：

背包問(wèn)題

眾所周知，背包問(wèn)題是一個(gè)組合問(wèn)題，可以通過(guò)動(dòng)態(tài)編程來(lái)求解。內核的結構如圖4所示。其中黑體字的變量都是在運行時(shí)間從

內存讀取。因此，無(wú)法確切知道從哪個(gè)位置加載的變量opt_without。當w和n 比較大時(shí)，我們無(wú)法在片上緩沖整個(gè)opt陣列。我們只能讓計算引擎取回所需的部分。

圖5給出了運行時(shí)間對比情況，將使用我們的方案(DPP)生成的加速器與單純通過(guò)HLS推送函數而生成的加速器進(jìn)行比較。圖中還顯示了在A(yíng)RM處理器上運行函數時(shí)的性能。 我們將n(項數)固定為40，使w (背包的總重量)在100至3,200之間變化。

圖6 – 稀疏矩陣向量乘法

從對比中很容易看出，通過(guò)單純使用Vivado HLS來(lái)映射軟件內核這種方法得到的 ARM處理器性能高出約4.5倍。另外，當使用

加速器性能比基準要求慢很多。 DPP時(shí)，各種內存訪(fǎng)問(wèn)機制之間的Zynq SoC 上的超標量 差別相當小——使用我們的方案時(shí)，無(wú)序式ARM內核能受內存訪(fǎng)問(wèn)時(shí)延的影響要小很多。

圖7 – 針對稀疏矩陣向量乘法的運行時(shí)間對比

很大程度開(kāi)拓指令級并行性，而且具有一個(gè)高性能片上高速緩存。Vivado HLS工具提取的案例研究2：稀疏矩陣向量乘法

附加并行性顯然不足以補償硬處理器內核對于稀疏矩陣向量(SpMV)乘法是一個(gè)可編程邏輯的時(shí)鐘頻率優(yōu)勢計算內核，已經(jīng)在各種研究項目中以很多不同方法進(jìn)行過(guò)研究、變換和基準確定。這里，我們的目的不是以及來(lái)自可重配置陣列的使用特殊數據結構和存儲分配方式更長(cháng)的數據訪(fǎng)問(wèn)時(shí)延。構建最佳性能的SpMV乘法，不過(guò)，當內核被解耦，分成而是想根據最基本的算法描述多個(gè)處理階段時(shí)，看看在使用Vivado HLS時(shí)重構性能就會(huì )明顯比傳遞能提供多少優(yōu)勢。

如圖6所示，在我們的實(shí)驗中，稀疏矩陣以壓縮稀疏行(CSR)格式存儲。在取回數字以進(jìn)行實(shí)際的浮點(diǎn)乘法之前，需要先執行來(lái)自索引數組的負載。用來(lái)決定訪(fǎng)問(wèn)哪個(gè)控制流程和內存位置的數值只有在運行時(shí)間才知道。在圖7所示的運行時(shí)間對比中，矩陣的平均密度為1/16，尺寸在32和2,048之間變化。

此處，單純的映射法在性能上再次落后于軟件版。當不使用FPGA上的高速緩存時(shí)，用我們的方法生成的解耦處理流水線(xiàn)在性能上幾乎與基準性能相同。

當在可重配置陣列上實(shí)例化一個(gè)64KB高速緩存時(shí)，DPP的性能接近基準的兩倍。與之前的基準相比，高速緩存的增加對DPP的性能具有更顯著(zhù)的影響。

案例研究3：FLOYD-WARSHALL 算法

Floyd-Warshall是一種圖形算法，用來(lái)找到任意一對頂點(diǎn)之間成對的最短路徑。內存訪(fǎng)問(wèn)模式比之前的基準要簡(jiǎn)單。因此，有可能存在一種方法可以設計出DMA+加速器結構，以獲得很好的計算重疊和片外通信。我們的方案能試著(zhù)自動(dòng)實(shí)現這種重疊，但是我們尚未進(jìn)行相關(guān)的研究，以表明絕對最佳與實(shí)際所得之間的差距。

不過(guò)，與之前的基準一樣，我也進(jìn)行了運行時(shí)間對比。這里，我們使圖形的大小在40個(gè)節點(diǎn)至160個(gè)節點(diǎn)之間變化。每個(gè)節點(diǎn)平均有全部節點(diǎn)的1/3作為其鄰點(diǎn)。得到的結果與背包問(wèn)題中的十分類(lèi)似。

圖8 –Floyd-Warshall算法

解耦處理流水線(xiàn)所實(shí)現的性能約為軟件基準的3倍，吞吐量達到任何單純映射法的兩倍多。當使用DPP時(shí)，對FPGA高速緩存的影響也很小，展示出了對于內存訪(fǎng)問(wèn)時(shí)延的容限。

我們這種簡(jiǎn)單的技術(shù)構建出的處理流水線(xiàn)可以更好地使用內存帶寬，而且對內存時(shí)延有更好的容限，因此能夠改善Vivado HLS的性能。所描述的方法可對控制數據流圖中的內存訪(fǎng)問(wèn)和較長(cháng)的依賴(lài)循環(huán)解耦，這樣高速緩存缺失就不會(huì )拖延加速器的其它部分。

圖9 – 針對Floyd-Warshall算法的運行時(shí)間比較