非平穩(wěn)多任務(wù)下的動態(tài)功耗管理隨機(jī)策略

馬喜強(qiáng)，劉維亞，鄭喜鳳，程 鵬

（1.中國科學(xué)院長春光學(xué)精密機(jī)械與物理研究所，長春130033；2.中國科學(xué)院大學(xué)，北京100039）

0 引 言

隨著半導(dǎo)體技術(shù)的發(fā)展和嵌入式設(shè)備性能的提高，系統(tǒng)性能約束下的功耗問題成為嵌入式系統(tǒng)研究的焦點(diǎn)［1－3］。現(xiàn)階段，系統(tǒng)設(shè)計(jì)中通用的低功耗策略包括動態(tài)功耗管理（Dynamic power management，DPM）和動態(tài)電壓調(diào)節(jié)（Dynamic voltage scaling，DVS）。通常情況下，把DVS也作為DPM的一種來看待［4］。

DPM策略大體上可分為3類：①Timeout超時策略?；舅枷胧窃谪?fù)載經(jīng)過一段超時閾值后將負(fù)載置為低功耗狀態(tài)，包括固定超時閾值策略和自適應(yīng)超時閾值策略［5－8］。②Predict預(yù)測策略。其本質(zhì)是在做出決策前對本次空閑時間長度進(jìn)行預(yù)測，如果預(yù)測值足夠大，就直接將PMC（Power manageable component）切換到相應(yīng)的休眠模式［9］。③隨機(jī)Markov策略。通過建立Markov模型來描述系統(tǒng)設(shè)備操作請求和設(shè)備服務(wù)的隨機(jī)行為，把DPM決策問題看成一個受控馬氏鏈問題，從而更準(zhǔn)確地選擇決策時刻和設(shè)備轉(zhuǎn)換狀態(tài)。

Timeout超時策略具有原理簡單應(yīng)用廣泛的特點(diǎn)，但它是一種探索式策略。Predict預(yù)測策略一旦閾值預(yù)測不準(zhǔn)確，則可能會適得其反，增大功耗。隨機(jī)Markov策略根據(jù)建立的DPM決策模型可分為：基于馬爾可夫修正隨機(jī)過程的層次DPM模型［10］；基于連續(xù)時間的馬爾可夫決策過程DPM模型［11］；基于離散時間的馬爾可夫決策過程DPM模型［12］。以上策略均忽略了遠(yuǎn)距離歷史效應(yīng)，并且均未考慮多任務(wù)下系統(tǒng)負(fù)載的非平穩(wěn)問題。多任務(wù)下系統(tǒng)負(fù)載的非平穩(wěn)特性是指不同任務(wù)使用設(shè)備的方式和任務(wù)執(zhí)行的順序有差別而使設(shè)備負(fù)載表現(xiàn)出的隨機(jī)性?；跁r間索引的半馬爾可夫決策過程DPM模型［13］雖然加入了歷史事件的參數(shù)，但其本質(zhì)屬于一種隨機(jī)超時策略。

吳琦等從理論上證明了DPM最優(yōu)策略是確定性馬爾可夫策略［14］，并說明了超時策略具有很好功耗性能的原因，但其DPM模型忽略了狀態(tài)轉(zhuǎn)換間的延時，其DPM控制算法本質(zhì)上屬于超時策略，并且假設(shè)空閑時間長度服從Pareto分布，有一定的局限性。本文針對非平穩(wěn)多任務(wù)下的動態(tài)電源管理問題，提出了SMBSP（System message based stochastic policy）算法。該算法在分析系統(tǒng)任務(wù)的設(shè)備利用率的基礎(chǔ)上建立了半Markov隨機(jī)模型，并給出了該隨機(jī)模型下的在線優(yōu)化方法。半Markov控制過程模型對系統(tǒng)的動態(tài)特性描述精確，優(yōu)化算法不依賴系統(tǒng)參數(shù)的信息，自適應(yīng)性強(qiáng)。該算法能夠同時給出功耗轉(zhuǎn)換狀態(tài)及轉(zhuǎn)換時刻。通過OMAP－L137平臺動態(tài)電源管理的應(yīng)用試驗(yàn)可驗(yàn)證算法的有效性。

1 任務(wù)的設(shè)備利用率

線程（本文對線程和進(jìn)程不做區(qū)分）的執(zhí)行可以根據(jù)設(shè)備的應(yīng)用程序接口函數(shù)被調(diào)用地址進(jìn)行劃分，堆棧（stack）反映了線程的調(diào)用過程，可以采用棧深（stack depth）和返回地址（return address）來聯(lián)合區(qū)分設(shè)備唯一調(diào)用路徑［15］。堆棧深是指當(dāng)前棧指針（即當(dāng)前sp寄存器的內(nèi)容）與初始棧指針的差值，返回地址是指當(dāng)前鏈接寄存器中的內(nèi)容，這些可以從線程保存的上下文中獲取。這樣可以根據(jù)應(yīng)用程序接口函數(shù)調(diào)用的堆棧深度和返回地址來聯(lián)合預(yù)測任務(wù)的設(shè)備使用率，用U（d，r）表示任務(wù)的設(shè)備利用率（即與系統(tǒng)歷史堆棧深度和返回地址相關(guān)程度），定義如下：

式中：a為折扣因子，根據(jù)試驗(yàn)a取值為0.2～0.8［16］。

以U（d，r）為元素建立統(tǒng)計(jì)查找表，則查找表中保存的分布信息即為所需的各線程設(shè)備操作時間間隔分布，即當(dāng)前任務(wù)使用設(shè)備時間占設(shè)備總工作時間的比例，查找表結(jié)構(gòu)如圖1所示，圖中還給出了一個包括3個任務(wù)（telnet、ftp和gcc）和3個設(shè)備（UART、ADC和RAM）的查找表實(shí)例，每次操作請求到來時根據(jù)返回地址和堆棧深度匹配查找表，并根據(jù)實(shí)際的任務(wù)設(shè)備利用率更新設(shè)備查找表。

圖1 基于系統(tǒng)信息的設(shè)備查找表和實(shí)例Fig.1 Lookup table of a device corresponding to system message and an example

2 SMBSP算法

2.1 半Markov隨機(jī)模型

DPM隨機(jī)模型主要有離散時間馬氏決策過程、半馬氏決策過程和連續(xù)時間馬氏決策過程［17］。在離散時間馬氏決策過程中，忽略了時間因素，有一定的局限性，連續(xù)時間馬氏決策過程中的狀態(tài)轉(zhuǎn)移函數(shù)在系統(tǒng)的DPM問題中是很難確定的，而半馬氏決策過程對時間分布函數(shù)和代價(jià)函數(shù)的假設(shè)與DPM問題是一一對應(yīng)的，因此，半馬爾可夫隨機(jī)模型是最優(yōu)的DPM隨機(jī)模型［18］。本文DPM模型采用離散時間的半Markov決策模型，時間被描述為一連串離散值，假設(shè)設(shè)備有N種低功耗模式，分別由m0，m1，…，mN表示，則系統(tǒng)狀態(tài)變化過程可以由如下的半馬爾可夫過程描述：

式中各元素的定義如下：

（1）系統(tǒng)狀態(tài)集

（2）決策集A（i）是狀態(tài)為i∈S時的功耗管理器可用命令集合。

（3）Pij（a）為轉(zhuǎn)換概率，指當(dāng)前狀態(tài)為i采取決策a∈A（i）時，下一狀態(tài)為j的概率。

（4）T（·｜i，a，j）為從狀態(tài)i轉(zhuǎn)移到狀態(tài)j所需的時間分布函數(shù)，分布函數(shù)可以從上節(jié)建立的查找表中獲得。定義期望逗留時間為：

（5）r（u，i，a，j，t）是代價(jià)函數(shù)，指狀態(tài)為i采取決策a，且轉(zhuǎn)移時間為t的條件下，系統(tǒng)在時間段［0，u］中（u≤t）的功耗，其函數(shù)定義為：

式中：r1（i，a，j）為狀態(tài)轉(zhuǎn)換延時功耗；r2（i，a，j）為在轉(zhuǎn)移途中單位時間內(nèi)功耗。

（6）V為目標(biāo)優(yōu)化函數(shù)。

2.2 Markov策略優(yōu)化

通過定義1就把無限時段的半Markov決策過程轉(zhuǎn)換為有限時段的半Markov決策過程。

定義功耗和性能損失向量：

策略優(yōu)化的實(shí)質(zhì)是性能約束下的功耗優(yōu)化，本文采用折扣模型進(jìn)行分析。

對策略π和固定的折扣因子β（β＜1），系統(tǒng)在第n個決策周期的d和c的折扣期望為：

式中：約束值D為根據(jù)系統(tǒng)的工作歷史求出的性能約束的期望值。

折扣準(zhǔn)則下式（10）轉(zhuǎn)化為式（11）的線性規(guī)劃問題（Linear programming，LP）。

式中：fi，a為在i狀態(tài)下發(fā)出命令a的頻率；β表示系統(tǒng)繼續(xù)運(yùn)行的概率；為系統(tǒng)初始狀態(tài)為i的概率。

對線性規(guī)劃（11）采取兩階段法的單純形法求解fi，a，第1階段引入人工變量，構(gòu)造一個輔助的目標(biāo)函數(shù)，以求解原始線性規(guī)劃問題的初始基本可行解；第2階段迭代求解原始線性規(guī)劃問題的目標(biāo)函數(shù)，直到達(dá)到最優(yōu)解為止。最優(yōu)策略V（π＊）中的元素Vi，a可由式（12）計(jì)算得出：

3 試驗(yàn)結(jié)果

為了評估策略的節(jié)能效果和對性能的影響，本文采用OMAP-L137平臺作為試驗(yàn)對象，將本文算法與不同超時閾值的超時策略、預(yù)測策略和隨機(jī)策略進(jìn)行比較。OMAP-L137應(yīng)用處理器采用浮點(diǎn)DSP與ARM9相結(jié)合的架構(gòu)，提供用于聯(lián)網(wǎng)的各種外設(shè)，并運(yùn)行Linux或DSP／BIOS實(shí)時內(nèi)核以實(shí)現(xiàn)操作系統(tǒng)靈活性，還可在極低的功耗水平下工作，圖2給出了浮點(diǎn)DSP核的PSM（Power state machine）模型。各個狀態(tài)均標(biāo)有相應(yīng)的功耗，邊線上標(biāo)出了狀態(tài)轉(zhuǎn)換所需要的時間及切換功耗。

圖2 某型射擊諸元計(jì)算器的PSM模型Fig.2 PSM module of artillery firing data calculator

在本文的試驗(yàn)環(huán)境中，為驗(yàn)證效果產(chǎn)生了6個不同的任務(wù)列，各任務(wù)在N個時間段內(nèi)的設(shè)備利用率統(tǒng)計(jì)查找表如表1所示（一個時間段即一個決策周期，N取1000）。

每個任務(wù)列分別應(yīng)用以下電源管理策略（其中平衡時間［19］定義為Tbe）：

（1）Timeout：超時閾值＝Tbe的固定時限超時策略，達(dá)到超時時間值時直接轉(zhuǎn)為S2低功耗狀態(tài)。

（2）CTMDP［11］：連續(xù)時間Markov隨機(jī)策略。

（3）Predict［16］：Hwang的指數(shù)平均法（預(yù)測策略），取a＝0.5，使最近的歷史和先前的歷史有相等的權(quán)值，達(dá)到預(yù)測時間值時直接轉(zhuǎn)為S2低功耗狀態(tài)。

（4）Adaptive［5］：超時閾值＝Tbe的自適應(yīng)DPM策略，達(dá)到超時閾值時直接轉(zhuǎn)為S2低功耗狀態(tài)。

（5）DTMDP［12］：離散時間Markov隨機(jī)策略。

（6）Ours：本文策略。

表1 基于系統(tǒng)信息的時間序列概率統(tǒng)計(jì)Table 1 Time series of probability statistics based on system message

采用競爭率作為功耗評估指標(biāo)，延遲率作為性能指標(biāo)，命中率作為策略的預(yù)測效率指標(biāo)，分別定義如下：

式中：EA為當(dāng)前策略的能耗；Eno為無策略的能耗；Eopt為最優(yōu)離線策略下的能耗。

式中：TA為當(dāng)前策略下的總時間；Tno為無策略時的總時間。

競爭率ζ表示當(dāng)前策略相對于最優(yōu)策略的功耗效率，各策略的競爭率比較如圖3（a）所示，從圖中可以看出，本文策略的功耗效率是顯著的，平均值達(dá)到了0.57，高出自適應(yīng)策略3個百分點(diǎn)。CTMDP具有最低的功耗效率，這是因?yàn)镃TMDP策略是基于用戶到達(dá)服從指數(shù)分布的假定，導(dǎo)致長的空閑時間缺失和設(shè)備關(guān)閉次數(shù)增加，并且該策略還需要周期性的模型計(jì)算，消耗了大量的能量。

各策略的延遲率和命中率比較分別如圖3（b）和圖3（c）所示，Adaptive策略擁有較低的延遲率和較高的命中率，Predict策略的競爭率有較大的波動性。超時策略只有準(zhǔn)確選擇超時閾值時，節(jié)能效果才趨近于最優(yōu)，否則效果十分不理想，對同一系統(tǒng)進(jìn)行決策時，其估計(jì)值有可能不同，所以準(zhǔn)確的超時閾值是很難得到的。從整體上看，除本文策略延遲率小于0.1外，其他策略都超過了0.15。

圖3 各策略的競爭率、延遲率和命中率比較Fig.3 Comparison of competitive ratios，delay ratios and hit ratios for all policies

為了進(jìn)一步探討本文策略與實(shí)際負(fù)載的相互關(guān)系，產(chǎn)生了4個任務(wù)（兩個周期性任務(wù)和兩個非周期性任務(wù)），系統(tǒng)負(fù)載實(shí)際跟蹤曲線如圖4所示（只列出了自適應(yīng)超時策略和本文策略的效果對比）。從圖中可以看出本文策略有較好的魯棒性，這是因?yàn)楸疚牟呗允腔谌蝿?wù)級的，并且喚醒設(shè)備是事件驅(qū)動的，與具體的設(shè)備無關(guān)。

在考慮性能損失的條件下，假定初始時刻設(shè)備處于S1模式，無請求且隊(duì)列為空，則初始概率分布為b＝（1，0，0，0，0，…，0）T。設(shè)折扣因子β＝0.8，基于系統(tǒng)信息的時間序列概率統(tǒng)計(jì)如表1所示，則根據(jù)式（10）和（11）求解該線性規(guī)劃得到各決策周期（取前12個決策周期）內(nèi)的最優(yōu)策略如下：

圖4 系統(tǒng)負(fù)載實(shí)際跟蹤功耗比較Fig.4 Comparison of energy consumption with system trace

4 結(jié)束語

針對嵌入式系統(tǒng)的多任務(wù)環(huán)境下的非平穩(wěn)特性，提出了一種SMBSP算法，通過堆棧深度和返回地址來聯(lián)合區(qū)分設(shè)備調(diào)用路徑，采用基于任務(wù)級的隨機(jī)半Markov模型進(jìn)行決策。本文給出的隨機(jī)最優(yōu)算法不受空閑時間長度的分布限制，可以適用于一般分布，給出了確定決策時刻和選擇決策策略的方法，算法計(jì)算量小，在節(jié)能和系統(tǒng)性能之間找到了折衷切入點(diǎn)。需要指出的是，試驗(yàn)最后部分得到的策略適當(dāng)?shù)睾喕讼到y(tǒng)模型，其結(jié)果僅具有參考性；其次，基于系統(tǒng)信息的馬爾可夫模型是對一個復(fù)雜的隨機(jī)過程的概率估計(jì)，對于同一系統(tǒng)其估計(jì)值有可能不同，但通過本文算法得到的最終策略都是趨近于最優(yōu)的。試驗(yàn)結(jié)果表明：本文策略的延遲率小于0.10，競爭率可以達(dá)到0.57。有利于在嵌入式系統(tǒng)中應(yīng)用。

［1］Soteriou V，Peh L S.Dynamic power management for power optimization of interconnection networks using on／off links［C］∥11th Symposium on High Performance Interconnects，Stanford，C A，USA，2003：15-20.

［2］Kachroo P，Shukla S K，Erbes T，et al.Stochastic learning feedback hybrid automata for power management in embedded systems［C］∥Proceedings of the 2003 IEEE International Workshop on Soft Computing in Industrial Applications，Binghamton，N Y，USA，2003：121-125.

［3］Weng L C，Wang X J，Liu B.A survey of dynamic power optimization techniques［C］∥3rd IEEE International Workshop on System-on-Chip for Real-Time Applications，Calgary，Alberta，Canada，2003：48-52.

［4］Benini L，De Micheli G.System-level power optimization：techniques and tools［J］.ACM Transactions on Design Automation of Electronic Systems，2000，5（2）：115-192.

［5］Lu Y H，De Micheli G.Comparing system-level power management policies［J］.IEEE Design ＆Test of Computers，2001，18（2）：10-19.

［6］Krishnan P，Long P M，Vitter J S.Adaptive disk spin-down via optimal rent-to-buy in probabilistic environments［J］.Algorithmica，1999，23（1）：31-56.

［7］王毅，張德運(yùn)，馬新新，等.無線傳感器網(wǎng)絡(luò)傳感器節(jié)點(diǎn)動態(tài)功耗管理方法［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，2008，38（4）：880-885.

Wang Yi，Zhang De-yun，Ma Xin-xin，et al.Novel dynamic power management of sensor node in wireless sensor networks［J］.Journal of Jilin University（Engineering and Technology Edition），2008，38（4）：880-885.

［8］Helmbold D P，Long D D E，Sconyers T L，et al. Adaptive disk spin-down for mobile computers［J］. Mobile Networks ＆Applications，2000，5（4）：285-297.

［9］Srivastava M B，Chandrakasan A P，Brodersen R W.Predictive system shutdown and other architectural techniques for energy efficient programmable computation［J］.IEEE Transactions on Very Large Scale Integration（VLSI）Systems，1996，4（1）：42- 55.

［10］Ren Z Y，Krogh B H，Marculescu R.Hierarchical adaptive dynamic power management［J］.IEEE Transactions on Computers，2005，54（4）：409-420.

［11］江琦，奚宏生，殷保群.動態(tài)電源管理的隨機(jī)切換模型與策略優(yōu)化［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（5）：680-686.

Jiang Qi，Xi Hong-sheng，Yin Bao-qun.Stochastic switching model and policy optimization for dynamic power management［J］.Journal of Computer-aided Design ＆Computer Graphics，2006，18（5）：680-686.

［12］Benini L，Bogliolo A，Paleologo G A，et al.Policy optimization for dynamic power management［J］. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems，1999，18（6）：813-833.

［13］Simunic T，Benini L，Glynn P，et al.Event-driven power management［J］.IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems，2001，20（7）：840-857.

［14］吳琦，熊光澤.非平穩(wěn)自相似業(yè)務(wù)下自適應(yīng)動態(tài)功耗管理［J］.軟件學(xué)報(bào)，2005，16（8）：1499-1505.

Wu Qi，Xiong Guang-ze.Adaptive dynamic power management for non-stationary self similar requests［J］.Journal of Software，2005，16（8）：1499-1505.

［15］戚隆寧，張哲，黃少珉.多任務(wù)下I／O設(shè)備的動態(tài)功耗管理［J］.中國工程科學(xué)，2008，10（2）：60-65.

Qi Long-ning，Zhang Zhe，Huang Shao-min.Dynamic power management for I／O devices under multi-task environment［J］.Engineering Science，2008，10（2）：60-65.

［16］Hwang C H，Wu A C H.A predictive system shutdown method for energy saving of event-driven computation［J］.ACM Transactions on Design Automation of Electronic Systems，2000，5（2）：226-241.

［17］唐昊，吳玉華，周雷.半Markov決策過程的數(shù)值迭代優(yōu)化［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，2006，36（1）：108-112.

Tang Hao，Wu Yu-hua，Zhou Lei.Value iteration optimization for Semi-Markov decision processes［J］. Journal of Jilin University（Engineering and Technology Edition），2006，36（1）：108-112.

［18］胡奇英，劉建庸.馬爾可夫決策過程引論［M］.西安：西安電子科技大學(xué)出版社，2002.

［19］Lee W K，Lee S W，Siew W O.Hybrid model for dynamic power management［J］.IEEE Transactions on Consumer Electronics，2009，55（2）：656-664.