96-00年CPU功耗感知调度研究

最近读了一些1996-2000年的通过调度来降低cpu能耗的文章,主要文章有[1] [2] [3] [4] [5], 简单总结一些该时期单核CPU功耗感知的调度策略。

96-00年CPU功耗感知调度研究_第1张图片

该时期还出现了很多关于低功耗电路设计的文章,利用电压可调节的技术,将执行单元作为节点,执行单元之间传输的数据作为边,构成DAG,对DAG进行分析,在满足throughput limit的情况下调节node的电压来降低功耗。

Paper Analysis

Hongy于1998年DAC发表的论文[1]中主要针对拥有多电压可编程处理器核和内存的SOC进行功耗降低,文章可以分为两部分,第一部分是设计层面动态分配资源,调整处理器核、icache和dcache的数量和参数;第二部分是任务层面的调度,通过least-constraining most-constrained提出了非抢占式调度算法,下面讲一下其第二部分调度算法,该调度算法分为两部分:

  1. 假设所有的任务在很小的电压下调度

    Untitled

    首先对任务时间进行分片,分为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进行更新,然后递归调度

  2. 为了降低功耗调整电压

    Untitled

同一年Hongy又发了另一篇文章[2],思路和[1]一样,第一部分进行Resource Allocation,第二部分进行Task schedule,这一篇文章中任务调度算法为可抢占的任务调度算法,同时考虑了电压切换的限制,虽然仍假设电压是连续变化的,但是对最大变化速率(斜率)做出了限制,设定最大为K,且变化时仍能工作。算法思路仍是least-constraining most-constrained启发式调度算法,增加了抢占机制,先调度后调压。


Ishihara于1998年发表的论文[3]中对可动态调节电压上的调度问题进行了分析,提出了几个lemma和theorem,比较出彩的是他考虑到了电压不能连续变化的抢矿,指出两个相关的theorem:

  1. 当处理器只能使用一部分离散的电压值,最多两个电压变化即可最小化energy
  2. 最小化energy的两个电压值是相邻于$V_{ideal}$(假如用一个供电电压v正好在deadline完成任务,那么v是使energy最小化的供电电压,记为$V_{ideal}$)

两个定理表明,通常最优化的电压调节只需要一次电压更改,因此电压变化带来的开销往往是可以忽略的

最终给出了调度问题的整数线性规划(ILP)形式

96-00年CPU功耗感知调度研究_第2张图片


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的方法得到任务的最坏情况执行时间(在可变电压处理器上,根据其处理器最大速度情况下计算)。作者基于以下两个观察:

  1. 任务一般比WCET跑得快
  2. 在固定优先级调度中,即使任务跑在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的优先级比较,来判断是否发生任务切换。

作者增加了两种机制

  1. 如果没有等待执行任务(run queue为空)和正在执行的任务,所有任务都在等待下一次任务到来,则进入power-down模式
  2. 如果没有等待执行任务(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

相较于90-95,出现了针对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.

你可能感兴趣的