引言

可重構系統(tǒng)是指以軟件改變硬件結構以實現(xiàn)具體應用的計算平臺，一般由非柔性但可編程的處理器和柔性的以程序控制重構的數字邏輯器件構成。目前國內外的可重構系統(tǒng)研究中，采用的可重構硬件主要是現(xiàn)場可編程門陣列（Field Programming Gate Array， FPGA）?？芍貥嬒到y(tǒng)非常適合于那些對功耗有嚴格要求或者計算密集的應用，因為此類應用在FPGA上實現(xiàn)的功耗要大大低于在處理器上實現(xiàn)的功耗。將在FPGA上運行的任務視為“硬件任務”納入實時操作系統(tǒng)（Realtime Operating System， RTOS）的統(tǒng)一管理范圍，可簡化系統(tǒng)的設計與管理。因此，需要在傳統(tǒng)的RTOS中引入硬件任務管理器，實現(xiàn)硬件任務的管理和調度。

目前，該研究已經取得了一定進展。如在參考文獻［1］中提出的商用可重構系統(tǒng)OS4RS，包含的主要功能有任務的創(chuàng)建/銷毀、異構任務的動態(tài)遷移、任務之間的相互通信等。支持軟/硬件任務調試以及允許對操作系統(tǒng)模塊和用戶任務的跟蹤監(jiān)控，是可重構硬件操作系統(tǒng)的重要特征。在參考文獻［2］中設計了一種基于軟/硬件統(tǒng)一多任務模型的實時操作系統(tǒng)SHUMμCOS，實現(xiàn)了統(tǒng)一任務的管理、基于靜態(tài)優(yōu)先級的軟/硬件任務獨立調度、硬件資源的管理以及軟/硬件任務基于軟件層的通信等機制。

但是大多數研究者考慮的軟/硬件調度算法一般難以在現(xiàn)有的FPGA硬件平臺上實現(xiàn)，如參考文獻［2］中FORS算法采用的2D FPGA資源模型。這是因為當前的FPGA技術只允許所有的任務占用同樣的“高度”［3］，并且上述工作中幾乎沒有將功耗納入考慮范疇。因此，類似在嵌入式微處理器中廣泛采用動態(tài)電壓調整（Dynamic Voltage Scaling， DVS）技術以降低系統(tǒng)功耗，本文提出了一種動態(tài)調整FPGA工作頻率的算法，在可重構系統(tǒng)的性能需求和功耗需求之間達到平衡，并且可以在當前的FPGA技術條件下實現(xiàn)。

1 調度模型

1.1 可重構系統(tǒng)體系結構

本文只考慮在當前FPGA技術條件下的可重構系統(tǒng)結構，如圖1所示。FPGA分為動態(tài)和靜態(tài)兩部分。動態(tài)部分包括很多可重構模塊（Reconfigurable Modules， RM），每個硬件任務運行在1個RM上，各個RM占用的FPGA寬度可以不相等，一般由若干同列的CLB（Configurable Logic Block，可重構單元）組成。靜態(tài)部分則負責與CPU和RM之間的數據交互。

圖1 可重構系統(tǒng)體系結構

假設FPGA是由很多CLB成陣列排列而成，每1個CLB可以看成1個1×1的單位正方形，1個FPGA則是1個面積為w×h的長方形。其中w為長方形的寬度，h為長方形

圖2 1塊5×4的FPGA

的高度，w×h為該FPGA包含CLB的總數（即面積）。圖2所示為1塊5×4的FPGA。

在實現(xiàn)中，因為每個RM都使用相同的FPGA高度，即h，所以最小的RM的面積是wmin×h，其中，wmin的大小依賴于硬件任務需要使用的CLB的個數。所以，1塊FPGA上RM最多可以有：

當對1塊FPGA進行配置時，其動態(tài)部分可以劃分成具有不同寬度的RM，從而具有不同CLB需求的多個硬件任務可以同時運行在FPGA上。另外，對其中1個RM進行配置時，對于其他正在運行的部分沒有影響，從而可重配置硬件使得硬件任務以一種真正的動態(tài)多任務方式運行。

1.2 任務定義

① 硬件任務：硬件任務是指可重構系統(tǒng)中基于FPGA實現(xiàn)的功能模塊。一個硬件任務配置完成后即可開始執(zhí)行，在完成之前一般不會釋放其占用的可重配置資源，即不能被其他硬件任務搶占。

② 一個硬件任務可表示為Ti（fi，max，wi，ai，ci，ti，ei，fworking）。其中，fi，max是硬件任務可以運行在RM上的最大時鐘頻率，這個頻率是由每個具體硬件任務設計的時序狀況決定的，所以每個任務fi，max可能不同。wi是任務占用的可重構硬件的寬度資源，ai表示硬件任務的到達時間，ci表示硬件任務的最后完成時限，ti是硬件任務工作在fi，max時的運行時間。本文中不單獨考慮硬件任務在FPGA上的配置時間，而是把它并入運行時間中一起考慮。e是硬件任務工作在fi，max時的功耗，可由參考文獻［4］建立的功耗模型進行估算。fworking是該任務在運行時FPGA的實際頻率。

硬件任務的功耗和硬件的運行頻率直接相關，因此，可以使用以下2個公式對硬件任務實際的運行時間和功耗進行估算：

其中，f是硬件任務實際的運行頻率。

2 功耗相關硬件任務調度算法EEHTS

2.1 硬件任務調度器設計

目標系統(tǒng)如圖3所示。用戶程序分為2部分，其中軟件任務運行在CPU上，硬件任務運行在FPGA上。本文中只考慮功耗相關的硬件任務的調度，目標是將軟/硬件任務統(tǒng)一起來進行考慮，在滿足任務截止時限要求的情況下降低系統(tǒng)的整體功耗，即：

圖3 硬件任務調度器

2.2 調度原則和放置原則

在嵌入式系統(tǒng)中，任務的正確性不但依賴于其功能正確性，而且依賴于其執(zhí)行的及時性，所以確保任務不錯過截止期是最重要的調度依據。在滿足任務截止時間的前提下，1個新到達的硬件任務Ti的最遲開始執(zhí)行時間（Last Starting time， LST）為LST（Ti）=ci-ti，如果Ti在放置時沒有找到合適的位置，調度器并不立刻拒絕Ti，因為只要在LST（Ti）之前有滿足Ti需求的資源被釋放，那么Ti仍然可以滿足其截止期要求。在EEHTS算法中，需要維護到達任務列表Alist，Alist中保存所有已經到達且未能成功分配的任務。已到達列表的任務按照任務的LST增序排列，即按照最早最遲開始時間優(yōu)先（Earliest Last Starting time First ， ELST）的原則進行調度。

硬件任務調度器的核心是進行定位分配，即根據硬件任務占用FPGA資源大小在FPGA上尋找合適的位置對FPGA進行配置，如參考文獻［5］中提出的MER算法。但是此類算法采用的FPGA面積模型都是2D資源模型，并不能在當前的FPGA技術條件下實現(xiàn)，所以本文采用類似傳統(tǒng)操作系統(tǒng)管理存儲器資源的方法，即首次適配（FirstFit）［6］算法。在EEHTS算法中，需要維護空白資源列表B，B中保存了所有當前未被使用的FPGA上的空白區(qū)域。放置成功的硬件任務即可開始配置運行，因此在EEHTS算法中需要維護正在運行的任務列表Elist。執(zhí)行列表Elist中包含所有正在運行的硬件任務Ti，任務按照執(zhí)行完畢時間的增序排列。

在硬件任務完成之前，不能被其他任務搶占；當硬件任務完成之后，即可釋放其占用的FPGA資源，并將執(zhí)行完畢的任務插入到執(zhí)行完畢任務列表Flist中。這個特點是硬件任務和軟件任務的顯著區(qū)別。

2.3 功耗相關硬件任務調度算法EEHTS

（1） 算法1：EEHTS算法

1： for Ti∈Alist do

2： if （ FirstFit （Ti，B） ） then

3：Place Ti on FPGA

4：Elist=Elist+Ti

5：Alist=Alist-Ti

6： fe=SelectWorkingFrequency（Elist，F(xiàn)）

7：if （fe

8：fworking=fe

9：endif

10：start Ti at fworking

11：return ACCEPT

12：elseif LST（Ti）》=t

13：return REJECT

14：else

15：return NULL

16：end if

在任何時刻t，EEHTS算法首先檢查Alist隊列中的第1個任務Ti，函數有3種可能的返回結果：ACCEPT、REJECT和NULL。第2行中如果FPGA空白區(qū)域列表B中有合適的位置放置任務Ti，那么將Ti加入到Elist中，然后第6行重新計算1個更加優(yōu)化的FPGA頻率fe，如果fe小于當前FPGA運行的頻率fworking，并且在fe下所有Elist中任務均能在其截止期內完成，那么說明可以在保證任務截止期的條件下通過降低頻率而降低硬件任務的整體功耗，所以此時算法返回ACCEPT；第13行如果任務即將或者已經錯過最遲開始時間，那么此時函數返回REJECT，表示此任務被拒絕；第15行如果當前時刻沒有合適的位置，但是任務仍沒有到其最遲開始時間，表示在將來的時刻仍然可能獲得任務所需資源，所以函數返回結果NULL。

算法1中第6行重新計算FPGA工作頻率的算法如算法2所示，其中F是所有硬件任務工作頻率值的集合。需要說明的是，同一時刻在FPGA運行的硬件任務的工作頻率值必須相同，并且選擇5作為FPGA頻率的增量也是符合實際FPGA技術情況的。

（2） 算法2：選擇最優(yōu)的頻率值作為FPGA的運行頻率

步驟1： fscheduled，max=min（fi，min|Ti∈Elist）

步驟2： 對于F集合中的滿足fmin≤f≤fscheduled，max的每個f值，計算：

選取使得計算步驟2中結果最小的f值作為FPGA的運行頻率值，從而使得FPGA的總體功耗最低。

3 模擬實驗及分析

由于當前并沒有一個統(tǒng)一的基準用于評價可重構系統(tǒng)功耗相關的調度算法，因此采取了類似參考文獻［2］中的模擬實驗模型設計了離散時鐘的模擬器，模仿實時系統(tǒng)中的時鐘滴答以進行任務截止期的檢查。然后設計隨機任務生成器，生成分別含有1 000、2 000、3 000、4 000、5 000、6 000個Ti（fi，max，wi，ai，ci，ti，ei，fworking）的任務集，硬件任務的寬度和執(zhí)行時間也是隨機生成的。

假定目標器件為 Xilinx Virtex XCV1000，共 96列×64 行，其中可用于配置硬件任務的動態(tài)部分是80 列，其他用于操作系統(tǒng)進行通信和 I/O。模擬實驗中采用的參數如下： 任務的最小寬度wmin=1，Nmax=80，任務的寬度范圍wi為1~80；fmin=20 MHz，fmax=100 MHz，所以各個任務的可運行的最大頻率fi，max∈［20，25，…，1 000］；

任務在fi，max頻率時的運行時間ti范圍為100~1 000 ms。ei范圍為20~200 mJ，ei的大小和任務寬度相關。到達時間范圍0.5~500 ms，模擬器的時鐘滴答設置為500 μs。分別模擬了采用ELST算法和EEHTS算法的任務集的總體運行時間和整體功耗，如圖4和圖5所示。從圖4中可以看到，采用ELST算法的任務運行時間曲線要比采用EEHTS算法的低，這是因為只采用ELST算法時并不改變FPGA的運行頻率，F(xiàn)PGA始終使用最高頻率運行，顯然這種方法的功耗會大于EEHTS算法，實驗結果也證明了這點。如圖5所示，EEHTS算法雖然犧牲了一些時間性能，但是硬件任務仍然可以在其截止期內完成，并且相對于ELST算法，硬件任務功耗大約降低了32%。

圖4 總體運行時間

圖5 總體任務功耗

結語

在嵌入式系統(tǒng)中，低功耗是非常重要的目標。本文通過對可重構系統(tǒng)中硬件任務調度算法的研究，在對硬件任務調度時加入了對功耗的考慮，動態(tài)改變硬件任務運行的頻率，從而降低系統(tǒng)整體功耗。