摘要：測量和監(jiān)控領(lǐng)域中一種普通的周期模式是：完成一次程序運行后睡眠，定時喚醒，進入下一周期，再運行，再睡眠，……。該文對此定義了一個S+R（Sleep+Run）工作模式?；仡櫫嘶陔妷侯l率調(diào)整的能效調(diào)度之學(xué)術(shù)動態(tài)，討論了多作業(yè)S+R模式下的最低能耗計算問題。針對單作業(yè)的S+R模式，給出了最低能耗時的臨界頻率計算公式。并指出系統(tǒng)的最高工作頻率、最低工作頻率以及它們之間的某一點都可能為臨界頻率點。

關(guān)鍵詞：S+R模式；臨界頻率；運行期；睡眠期；周期T總能耗

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）26-0045-03

1 概述

運行（run）→睡眠（sleep），再運行→再睡眠，周而復(fù)始，這種工作模式出現(xiàn)在許多嵌入式場合。從無人氣象測量、智能家居、到物聯(lián)網(wǎng)節(jié)點等等方面，都可找到類似的應(yīng)用方式。之所以安排睡眠，一個主要目的當然是降低能耗，特別是電池供電的裝置。

多年來學(xué)者們關(guān)于實時和嵌入式能效問題進行了大量研究[1]。因為一個CMOS電路的功率消耗隨其工作頻率的升高而增加[2]，所以，在不影響實時性能的前提下，盡量降低一個裝置的工作頻率和電壓是節(jié)能的一個主要思路。負荷較重時升壓升頻，負荷較輕時降壓降頻，這一重要手段便是動態(tài)電壓和頻率調(diào)整DVFS（Dynamic Voltage/Frequency Scaling） [3]。又因電壓的調(diào)整往往和頻率有關(guān)：頻率高時一般要求電壓也較高，故有的學(xué)者討論DVFS時只提速率調(diào)整（Speed Scaling）。再考慮到處理器往往具有待機（Standby）、停機（Stop）、或睡眠等多個狀態(tài)，人們便想到將這些低功耗狀態(tài)與速率調(diào)整相結(jié)合，努力尋找最低能耗調(diào)度方案（Minimum Energy Scheduler）。

設(shè)在一確定時間段內(nèi)有[n]個作業(yè)等待執(zhí)行，基于EDF（Earliest Deadline First）規(guī)則[4]，文獻[5]提出了一個離線（offline）最優(yōu)算法[YDS] （以作者姓氏首字母命名），用以找到最低能耗調(diào)度方案，時間復(fù)雜度最多是[O（n3）]。該算法只是速率調(diào)整，并未考慮與低功耗狀態(tài)相結(jié)合。

文獻[6]提出了速率調(diào)整+睡眠（Speed Scaling with Sleep State）的研究模型，假定睡眠期間電流為零，給出了一個離線近似算法，但能找出最低能耗調(diào)度方案的離線最優(yōu)算法并未給出。文獻[7]則指出這一最優(yōu)算法是一[NP]難度問題。

文獻[6]的另一重要貢獻是提出了一個臨界頻率（critical frequency）[fcrit]的概念：假設(shè)頻率為零時處理器也要消耗一定的能量，那么，選工作頻率為[fcrit]，可使得完成作業(yè)所需的能耗最低。注意[fcrit]不一定是最低頻率。

再看前面提到的“運行→睡眠→運行→…”周期模式，以下簡稱為[S+R]（Sleep+Run） 模式。如何最省電？一個直觀的想法是運行時間相對于睡眠時間越短越好；另一個是運行時的頻率越低越好。從臨界頻率的概念容易推斷不應(yīng)該這樣輕易下結(jié)論。即使總共只有一個作業(yè)。下面先對這一問題做出規(guī)范的定義，然后探索[S+R]模式下的最低能耗計算公式。

2 相關(guān)定義及術(shù)語

定義1（[S+R]模式）：一個周期為[T]的實時系統(tǒng)，每個周期由兩個部分組成：前一段為連續(xù)的運行期，后一段為連續(xù)的睡眠期。睡眠期結(jié)束時處理器被喚醒，進入下一周期的運行期。程序的運行都在運行期完成，而睡眠期內(nèi)處理器處于低功耗狀態(tài)。這樣的工作模式稱為[S+R]（Sleep+Run）模式。

3 S+R模式的最低能耗計算

3.1 多作業(yè)最低能耗計算

（3） 式中的能量由三部分組成：①[Esleep]的計算比較容易，只要調(diào)度方案確定了[trun]的值。這里還假定[twake-up<

如何做到[S+R]模式的能耗最低？文獻[5]的YDS只考慮如何以最低能耗運行完[n]個作業(yè)，完全不考慮sleep態(tài)的存在；文獻[6]和[7]雖然考慮sleep態(tài)，但假設(shè)[Psleep=0]，且即使如此，最優(yōu)調(diào)度方案的獲取也是一NP難度的問題。

而在上述定義1中，不忽略[Psleep]，最優(yōu)調(diào)度方案很可能也是NP難度。總之，“多作業(yè)”、“考慮sleep態(tài)”和“[Psleep≠0]”這幾個因素，使得[（ET）min]的具體計算（或[fcrit]的計算）非常復(fù)雜。但是，在適當假定的前提下，問題可以得到簡化。

3.2 單作業(yè)最低能耗計算

假定1： [S+R]模式中喚醒能量[Ewake-up]為常數(shù)。

假定2： [S+R]模式中只有一個作業(yè)，且該作業(yè)在運行期要求不間斷連續(xù)運行，運行過程中頻率[f]固定不變。

這兩個假定在某些簡單的應(yīng)用場合是基本合理的。比如，記錄溫度的單片機只讀取溫度傳感器的數(shù)據(jù)，記錄進存儲器后進入sleep；又如，一個無線節(jié)點只定期發(fā)出信標（供其他節(jié)點同步），然后睡眠。這樣的簡單系統(tǒng)往往沒有必要采用多作業(yè)結(jié)構(gòu)，一個作業(yè)就夠了，并且，實際設(shè)計中，常常也考慮在短暫的運行期中不要停頓，不要去改變頻率（預(yù)先選好）。

在上述假定下，運行期的功率可以用平均功率[Prun]表示（大寫字母P）。關(guān)于[Prun]的計算，有的研究模型取[Prun∝f2][5]；有的按[Prun=f3+…]進行研究[6]。一般性地，[Prun=βfα+γ]，[α]、[β]和[γ]都看作大于零的常數(shù)[7]。

3.2.3 討論

①關(guān)于臨界頻率[fcrit]的實際取值。

參考文獻：

[1] 錢光明. 實時系統(tǒng)中兩類高能效調(diào)度問題[J]. 電子世界，2016（499）：80-81.

[2] D.M. Brooks，P.Bose， Schuster S E， et al. Power-aware microarchitecture： Design and modeling challenges for next-generation microprocessors[J]. Micro， IEEE， 2000， 20（6）：26-44.

[3] 徐太龍，薛峰等. 用于DVFS片上系統(tǒng)的全數(shù)字SARDLL設(shè)計[J].計算機工程， 2015， 41（4）：273-283.

[4] C L Liu， J W Laylan. Scheduling Algorithms for Multiprogramming in a Hard Real—Time Environment[J]. J.ACM，1973，20（1）：40-61.

[5] F.Yao， A.Demers &S.Shenker. A scheduling model for reduced CPU energy[C]. In Proc. 36th Annual IEEE Symposium on Foundations of Computer Science. pp. 374-382， Milwaukee， USA， Oct. 1995.

[6] S.Irani， S.Shukla， R.Gupta. Algorithms for power savings[J]. ACM Transactions on Algorithms （TALG）， 2007， 3（4）：41.

[7] S.Albers， A.Antoniadis. Race to idle： new algorithms for speed scaling with a sleep state[J]. ACM Transactions on Algorithms （TALG）， 2014， 10（2）：9.

[8] STM32F103xC STM32F103xD STM32F103xE Datasheet-production data， 2015， www.st.com.

[9] L.Benini， A. Bogliolo， G.De. Micheli. A survey of design techniques for system-level dynamic power management[J]. Very Large Scale Integration （VLSI） Systems， IEEE Transactions on， 2000， 8（3）：299-316.

[10] B.Liu， M.H.Foroozannejad， S.Ghiasi， &B.M.Baas. Optimizing power of many-core systems by exploiting dynamic voltage， frequency and core scaling[C]. In 58th IEEE International Midwest Symposium on Circuits and Systems （MWSCAS）. pp. 1-4， Colorado， USA， Aug. 2015.

[11] Bini E， Buttazzo G， Lipari G. Minimizing CPU energy in real-time systems with discrete speed management[J]. ACM Transactions on Embedded Computing Systems （TECS）， 2009， 8（4）：31.1-31.23.endprint