1．2 任務定義

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

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

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

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

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

　　2．1 硬件任務調度器設計

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

　　2．2 調度原則和放置原則

　　在嵌入式系統中，任務的正確性不但依賴于其功能正確性，而且依賴于其執行的及時性，所以確保任務不錯過截止期是最重要的調度依據。在滿足任務截止時間的前提下，1個新到達的硬件任務Ti的最遲開始執行時間（Last：Starting time，LST）為LST（Ti）=ci-ti，如果Ti在放置時沒有找到合適的位置，調度器并不立刻拒絕Ti，因為只要在LST（Ti）之前有滿足Ti需求的資源被釋放，那么Ti仍然可以滿足其截止期要求。在EEHTS算法中，需要維護到達任務列表Alist，Alist中保存所有已經到達且未能成功分配的任務。已到達列表的任務按照任務的LST增序排列，即按照最早最遲開始時問優先（EarliestLast Starting time First，ELST）的原則進行調度。硬件任務調度器的核心是進行定位分配，即根據硬件任務占用FPGA資源大小在FPGA上尋找合適的位置對FPGA進行配置，如參考文獻［5］中提出的MER算法。但是此類算法采用的FPGA面積模型都是2D資源模型，并不能在當前的FPGA技術條件下實現，所以本文采用類似傳統操作系統管理存儲器資源的方法，即首次適配（FirstFit）算法。在EEHTS算法中，需要維護空白資源列表B，B中保存了所有當前未被使用的FPGA上的空白區域。放置成功的硬件任務即可開始配置運行，因此在EEHTS算法中需要維護正在運行的任務列表Elist。執行列表Elist中包含所有正在運行的硬件任務Ti，任務按照執行完畢時間的增序排列。

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

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

　?。?）算法1：EEHTS算法

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

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