功耗管理中的動態電壓調整綜述
2007-12-31 00:00:00王彪王小鴿
計算機應用研究 2007年8期
摘要：綜述了十年來動態電壓調整的相關文獻，對各種策略進行分類介紹；對DVS問題的數學模型進行提煉，抽象出它們解決問題的思路，評價它們的優缺點，并簡述典型策略的實現。
關鍵詞：動態電壓調整； 電源管理； 時間片； 任務調度
中圖分類號：TP316.2文獻標志碼：A
文章編號：1001－3695(2007)08－0008－05
功耗問題日益成為人們關注的熱點，這主要是基于如下兩種原因：無線、移動終端設備越來越普遍，并且功能越來越強大，這些設備使用電池供電，而電池供電量的增長遠遠落后于這些設備功耗的增長；發熱問題越來越嚴重，已經開始制約性能的進一步增長[1]。人們由過去單純追求性能的增長變為追求性能與功耗的平衡。
典型的CMOS工藝制造的芯片，其消耗的電流主要分為動態電流(dynamic current)與漏電流(leakage current)兩個部分。一般而言，動態電流占絕大多數。但隨著制造工藝的進步，漏電流所占的比重越來越大。動態部分的功耗計算公式[2]為
其中：CL為負載電容；N為網絡活躍晶體管數目，即所謂的活躍系數；Vdd為工作電壓； f為頻率。漏電流的計算比較復雜，但降低頻率對它的影響更大[2，3]。
動態電壓（頻率）調整正是基于以上事實：功耗與頻率和電壓的平方成正比關系。這意味著，若能降低CPU芯片的工作電壓，則能顯著地降低功耗。當然，工作電壓降低，晶體管的狀態變換速度必然變慢，這要求降壓的同時要降頻。DVS正是根據系統的運行負載，動態調整頻率與電壓，以達到既節省能量又不損傷性能的目的。
市場上出售的供移動設備使用的CPU現在幾乎均具備了動態調整頻率與電壓的功能，如Intel的XScale、Transmeta的Crusoe、AMD的Athlon。這為動態電壓調整提供了物質基礎[4~6]。
關于在何處實現DVS至今仍是一個開放問題[7]，絕大多數的DVS實現基于操作系統。衡量一個DVS策略的好壞有如下幾個標準：a）節能水平。無疑這是最重要的標準。b）對性能的影響水平。降低頻率肯定對性能有影響，但要做到終端用戶感覺不到，關鍵應用不受影響。c）盡量做到無須應用程序參與。這是由絕大多數已存應用程序缺乏這方面考慮的現實原因決定的。d）盡量做到對操作系統的侵入最少。動態調頻是一個底層機制，與硬件有莫大的關系，不可能不影響現有系統，但可以做到少一些影響。
1各種DVS策略介紹與分析
DVS策略關注的是CPU在什么時間以什么速度運行負載。
早期的研究采用基于時間片的策略。Weiser等人[8]最早提出把時間分為固定長度的時間片，在各個時間片把速度設置為保證大部分任務能在此時間片的末尾完成。稍后Chan等人[9]改進了Weiser的策略，把它分為兩個部分，即預測與設置。一個時間片開始時，預測部分預測這個時間片CPU的工作量（忙碌程度，往往用CPU使用率來表征，即此時間片內非空閑時間的比率）；然后設置部分利用這些信息設置該時間片的速度。但是其共同缺陷是要求知道未來的CPU利用率，以此得出最優的調度，所以只有理論上的意義。稍后Pering等人[10]及Grunwald等人[11]都指出了這個缺點，并提出了他們的預測模型與設置策略（1．1節將詳細描述）。他們比較了自己的以及另外的一些策略，得出的結論是悲觀的，認為不可能做到既節約能量又不損害性能。但這種思想還是應用在了Transmeta的LongRun技術上。它簡單地間隔固定時間測量CPU的利用率，然后根據利用率增加或減少CPU的頻率[6]。
Pering等人及Grunwald等人在比較上述策略時提出了時限的想法，認為若一個任務的時限能得到滿足，那么運行快慢無關緊要，從而引出了基于任務的DVS策略。它的關鍵在于怎樣獲取各個任務的時限與周期需求，從而求得各個任務運行中的最佳頻率設置。Flautner等人[7，12]、Lorch等人[13~16]和Yuan等人[17]分別在解決這些問題時提出了自己的策略。其主要不同是任務分類與動態的周期需求探測所用的方法不同。
除了上述分類方法，還可以將這些策略分類為通用系統上與實時系統上的策略。本文關注的主要是通用系統策略與軟實時策略，主要原因在于硬實時策略往往需要應用告知系統其明確的最壞執行時間與周期需求，而大部分手持設備應用也不需要硬實時。
1．1基于時間片的策略
Flat策略與copt策略作為兩種參考策略出現。前者把CPU的頻率限定在某個常數水平，即沒有電壓與頻率的改變。后者只有理論上的意義，因為它假設知道將來的性能要求，從而可以作出最優調度；具體做法一般是測量實際數據，然后計算出在這種情況下的最優能耗[9]。
Past[8]是第一個比較實際的策略，其預測部分只分析前1個時間片的CPU使用率。根據某種預設的閾值，若超過則設置部分開始提速；若低于則減速。它基于利用率連續的假設，簡單地用前1個時間片的利用率預測當前利用率。在實現時作了優化，主要是考慮時間片長度、各個時間片里溢出的情況（即沒有完成的周期數）等。這種簡單的預測模式在運行周期變化比較平穩的系統負載時較為理想，所以根據一批基準測試得出的結果還是不錯的。 Chan等人[9]隨即試著在實際系統中實現這些策略，發現效果不理想，并提出了如下幾個新的策略：
a)AVG計算以前時間片中利用率的指數移動平均值。具體而言是在每個時間片用上個時間片的利用率與以前的平均利用率的平均作為當前時間片調度的依據；在計算時使用一個權值weight，方法為(weight×old+new)/(weight+1)。
b)Long_short試圖找到短期行為與長期行為的結合點。它維護兩個利用率，即前面3個時間片的平均利用率和前面12個時間片的平均利用率；然后以兩者的加權平均為基礎設置當前時間片的頻率。Aged_average是long_short策略的一種改進，基本想法是越往前的時間片所占的權重越低。
c)Cycle是flat策略的一種改進，它檢查最后16個時間片的利用率，看是否存在某種周期性，當然這個周期性只要大致精確即可。如果存在這種周期性，則在當前時間片延續這種周期性；否則用常數的頻率設置。Pattern是cycle的一種泛化，它把利用率分成四個等級，即0~0．25、0．25~0．5、0．5~0．75、0．75~1．0；然后尋找與最后模式串相同的模式，并用以前的模式來預測當前時間片的利用率并設置頻率（實質是把cycle的條件降低，使得在cycle中不算周期的利用率序列也能算上）。
d)Peak是一種考慮窄的峰值性能需求的策略，它采用某些啟發式算法。例如，若利用率正在下降，則認為它會繼續下降；若利用率已經很高，則預測它會經過其峰值然后下降一點；若利用率很低且變化平坦，則預測它會保持低而平坦等等。
Chan等人在工作站上的模擬結果表明，peak算法是比較好的一個，并認為復雜的預測策略不可取，而試著平滑速度改變的簡單策略則在總體上占優。同時從結果可以看出，上述種種算法實質上都表現不佳，因為與沒有調度（flat）比，大部分算法反而有下降。Grunwald等人認為這是由于沒考慮到任務的差異性而造成的，且基于時間片的調度算法不可能做到既節能又不損害性能。
1．2基于任務的策略
由于Pering和Grunwald等人的研究結論，研究者開始轉向基于任務的策略，主要考慮任務所需要的CPU時間（周期需求）與任務必須完成的時限。因為只要滿足時限要求，則可以認為性能要求得到滿足，而任務并不是每時每刻都需要峰值速度，這是調整電壓與頻率的前提。
1.2.1問題的形式化描述
對上面模型的各個假設或參數略為調整，便可以得出以下各個策略：如若令任務數目為1，則是pace策略；若取消任務時限為常數的假設，則是vertigo策略；若任務種類限制在多媒體應用，則是graceos策略等。
上面模型假設了任務的周期需求分布已知，但在實際系統中，這個需求是未知的，采用何種探測方法來盡可能精確的求得這個需求分布是各個算法(策略)的主要區別。
1.2.2Pace系列策略
Pace策略是一種調整算法，它本身不能作為一種獨立的策略，而是改進已存策略。它基于兩個事實：若兩個DVS策略在pace調整后都能在時限前完成，則兩個算法的性能相同；在保證時限的前提下，任務執行采用不同的頻率可以節約能量。該算法的關鍵是在不改變已有算法的時限前完成周期數，也不改變時限后剩余周期數，而僅僅改變在兩個階段中的頻率。
Pace策略假設了速率連續可調，即把速度假設為時間（或者已完成周期數，稱為工作）的連續函數（本文給出的模型已經去除了這個不合理的假設）。但是速率不可能連續可調，所以通過一個任務執行周期內分階段設置速率以達到次優化的目標，這涉及到兩個問題：
a)如何選擇轉折點，即各個階段如何劃分。在上述模型的基礎上，用如下公式來選擇：
b)速率如何設置。首先用幾種傳統的基于時間片算法中常用的策略（AGED、long_short等）來處理采樣任務所需的周期數，這一般是一個周期數的帶權和；然后根據這些樣本來確定一個任務的需求分布。在確定這些分布時試驗了Gamma分布、正態分布等常用方法（即假設這個任務的需求分布屬于這些分布，然后用樣本值估算確定一個分布的具體參數，如正態分布的期望與方差，從而確定一個具體分布）。
所以只要給出了階段與分布，就可以給出調度。這就是pace算法的關鍵所在。
完整的基于pace的DVS策略是稍后提出的rightspeed策略，并在基于Transmeta Crusoe CPU和AMD CPU的Windows 2000機器上實現了該策略。筆者主要考慮交互式任務，用上述啟發式算法確定各個不同類型的UI事件（如擊鍵、鼠標移動、鼠標擊鍵等）的開始與結束，從而得出其性能要求分布與時限要求。筆者用改進的pace算法求得最優調度。改進主要指根據離散而不是連續的可調度頻率范圍、功耗與頻率的非線性關系等因素得出。
1.2.3Vertigo策略
Flautner等人[12]提出把任務分類，并修改OS內核來自動獲取任務所需的CPU時間與時限。其核心思想即是通過在線（運行時）的監控來獲取任務信息，通過動態調整來適應任務性能要求的變化。
他們把任務分為交互性任務與周期性任務，又把周期性任務分為生產者任務與消費者任務。在交互性任務中，計算出全速運行所需的時間和一個感觀閾值（也就是一般用戶能接受的反應時間。根據一般的用戶行為研究給出為50~100 ms）；兩者的比即是性能因子（設置的頻率為最高頻率乘以性能因子）。這是事后計算，為的是預測下一個時間到來時的性能因子。
至于周期性任務，則簡單地把速度減慢到在下一個周期開始或與之對應的消費者任務開始時執行完。值得注意的是，若同時有周期性任務與交互性任務，則在一個交互性任務開始時，若其預測的性能因子高于周期性任務的性能因子，取較高的值。
Vertigo把策略分為三個級別。最頂上的策略用上述的交互式算法來選擇預測值。具體做法是監控某個事件，以作為一個時間處理期的開始，然后看看此事件所激發的任務與哪些任務聯系；當所有與這個事件的有關處理工作都完成后，認為這個事件期完成。設置兩個時限，一個是可忽略時限，一般設為5 ms；這是指那些典型的小型事件（如輸入時擊鍵、普通的鼠標移動等），低于這個時間完成的事件均認為可以用最低的CPU速度來執行，從而不需要進入加速期。再設置一個感觀時限，一般定為50 ms；若超過這個時限，則全速運行，以不損傷用戶感觀。在每個事件期執行完成后，計算其全速運行的總時間，用指數遞減平均值的方法求得下個事件期的預測運行時間。若下個事件期的執行時間超過可忽略時限，則用計算出的預測時間與感觀時限的比來設置性能因子。
中間層的策略是用應用程序指定的方法來得到時限與性能需求（這在實時系統中普遍采用，這是操作系統設計的趨勢，應用程序參與的電源管理會更直接而有效）。但本文只是用于調試目的，因為目前所有應用（通用系統或PDA應用）幾乎都不考慮功耗要求。
最底層的策略是采用任務級的時間片算法。這里與傳統時間片算法的主要區別是粒度不同，不是全局地用一個系統的CPU利用率，而是在任務級采用。這樣的預測往往精確得多。因為就任務而言，其周期性顯然強過一個通用的系統。其次就是直接采用預測時間來設置速率，而不是像傳統時間片算法那樣把一個策略分為兩部分，典型的設置策略是在以前的頻率水平上加或減去一個人為的值。這個人為的值也影響了傳統時間片算法的精確性。
具體而言，一個任務從開始執行到其主動讓出CPU，包括中間被其他任務搶先，被認為是一個任務周期；把其中完整的CPU時間加起來，形成本周期的任務執行時間(Workfse)，用指數遞減平均值作為新的預測執行時間，用同樣的辦法算出新的時限
上述三種策略形成了一個策略層次機構，成為一個策略棧。它們對各種不同的事件作出反應，然后作出自己的決策。一個全局決策機構得出最優的決策，一般是最頂層的策略優先。因為認為性能是要優先保證的，而頂層的策略保證了用戶的觀感不會有損害。
將vertigo算法與CPU本身的DVS策略（LongRun）作比較后得出的結論是，在大部分情況下LongRun顯得過于保守，它總是很快地將CPU的速度調節到最高或較高的頻率，在低頻率水平停留的時間很短。筆者認為這是基于系統利用率的原因。因為不知道具體任務的性能需求，所以只能采取保守策略。Vertigo則使大部分任務在較低頻解決，只有在超過恐慌時限時才設置到全速運行，能有效地節約能量。又由于頂層的策略保證了用戶的感覺不會受到什么損害，如在播放MPEG時并沒有丟幀。
1.2.4GRACEOS策略
Wanghong Yuan等人[17]提出graceos策略，把軟實時調度算法與DVS策略整合在一起，為手持終端的多媒體應用提出節能又保證服務質量的OS調度策略。
該算法是基于PACE算法的改進，但在以下幾個方面作了改進：a）去掉了頻率連續可調的假設，代之以離散的頻率范圍；b）在線估測CPU周期需求時不是按某種已知分布，而是用統計分布圖來大致地求得分布函數，即把從最小的周期數到最大的周期數分成等分的區間，然后統計一定范圍（最近n次同一任務的周期需求，如100）內落入各個區間的數目，則可以得出一個從小到大按序的分布圖；c）引入了最早時限優先算法（EDF），在統計上保證不超過時限的概率（即在分布圖中選擇一個合適的周期數目，低于這個周期數目的概率要超過一個預先定義的閾值）。
對每一個任務完成點，可由設置的頻率得出，在安排一個任務時，其最佳調度便可應用。結果顯示，在低負載的系統環境下，只有極少任務不能滿足性能需求，在高負載的環境下，大部分任務（90％以上）能滿足性能要求；同時支持多任務環境，這對于pace也是一個改進。
1．3其他類型的策略
為了保證實時性提出的各種策略，本文不加以關注。這主要基于如下兩點原因：a)各種實時性策略往往需要應用程序提供額外的信息，如最壞執行時間、周期需求。在普通的PDA或通用系統上不可能要求應用程序員提供這樣的信息，大部分任務交互式的特性也決定了不可能提供類似的信息。b)在普通的PDA或通用系統上不需要保證硬實時，大部分是盡力而為型，少部分為軟實時型，如多媒體應用。
2實現簡介
RightSpeed的實現包括一個底層的速度控制器，負責具體執行頻率設置；一個時鐘，負責提供1 ms級別的調度粒度；一個任務組文件管理器，因為各個任務都有其相關的信息需要記錄，如其時限、性能要求、以前采樣的運行時間，以及下一個任務周期該采用的調度（即在一個任務周期的各個時段采用的頻率水平和各個時段長度）；一個任務管理器和采樣隊列，在任務啟動或結束時通知速度控制器，并在任務結束時把采樣信息存入采樣隊列，以便在系統比較空閑時用pace算法計算任務的預測調度；一個空閑監測器，它是一個僅比系統空閑線程優先級高的線程，負責識別任務的結束和計算最優調度值；一個I/O計數器，主要幫助空閑監測器識別任務結束（參見前述兩個條件）；一個用戶庫，主要檢測用戶的UI事件。
RightSpeed的實現特點是基于系統線程，而不是更改操作系統調度程序。這一優點使它可以在某些封閉源碼的商業操作系統上實現。
Vertigo則是在內核級實現。因為它實現在Linux操作系統上，包括策略棧、事件追蹤模塊、速度控制器等。策略棧產生具體策略；事件追蹤模塊負責獲取任務的CPU需求分布；速度控制器負責具體的頻率（電壓）調整。
Vertigo的實現特點是其策略棧可以綜合所有的策略，得出對各種類型的任務都較佳的調度。
Graceos在內核級實現，實現在Linux上，包括探測器、軟實時調度器、速度適配器。探測器負責收集監控任務的CPU周期；軟實時調度負責調度及產生策略；速度適配器負責具體的頻率（電壓）調整。
以上幾種實現的一般架構是：底層的驅動程序負責與具體的CPU DVS芯片交互，實現頻率調整，向上提供接口。更換CPU時，可以保證只有這部分代碼需要重寫；策略管理器負責執行具體的DVS策略，其實現要求是可以動態調換不同的DVS策略，可以更新DVS策略；探測器可以追蹤任務或系統的運行情況，得出CPU的負載；核心負責向上提供應用編程接口(API)，向其他組件提供服務例程，并協調各個組件的工作。
3相關工作與后續工作
關于DVS策略的綜述不是很多。Chan等人比較了早期的各個基于時間片的DVS策略。他們用模擬驗證了早期Weiser等人提出的一些想法，并提出了自己的策略。Pering等人比較了另外一些策略，并在實際系統中實現了幾個算法，得出了被引頻次極高的結論。Grunwald等人的研究與Pering等人的研究共同催生出基于任務的DVS策略。
但以上文獻均只是總結與比較了早期基于時間片的DVS策略。本文總結了十年以來有關DVS策略的相關文獻，對其進行分門別類，比較系統地介紹了DVS策略從算法到實現的方方面面。
今后，筆者將在德信的一款基于XScale的智能手機上具體實現上述種種算法，并在實際工作中進一步檢驗上述策略，盡可能提出自己的策略。
4結束語
功耗的重要性已經提升到與性能和成本同等重要的地位。從小處著眼，它可以延長電池使用的壽命，降低芯片散發的熱量；從大處著眼，它可以降低對能源的消耗，減少對環境的影響，是一個值得關注與重視的問題。
DVS是降低功耗的有效途徑，經過近十年的發展，很多算法與策略已經得到工業級別的應用，但空間還很大。作為進一步的研究，筆者給出如下建議：
a）探求更清晰的任務周期需求預測與監控方法。這是得到最優調度的必要條件。現在的基于用戶界面事件和任務分類方法比較寬泛，不夠精確，分類的標準也沒有統一。
b）對數學模型進行進一步研究，盡量去掉不合理的假設，如考慮調整時間。實際上，在Intel基于XScale微架構的PXA27x應用處理機上，調整一次頻率的代價大概在102 μs級別，這在時間要求較高的應用中是不能忽略的。又比如考慮各個任務的交互等。
c）實現架構的研究，可以提出DVS策略的通用體系結構。本文給出的結構可以作為一種參考，但各個接口函數、各個部分間的交互沒有標準化。同時DVS策略暴露給應用程序員的接口沒有標準化，但這是一種趨勢，即允許應用程序員與用戶參與到功耗管理中，應用參與的功耗管理將更直接而有效。直接告知比迂回的探測肯定更有效，因為應用程序員與用戶最清楚它的性能需求與時限要求。
d）在實際系統中試驗與創造DVS策略。本文所述的很多策略都是用模擬來驗證的，不能提供讓人確信的結論。實際的系統有很多細節可以抵消可能的節能措施，在模擬器上驗證，靠一兩組挑選的基準測試往往容易得出過于樂觀的結論。
參考文獻：
［1］LORCH J R. Operating systems techniques for reducing processor energy consumption[D]. California:University of California at Ber￣keley， 2001.
[2］SOUDRIS D. Designing CMOS circuits for low power[M]. Netherlands: Kluwer Academic Publishers ，2002:9－22.
[3］JEJURIKAR R，PEREIRA C，GUPTA R. Leakage aware dynamic voltage scaling for realtime embedded systems[C]//Proc of the 41st DAC’04.San Diego:[s.n.]， 2004.
[4］Intel公司. Intel PXA27x processor family developer’s manual[EB/OL].http://www.intel.com/design/pca/products/pxa27x/techdocs.htm.
[5］AMD公司. Mobile AMD Athlon 4 processor model 6 CPGA data sheet[EB/OL]. http://www.amd.com.
[6］KLAIBER A. The technology behind CrusoeTM processors[R].[S.l.]: Transmeta Corporation， 2000.
[7］FLAUTNER K， MUDGE T. Vertigo: automatic performancesetting for Linux[C]//Proc of the 5th USENIX Symposium on Operating Systems Design and Implementation (OSDI).Boston:[s.n.]， 2002:105116.
[8］WEISER M， WELCH B， DEMERS A， et al. Scheduling for reduced CPU energy[C]//Proc of the 1st Symposium on Operating Systems Design and Implementation.New York:The Advanced Computins Systems Association， 1994:13－23.
[9］GOVIL K， CHAN E， WASSERMAN H. Comparing algorithms for dynamic speedsetting of a lowpower CPU[C]//Proc of the 1st International Conference on Mobile Computing and Networking.New York:ACM Press， 1995.
[10］PERING T， BURD T， BRODERSEN R W. The simulation and evaluation of dynamic voltage scaling algorithms[C]//Proc of the 1998 International Symposium on Low Power Electronics and Design.Monterey， CA:ACM，1998:76－81.
[11］GRUNWALD D， LEVIS P， FARKAS K I， et al. Policies for dynamic clock scheduling[C]//Proc of the 4th Symposium on Operating Systems Design and Implementation.San Diego:[s.n.]， 2000.
[12］FLAUTNER K， REINHARDT S， MUDGE T. Automatic performa￣ncesetting for dynamic voltage scaling[C]//Proc of the 7th ACM International Conference on Mobile Computing and Networking (MOBICOM 2001). 2001.
[13］LORCH J R， SMITH A J. The VTrace tool: building a system tracer for Windows NT and Windows 2000[J]. MSDN Magazine， 2000，15(10):86102.
[14］LORCH J R ， SMITH A J. Improving dynamic voltage scaling algorithms with pace[C]//Proc of the 2001 ACM SIGMETRICS Confe￣rence.Cambridge:[s.n.]， 2001:50－61.
[15］LORCH J R ， SMITH A J. Using user interface event information in dynamic voltage scaling algorithms[R]. California:University of Cali￣fornia at Berkeley， 2002.
[16］LORCH J R， SMITH A J. Operating system modifications for taskbased speed and voltage scheduling[C]//Proc of the 1st Intl Conf on Mobile Systems， Applications， and Services.San Francisco:[s.n.]， 2003.
[17］YUAN Wanghong， NAHRSTEDTK.Energyefficient soft realtime CPU scheduling for mobile multimedia systems[C]//Proc of the 19th SOSP’03.New York:ACM， 2003.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
