動態(tài)電源管理算法總結(jié)

1、動態(tài)電源管理經(jīng)典算法總結(jié)written by: zengyi 2008-12-4操作系統(tǒng)級動態(tài)電源管理的提出者是Mark Weiser，在其1994年發(fā)表的一篇名為 Scheduling for Reduced CPU Energy的文章中首次提出節(jié)能和操作系統(tǒng)級的電源管理思 想。在其后的一些年中Kinshuk Govil在操作系統(tǒng)級電源管理方面也做出了比較大的貢獻(xiàn)， 在其發(fā)表的名為Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU一 文中對Mark Weiser提出的算法進(jìn)行了改進(jìn)，創(chuàng)造出了一些自己的方法。在國內(nèi)

2、，對操作系統(tǒng)級動態(tài)電源管理的研究開始地比較遲；從閱讀文章來看：科學(xué)院、 中科大、國防大學(xué)、復(fù)旦大學(xué)等在這方面有著比較前沿的研究。相對于國外的研究來說，中 國的研究似乎更注重于用繁雜成型算法來優(yōu)化功耗：如采用隱馬模型、蟻群算法等。一、動態(tài)電壓調(diào)節(jié)算法：1、 OPT(unbounded-delay perfect-future):提出者mark weiser，文獻(xiàn)scheduling for reduced cpu energy， 主要思想：是使用整個蹤跡數(shù)據(jù)(意思也就是說要知道將來的所有時間里cpu使用情況)，將運行時間延 伸以填補所有的空閑時間周期。該算法能達(dá)到的最大可能節(jié)省通常被最小速率所限

3、制。這個算法既不 實際也不合乎邏輯。不實際是因為它需要任務(wù)在將來周期內(nèi)的一些完美數(shù)據(jù)，同時它也假設(shè)空閑能被 運行時間所填補。不合乎邏輯是因為在各個進(jìn)程運行的過程中產(chǎn)生了大量的延遲，而沒有很好地管理 好實時進(jìn)程和交互進(jìn)程的響應(yīng)時間，如用戶擊鍵或網(wǎng)絡(luò)包來臨了都可能會無限制地等待下去。2、FUTUR(Ebounded-delay limited-future)：提出者mark weiser，文獻(xiàn)scheduling for reduced cpu energy， 主要思想：是OPT算法的一個改進(jìn)，只不過它所指的將來縮短為了一個小的時間窗口，在那個時間窗 口內(nèi)優(yōu)化能耗，這樣的話將不會拖延任務(wù)的響應(yīng)時間

4、；同樣，它也假設(shè)下一間隔的所有空閑時間可以 被消除，除非達(dá)到了 cpu的最小工作頻率。而且當(dāng)時間窗口達(dá)到400秒的時候，該算法跟OPT幾乎是一 樣的效果。該算法也是不實際的，原因也是因為它使用了將來的信息；但它卻是合理的，因為沒有一 個實時響應(yīng)的延遲會超過一個時間窗口。(意思是說只要時間窗口定義恰當(dāng)，還是可以滿足一些實時響 應(yīng)的要求，至少不會出現(xiàn)無限制地延遲)。3、PAST(bounded-delay limited-past)：提出者mark weiser，文獻(xiàn)scheduling for reduced cpu energy，是一個能實現(xiàn)的FUTURE版本。與FUTURE算法往前看一個固定

5、窗口相反，該 算法是往后看一個固定大小的時間窗口，同時假設(shè)下一時間窗口的工作量跟上一窗口是 相像的。主要思想是根據(jù)前一個時間片上遺留的工作和處理器使用率來設(shè)置下一個時間 片上處理器的頻率和電壓。將時間劃分為固定長度的時間片，在每個時間片開始的時候， 計算前一個時間片上處理器使用率，預(yù)測在下一個時間片上處理器會同樣忙。算法使用 處理器使用率的兩個門限值來決定在下一個時間片上是增加、減少、還是保持當(dāng)前的處 理器頻率。如果預(yù)測的使用率低于下門限值，就降低處理器頻率，高于上門限值就增加 處理器頻率，否則保持處理器的頻率不變。具體調(diào)節(jié)多少頻率一般是與使用的處理器相 關(guān)，處理器可用的頻率并不是連續(xù)變化的，

6、而是幾個分離的頻率點，通常的調(diào)節(jié)是每次 增加或減少一擋頻率。4、 AVGn： 提出者Kinshuk Govil，文獻(xiàn)Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU，主要思想是與Past算法類似，只是在預(yù)測下一個時間片上的處理器 的使用率時有所不同。采用了指數(shù)平均數(shù)的方法，預(yù)測下一個時間片上的使用率是以前 所有時間片上的使用率的加權(quán)平均，每個時間片上的權(quán)隨著時間的向前推移而幾何減 小。即令n是指數(shù)平均的衰退因子，Ut是時間片t上的實際的使用率，Wt是該區(qū)間上預(yù)測的使用率，則AVGn算法預(yù)測時間片t上的使用率為一1

7、。衰退因子n權(quán)衡了負(fù)載響應(yīng)的及時性與穩(wěn)定性，當(dāng)n越小時，系統(tǒng)響應(yīng)負(fù)載的變化越快，但系 統(tǒng)的頻率/電壓變化波動越大；n越大，系統(tǒng)響應(yīng)負(fù)載的變化就越慢。跟我自己看的有些 出入。不知道是不是另一算法。5、LongShort:提出者Kinshuk Govil,文獻(xiàn)Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU，該算法更注重于預(yù)測方面，它試圖在本地行為以及一個相當(dāng)長時 期里的平均值之間尋找到一個黃金平均值。它有一個非負(fù)的實參，本地行為的權(quán)重將隨 著該參數(shù)的增加而增加。通過給本地行為指定一個最優(yōu)可能權(quán)值，來發(fā)現(xiàn)該算法的一個

8、 最優(yōu)預(yù)測值。按預(yù)測設(shè)置模型來說就是：一、查找最近12個運行百分比，最近的三個構(gòu) 成短期預(yù)測數(shù)，余下的9個構(gòu)成長期預(yù)測數(shù)。對接下來的運行百分比預(yù)測為一個加權(quán)平 均值，在這個加權(quán)平均值中短期數(shù)據(jù)需乘以一個權(quán)重，也即是前面所提及的參數(shù)；二、 設(shè)置一個盡可能快的速率來完成預(yù)測工作。例如：假設(shè)權(quán)重值為4,最近12次的運行百 分比是0、0.3、0.5、1、1、1、0.8、0.5、0.3、0.1、0、0；于是我們可以設(shè)置速率為： (0+0.3+0.5+1+1+1+0.8+0.5+0.3+4*(0.1+0+0)/(9+4*3)=0.2766、 Flat： 提出者Kinshuk Govil, 文獻(xiàn)Compar

9、ing Algorithms for Dynamic Speed Setting of a Low Power CPU，該算法在預(yù)測方面比較薄弱，它只是簡單地將速率平滑到全局的平均 使用率上。該算法需要一個輸入?yún)?shù)，而且必須是0-1之間的常數(shù)。算法分為兩步：一、 預(yù)測一個常數(shù)級的運行百分比；二、設(shè)置一個速率使其能足夠快完成預(yù)測出的新的及遺 留的任務(wù)。該思想希望將運行百分比保持的盡量平滑，不至于出現(xiàn)突變。由于速率總是 設(shè)置成足夠快來完成預(yù)測的新任務(wù)和遺留任務(wù)，所以所有任務(wù)的延遲都不會超過一個時 間間隔。這一思想也被應(yīng)用到其他算法中。7、 AGED_AVERAGES:提出者Kinshuk Govi

10、l,文獻(xiàn)Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU，與L ONG_SHORT 方法不一樣，該算法采用了一種 指數(shù)級的平滑方式，試圖通過加了權(quán)重的平均值來預(yù)測下一個時間間隔的運行百分比。 例如：假設(shè)間隔長度為0.01秒，權(quán)重值為2/3,先前的運行百分比是P(t),P(t-1)，P(t-2)，.， 預(yù)測的新運行百分比是1/3*P(t)+2/9*P(t-1)+4/27*P(t-2)+.。注：權(quán)重值定義的注意點是 應(yīng)與間隔長度基本保持獨立。8、CYCLE：提出者Kinshuk Govil，文獻(xiàn)Comparing A

11、lgorithms for Dynamic Speed Setting of a Low Power CPU，應(yīng)該說以前的一些算法都比較的久經(jīng)世故。然而在對運行百分比圖 的觀察中，我們發(fā)現(xiàn)這些運行百分比似乎都是周期性出現(xiàn)的，這一規(guī)律是否可以被我們 所利用呢？我們是否能找到一個這樣的X，使得在x開始處的長度上與2x開始處的一個x 長度上兩者圖形幾乎一樣呢？為此我們定義了一個變量error-measure，該變量的計算是 這樣的，對于兩個一樣長的跟蹤數(shù)據(jù)，對應(yīng)位相減后取絕對值再相加的平均值?？雌饋?有點拗口，讓我們來舉一個例子：假設(shè)最近的8個數(shù)據(jù)是0-0.4-0.8-0.1-0.3-0.5-0.7

12、-0.x取為 4，于是我們可以將這八個數(shù)據(jù)分成兩組，0-0.4-0.8-0.1和0.3-0.5-0.7-0，最后error-measure 計算如下：(I0-0.3I+I0.4-0.5I+I0.8-0.7I+I0.1-0I)/4=0.15。由此我們可以很容易看出， error-measure的值越小，兩者的相似度越高。于是我們可以通過具有最小e rror-measure 值的區(qū)間預(yù)測下一個周期內(nèi)的運行百分比。但如果算出來的e rror-measure都大于0.2，則 將運行百分比預(yù)測為一個常數(shù)。(在有些地方，該算法也叫著自相似性，應(yīng)該說有著一定 的道理，不過由于用戶的參與，使得隨機性很大，有時

13、根本就沒什么規(guī)律)9、PATTERN：提出者Kinshuk Govil，文獻(xiàn)Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU，主要思想是將先前的運行百分比轉(zhuǎn)變成一種樣式，例如我們可以 定義字母表中囹代表00.25的運行百分比，B代表0.250.5, C代表0.50.75, D代表0.751； 于是假設(shè)我們有這樣一個跟蹤序列0-0.13-0.28-0.33-0.52-0.79，那么我們可以轉(zhuǎn)變成這樣的一個樣式AABBCD。往后查看如果發(fā)現(xiàn)跟在該樣式后面的是一個A的話，那么我們可 以猜測下一間隔的運行百分比為0.125(A的中間值)。10、Peak:提出者Kinshuk Govil,文獻(xiàn)Comparing Algorithms for Dynamic Speed Settingof a Low Power CPU，主要思想算法預(yù)測當(dāng)前的負(fù)載將伴隨一個窄峰值，即預(yù)測一個上 升的運行百分比將對稱地下降，而下降的運行百分比將繼續(xù)下降。