時間約束下FPGA 資源最小化的動態重構?

安 洋 趙 蒙

(1.焦作師范高等專科學校理工學院，河南 焦作 454002；2.蘇州科技大學 物理科學與技術學院 江蘇 蘇州 215009)

動態可重構計算包括在同一設備上連續執行一系列算法，其目標是在相同的硬件結構上交換不同的算法，方法是在有限的時間內采用規定的劃分和調度，在硬件中多次重新配置現場可編程門陣列(Field Programmable Gate Array，FPGA)[1－3]。對于實時處理，國內外學者已經提出了一些體系結構設計，并驗證了動態可重構計算的概念[4－8]。文獻[4]提出了一種支持需求驅動的指令集修改的動態指令集計算機(Dynamic Instruction Set Computer，DISC)，采用部分可重構的FPGA 實現，通過將指令模塊物理地重新定位到可用的FPGA 空間，從而進一步提高了FPGA 的功能密度；文獻[5]描述了FPGA 體系結構及如何解決FPGA 體系結構中存在的邏輯粒度、配置時間、前向兼容性、硬約束和編譯時間等問題，并與傳統的數字信號處理器、微控制器或通用處理器相結合，實現支持系統的各種計算需求，而不需要定制硬件；文獻[6]提出了一種在不影響FPGA動態部分重構性能的情況下，提高FPGA 動態部分重構安全性的解決方案。所提出的解決方案在目標FPGA 上引入了1% 的可用資源開銷，實現了2.5 Gbyte/s的重配置吞吐量；文獻[7]針對動態可重構系統中相互耦合的劃分、調度和布局問題進行了研究，建立了調度和布局的問題模型，提出了相應的優化算法。為了表示動態可重構系統中的任務調度和布局，提出了三元序列組(Triple Sequence)的表示方法。通過求解混合嵌套序列對的最長公共子序列，能夠計算出任務位置坐標。將重構序列和任務數據依賴關系相結合，可以構建重構約束圖(Reconfigurable Constraints Graph，RCG)來表示動態重構過程中任務的優先約束關系。通過求解重構約束圖中到頂點的最長路徑，能夠計算出任務配置時刻和執行時刻。在動態可重構過程中，任務調度和布局必須滿足硬件資源約束和任務數據依賴關系。并給出了可行任務調度和布局的充要條件和可以確立三元序列組完整的可行解空間；文獻[8]研究了基于多FPGA 部件的可重構系統高能耗問題。對多FPGA部件可重構系統的特征，包括重構端口受限、資源受限及通信開銷等進行了建模，并基于概率論與統計學的離散方差理論，采用負載均衡思想設計和實現了一種低能耗調度算法。結果表明提出的算法復雜度低、運行速度快，不僅節約能量，而且還縮短了最大完成時間；然而，對于運行時間重構(Runtime Reconfiguration，RTR)算法的最優化分解機制仍然有許多需要解決的問題。事實上分析這一領域的研究可以發現，它們僅局限于應用開發方法。我們還注意到:首先，這些方法不能得到最小的空間資源；其次，好的時間分割/劃分可以避免所需資源過大[9－10]。

在實現可重構硬件算法的任務中，可以分為2 種方法，如圖1 所示。最常見的是應用開發方法，另一種是所謂的系統設計方法。在第一種情形下，必須在現有的由連接到可重構邏輯陣列的主CPU 實現的系統中選擇一種具有可選時間約束的算法，這時，最優化實現的目標是使得下列一個或多個指標最小化:處理時間、存儲帶寬和重新配置的數量；而在第二種情況下，必須在仍處于設計探索階段的系統上實現一個具有要求時間約束的算法，設計參數是用于實現算法的數據路徑部分的邏輯陣列的大小。這時，最優化實現的目標是得到可重構陣列的最小面積。

圖1 用于在可重構硬件上實現算法的2 種方法

嵌入式系統可以利用FPGA 的優勢，最明顯的就是頻繁更新數字硬件功能。但是，也可以采用動態資源分配來實例化僅有嚴格時間要求的每個算子(也稱運算符)，這可以通過減少可重構陣列的面積來提高核的效率[11]。

關于RTR 體系結構的時間劃分(也稱分區或分割)和綜合已提出了一些有益的探索[12－16]。這些提出的方法都假設存在資源約束。文獻[12]的目標是通過采用數據路徑合成工具門陣列編程(Gate ARrays Program，GAMA)[13]和GARP 可重構處理器在C 程序中實現循環的硬件加速；文獻[14－15]專為多FPGA 可重構計算架構上的應用開發而設計了一款CAD 工具套件，其中采用的主要成本函數是數據存儲帶寬；在文獻[16]中，作者提出了一種模型和一種方法來利用連續分區中的公共算子，提出的簡單模型用于指定、可視化和開發設計，其中包含可以在運行時可重新配置的元素。這種方法可以減少配置時間和應用執行時間，但是需要額外的邏輯資源來完成這種方法。此外，這種模型不包括滿足實時性的時序要求，也沒有明確實現的分區。

上述研究的目標或者是資源約束，或者是單一的配置時間和應用執行時間約束。實際上，RTR 的劃分問題是可重構計算系統中最重要的問題。對此，本文在可重構體系結構設計流程中采用RTR 算法，以使得實現時間約束條件下所需的FPGA 資源最小化，即實現雙重任務。

1 問題構建

運行時間重構實時應用的劃分可以歸類為一個時空問題，因此，必須在時間上對算法進行劃分，并在空間上確定每個分區，相比于運行時間重新配置的調度，它是采用動態資源分配的一個時間約束問題。對實時應用作以下假設。首先，算法可以建模為一個無環數據流圖(Data-Flow Graph，DFG)，表示為G(V，E)，其中頂點集V＝{O1，O2，…，Om}對應于算術算子和邏輯算子，有向邊集E＝{e1，e2，…，ep}表示運算之間的數據依賴關系；其次，對應用設置一個約束時間T，需要解決的問題如下。

對于一個給定的FPGA 系列，必須尋找G的子圖集{P1，P2，…，Pn}，使得:

該式允許通過滿足時間約束T和通過E建模的數據依賴關系來執行算法，而且需要的FPGA 單元數量最少。所采用的FPGA 單元數量是陣列面積(也稱區域)的一個近似值，由式(2)給出:

式中:Pi是n個分區中的一個。一個分區Pi所需的FPGA 資源由式(3)給出:

式中:Mi是分區Pi中的基本算子的數量，Area(Ok)是算子Ok所需的資源數量。

2 劃分策略

劃分策略的總的流程圖如圖2 所示，它由3 個主要模塊構成。首先，計算出分區(圖2 中的模塊A、B、C、D)數量的一個近似值，然后得出分區界限(模塊E)，最后，在可能的情況下，細化最后的分區(模塊E、F)。

圖2 分區方法的原理流程圖

2.1 分區數量和分區大小

為了減少搜索區域，首先估計可以得到的最小分區數量和在分區中允許的資源數量。為此，使用一個與目標相關的算子庫，這個庫可以將兩個屬性關聯到圖G的每個頂點，這兩個屬性分別是ti和Area(Oi)，即最大路徑延遲和算子Oi需要的基本FPGA 單元的數量，這兩個量是要處理的數據大小(位數)的函數。如果知道要處理的原始數據的大小，就很容易通過對輸入數據的最大值的圖的“軟件執行”來得到每個節點的大小。

此外，還作如下假設。

(1)要處理的數據被分組為N個數據的塊；

(2)應用于一個塊中的每個數據的運算/操作數量是確定的(即不依賴于數據)；

(3)在圖的全部節點之間采用管道寄存器；

(4)考慮重構時間由rt(·)給定，它是所采用的FPGA 技術的函數；

(5)忽略讀寫計數器(指針)和小關聯狀態機(控制器部分)所需的資源，在本文的應用中，這相當于一個靜態部分，實現時將在所需資源總量中考慮到這部分(見第4 節)。

因此，最小運算時間周期tmax為:

而應用所使用的單元總數C為:

式中:{1，…，m}為數據路徑G的全部算子的集合。由此得到了由式(6)給出的最小分區數n和由式(7)給出的相應的每個分區的最佳大小Cn(單元數)為:

式中:T是約束時間(單位為s)，N是一個數據塊中的數據字數，σ是整個數據路徑的總延遲周期數，tmax是DFG 中最慢算子的傳播延遲(單位為s)，且它對應于圖G的兩個連續頂點之間的最大時間(由于是一個完整的流水線過程)，rt()是重構時間。在部分可重構FPGA 技術的情況下，rt()可以用下載的功能單元面積的線性函數來近似。rt()的表達式如下:

式中:V是FPGA 的配置速度(單元/s)，C是執行整個DFG 所需的單元數量。考慮每個重新配置都覆蓋了以前的分區(即配置的單元數量等于最大分區大小)，這就保證了先前的配置不會干擾當前的配置；在完全可重構FPGA 技術的情況下，rt()函數是一個依賴于FPGA 大小的常數。這時，rt()是一個按步長增加的離散線性函數，對應于不同大小的FPGA。式(6)的分子是總的允許處理時間(約束時間)，分母的第一項是一個數據塊(包含N個數據)的有效處理時間，第二項是加載n個配置所釋放的時間(G的總重新配置時間)。

在大多數應用領域如圖像處理中，相比于處理時間，可以忽略管道延遲時間的影響(N?σ)，因此，在部分可重構FPGA 技術的情況下，可以將式(6)近似為式(9)(對應于圖2 中的模塊D):

由式(9)給出的n值是一個粗略值(最壞的情況)，因為考慮每個分區中存在最慢的算子。

2.2 劃分算法

本文提出的劃分算法實現的偽代碼如下:

算法中采用了一個First＿Leave()函數，它以DFG 作為參數并返回終端節點。通過累加覆蓋節點的大小來覆蓋從葉子到根的圖，直到總和盡可能接近Cn為止。這些覆蓋的頂點形成第一個分區，然后從圖中刪除相應的節點，并反復覆蓋，直到剩下的圖為空，然后完成劃分。

在First＿Leave()函數的執行過程中有很大的自由度，因為DFG 中通常有很多葉子，唯一的強約束是必須作出選擇，以確保整個分區的數據依賴性。DFG 的葉子的讀出可以是隨機的或有序的，在本文的情形下，它是有序的。把G視為一個包含與DFG算子相關的參數的二維表。First＿Leave()是按表的讀取順序執行的，其中包含DFG(從左到右)的算子參數。First＿Leave()函數的第一個目標是創建盡可能均勻的劃分，此時，First＿Leave()并不關心存儲帶寬。

2.3 劃分后的改進

在對2.2 劃分階段得到的每個分區進行放置和尋由之后，就可以計算精確的處理時間。還可能要考慮到每個分區的合成頻率接近最大處理頻率的值。

分析總的處理時間(配置和執行)與約束許可時間之間的差，就可以對分區作出判決。如果有必要減少分區數量或可能增加分區數量，就返回到2.2節中所描述的步驟，并為n提供一個新的值，否則，分區將被視為最佳分區(見圖2)。

3 劃分策略的應用—圖像處理

3.1 算法思想

本節用一個圖像處理算法來舉例說明本文提出的劃分策略，這是驗證本文劃分策略的一個很好的選擇，因為圖像處理數據是按塊自然組織的，有許多低層的處理算法可以用DFG 建模，而且約束時間通常是圖像采集周期。假設圖像以25 次/s 的速率拍攝，空間分辨率為512×512 像素，每個像素灰度級為8 位值，這樣，就有40 ms 的約束時間。

圖像處理采用的算法是一個3×3 的中值濾波器，后面接的是一個邊緣檢測器，圖3 給出了邊緣檢測器總的原理圖。在這個例子中，考慮一個可分離中值濾波器和一個Sobel 算子[17]。中值濾波器提供3 個垂直連續水平中值的中值。每個水平中值只是一條直線中3 個連續像素的中間值。該濾波器可以在保持邊緣質量的同時消除脈沖噪聲。其實現原理是對3×3 鄰域中的像素根據它們的灰度級值進行排序，然后僅使用中間值(在9 個值的第5 個位置上的值)；算子由8 位比較器和多路復用器構成。梯度計算是通過Sobel 算子實現的，這對應于兩個一維濾波器連續應用的圖像卷積，這些濾波器分別是垂直和水平Sobel 算子。中心像素的最終梯度值是垂直和水平梯度的最大絕對值，線路延遲由FPGA的外部組件造成的(見圖3)。

圖3 圖像邊緣檢測器的總的原理圖

3.2 DFG 注釋

本例中使用的FPGA 系列是Atmel AT40K 系列，這些FPGA 的配置速度約為1 365 個單元/ms，并具有部分重新配置模式。通過對Atmel AT40K 系列數據表[18]的分析，可以得到某些算子類型的特征，如表1 所示。在表1 中，Tcell是一個單元的傳播延遲，Trouting是算子內的路由延遲，Tsetup是觸發器設置時間。根據文獻[18]給出的數據表特征，得到對常用初等算子的執行時間的第一次估計，如表2 所示。

表1 AT40K 系列常用算子特征

表2 采用AT40K 技術的一些8 位算子的估計執行時間

在實際應用中，估計執行時間與實際執行時間之間存在線性關系，它將兩個連續節點之間所需的尋由時間結合起來，圖4 所示為一些已在寄存器之間的FPGA 陣列中分別實現的不同常用低層算子的估計執行時間與實際執行時間的關系。當這些算子在嚴格的級聯中很好地對齊時，這種線性特性會保持得很好。但這種關系對于在FPGA 中的已經硬連接的專門功能是無效的(如RAM 塊、乘法器等)。基于圖4，可以得到包含在數據路徑中的算子的執行時間的近似值。由于算法是規則的如數據路徑(嚴格的算子級聯)，所以結果更加精確。

圖4 AT40K 技術中一些算子的估計時間和實際執行時間的關系

通過這些估計值，并考慮到處理導致的數據大小的增加，就可以對DFG 進行注釋，然后就可以得到全部算子的數量和特征，表3 給出了關于算法示例的數據。在表3 中，執行時間是對實際執行時間的估計。基于這些數據，就得到以最優化方式實現專用數據路徑所需的分區數。從表3 和表4 可見，對于邊緣檢測器來說，在數據路徑的全部算子內，最慢的算子是一個8 位比較器，而且必須重新配置467 個單元。因此，根據式(9)(模塊D 的結果)，可以得到n的值為3，實現全局數據路徑的每個分區(Cn)大小應大約為156 個單元，表4 總結了算法的RTR 實現的估計。通過應用節2 中描述的方法，得到圖5 表示的第一個分區(模塊E 的結果)。

圖5 用于實現圖像邊緣檢測器DFG 的分區

表3 邊緣檢測器的算子數量和特征(AT40K)

表4 圖像邊緣檢測器的資源估計

3.3 實施結果

為了說明本文的劃分方法，我們在Ardoise 體系結構[6]上測試了本文提出的劃分策略，該平臺由AT40K FPGA 和2 個1 MB 的SRAM 存儲器堆構成。盡管本文提出的劃分策略并不是針對資源約束這類體系結構的，但根據所使用的資源和工作頻率得到的結果對于任何類似于AT40K 的陣列仍然適用。所需要的特性是小的邏輯單元間隔尺寸、每個單元中有一個觸發器，以及部分配置的可能性。表5 所示為邊緣檢測算法(模塊F 的結果)的實施結果。從表5 可見，三個步驟中的動態執行是可以實時實現的，這與估計值(見表4)是一致的。

表5 AT40K 邊緣檢測器的實施結果

可以看到，第四個分區是不可行的(模塊E 和F的第二次迭代是不可能的，見圖2)，因為允許的最大算子執行時間小于34 ns。事實上，如果分析剩余的時間，會發現一個追加的分區不允許實現實時處理。通過劃分的最大單元數量允許確定由運行時間重新配置執行所得到的功能密度增益因子[11]。在本例中，采用功能密度的增益因子與實時處理的該數據路徑(靜態實現)的全局實現相比大約為3。這個增益的獲得沒有考慮控制器部分(靜態部分)。

顯然，最好的解決方案是找到每一步中使用相同的單元數量。但在實際應用中，必須考慮到存儲帶寬瓶頸，這就是為什么最實用的劃分需要保持數據的吞吐量與所使用的存儲器的性能一致。

通常，如果有足夠的存儲帶寬，可以采用以下方式來估算控制部分的成本。存儲資源必須能夠存儲2 個圖像(假設是一個不變流量處理)，存儲大小為256 kbyte，控制器需要2 個計數器來尋址存儲器，一個是控制RTR 的狀態機，一個用于讀寫訪問的存儲器管理。在本文的示例中，控制器由2 個18 位計數器(N＝5122像素)、1 個有5 個狀態的狀態機、1 個捕獲分區數量的4 位寄存器(假設重構數量小于16)、1 個指示分區數量的計數器、1 個4 位比較器和1 個非操作符(以指示必須讀寫哪些備用緩沖內存)構成。采用有針對性的FPGA 結構，在每個配置階段的控制器邏輯區域需要49 個邏輯單元的資源數量。如果將控制器區域添加到本文示例所需的資源中，我們將得到209 個單元的計算區域，存儲帶寬為19 位。

3.4 與一般體系結構綜合法的定性比較

將本文提出的策略與一般體系結構綜合法相比較，后者是通過加強對算子控制的重用。盡管兩種策略的目標都是硬件資源的最小化，但在應用體系結構綜合法時，必須針對最大的數據對算子進行量化，即使一個算子不頻繁使用，在整個處理期間也必須存在(從而消耗資源)；對于運行時間可重構體系結構，這些缺點不再存在，從而使得邏輯資源增加；此外，與全空間數據路徑相比，資源重用可能導致路由延遲增加，從而降低全局架構效率，而利用FPGA的動態資源分配特性，僅在每個時刻(時間局部性)實例化所需算子，并確保算子的相對位置對于當前處理(功能性局部性)是最優的。

4 結束語

本文提出了一種采用動態可重構特征的DFG的時間劃分以使FPGA 的陣列大小最小化的劃分策略，以在最小面積上的最大允許頻率處理和滿足實時約束來提高核的效率。除其他步驟外，采用目標FPGA 的特征化(速度和面積)算子庫來估計可能的分區數量。通過在一個圖像處理算法上的應用和在Ardoise 體系結構上的實際實施，說明了方法的有效性。

對于未來的研究，將致力于更精確的資源估計，考慮數據路徑的存儲管理部分，并嘗試調整First＿Leave()函數來包含存儲帶寬，實現分區搜索過程的自動化。