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

• 2021 年 11 月 21 日
• 筆記
• 高性能低功耗

最近讀了一些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提出了非搶佔式調度演算法，下面講一下其第二部分調度演算法，該調度演算法分為兩部分：

1. 假設所有的任務在很小的電壓下調度

   

   首先對任務時間進行分片，分為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. 為了降低功耗調整電壓

   

同一年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）形式

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.