基于系統信息的動態功耗管理策略

李 波，董 嵐，任 玲

（吉林省六六一臺，長春 130119）

基于系統信息的動態功耗管理策略

李 波，董 嵐，任 玲

（吉林省六六一臺，長春 130119）

傳統的嵌入式系統動態功耗管理策略僅從設備的角度考察工作負載狀況，忽略了工作負載的應用特征，針對這一問題，本文從系統狀態的角度分析負載，提出非平穩系統下功耗策略改進方法SMBSP。

動態功耗管理；Markov決策過程；策略優化；嵌入式系統

1 引言

動態電源管理（DPM）根據系統工作負載的變化情況來有選擇地將系統資源設置為低功耗模式，以最少的元件或元件最小工作量的低耗能狀態來完成系統任務，從而達到降低系統能耗的目的。性能限制條件下的功耗最小化（或者功耗限制條件下的性能最大化）策略模型是一個受限的最優化問題。

DPM功耗管理策略大體上可分為三類：超時策略、預測策略和隨機策略。其中，超時策略（Timeout）是一種原理最為簡單，但同時也是應用最為廣泛的技術，它分為兩種情況：具有固定超時時限的策略（Fixed Timeout）和自適應超時策略（Adaptive Timeout），前者在設備經過一段固定的空閑時間段后會關閉目標設備，而后者會根據設備的歷史記錄來動態調整超時時限值。預測策略在開始時就對本次空閑時間長度進行預測，一旦預測值足夠大，在一開始就將PMC（Power Manageable Component）切換到相應休眠模式。隨機策略則通過設備操作請求和設備服務的Markov模型描述系統的隨機行為，從而能夠更準確地選擇設備將要進入的低功耗狀態。

近年來，關于隨機DPM策略的研究非?；钴S。對于非平穩系統，Chung等提出了基于滑動窗口的DPM算法；Li等應用基于強化學習的Q學習方法對參數未知系統進行優化，能夠有效地優化確定型策略，但不能很好地滿足帶約束優化問題的需要；S.Irany提出的是基于概率統計的超時策略，用窗口內的樣本直方圖近似計算分布從而確定最佳超時門限[18]。以上算法都假設空閑時間長度服從一定的概率分布，如幾何分布、負指數分布、重尾分布等，不適用于一般分布的情況，本文通過對設備負載的進一步分析，提出了SMBSP算法。

2 系統信息的獲取

參考基于程序計數器的訪問預測（PCAP）策略方法，線程的執行可以根據設備的API函數被調用地址進行劃分，棧（stack）反映了線程的調用過程，如圖1所示，采用棧深（stack depth）和返回地址（return address）來聯合區分調用路徑。其中，棧深是當前棧指針（stack pointer，即當前sp寄存器的內容）與初始棧指針的差值，返回地址是當前鏈接寄存器的內容，這些可以從線程保存的上下文中獲取，這樣可以根據函數調用的棧深和返回地址來預測設備操作的間隔時間。

基于系統信息建立統計查找表，其中保存了間隔時間的設備操作所對應的Ra和Sd以及間隔時間的分布（Ra，Sd分別表示返回地址和棧深），每次操作請求到來時根據Ra和Sd匹配查找表，并根據實際的間隔時間更新分布。屬于相同進程和線程組分類的操作序列具有相似性，因此可以共享同一張查找表。查找表中保存的分布信息即為所需的各進程設備操作時間間隔的分布。

3 SMBSP算法

3.1 Markov隨機模型

設PMC具有K種低功耗休眠模式，按功率由高到低排列分別由m1，m2，…，mk+1表示。PMC空閑并保持就緒模式記為m0，就緒模式是指PMC空閑并保持就緒。PMC工作狀態記為mk+1=mw。有w(m0)≥w(m1)≥…≥w(mk)≥w(mk+1)。

PMC狀態集合包括可長時間駐留狀態，用M=｛mi|i=0，1，…，K+1}表示。可將一次空閑時段內PMC狀態變化過程抽象為受控馬爾科夫鏈，由以下五元組描述：

式中，狀態空間S={(tk，mk)|n=0，1…，NMAX}，(t0，m0)開始狀態和（tMAX，mK+1）為終止狀態，當PMC轉變為mK+1模式，則保持mK+1模式，直到tMAX，時間t可以上節中建立的查找表獲得；A(s)是狀態為s∈S時功耗管理器可用命令集合；Pst(a)是轉換概率，指當前狀態為s采取動作a∈A(s)時，下一狀態為t的概率；c(s，a)是代價函數，指狀態為s采取動作a時，在隨后間隔時間內的功耗；v為目標優化函數，指空閑時間總功耗的數學期望，若設備處于模式i時的平均功耗為ai，從模式i進入正常工作狀態的轉換能耗為bi，設備操作的間隔時間服從概率密度函數為FD(t)的分布，設置從模式i轉換到狀態i+1的超時門限為k，則空閑時間總功耗的數學期望為

3.2 Markov策略優化

定義功耗和性能損失向量

策略優化實質上是性能約束下的功耗優化問題，本文采用折扣模型進行分析。

對策略π和固定的折扣因子β（0＜β＜1），系統在第n個決策周期的d和c的折扣期望可用式（5）表示

式中，p(1)表示系統在初始時刻t1的狀態概率分布；表示在策略π下，從決策周期0到周期n-1的轉移矩陣。因此，性能約束下的功耗優化問題可用式（6）描述。

折扣準則下式（6）轉化為式（7）的線性規劃問題（LP）。

4 實驗結果

為了評估策略的節能效果和對性能的影響，本文用VC6.0仿真環境來驗證隨機最優算法的效果，并將其與timeout，predictive算法進行比較。采用某型諸元計算器作為實驗對象，圖2給出了某型諸元計算器的PSM（Power State Machine）模型。各個狀態均標有相應的功耗，邊線上標出了狀態轉換所需要的時間及切換功耗。

在本文的仿真環境中，為驗證效果產生了六個不同的任務列，基于系統信息的時間序列概率統計查找表如表1所示，決策時刻即為表中的各時間點。

每個任務列分別應用以下電源管理策略（其中平衡時間Tbe=80，時間點數N=12）：

（1）Timeout1：超時閾值=80（等于Tbe）的固定時限超時策略。

（2）Timeout2：超時閾值=120（等于1.5倍Tbe）的固定時限超時策略。

（3）Predict：Hwang的指數平均法[11]（預測策略），取a=0.5，使最近的歷史和先前的歷史有相等的權衡值。

（4）Adaptive1：超時閾值=80的自適應DPM策略。

（5）Adaptive2：超時閾值=120的自適應DPM策略。

（6）This paper：本文策略。

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

延遲率（TA為當前策略下的總時間，Tno為無策略時的總時間）。

命中率η=預測正確次數/預測總次數。

競爭率反映了當前策略相對于最優策略降低功耗的效率，值越高表示節能效果越接近最優策略，各策略的競爭率比較如圖3所示，Timeout策略的超時閾值大小決定了競爭率結果，如果選擇不準確則節能效果十分不理想。Predict策略波動很大，而Adaptive策略則相對比較穩定，這是因為Predict策略預測值有比較大的延遲性，而Adaptive策略則加入了一定的自適應機制。本文策略的競爭率達到了0.57。在不考慮性能損失的條件下，選擇超時閾值準確的超時策略和本文策略的節能效果都是趨近于最優的。

各策略的延遲率和命中率比較分別如圖4和圖5所示，Adaptive策略擁有較低的延遲率和較高的命中率，Predict策略雖然有最高的命中率但同時有最高的延遲率，這也導致了它的競爭率有較大的波動性。超時策略只有準確選擇超時閾值時，節能效果才趨近于最優，否則效果十分不理想，但對同一系統進行統計時，其估計值是可能不同的，所以準確的超時閾值是很難得到的。從整體上看，除本文策略延遲率小于0.1外，其他策略都超過了0.15，主要原因是其他策略均沒有引入決策時刻機制。從圖中可以看出對同一系統進行系統信息的時間序列概率統計時，其估計值是可能不同的，策略可能不是最優的，但通過本文算法得到的最終策略都是趨近于最優的。

在考慮性能損失的條件下，假定初始時刻SP處于S1模式，無請求且隊列為空，則初始概率分布為b=(1,0,0,0,0,…,0)T。設折扣因子β=0.8，時間點數N=12，則根據公式（7）求解該線性規劃得到各時刻點最優策略如下

5 結束語

針對嵌入式系統的多任務環境，本文提出了一種基于系統信息的隨機策略（SMBSP），通過任務的調用和堆棧信息分析任務對設備的訪問模式，采用基于概率統計的隨機模型進行決策。本文給出的隨機最優算法可以在節能和系統性能之間找到恰當的折衷切入點，在二者之間取得較好的平衡，算法計算量小，適合在嵌入式系統中應用。需要指出的是，實驗最后部分通過該算法得到的策略適當地簡化了系統模型，其結果僅具有參考性；其次，基于系統信息的馬爾可夫模型只是對一個相當復雜的隨機過程的大致估計，對于同一系統其估計值是可能不同的，但通過本文算法得到的最終策略都是趨近于最優的。

System Message based Dynamic Power Management Policy

Li Bo, Dong Lan, Ren Ling
(The 661th Station Jilin province, Changchun, 130119)

Traditional dynamic power management policies of embedded system only focus on equipment workload situation from the perspective of device, and ignore the application features of the workload. An improved method called SMBSP (System message based stochastic policy) is proposed on the basis of analyzing workload according to system state.

Dynamic power management; Markov decision processes; Policy optimization; Embedded system

10.3969/J.ISSN.1672-7274.2015.06.009

TK01+8

B

1672-7274（2015）06-0054-04