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

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

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

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

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

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

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

7、。衰退因子n權(quán)衡了負(fù)載響應(yīng)的及時(shí)性與穩(wěn)定性，當(dāng)n越小時(shí)，系統(tǒng)響應(yīng)負(fù)載的變化越快，但系 統(tǒng)的頻率/電壓變化波動(dò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ù)測(cè)方面，它試圖在本地行為以及一個(gè)相當(dāng)長(zhǎng)時(shí) 期里的平均值之間尋找到一個(gè)黃金平均值。它有一個(gè)非負(fù)的實(shí)參，本地行為的權(quán)重將隨 著該參數(shù)的增加而增加。通過(guò)給本地行為指定一個(gè)最優(yōu)可能權(quán)值，來(lái)發(fā)現(xiàn)該算法的一個(gè)

8、 最優(yōu)預(yù)測(cè)值。按預(yù)測(cè)設(shè)置模型來(lái)說(shuō)就是：一、查找最近12個(gè)運(yùn)行百分比，最近的三個(gè)構(gòu) 成短期預(yù)測(cè)數(shù)，余下的9個(gè)構(gòu)成長(zhǎng)期預(yù)測(cè)數(shù)。對(duì)接下來(lái)的運(yùn)行百分比預(yù)測(cè)為一個(gè)加權(quán)平 均值，在這個(gè)加權(quán)平均值中短期數(shù)據(jù)需乘以一個(gè)權(quán)重，也即是前面所提及的參數(shù)；二、 設(shè)置一個(gè)盡可能快的速率來(lái)完成預(yù)測(cè)工作。例如：假設(shè)權(quán)重值為4,最近12次的運(yùn)行百 分比是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ù)測(cè)方面比較薄弱，它只是簡(jiǎn)單地將速率平滑到全局的平均 使用率上。該算法需要一個(gè)輸入?yún)?shù)，而且必須是0-1之間的常數(shù)。算法分為兩步：一、 預(yù)測(cè)一個(gè)常數(shù)級(jí)的運(yùn)行百分比；二、設(shè)置一個(gè)速率使其能足夠快完成預(yù)測(cè)出的新的及遺 留的任務(wù)。該思想希望將運(yùn)行百分比保持的盡量平滑，不至于出現(xiàn)突變。由于速率總是 設(shè)置成足夠快來(lái)完成預(yù)測(cè)的新任務(wù)和遺留任務(wù)，所以所有任務(wù)的延遲都不會(huì)超過(guò)一個(gè)時(shí) 間間隔。這一思想也被應(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ù)級(jí)的平滑方式，試圖通過(guò)加了權(quán)重的平均值來(lái)預(yù)測(cè)下一個(gè)時(shí)間間隔的運(yùn)行百分比。 例如：假設(shè)間隔長(zhǎng)度為0.01秒，權(quán)重值為2/3,先前的運(yùn)行百分比是P(t),P(t-1)，P(t-2)，.， 預(yù)測(cè)的新運(yùn)行百分比是1/3*P(t)+2/9*P(t-1)+4/27*P(t-2)+.。注：權(quán)重值定義的注意點(diǎn)是 應(yīng)與間隔長(zhǎng)度基本保持獨(dú)立。8、CYCLE：提出者Kinshuk Govil，文獻(xiàn)Comparing A

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

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

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