李延祺，任 海，白 亮，邱 源，張鳳源，牛建偉，李輝勇

(1.北京航空航天大學 計算機學院，北京 100191； 2. 上海航天電子技術研究所，上海 200082)

0 引言

由于星載嵌入式系統在獨立的太空環(huán)境中工作，所以航天設備需要的電量資源必須能夠自給自足。為了延長設備的工作時間，需要在操作系統層面針對各任務進行合理的調度，以統籌各任務的能耗。對于功能強大的嵌入式處理器來說，合理的分配資源以降低整體能耗是十分重要的。因此，星載實時操作系統的性能和能耗之間的平衡問題是使用電池的嵌入式系統所必須面對的重要課題。

為了提高嵌入式系統對電池資源的利用率，滿足任務執(zhí)行的時間約束以及保證系統的實時性，目前國內外大多采用實時電壓和頻率縮放(DVS)技術。DVS技術可以讓嵌入式設備動態(tài)適配CPU的當前電壓來達到理想中的低能耗狀，目前多數嵌入式和分布式系統都采用DVS技術以降低系統能耗。DVS技術的研究主要從具有嚴格時間約束的實時獨立任務方面進行，以達到顯著降低任務整體能耗的目的。如文獻[1]采用一種應用在單核處理器的嵌入式系統中的偽多項式動態(tài)規(guī)劃算法，以求解具有離散電壓值的周期性實時任務的最優(yōu)解。文獻[2]通過重復利用時間以允許其余任務可以在低于標準電壓的情況下運行。

為了能夠在滿足時間約束的前提下提高整個系統的能效，可以從基于概率的嵌入式系統任務調度方向進行研究。文獻[3]首先考慮具有不確定性的執(zhí)行時間的任務，然后引入概率輪轉調度算法來縮短具有無環(huán)拓撲架構任務圖的執(zhí)行時間。文獻[4]采用調度算法將任務動態(tài)地重新映射到適當的處理器中，并設定處理器內部執(zhí)行任務的順序，將多余的時間分配給未執(zhí)行的任務。文獻[5]提出一種不限制嵌入式系統處理器數量的動態(tài)規(guī)劃算法來解決異構嵌入式系統的任務分配問題。

本文采用一種局部重啟搜索算法(LSR)以找到嵌入式系統的最佳調度策略。首先，設計一個有效的處理器分配算法來生成處理器分配方案；然后使用電壓分配算法，以一定概率下完成任務的思路來最小化整體的能耗；最后，為了避免局部最優(yōu)解，使用帶有重新啟動的本地搜索再次對資源進行優(yōu)化并得到全局最優(yōu)解。本文采用的LSR算法和傳統調度算法能夠為軟實時嵌入式系統提供一些滿足時序和置信度要求的更低成本解決方案，以動態(tài)調度的思想來解決專屬虛擬接入點(PVAP)問題。

1 問題建模

由于條件指令和時變外部環(huán)境(如波動的網絡帶寬、不同的用戶輸入和DVS)的變化，星載實時嵌入式操作系統的同一任務會在不同環(huán)境下產生不同的執(zhí)行時間。即，一個任務在不同的環(huán)境下可能會有不同的完成概率。

以下符號用于問題的數學表述中：DAGG=〈V,E〉用于表示所有任務及其數據的依賴關系，V={v1,…,vi,…,vx}是任務節(jié)點集合，x是任務數量。E={e11,…,eij,…,enn}是邊的集合，當eij為1時，表示當前vi和vj節(jié)點之間存在數據依賴，反之為0無依賴。

關于嵌入式處理器的定義如下：PE={pe1,…,pei,…,pey}是處理器單元的集合，y是處理器數量。pei表示第i個處理器。Vol={Vol1,…,Voli,…,VolM}，Voli={Voli,l,…,Voli,j,…,Voli,L}是pei電壓的集合，L是處理器的可用電壓值。

TA(G)=max{si+r(i),si+ct(i)},

?vi∈V

(1)

(2)

(3)

由于任務vi取決于前置的數據輸出，當且僅當只有前置任務完成后才能運行。

建模之后，給出PVAP問題的定義：給定一個有限的處理器集合PE，一個電壓電平集合Vol，一個執(zhí)行概率集合B，有向無環(huán)圖DAGG=〈V,E〉，一個時間約束T和一個置信度P，問題是要為每個任務vi確定一個合適的處理器和電壓電平，其提供了在時間約束T下的最小能量消耗和具有保證置信概率P的優(yōu)先約束。

2 PVAP問題的解決方案

提出了一種面向星載嵌入式系統，具有數據依賴和CPU資源約束的非周期性任務圖的可變電壓概率調度的解決方案。解決方案分為三個階段：第一階段，使用有效的調度算法以獲得初始處理器的分配方案；第二階段，基于已得到的分配策略，提出電壓分配算法，以保證任務能在一定的置信度和時間約束下執(zhí)行完成，同時對能耗較高的任務進行優(yōu)化分配，并將能耗最小化；第三階段，使用LSR算法來擺脫局部最優(yōu)解。LSR算法通過更新目標函數從候選解決方案中搜索最優(yōu)解，直到任務結束或者超出時間約束，這些都將在下文中對其分別討論。

2.1 初始處理器分配策略

由于嵌入式系統中處理器的數量有限，研究時需要為每個任務分配合適的處理器，以有效使用處理器。為了避免局部最優(yōu)解，本文使用不同的調度算法，如基于盡可能晚(ALAP)調度算法[7]、基于盡可能快 (ASAP)調度算法和整數線性規(guī)劃(ILP)調度算法[8]來生成原始的處理器分配策略。

處理器調度算法(ASAP/ALAP)的實現過程如下：首先使用拓撲排序獲得目標任務列表具有優(yōu)先級限制的DAG拓撲序列；然后計算每個任務的最差執(zhí)行時間，在最早/最近狀態(tài)下，使用ASAP/ALAP算法根據任務的優(yōu)先級進行調度，通過為同一處理器上的連續(xù)任務間插入模擬邊界來保證任務的執(zhí)行順序；最后使用ASAP/ALAP算法將任務圖中的每個任務分配給適當的處理器，就可以生成用于解決PVAP問題的新DAG。

ILP算法的實現如下：首先計算每個任務的執(zhí)行時間；然后采用整數線性規(guī)劃(ILP)調度算法[8]完成ILP的PVAP問題的數學表達式；最后使用LINGO 9.0軟件的非線性規(guī)劃解算器來獲得處理器分配策略。

2.2 電壓分配方案

該節(jié)討論如何使用動態(tài)編程(DP)來解決PVAP中電壓分配問題。

1)令K={S1,S2}，式中，S1和S2分別是圖G1和G2的解空間；

2)S′0=CombineSubSolution(K)；

3)S0=S′0⊙B0；

4)刪除S0中的冗余解和不可行解。

根據上述思想，按照自下向上的順序計算出圖1(a)任務樹中各個節(jié)點i的解決方案。當算法到達根節(jié)點0時，需計算出S0所需要的全部結果，并重復使用子圖的解來計算。然后從最小的子圖開始，逐步解決大規(guī)模的問題。在此計算過程中應保存已有子圖的解決方案，通過重復使用子圖來提高問題的解決速度。整個圖的PVAP問題可以分解為多個子圖的PVAP問題。通過去除Si中的冗余和不可行解，可獲得滿足時間和概率約束的候選解，并將具有最小能耗的解視為整棵樹的最優(yōu)解。共同節(jié)點問題如圖1所示。

圖1 共同節(jié)點問題Fig.1 Common node problem

然而對于具有任意數量邊和節(jié)點的DAG，由于其中可能存在公共節(jié)點(出現在2個或更多子圖中的節(jié)點)，所以在電壓選擇過程中會產生沖突。例如在圖1(b)中，v4節(jié)點屬于2個子圖G1和G2，可能存在V4在S1中為v4優(yōu)先選擇vol0，而在S2中選擇。因此即使G1和G2的解決方案(S1和S2)都是最佳的，但是由于電壓的選擇會發(fā)生沖突，所以S0不能獲得最佳的分配方案。下面列舉所有節(jié)點中可能存在的組合方案來解決此問題，在所有可能的組合中，PVAP_DP算法能夠選擇最佳的電壓分配方案。算法流程如圖2所示。

圖2 算法流程圖Fig.2 Algorithm flowchart

采用PVAP_DP算法來解決電壓分配問題，如圖2(a)所示。首先要解決子問題，得到逆拓撲排序。之后為了解決公共節(jié)點的問題，需要列舉多個節(jié)點中可能存在的電壓分配方案。由于從逆拓撲順序的第1個節(jié)點(假設為v1)沒有子節(jié)點，所以可行解S1就是概率執(zhí)行列表B1。

為了得到Si，第一步首先需要通過Gi,Gi1,…,Giw的解來得到S′i,然后對于每個S′i,j∈S′i和b=Bi,對s′i,j和b進行⊙操作從而得到Si。當內層的循環(huán)結束時，得到所有節(jié)點的最優(yōu)電壓分配SN。最后合并每個循環(huán)中產生的最佳電壓分配方案SN。當外層循環(huán)結束時，在當前的處理器選擇下獲得所有節(jié)點的最優(yōu)電壓分配方案。當外循環(huán)結束后，從集合S中去除冗余解和不可行解，得到最優(yōu)解。

2.3 LSR局部重啟搜索策略

采用局部重啟搜索算法(LSR)在所有候選解中尋找最優(yōu)解。圖2(b)中給出了LSR算法流程圖。首先使用有效調度算法(如ALAP)生成初始處理器調度(DAG)；然后基于新生成的DAG，在該步驟中采用帶有局部搜索的PVAP_DP算法來最小化能耗；最后從初始調度開始，在內部循環(huán)中，采用局部搜索算法在候選解的解空間中尋找更優(yōu)的處理器和電壓分配。為了避免局部最優(yōu)，在外循環(huán)中應用LSR。使用不同的處理器調度策略(本例中使用PVAP_DP算法)來生成初始處理器分配方案，以便對不同的初始調度表采用LSR。當達到重啟次數時終止循環(huán)。重啟次數是一個經驗常數，取決于不同的應用場景。

3 實驗

依據參考文獻[9]進行實驗設計，并且利用實驗結果對PVAP_LSR算法進行性能評估[10]。ASAP和ALAP調度算法廣泛應用于各種處理器和電壓分配算法中，本文實驗中使用的基于ASAP/ALAP的調度算法是ASAP/ALAP和PVAP_DP的結合，而PVAP_LSR算法是LSR和PVAP_DP算法的結合，通過這種方式能夠提升LSR算法的性能。本文還對PVAP_LSR算法和其他搜索算法，如禁忌搜索(TS)和模擬退火算法(SA)進行比較。

3.1 實驗基準

針對表1中2個基準進行了對比實驗，使用隨機化任務圖生成器[7]得到任務圖，TGFF-1具有很長的關鍵路徑，TGFF-2具有相對較短的關鍵路徑。

表1 實驗任務圖的基準描述

首先針對估計不同頻率下的CPU功率進行分析。本文采用PowerPC處理器和ARM處理器。處理器的電壓以及各自的功率與頻率見表2。

表2 ARM和PowerPC處理器的電壓和功耗

在表3～5、圖3～4中，能源消耗的單位是能源單位(EU)，時間約束或者任務執(zhí)行時間的單位是時間單位(TU)，列“TC/PEs”表示“時間約束/處理器數量”。PVAP_LSR算法的平均提升效果顯示在每個表的最后一行。實驗中可以靈活的選擇要部署的處理器數量(2個或者3個)。前者意味著所有任務都在2個處理器(PowerPC和ARM處理器)上執(zhí)行，后者意味著所有任務在2個PowerPC處理器和1個ARM處理器上執(zhí)行。

3.2 與ILP算法的比較

將本文中使用的算法和ILP進行了比較。對使用TGFF-1標準的實驗結果分別見表3，4。在表3，4中，“ILP1”“ILP2”和“PVAP_LSR”三列分別表示不含DVS的ILP、具有DVS的ILP和PVAP_LSR算法獲得的結果。“%I1”和“%I2”兩列分別代表本文中使用的算法相對于不具有DVS的ILP算法和具有DVS的ILP算法的改進。在本文中，所有表中帶有“×”的條目表示相應的分配未能生成有效的調度。

實驗結果表明：PVAP_LSR算法在保證置信概率的同時，能夠提高能效。表3中 PVAP_LSR算法與ILP2算法相比，在置信概率分別為0.8，0.9和1.0時，平均(最大)能耗降低分別為18.4%(23.7%)，13.3%(17.4%)和9.8%(14.1%)；與ILP1算法相比，分別獲得37.2%(41.4%)，33.8%(38.5%)和31.2%(36.0%)的平均(最大)能耗降低，置信概率分別為0.8，0.9和1.0。表4中PVAP_LSR算法與ILP2算法相比，平均(最大)能耗降低分別為17.4% (20.8%)，10.8%(15.7%)和1.3%(4.5%)，置信概率分別為0.8，0.9和1.0；與ILP1算法相比，平均(最大)能耗降低分別為28.0%(41.0%)，22.2%(37.3%)和31.2% (36.0%)，置信概率分別為0.8，0.9和1.0。

表3 有ILP的DVS、無ILP的DVS和PVAP_LSR的能耗比較

表4 有ILP的DVS、無ILP的DVS和PVAP_LSR的能耗比較

對于TGFF-1基準，圖3顯示算法相對于ILP1和ILP2的改進。與ILP1和ILP2相比，PVAP_LSR算法在所有時間約束下能夠實現更好的能效，橫坐標為人為設定的時間約束，縱坐標為調度算法執(zhí)行完的任務總能耗。ILP算法在一定的時間范圍內可能無法找到近似最優(yōu)解。

3.3 與基于ALAP和ASAP的算法比較

將本文使用的算法與其他2種算法(ALAP，ASAP)進行比較。ASAP的使用方法為：對于處理器分配，使用基于ASAP的列表調度；對于電壓分配，使用PVAP_DP算法。ALAP的使用方法為：對于處理器分配，使用基于ALAP的列表調度；對于電壓分配，使用PVAP_DP算法。

基于TGFF-2標準的實驗結果見表5。表中“A1”“A2”和“PVAP_LSR”分別表示由ASAP，ALAP和PVAP_LSR算法的結果，“%A1”和“%A2”分別表示相對于ASAP和ALAP算法的改進效果。

圖4是PVAP_LSR相對于TGFF-1基準的ASAP和ALAP調度的改進。在對于TGFF-1基準，PVAP_LSR在功耗方面可以獲得最佳的可變電壓調度。與基于ALAP的調度相比，PVAP_LSR相對于基于ALAP的調度分別實現15.6%(23.0%)，13.9%(19.2%)和11.5%(17.4%)的平均(最大)能耗降低，置信概率分別為0.8，0.9和1.0)。PVAP_LSR算法與基于ASAP算法相比，PVAP_LSR分別獲得15.2%(24.3%)，13.4%(20.6%)和11.0%(18.8%)的平均(最大)功率優(yōu)化，置信概率分別為0.8，0.9和1.0。而且PVAP_LSR算法在所有時間約束下都具有更好的能效。

圖3 ILP1, ILP2和PVAP_LSR基于TGEF-1基準的能耗Fig.3 Benchmark energy consumption of ILP1, ILP2 and PVAP_LSR based on TGEF-1

圖4 ALAP, ASAP和PVAP_LSR基于TGEF-1基準能耗Fig.4 Benchmark energy consumption of ALAP, ASAP and PVAP_LSR based on TGEF-1

表5 ASAP, ALAP和PVAP_LSR基于TGFF-2基準的能耗對比

4 結束語

現有的研究對實時嵌入式系統的執(zhí)行時間和能耗等不確定性因素的關注度不夠。針對資源有限的星載實時嵌入式系統，本文采用概率方法，提出一套處理器和電壓分配算法來解決具有優(yōu)先級約束的非周期任務的可變電壓調度問題。實驗結果表明：與目前流行的方法相比，該方法能夠提高星載嵌入式操作系統的能效，為用戶實現能效提供更多選擇，同時在保證置信度的前提下滿足定時約束。本方法對于軟實時應用程序較為有效。