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

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

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

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

HLS工具如何起作用?

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

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

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

同時，由于浮點乘法通常使用上次迭代的乘法結(jié)果

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

該方案何時達不到理想效果?

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

圖1 – 設(shè)計實例：(a) 包含不規(guī)則內(nèi)存訪問模式的函數(shù);(b) 重構(gòu)得到的流水線結(jié)構(gòu)

圖2 – 不同情形下的執(zhí)行調(diào)度：(a) 當(dāng)所有數(shù)據(jù)都在片上高速緩存;

(b) 動態(tài)取數(shù)據(jù);(c) 解耦運算

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

重構(gòu)/解耦實例

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

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

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

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

我們?nèi)绾芜M行重構(gòu)?

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

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

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

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

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

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

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

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

流水線化內(nèi)存訪問

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

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

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

圖3 – 對子圖的重構(gòu)

圖4 – 背包問題

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

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

復(fù)制或通信?

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

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

內(nèi)存的突發(fā)訪問

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

實驗評估

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

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

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

圖5 – 針對背包問題的運行時間比較

案例研究1：

背包問題

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

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

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

圖6 – 稀疏矩陣向量乘法

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

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

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

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

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

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

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

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

案例研究3：FLOYD-WARSHALL 算法

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

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

圖8 –Floyd-Warshall算法

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

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

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