時(shí)間約束下FPGA 資源最小化的動(dòng)態(tài)重構(gòu)?

安 洋 趙 蒙

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

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

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

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

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

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

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

1 問題構(gòu)建

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

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

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

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

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

2 劃分策略

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

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

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

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

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

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

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

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

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

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

因此，最小運(yùn)算時(shí)間周期tmax為:

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

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

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

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

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

由式(9)給出的n值是一個(gè)粗略值(最壞的情況)，因?yàn)榭紤]每個(gè)分區(qū)中存在最慢的算子。

2.2 劃分算法

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

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

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

2.3 劃分后的改進(jìn)

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

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

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

3.1 算法思想

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

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

圖3 圖像邊緣檢測(cè)器的總的原理圖

3.2 DFG 注釋

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

表1 AT40K 系列常用算子特征

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

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

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

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

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

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

表4 圖像邊緣檢測(cè)器的資源估計(jì)

3.3 實(shí)施結(jié)果

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

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

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

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

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

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

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

4 結(jié)束語

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

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