96-00年CPU功耗感知调度研究
最近读了一些1996-2000年的通过调度来降低cpu能耗的文章，主要文章有[1] [2] [3] [4] [5]， 简单总结一些该时期单核CPU功耗感知的调度策略。
该时期还出现了很多关于低功耗电路设计的文章，利用电压可调节的技术，将执行单元作为节点，执行单元之间传输的数据作为边，构成DAG，对DAG进行分析，在满足throughput limit的情况下调节node的电压来降低功耗。
Paper Analysis
Hongy于1998年DAC发表的论文[1]中主要针对拥有多电压可编程处理器核和内存的SOC进行功耗降低，文章可以分为两部分，第一部分是设计层面动态分配资源，调整处理器核、icache和dcache的数量和参数；第二部分是任务层面的调度，通过least-constraining most-constrained提出了非抢占式调度算法，下面讲一下其第二部分调度算法，该调度算法分为两部分：
-
假设所有的任务在很小的电压下调度
首先对任务时间进行分片，分为time region。通过目标函数计算time region的值
$$
OBJ(TimeRegion tr) = maxVoltage(tr) * aveVoltage(tr)
$$
然后假定所有的任务从arrival time执行到deadline，计算time region中所有任务的最大电压和平均电压，time region的OBJ用来计算task的constraint
$$
OBJ(Task t) = \sum_{tr ∈[a_t, b_t]}OBJ(tr) * r_t^2/(d_t - a_t)^2
$$
$ r_t$ 是任务在该电压下的执行时间（execution time），其中没有被包含在其他任务时间下的，且OBJ最大即most_constrained的task，被调度在和他run-time相同的interval（a subset of time regions with the lowest sum of objective functions）下执行，调度完任务t后，对其他任务的arrival time和deadline进行更新，然后递归调度 -
为了降低功耗调整电压
同一年Hongy又发了另一篇文章[2]，思路和[1]一样，第一部分进行Resource Allocation，第二部分进行Task schedule，这一篇文章中任务调度算法为可抢占的任务调度算法，同时考虑了电压切换的限制，虽然仍假设电压是连续变化的，但是对最大变化速率（斜率）做出了限制，设定最大为K，且变化时仍能工作。算法思路仍是least-constraining most-constrained启发式调度算法，增加了抢占机制，先调度后调压。
Ishihara于1998年发表的论文[3]中对可动态调节电压上的调度问题进行了分析，提出了几个lemma和theorem，比较出彩的是他考虑到了电压不能连续变化的抢矿，指出两个相关的theorem：
- 当处理器只能使用一部分离散的电压值，最多两个电压变化即可最小化energy
- 最小化energy的两个电压值是相邻于$V_{ideal}$（假如用一个供电电压v正好在deadline完成任务，那么v是使energy最小化的供电电压，记为$V_{ideal}$)
两个定理表明，通常最优化的电压调节只需要一次电压更改，因此电压变化带来的开销往往是可以忽略的
最终给出了调度问题的整数线性规划（ILP）形式
1999年，Shin在DAC中发表了一篇关于硬实时系统上固定优先级调度算法的研究[4]。首先介绍一下什么是固定优先级调度算法，在基于优先级的抢占调度算法（priority-based preemptive scheduling algorithm）问题中，一般分为两种算法
-
fixed-priority（static） algorithm
任务运行前静态设置好其优先级，运行中优先级不发生变化。经典的有RMS（Rate-Monotonic Scheduling）或DMS（Deadline-Monotonic Scheduling）。
-
dynamic-priority algorithm
任务运行时动态设置其优先级，比如EDF（Earliest Deadline First）
关于上面三种算法，可以参考博客，这里不进行介绍。
在嵌入式系统中，通常将任务分为具有deadline要求的周期性（periodic）任务和非周期性（aperiodic）任务，为了分析系统的可调度性，通常会通过static analysis[6] [7]、profiling或direct measurement的方法得到任务的最坏情况执行时间（在可变电压处理器上，根据其处理器最大速度情况下计算）。作者基于以下两个观察：
- 任务一般比WCET跑得快
- 在固定优先级调度中，即使任务跑在WCET，也会出现一些idle time
以上两种情况会导致idle time的出现，如果可以通过DVFS或DPM技术，降低idle时间的出现，同时在出现idle的时候进入power-down mode，就可以大大减少功耗。于是作者在现有调度技术上进行修改，现有的调度器维持两个队列：
-
run queue
存储准备在cpu上执行的任务，按照优先级排序。
-
delay queue
存储等待下一个周期到来的任务，按照release time排序。
正在cpu上执行的任务称为active task，每次调度器运行时，会检查delay queue中是否有任务可以被移到run queue，如果有的话，移入run queue，然后将run queue首节点和active task的优先级比较，来判断是否发生任务切换。
作者增加了两种机制
- 如果没有等待执行任务（run queue为空）和正在执行的任务，所有任务都在等待下一次任务到来，则进入power-down模式
- 如果没有等待执行任务（run queue为空）且有正在执行的任务，则调整电压尽可能降低，节省功耗。考虑了切换的开销。delay queue首节点的release time标识下一个任务的到来，所以可以根据该事件来调整电压。
2000年，Shin延伸了他的工作，在ICCAD发表了文章[5]，给定任务的T（period）、D（Deadline）和C（WECT），分两部分进行调度，第一部分offline计算保证schedule feasible的前提下最低处理器速度，第二部分online根据任务执行队列中的情况动态调整电压和进入power-down模式。后面动态电压调节和进入power-down模式和1999年的论文相似。
Summary
相较于，出现了针对real-time下time constraint和DVFS与DPM相结合的文章，但同时也存在一定局限，局限在于首先还是大多evaluation都是仿真，仿真中假设了电压的连续变化，同时power-down模式的功耗开销[4] [5]中只是假设为5%的正常开销，没有实际测量，模式切换和电压调节的开销也并不准确。
Reference
[1] Inki Hong, D. Kirovski, Gang Qu, M. Potkonjak and M. B. Srivastava, "Power optimization of variable voltage core-based systems," Proceedings 1998 Design and Automation Conference. 35th DAC. (Cat. No.98CH36175), 1998, pp. 176-181, doi: 10.1109/DAC.1998.724462.
[2] Hong, I., Qu, G., Potkonjak, M. & Srivastavas, M. B. Synthesis techniques for low-power hard real-time systems on variable voltage processors. in Proceedings 19th IEEE Real-Time Systems Symposium (Cat. No.98CB36279) 178–187 (1998). doi:10.1109/REAL.1998.739744.
[3] Ishihara, T. & Yasuura, H. Voltage scheduling problem for dynamically variable voltage processors. in Proceedings. 1998 International Symposium on Low Power Electronics and Design (IEEE Cat. No.98TH8379) 197–202 (1998). doi:10.1145/280756.280894.
[4] Shin, Y. & Choi, K. Power conscious fixed priority scheduling for hard real-time systems. in Proceedings 1999 Design Automation Conference (Cat. No. 99CH36361) 134–139 (1999). doi:10.1109/DAC.1999.781298.
[5] Shin, Y., Choi, K. & Sakurai, T. Power optimization of real-time embedded systems on variable speed processors. in IEEE/ACM International Conference on Computer Aided Design. ICCAD - 2000. IEEE/ACM Digest of Technical Papers (Cat. No.00CH37140) 365–368 (2000). doi:10.1109/ICCAD.2000.896499.
[6] S. Lim, Y. Bae, G. Jang, B. Rhee, S. Min, C. Park, H. Shin, K. Park, and C. Kim, “An accurate worst case timing analysis for RISC processors,” in Proc. IEEE Real-Time Systems Symposium. pp. 97-108, Dec. 1994.
[7] Y. S. Li, S. Malik, and A. Wolfe, “Performance estimation of embedded software with instruction cache modeling,” in Proc. Int’l Conf. on Computer Aided Design, pp. 380-387, Nov. 1995.