安 洋 趙 蒙

(1.焦作師范高等?？茖W(xué)校理工學(xué)院，河南 焦作 454002；2.蘇州科技大學(xué) 物理科學(xué)與技術(shù)學(xué)院 江蘇 蘇州 215009)

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

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

圖1 用于在可重構(gòu)硬件上實現(xiàn)算法的2 種方法

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

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

上述研究的目標(biāo)或者是資源約束，或者是單一的配置時間和應(yīng)用執(zhí)行時間約束。實際上，RTR 的劃分問題是可重構(gòu)計算系統(tǒng)中最重要的問題。對此，本文在可重構(gòu)體系結(jié)構(gòu)設(shè)計流程中采用RTR 算法，以使得實現(xiàn)時間約束條件下所需的FPGA 資源最小化，即實現(xiàn)雙重任務(wù)。

1 問題構(gòu)建

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

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

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

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

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

2 劃分策略

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

圖2 分區(qū)方法的原理流程圖

2.1 分區(qū)數(shù)量和分區(qū)大小

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

此外，還作如下假設(shè)。

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

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

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

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

(5)忽略讀寫計數(shù)器(指針)和小關(guān)聯(lián)狀態(tài)機(控制器部分)所需的資源，在本文的應(yīng)用中，這相當(dāng)于一個靜態(tài)部分，實現(xiàn)時將在所需資源總量中考慮到這部分(見第4 節(jié))。

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

而應(yīng)用所使用的單元總數(shù)C為:

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

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

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

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

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

2.2 劃分算法

本文提出的劃分算法實現(xiàn)的偽代碼如下:

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

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

2.3 劃分后的改進

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

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

3 劃分策略的應(yīng)用—圖像處理

3.1 算法思想

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

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

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

3.2 DFG 注釋

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

表1 AT40K 系列常用算子特征

表2 采用AT40K 技術(shù)的一些8 位算子的估計執(zhí)行時間

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

圖4 AT40K 技術(shù)中一些算子的估計時間和實際執(zhí)行時間的關(guān)系

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

圖5 用于實現(xiàn)圖像邊緣檢測器DFG 的分區(qū)

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

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

3.3 實施結(jié)果

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

表5 AT40K 邊緣檢測器的實施結(jié)果

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

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

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

3.4 與一般體系結(jié)構(gòu)綜合法的定性比較

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

4 結(jié)束語

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

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