|
引 言 可重構系統是指以軟件改變硬件結構以實(shí)現具體應用的計算平臺，一般由非柔性但可編程的處理器和柔性的以程序控制重構的數字邏輯器件構成。目前國內外的可重構系統研究中，采用的可重構硬件主要是現場(chǎng)可編程門(mén)陣列(Field Programming Gate Array，FPGA)�？芍貥嬒到y非常適合于那些對功耗有嚴格要求或者計算密集的應用，因為此類(lèi)應用在FPGA上實(shí)現的功耗要大大低于在處理器上實(shí)現的功耗。將在FPGA上運行的任務(wù)視為“硬件任務(wù)”納入實(shí)時(shí)操作系統(Real-time Operating Sys-tem，RTOS)的統一管理范圍，可簡(jiǎn)化系統的設計與管理。因此，需要在傳統的RTOS中引入硬件任務(wù)管理器，實(shí)現硬件任務(wù)的管理和調度。 目前，該研究已經(jīng)取得了一定進(jìn)展。如在參考文獻[1]中提出的商用可重構系統OS4RS，包含的主要功能有任務(wù)的創(chuàng )建／銷(xiāo)毀、異構任務(wù)的動(dòng)態(tài)遷移、任務(wù)之間的相互通信等。支持軟／硬件任務(wù)調試以及允許對操作系統模塊和用戶(hù)任務(wù)的跟蹤監控，是可重構硬件操作系統的重要特征。在參考文獻[2]中設計了一種基于軟／硬件統一多任務(wù)模型的實(shí)時(shí)操作系統SHUM-μCOS，實(shí)現了統一任務(wù)的管理、基于靜態(tài)優(yōu)先級的軟／硬件任務(wù)獨立調度、硬件資源的管理以及軟／硬件任務(wù)基于軟件層的通信等機制。 但是大多數研究者考慮的軟／硬件調度算法一般難以在現有的FPGA硬件平臺上實(shí)現，如參考文獻[2]中FORS算法采用的2D FPGA資源模型。這是因為當前的FPGA技術(shù)只允許所有的任務(wù)占用同樣的“高度”，并且上述工作中幾乎沒(méi)有將功耗納入考慮范疇。因此，類(lèi)似在嵌入式微處理器中廣泛采用動(dòng)態(tài)電壓調整(DynamicVoltage Scaling，DVS)技術(shù)以降低系統功耗，本文提出了一種動(dòng)態(tài)調整FPGA工作頻率的算法，在可重構系統的性能需求和功耗需求之間達到平衡，并且可以在當前的FPGA技術(shù)條件下實(shí)現。 1 調度模型 1．1 可重構系統體系結構 本文只考慮在當前FPGA技術(shù)條件下的可重構系統結構，如圖1所示。FPGA分為動(dòng)態(tài)和靜態(tài)兩部分。動(dòng)態(tài)部分包括很多可重構模塊 (Reconfigurable Modules，RM)，每個(gè)硬件任務(wù)運行在1個(gè)RM上，各個(gè)RM占用的FPGA寬度可以不相等，一般由若干同列的CLB(Config-urabIe Logic Block，可重構單元)組成。靜態(tài)部分則負責與CPU和RM之間的數據交互。 
假設FPGA是由很多CLB成陣列排列而成，每1個(gè)CLB可以看成1個(gè)1×1的單位正方形，1個(gè)FPGA則是1個(gè)面積為ω×h的長(cháng)方形。其中ω 為長(cháng)方形的寬度，h為長(cháng)方形的高度，ω×h為該FPGA包含CLB的總數(即面積)。圖2所示為1塊5×4的FPGA。在實(shí)現中，因為每個(gè)RM都使用相同的FPGA高度，即h，所以最小的RM的面積是ωmm×h，其中，ωmin的大小依賴(lài)于硬件任務(wù)需要使用的CLB的個(gè)數。所以，1塊FPGA上RM最多可以有：
當對1塊FPGA進(jìn)行配置時(shí)，其動(dòng)態(tài)部分可以劃分成具有不同寬度的RM，從而具有不同CLB需求的多個(gè)硬件任務(wù)可以同時(shí)運行在FPGA上。另外，對其中1個(gè)RM進(jìn)行配置時(shí)，對于其他正在運行的部分沒(méi)有影響，從而可重配置硬件使得硬件任務(wù)以一種真正的動(dòng)態(tài)多任務(wù)方式運行。 1．2 任務(wù)定義 ①硬件任務(wù)：硬件任務(wù)是指可重構系統中基于FPGA實(shí)現的功能模塊。一個(gè)硬件任務(wù)配置完成后即可開(kāi)始執行，在完成之前一般不會(huì )釋放其占用的可重配置資源，即不能被其他硬件任務(wù)搶占。 ②一個(gè)硬件任務(wù)可表示為T(mén)i(fi，max，ai,ci,ti,ei，fworking)。其中，fi,max是硬件任務(wù)可以運行在RM上的最大時(shí)鐘頻率，這個(gè)頻率是由每個(gè)具體硬件任務(wù)設計的時(shí)序狀況決定的，所以每個(gè)任務(wù)的fi,max可能不同。ωi是任務(wù)占用的可重構硬件的寬度資源，ai表示硬件任務(wù)的到達時(shí)間,ci表示硬件任務(wù)的最后完成時(shí)限，ti是硬件任務(wù)工作在fi,max時(shí)的運行時(shí)間。本文中不單獨考慮硬件任務(wù)在FPGA上的配置時(shí)間，而是把它并入運行時(shí)間中一起考慮。e是硬件任務(wù)工作在fi,max時(shí)的功耗，可由參考文獻[4]建立的功耗模型進(jìn)行估算。fworking是該任務(wù)在運行時(shí)FPGA的實(shí)際頻率。 在參考文獻[4]中，硬件任務(wù)的功耗和硬件的運行頻率直接相關(guān)，因此，可以使用以下2個(gè)公式對硬件任務(wù)實(shí)際的運行時(shí)間和功耗進(jìn)行估算：
其中，f是硬件任務(wù)實(shí)際的運行頻率。 2 功耗相關(guān)硬件任務(wù)調度算法EEHTS 2．1 硬件任務(wù)調度器設計 目標系統如圖3所示。用戶(hù)程序分為2部分，其中軟件任務(wù)運行在CPU上，硬件任務(wù)運行在FPGA上。本文中只考慮功耗相關(guān)的硬件任務(wù)的調度，目標是將軟／硬件任務(wù)統一起來(lái)進(jìn)行考慮，在滿(mǎn)足任務(wù)截止時(shí)限要求的情況下降低系統的整體功耗，即：
2．2 調度原則和放置原則 在嵌入式系統中，任務(wù)的正確性不但依賴(lài)于其功能正確性，而且依賴(lài)于其執行的及時(shí)性，所以確保任務(wù)不錯過(guò)截止期是最重要的調度依據。在滿(mǎn)足任務(wù)截止時(shí)間的前提下，1個(gè)新到達的硬件任務(wù)Ti的最遲開(kāi)始執行時(shí)間(Last：Starting time，LST)為L(cháng)ST(Ti)=ci-ti，如果Ti在放置時(shí)沒(méi)有找到合適的位置，調度器并不立刻拒絕Ti，因為只要在LST(Ti)之前有滿(mǎn)足 Ti需求的資源被釋放，那么Ti仍然可以滿(mǎn)足其截止期要求。在EEHTS算法中，需要維護到達任務(wù)列表Alist，Alist中保存所有已經(jīng)到達且未能成功分配的任務(wù)。已到達列表的任務(wù)按照任務(wù)的LST增序排列，即按照最早最遲開(kāi)始時(shí)問(wèn)優(yōu)先(EarliestLast Starting time First，ELST)的原則進(jìn)行調度。硬件任務(wù)調度器的核心是進(jìn)行定位分配，即根據硬件任務(wù)占用FPGA資源大小在FPGA上尋找合適的位置對FPGA 進(jìn)行配置，如參考文獻[5]中提出的MER算法。但是此類(lèi)算法采用的FPGA面積模型都是2D資源模型，并不能在當前的FPGA技術(shù)條件下實(shí)現，所以本文采用類(lèi)似傳統操作系統管理存儲器資源的方法，即首次適配(FirstFit)算法。在EEHTS算法中，需要維護空白資源列表B，B中保存了所有當前未被使用的FPGA上的空白區域。放置成功的硬件任務(wù)即可開(kāi)始配置運行，因此在EEHTS算法中需要維護正在運行的任務(wù)列表Elist。執行列表Elist中包含所有正在運行的硬件任務(wù)Ti，任務(wù)按照執行完畢時(shí)間的增序排列。 在硬件任務(wù)完成之前，不能被其他任務(wù)搶占；當硬件任務(wù)完成之后，即可釋放其占用的FPGA資源，并將執行完畢的任務(wù)插入到執行完畢任務(wù)列表Flist中。這個(gè)特點(diǎn)是硬件任務(wù)和軟件任務(wù)的顯著(zhù)區別。 2．3 功耗相關(guān)硬件任務(wù)調度算法EEHTS (1)算法1：EEHTS算法
在任何時(shí)刻t，EEHTS算法首先檢查Alist隊列中的第1個(gè)任務(wù)Ti，函數有3種可能的返回結果：ACCEPT、REJECT和NULL。第2行中如果FPGA空白區域列表B中有合適的位置放置任務(wù)Ti，那么將Ti加入到Elist中，然后第6行重新計算1個(gè)更加優(yōu)化的FPGA頻率fe，如果fe小于當前FPGA運行的頻率fworking，并且在fe下所有Elist中任務(wù)均能在其截止期內完成，那么說(shuō)明可以在保證任務(wù)截止期的條件下通過(guò)降低頻率而降低硬件任務(wù)的整體功耗，所以此時(shí)算法返回ACCEPT；第13行如果任務(wù)即將或者已經(jīng)錯過(guò)最遲開(kāi)始時(shí)間，那么此時(shí)函數返回REJECT，表示此任務(wù)被拒絕；第15行如果當前時(shí)刻沒(méi)有合適的位置，但是任務(wù)仍沒(méi)有到其最遲開(kāi)始時(shí)間，表示在將來(lái)的時(shí)刻仍然可能獲得任務(wù)所需資源，所以函數返回結果 NULL。 算法1中第6行重新計算FPGA工作頻率的算法如算法2所示，其中F是所有硬件任務(wù)工作頻率值的集合。需要說(shuō)明的是，同一時(shí)刻在FPGA運行的硬件任務(wù)的工作頻率值必須相同，并且選擇5作為FPGA頻率的增量也是符合實(shí)際FPGA技術(shù)情況的。 (2)算法2：選擇最優(yōu)的頻率值作為FPGA的運行頻率
步驟1：fscheduled,max=min(fi,min|Ti∈Elist) 步驟2：對于F集合中的滿(mǎn)足fmin≤f≤fscheduled，max的每個(gè)f值，計算：
選取使得計算步驟2中結果最小的，值作為FPGA的運行頻率值，從而使得FPGA的總體功耗最低。 3 模擬實(shí)驗及分析 由于當前并沒(méi)有一個(gè)統一的基準用于評價(jià)可重構系統功耗相關(guān)的調度算法，因此采取了類(lèi)似參考文獻[2]中的模擬實(shí)驗模型設計了離散時(shí)鐘的模擬器，模仿實(shí)時(shí)系統中的時(shí)鐘滴答以進(jìn)行任務(wù)截止期的檢查。然后設計隨機任務(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ù)的寬度和執行時(shí)間也是隨機生成的。 假定目標器件為Xilinx Virtex XCV1000，共96列×64行，其中可用于配置硬件任務(wù)的動(dòng)態(tài)部分是80列，其他用于操作系統進(jìn)行通信和I／O。模擬實(shí)驗中采用的參數如下：任務(wù)的最小寬度ωmin=1，Nmax=80，任務(wù)的寬度范圍ωi為1～80；fmin=20 MHz，fmax=100MHz，所以各個(gè)任務(wù)的可運行的最大頻率fi,max∈[20，25，…，1 000]；任務(wù)在fi,max頻率時(shí)的運行時(shí)間ti范圍為100～1 000 ms。ei范圍為20～200 mJ，ei的大小和任務(wù)寬度相關(guān)。到達時(shí)間范圍01．5～500 ms，模擬器的時(shí)鐘滴答設置為500 μs。分別模擬了采用ELST算法和EEHTS算法的任務(wù)集的總體運行時(shí)間和整體功耗，如圖4和圖5所示。從圖4中可以看到，采用ELST算法的任務(wù)運行時(shí)間曲線(xiàn)要比采用EEHTS算法的低，這是因為只采用ELST算法時(shí)并不改變FPGA的運行頻率，FPGA始終使用最高頻率運行，顯然這種方法的功耗會(huì )大于EEHTS算法，實(shí)驗結果也證明了這點(diǎn)。如圖5所示，EEHTs算法雖然犧牲了一些時(shí)間性能，但是硬件任務(wù)仍然可以在其截止期內完成，并且相對于 ELST算法，硬件任務(wù)功耗大約降低了32％。
結 語(yǔ) 在嵌入式系統中，低功耗是非常重要的目標。本文通過(guò)對可重構系統中硬件任務(wù)調度算法的研究，在對硬件任務(wù)調度時(shí)加入了對功耗的考慮，動(dòng)態(tài)改變硬件任務(wù)運行的頻率，從而降低系統整體功耗。 參考文獻 1. Marescaux T,Mignolet J Y,Bartic A.Networks on chip as hardware components of an OS for reconfigurable system[C].Proceedings of the 13th International Conference on Field Programmable Gate Array,2003:595-605. 2. 周博,王石記.SHUM-UCOS基于統一多任務(wù)模型可重構系統的實(shí)時(shí)操作系統[J].計算機學(xué)報,2006,29:209-218. 3. Xilinx Inc.Virtex RM 2.5V FPGA Complete Data Sheet (allfour Modules)[OL].(2002-02-15).http://www.xilinx.com. 4. Choi S,Jang J W,Mohanty S,et al.Domain-Specific Modeling or Rapid System-Wide Energy Estimation of Reconfigurable Architectures[C].Proceeding of Engineering of Reconfigurable Systems and Algorithms,2002. 5. Bazargan K,Kastner R,Sarrafzadeh M.Fast template placement for reconfigurable computing systems[J].IEEE Design and Test of Computers,2000,17:68-83. 6. Stallings William.操作系統內核與設計原理[M].魏迎梅,等譯.4版.北京:電子工業(yè)出版社,2002:233-234. 作 者：李冉,郭兵(四川大學(xué)) 沈艷(電子科技大學(xué)) 來(lái)源：《單片機與嵌入式系統應用》2009（9） |
