面向可重構(gòu)系統(tǒng)的一種功耗相關(guān)硬件任務(wù)調(diào)度算法設(shè)計(jì) - 全文

　　假設(shè)FPGA是由很多CLB成陣列排列而成，每1個(gè)CLB可以看成1個(gè)1×1的單位正方形，1個(gè)FPGA則是1個(gè)面積為ω×h的長方形。其中ω為長方形的寬度，h為長方形的高度，ω×h為該FPGA包含CLB的總數(shù)（即面積）。圖2所示為1塊5×4的FPGA。在實(shí)現(xiàn)中，因?yàn)槊總€(gè)RM都使用相同的FPGA高度，即h，所以最小的RM的面積是ωmm×h，其中，ωmin的大小依賴于硬件任務(wù)需要使用的CLB的個(gè)數(shù)。所以，1塊FPGA上RM最多可以有：

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

　　1．2 任務(wù)定義

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

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

　　在參考文獻(xiàn)［4］中，硬件任務(wù)的功耗和硬件的運(yùn)行頻率直接相關(guān)，因此，可以使用以下2個(gè)公式對(duì)硬件任務(wù)實(shí)際的運(yùn)行時(shí)間和功耗進(jìn)行估算：

　　其中，f是硬件任務(wù)實(shí)際的運(yùn)行頻率。

　　2 功耗相關(guān)硬件任務(wù)調(diào)度算法EEHTS

　　2．1 硬件任務(wù)調(diào)度器設(shè)計(jì)

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

　　2．2 調(diào)度原則和放置原則

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

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

　　2．3 功耗相關(guān)硬件任務(wù)調(diào)度算法EEHTS

　?。?）算法1：EEHTS算法

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

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

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

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

　　步驟2：對(duì)于F集合中的滿足fmin≤f≤fscheduled，max的每個(gè)f值，計(jì)算：

　　選取使得計(jì)算步驟2中結(jié)果最小的，值作為FPGA的運(yùn)行頻率值，從而使得FPGA的總體功耗最低。

　　3 模擬實(shí)驗(yàn)及分析

　　由于當(dāng)前并沒有一個(gè)統(tǒng)一的基準(zhǔn)用于評(píng)價(jià)可重構(gòu)系統(tǒng)功耗相關(guān)的調(diào)度算法，因此采取了類似參考文獻(xiàn)［2］中的模擬實(shí)驗(yàn)?zāi)Ｐ驮O(shè)計(jì)了離散時(shí)鐘的模擬器，模仿實(shí)時(shí)系統(tǒng)中的時(shí)鐘滴答以進(jìn)行任務(wù)截止期的檢查。然后設(shè)計(jì)隨機(jī)任務(wù)生成器，生成分別含有1 000、2 000、3 009、4 000、5 000、6 000個(gè)Ti（fi，max，ωi，ai，ci，ti，ei，fworking）的任務(wù)集，硬件任務(wù)的寬度和執(zhí)行時(shí)間也是隨機(jī)生成的。

　　假定目標(biāo)器件為Xilinx Virtex XCV1000，共96列×64行，其中可用于配置硬件任務(wù)的動(dòng)態(tài)部分是80列，其他用于操作系統(tǒng)進(jìn)行通信和I／O。模擬實(shí)驗(yàn)中采用的參數(shù)如下：任務(wù)的最小寬度ωmin=1，Nmax=80，任務(wù)的寬度范圍ωi為1～80；fmin=20 MHz，fmax=100MHz，所以各個(gè)任務(wù)的可運(yùn)行的最大頻率fi，max∈［20，25，…，1 000］；任務(wù)在fi，max頻率時(shí)的運(yùn)行時(shí)間ti范圍為100～1 000 ms。ei范圍為20～200 mJ，ei的大小和任務(wù)寬度相關(guān)。到達(dá)時(shí)間范圍01．5～500 ms，模擬器的時(shí)鐘滴答設(shè)置為500 μs。分別模擬了采用ELST算法和EEHTS算法的任務(wù)集的總體運(yùn)行時(shí)間和整體功耗，如圖4和圖5所示。從圖4中可以看到，采用ELST算法的任務(wù)運(yùn)行時(shí)間曲線要比采用EEHTS算法的低，這是因?yàn)橹徊捎肊LST算法時(shí)并不改變FPGA的運(yùn)行頻率，F(xiàn)PGA始終使用最高頻率運(yùn)行，顯然這種方法的功耗會(huì)大于EEHTS算法，實(shí)驗(yàn)結(jié)果也證明了這點(diǎn)。如圖5所示，EEHTs算法雖然犧牲了一些時(shí)間性能，但是硬件任務(wù)仍然可以在其截止期內(nèi)完成，并且相對(duì)于ELST算法，硬件任務(wù)功耗大約降低了32％。

　　結(jié) 語

　　在嵌入式系統(tǒng)中，低功耗是非常重要的目標(biāo)。本文通過對(duì)可重構(gòu)系統(tǒng)中硬件任務(wù)調(diào)度算法的研究，在對(duì)硬件任務(wù)調(diào)度時(shí)加入了對(duì)功耗的考慮，動(dòng)態(tài)改變硬件任務(wù)運(yùn)行的頻率，從而降低系統(tǒng)整體功耗。