一種面向節(jié)能的星載實(shí)時(shí)任務(wù)動(dòng)態(tài)調(diào)度算法研究

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

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

0 引言

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

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

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

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

1 問題建模

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

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

關(guān)于嵌入式處理器的定義如下：PE={pe1,…,pei,…,pey}是處理器單元的集合，y是處理器數(shù)量。pei表示第i個(gè)處理器。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)

由于任務(wù)vi取決于前置的數(shù)據(jù)輸出，當(dāng)且僅當(dāng)只有前置任務(wù)完成后才能運(yùn)行。

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

2 PVAP問題的解決方案

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

2.1 初始處理器分配策略

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

處理器調(diào)度算法(ASAP/ALAP)的實(shí)現(xiàn)過(guò)程如下：首先使用拓?fù)渑判颢@得目標(biāo)任務(wù)列表具有優(yōu)先級(jí)限制的DAG拓?fù)湫蛄校蝗缓笥?jì)算每個(gè)任務(wù)的最差執(zhí)行時(shí)間，在最早/最近狀態(tài)下，使用ASAP/ALAP算法根據(jù)任務(wù)的優(yōu)先級(jí)進(jìn)行調(diào)度，通過(guò)為同一處理器上的連續(xù)任務(wù)間插入模擬邊界來(lái)保證任務(wù)的執(zhí)行順序；最后使用ASAP/ALAP算法將任務(wù)圖中的每個(gè)任務(wù)分配給適當(dāng)?shù)奶幚砥鳎涂梢陨捎糜诮鉀QPVAP問題的新DAG。

ILP算法的實(shí)現(xiàn)如下：首先計(jì)算每個(gè)任務(wù)的執(zhí)行時(shí)間；然后采用整數(shù)線性規(guī)劃(ILP)調(diào)度算法[8]完成ILP的PVAP問題的數(shù)學(xué)表達(dá)式；最后使用LINGO 9.0軟件的非線性規(guī)劃解算器來(lái)獲得處理器分配策略。

2.2 電壓分配方案

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

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

2)S′0=CombineSubSolution(K)；

3)S0=S′0⊙B0；

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

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

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

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

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

采用PVAP_DP算法來(lái)解決電壓分配問題，如圖2(a)所示。首先要解決子問題，得到逆拓?fù)渑判?。之后為了解決公共節(jié)點(diǎn)的問題，需要列舉多個(gè)節(jié)點(diǎn)中可能存在的電壓分配方案。由于從逆拓?fù)漤樞虻牡?個(gè)節(jié)點(diǎn)(假設(shè)為v1)沒有子節(jié)點(diǎn)，所以可行解S1就是概率執(zhí)行列表B1。

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

2.3 LSR局部重啟搜索策略

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

3 實(shí)驗(yàn)

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

3.1 實(shí)驗(yàn)基準(zhǔn)

針對(duì)表1中2個(gè)基準(zhǔn)進(jìn)行了對(duì)比實(shí)驗(yàn)，使用隨機(jī)化任務(wù)圖生成器[7]得到任務(wù)圖，TGFF-1具有很長(zhǎng)的關(guān)鍵路徑，TGFF-2具有相對(duì)較短的關(guān)鍵路徑。

表1 實(shí)驗(yàn)任務(wù)圖的基準(zhǔn)描述

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

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

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

3.2 與ILP算法的比較

將本文中使用的算法和ILP進(jìn)行了比較。對(duì)使用TGFF-1標(biāo)準(zhǔn)的實(shí)驗(yàn)結(jié)果分別見表3，4。在表3，4中，“ILP1”“ILP2”和“PVAP_LSR”三列分別表示不含DVS的ILP、具有DVS的ILP和PVAP_LSR算法獲得的結(jié)果。“%I1”和“%I2”兩列分別代表本文中使用的算法相對(duì)于不具有DVS的ILP算法和具有DVS的ILP算法的改進(jìn)。在本文中，所有表中帶有“×”的條目表示相應(yīng)的分配未能生成有效的調(diào)度。

實(shí)驗(yàn)結(jié)果表明：PVAP_LSR算法在保證置信概率的同時(shí)，能夠提高能效。表3中 PVAP_LSR算法與ILP2算法相比，在置信概率分別為0.8，0.9和1.0時(shí)，平均(最大)能耗降低分別為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、無(wú)ILP的DVS和PVAP_LSR的能耗比較

表4 有ILP的DVS、無(wú)ILP的DVS和PVAP_LSR的能耗比較

對(duì)于TGFF-1基準(zhǔn)，圖3顯示算法相對(duì)于ILP1和ILP2的改進(jìn)。與ILP1和ILP2相比，PVAP_LSR算法在所有時(shí)間約束下能夠?qū)崿F(xiàn)更好的能效，橫坐標(biāo)為人為設(shè)定的時(shí)間約束，縱坐標(biāo)為調(diào)度算法執(zhí)行完的任務(wù)總能耗。ILP算法在一定的時(shí)間范圍內(nèi)可能無(wú)法找到近似最優(yōu)解。

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

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

基于TGFF-2標(biāo)準(zhǔn)的實(shí)驗(yàn)結(jié)果見表5。表中“A1”“A2”和“PVAP_LSR”分別表示由ASAP，ALAP和PVAP_LSR算法的結(jié)果，“%A1”和“%A2”分別表示相對(duì)于ASAP和ALAP算法的改進(jìn)效果。

圖4是PVAP_LSR相對(duì)于TGFF-1基準(zhǔn)的ASAP和ALAP調(diào)度的改進(jìn)。在對(duì)于TGFF-1基準(zhǔn)，PVAP_LSR在功耗方面可以獲得最佳的可變電壓調(diào)度。與基于ALAP的調(diào)度相比，PVAP_LSR相對(duì)于基于ALAP的調(diào)度分別實(shí)現(xiàn)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算法在所有時(shí)間約束下都具有更好的能效。

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

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

表5 ASAP, ALAP和PVAP_LSR基于TGFF-2基準(zhǔn)的能耗對(duì)比

4 結(jié)束語(yǔ)

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