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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）26-0045-03

1 概述

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

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

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

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

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

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

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

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

3 S+R模式的最低能耗計(jì)算

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

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

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

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

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

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

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

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

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

3.2.3 討論

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

參考文獻(xiàn)：

[1] 錢(qián)光明. 實(shí)時(shí)系統(tǒng)中兩類高能效調(diào)度問(wèn)題[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ì)[J].計(jì)算機(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