可重構(gòu)系統(tǒng)功耗相關(guān)的硬件任務(wù)調(diào)度算法

1、    可重構(gòu)系統(tǒng)功耗相關(guān)的硬件任務(wù)調(diào)度算法引言可重構(gòu)系統(tǒng)是指以軟件改變硬件結(jié)構(gòu)以實現(xiàn)具體應(yīng)用的計算平臺，一般由非柔性但可編程的處理器和柔性的以程序控制重構(gòu)的數(shù)字邏輯器件構(gòu)成。目前國內(nèi)外的可重構(gòu)系統(tǒng)研究中，采用的可重構(gòu)硬件主要是現(xiàn)場可編程門陣列(FieldProgrammingGateArray，F(xiàn)PGA)。可重構(gòu)系統(tǒng)非常適合于那些對功耗有嚴(yán)格要求或者計算密集的應(yīng)用，因為此類應(yīng)用在FPGA上實現(xiàn)的功耗要大大低于在處理器上實現(xiàn)的功耗。將在FPGA上運行的任務(wù)視為“硬件任務(wù)”納入實引 言    可重構(gòu)系統(tǒng)是指以軟件改變硬件結(jié)構(gòu)以

2、實現(xiàn)具體應(yīng)用的計算平臺，一般由非柔性但可編程的處理器和柔性的以程序控制重構(gòu)的數(shù)字邏輯器件構(gòu)成。目前國內(nèi)外的可重構(gòu)系統(tǒng)研究中，采用的可重構(gòu)硬件主要是現(xiàn)場可編程門陣列(Field Programming Gate Array，F(xiàn)PGA)?？芍貥?gòu)系統(tǒng)非常適合于那些對功耗有嚴(yán)格要求或者計算密集的應(yīng)用，因為此類應(yīng)用在FPGA上實現(xiàn)的功耗要大大低于在處理器上實現(xiàn)的功耗。將在FPGA上運行的任務(wù)視為“硬件任務(wù)”納入實時操作系統(tǒng)(Real-time Operating Sys-tem，RTOS)的統(tǒng)一管理范圍，可簡化系統(tǒng)的設(shè)計與管理。因此，需要在傳統(tǒng)的RTOS中引入硬件任務(wù)管理器，實現(xiàn)硬件任務(wù)的管理和調(diào)度。&

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

4、中FORS算法采用的2D FPGA資源模型。這是因為當(dāng)前的FPGA技術(shù)只允許所有的任務(wù)占用同樣的“高度”，并且上述工作中幾乎沒有將功耗納入考慮范疇。因此，類似在嵌入式微處理器中廣泛采用動態(tài)電壓調(diào)整(DynamicVoltage Scaling，DVS)技術(shù)以降低系統(tǒng)功耗，本文提出了一種動態(tài)調(diào)整FPGA工作頻率的算法，在可重構(gòu)系統(tǒng)的性能需求和功耗需求之間達到平衡，并且可以在當(dāng)前的FPGA技術(shù)條件下實現(xiàn)。1 調(diào)度模型11 可重構(gòu)系統(tǒng)體系結(jié)構(gòu)    本文只考慮在當(dāng)前FPGA技術(shù)條件下的可重構(gòu)系統(tǒng)結(jié)構(gòu)，如圖1所示。FPGA分為動態(tài)和靜態(tài)兩部分。動態(tài)部分包括很多可重構(gòu)模塊(

5、Reconfigurable Modules，RM)，每個硬件任務(wù)運行在1個RM上，各個RM占用的FPGA寬度可以不相等，一般由若干同列的CLB(Config-urabIe Logic Block，可重構(gòu)單元)組成。靜態(tài)部分則負(fù)責(zé)與CPU和RM之間的數(shù)據(jù)交互。    假設(shè)FPGA是由很多CLB成陣列排列而成，每1個CLB可以看成1個1×1的單位正方形，1個FPGA則是1個面積為×h的長方形。其中為長方形的寬度，h為長方形的高度，×h為該FPGA包含CLB的總數(shù)(即面積)。圖2所示為1塊5×4的FPGA。在實現(xiàn)中，因為每個RM

6、都使用相同的FPGA高度，即h，所以最小的RM的面積是mm×h，其中，min的大小依賴于硬件任務(wù)需要使用的CLB的個數(shù)。所以，1塊FPGA上RM最多可以有：       當(dāng)對1塊FPGA進行配置時，其動態(tài)部分可以劃分成具有不同寬度的RM，從而具有不同CLB需求的多個硬件任務(wù)可以同時運行在FPGA上。另外，對其中1個RM進行配置時，對于其他正在運行的部分沒有影響，從而可重配置硬件使得硬件任務(wù)以一種真正的動態(tài)多任務(wù)方式運行。12 任務(wù)定義    硬件任務(wù)：硬件任務(wù)是指可重構(gòu)系統(tǒng)中基于FPGA實現(xiàn)的功

7、能模塊。一個硬件任務(wù)配置完成后即可開始執(zhí)行，在完成之前一般不會釋放其占用的可重配置資源，即不能被其他硬件任務(wù)搶占。    一個硬件任務(wù)可表示為Ti(fi，max，ai,ci,ti,ei，fworking)。其中，fi,max是硬件任務(wù)可以運行在RM上的最大時鐘頻率，這個頻率是由每個具體硬件任務(wù)設(shè)計的時序狀況決定的，所以每個任務(wù)的fi,max可能不同。i是任務(wù)占用的可重構(gòu)硬件的寬度資源，ai表示硬件任務(wù)的到達時間,ci表示硬件任務(wù)的最后完成時限，ti是硬件任務(wù)工作在fi,max時的運行時間。本文中不單獨考慮硬件任務(wù)在FPGA上的配置時間，而是把它并入運行時間中一起考

8、慮。e是硬件任務(wù)工作在fi,max時的功耗，可由參考文獻4建立的功耗模型進行估算。fworking是該任務(wù)在運行時FPGA的實際頻率。    在參考文獻4中，硬件任務(wù)的功耗和硬件的運行頻率直接相關(guān)，因此，可以使用以下2個公式對硬件任務(wù)實際的運行時間和功耗進行估算：   其中，f是硬件任務(wù)實際的運行頻率。2 功耗相關(guān)硬件任務(wù)調(diào)度算法EEHTS21 硬件任務(wù)調(diào)度器設(shè)計    目標(biāo)系統(tǒng)如圖3所示。用戶程序分為2部分，其中軟件任務(wù)運行在CPU上，硬件任務(wù)運行在FPGA上。本文中只考慮功耗相關(guān)的硬件任務(wù)的調(diào)度，目標(biāo)

9、是將軟硬件任務(wù)統(tǒng)一起來進行考慮，在滿足任務(wù)截止時限要求的情況下降低系統(tǒng)的整體功耗，即：   22 調(diào)度原則和放置原則    在嵌入式系統(tǒng)中，任務(wù)的正確性不但依賴于其功能正確性，而且依賴于其執(zhí)行的及時性，所以確保任務(wù)不錯過截止期是最重要的調(diào)度依據(jù)。在滿足任務(wù)截止時間的前提下，1個新到達的硬件任務(wù)Ti的最遲開始執(zhí)行時間(Last：Starting time，LST)為LST(Ti)=ci-ti，如果Ti在放置時沒有找到合適的位置，調(diào)度器并不立刻拒絕Ti，因為只要在LST(Ti)之前有滿足Ti需求的資源被釋放，那么Ti仍然可以滿足其截止期要

10、求。在EEHTS算法中，需要維護到達任務(wù)列表Alist，Alist中保存所有已經(jīng)到達且未能成功分配的任務(wù)。已到達列表的任務(wù)按照任務(wù)的LST增序排列，即按照最早最遲開始時問優(yōu)先(EarliestLast Starting time First，ELST)的原則進行調(diào)度。硬件任務(wù)調(diào)度器的核心是進行定位分配，即根據(jù)硬件任務(wù)占用FPGA資源大小在FPGA上尋找合適的位置對FPGA進行配置，如參考文獻5中提出的MER算法。但是此類算法采用的FPGA面積模型都是2D資源模型，并不能在當(dāng)前的FPGA技術(shù)條件下實現(xiàn)，所以本文采用類似傳統(tǒng)操作系統(tǒng)管理存儲器資源的方法，即首次適配(FirstFit)算法。在EEHTS算法中，需要維護空白資源列表B，B中保存了所有當(dāng)前未被使用的FPGA上的空白區(qū)域。放置成功的硬件任務(wù)即可開始配置運行，因此在EEHTS算法中需要維護正在運行的任