sleep+run周期模式下的低能耗估算

摘要：测量和监控领域中一种普通的周期模式是：完成一次程序运行后睡眠，定时唤醒，进入下一周期，再运行，再睡眠，……。该文对此定义了一个S+R（Sleep+Run）工作模式。回顾了基于电压频率调整的能效调度之学术动态，讨论了多作业S+R模式下的最低能耗计算问题。针对单作业的S+R模式，给出了最低能耗时的临界频率计算公式。并指出系统的最高工作频率、最低工作频率以及它们之间的某一点都可能为临界频率点。

关键词：S+R模式；临界频率；运行期；睡眠期；周期T总能耗

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）26-0045-03

1 概述

运行（run）→睡眠（sleep），再运行→再睡眠，周而复始，这种工作模式出现在许多嵌入式场合。从无人气象测量、智能家居、到物联网节点等等方面，都可找到类似的应用方式。之所以安排睡眠，一个主要目的当然是降低能耗，特别是电池供电的装置。

多年来学者们关于实时和嵌入式能效问题进行了大量研究[1]。因为一个CMOS电路的功率消耗随其工作频率的升高而增加[2]，所以，在不影响实时性能的前提下，尽量降低一个装置的工作频率和电压是节能的一个主要思路。负荷较重时升压升频，负荷较轻时降压降频，这一重要手段便是动态电压和频率调整DVFS（Dynamic Voltage/Frequency Scaling） [3]。又因电压的调整往往和频率有关：频率高时一般要求电压也较高，故有的学者讨论DVFS时只提速率调整（Speed Scaling）。再考虑到处理器往往具有待机（Standby）、停机（Stop）、或睡眠等多个状态，人们便想到将这些低功耗状态与速率调整相结合，努力寻找最低能耗调度方案（Minimum Energy Scheduler）。

设在一确定时间段内有[n]个作业等待执行，基于EDF（Earliest Deadline First）规则[4]，文献[5]提出了一个离线（offline）最优算法[YDS] （以作者姓氏首字母命名），用以找到最低能耗调度方案，时间复杂度最多是[O（n3）]。该算法只是速率调整，并未考虑与低功耗状态相结合。

文献[6]提出了速率调整+睡眠（Speed Scaling with Sleep State）的研究模型，假定睡眠期间电流为零，给出了一个离线近似算法，但能找出最低能耗调度方案的离线最优算法并未给出。文献[7]则指出这一最优算法是一[NP]难度问题。

文献[6]的另一重要贡献是提出了一个临界频率（critical frequency）[fcrit]的概念：假设频率为零时处理器也要消耗一定的能量，那么，选工作频率为[fcrit]，可使得完成作业所需的能耗最低。注意[fcrit]不一定是最低频率。

再看前面提到的“运行→睡眠→运行→…”周期模式，以下简称为[S+R]（Sleep+Run） 模式。如何最省电？一个直观的想法是运行时间相对于睡眠时间越短越好；另一个是运行时的频率越低越好。从临界频率的概念容易推断不应该这样轻易下结论。即使总共只有一个作业。下面先对这一问题做出规范的定义，然后探索[S+R]模式下的最低能耗计算公式。

2 相关定义及术语

定义1（[S+R]模式）：一个周期为[T]的实时系统，每个周期由两个部分组成：前一段为连续的运行期，后一段为连续的睡眠期。睡眠期结束时处理器被唤醒，进入下一周期的运行期。程序的运行都在运行期完成，而睡眠期內处理器处于低功耗状态。这样的工作模式称为[S+R]（Sleep+Run）模式。

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

3.1 多作业最低能耗计算

（3） 式中的能量由三部分组成：①[Esleep]的计算比较容易，只要调度方案确定了[trun]的值。这里还假定[twake-up<

如何做到[S+R]模式的能耗最低？文献[5]的YDS只考虑如何以最低能耗运行完[n]个作业，完全不考虑sleep态的存在；文献[6]和[7]虽然考虑sleep态，但假设[Psleep=0]，且即使如此，最优调度方案的获取也是一NP难度的问题。

而在上述定义1中，不忽略[Psleep]，最优调度方案很可能也是NP难度。总之，“多作业”、“考虑sleep态”和“[Psleep≠0]”这几个因素，使得[（ET）min]的具体计算（或[fcrit]的计算）非常复杂。但是，在适当假定的前提下，问题可以得到简化。

3.2 单作业最低能耗计算

假定1： [S+R]模式中唤醒能量[Ewake-up]为常数。

假定2： [S+R]模式中只有一个作业，且该作业在运行期要求不间断连续运行，运行过程中频率[f]固定不变。

这两个假定在某些简单的应用场合是基本合理的。比如，记录温度的单片机只读取温度传感器的数据，记录进存储器后进入sleep；又如，一个无线节点只定期发出信标（供其他节点同步），然后睡眠。这样的简单系统往往没有必要采用多作业结构，一个作业就够了，并且，实际设计中，常常也考虑在短暂的运行期中不要停顿，不要去改变频率（预先选好）。

在上述假定下，运行期的功率可以用平均功率[Prun]表示（大写字母P）。关于[Prun]的计算，有的研究模型取[Prun∝f2][5]；有的按[Prun=f3+…]进行研究[6]。一般性地，[Prun=βfα+γ]，[α]、[β]和[γ]都看作大于零的常数[7]。

3.2.3 討论

①关于临界频率[fcrit]的实际取值。

参考文献：

[1] 钱光明. 实时系统中两类高能效调度问题[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片上系统的全数字SARDLL设计[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