本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
前回を読んでいない方はこちらからどうぞ．
リアルタイムシステムの記事一覧はこちらからどうぞ．
リアルタイムシステムで使われているリアルタイムOSは，主にC言語で書かれています．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
省電力スケジューリング（Energy-Efficient Scheduling）
コンピュータシステムでは，組込みシステムのような小規模なシステムから，PC，データセンタ，スーパーコンピュータ等の大規模なシステムまで省電力（省エネルギー）化が要求されます．
この理由として電気代の節約，バッテリ制約，発熱，半導体の寿命等が挙げられます．
これらの課題を解決するために，リアルタイムシステムの分野では，省電力スケジューリング（Energy-Efficient Scheduling）の概念が提案されました．
そこで，本記事では，省電力スケジューリングについて解説していきます．
消費電力
消費電力の公式\(P\)は以下になります．
$$\Large P = \underbrace{\alpha CfV_{dd}^2}_{P_{dynamic}} + \underbrace{I_{leak} V_{dd}}_{P_{static}} \tag{34.1}$$
| 記号 | 説明 |
|---|---|
| \(P\) | 消費電力 |
| \(P_{dynamic}\) | 動的電力（スイッチング電力） |
| \(P_{static}\) | 静的電力（リーク電力） |
| \(\alpha\) | スイッチング率（動作率） |
| \(C\) | 負荷容量 |
| \(f\) | 動作周波数 |
| \(V_{dd}\) | 供給電圧 |
| \(I_{leak}\) | リーク電流 |
CMOS回路は以下の例のような構成になります．
供給電圧と動作周波数は以下になります．
最大周波数\(f_{max}\)は電圧\(V\)に比例し，動的電力（スイッチング電力）\(P_{dynamic}\)は周波数の3乗に比例します．
リーク電流
リーク電流は，電子回路上で，絶縁されていて本来流れないはずの場所・経路で漏れ出す電流のことです．
リーク電流の公式は，「リーク電流＝サブスレッショルドリーク電流＋ゲートリーク電流＋接合リーク電流」になります．
サブスレッショルドリーク電流は，トランジスタがサブスレッショルド領域または弱い反転領域，つまりゲート-ソース間電圧が閾値電圧以下でのソース～ドレイン間の電流のことです．
トランジスタのスイッチングを高速化するには，閾値電圧を下げてトランジスタのオン電流を増加させる必要があります．
閾値電圧が下がり続けて0Vに近付くと，回路の入力電圧を0Vにしてもソース～ドレイン間を電流が流れるようになります．
また，サブスレッショルドリーク電流はプロセッサ温度Tに強く依存します（\(\propto T^2 \exp(-1/T)\)）．
ゲートリーク電流は，微細化によりゲート絶縁膜が薄くなり過ぎることが原因でシリコン基板側からゲートに向かって流れるようになる電流のことです．
IntelのHigh-κ絶縁体（厚さがあり，大量の電流を流せる高誘電率な素材）を利用すると，ゲートリーク電流を削減できます．
接合リーク電流は，半導体中の不純物濃度の不適正や格子欠陥により発生するソースとシリコン基板間やドレインとシリコン基板間で発生するリーク電流です．
プロセスルールの微細化や温度依存性は小さく，またほとんど管理が可能になっており，それほど大きな問題とはなっていません．
プロセッサ温度の公式は以下になります．
\begin{eqnarray}
\frac{dT(t)}{dt} &=& - \frac{1}{C_{th}R_{th}}(T(t) - T_{am}) + \frac{1}{C_{th}}P(t) \\
T(t) &=& T_{am} + R_{th} P(t) \\
\end{eqnarray}
ここで，\(T(0) = T_{am}\)，\(P(0) = 0\)になります．
| 記号 | 説明 |
|---|---|
| \(t\) | 時刻 |
| \(T(t)\) | プロセッサ温度 |
| \(C_{th}\) | 熱容量 |
| \(R_{th}\) | 熱抵抗 |
| \(T_{am}\) | 環境温度 |
| \(P(t)\) | 消費電力 |
省電力の評価指標と目的
省電力の評価指標は以下になります．
- 消費電力（Power Consumption）
- 記号：P
- 単位：W (Watt)
- 消費電力量＝消費エネルギー（Energy Consumption）
- 記号：W，E
- 単位：J (Joule) = Ws (Watt * second)
- 消費電力の時間積分：\(E =\int P dt\)
省電力と省エネルギーの関係は上図になります．
省電力と省エネルギーは，供給電圧（動作周波数）が高くなる場合はどちらも増加傾向にあります．
しかし，供給電圧が低くなる場合は，は遅延（処理時間）が長くなってしまうため，省電力になるほどエネルギーが増大してしまうことがわかります．
つまり，省電力にするためには供給電圧を低くすれば良いですが，省エネルギーの観点で言うとタスクを「ゆっくり実行」すれば良いとは限らないということです．
コンピュータの省電力化の目的は，システムの消費エネルギー（消費電力量）の最小化です．
※消費電力ではないことに注意して下さい．
具体的には，以下の制約条件を満たしつつ消費エネルギーを最小化する省電力スケジューリングを実現します．
- リアルタイム性：すべてのジョブがデッドラインまでに実行を完了
- タスク実行時：供給電圧と動作周波数にはそれぞれ上限と下限が存在
- アイドル時：スリープ（ディープスリープ，シャットダウン等）可能
省電力スケジューリングの例
上図が省電力スケジューリングの例です．
全てのタスクがデッドラインまでに実行を完了しつつ，電圧周波数制御やスリープすることで消費エネルギーを削減することがわかります．
省電力スケジューリングには，リアルタイム電圧周波数制御とリアルタイム動的電力管理の2つの方法がありますので，それぞれ解説していきます．
リアルタイム電圧周波数制御（RT-VFS：Real-Time Voltage/Frequency Scaling）
リアルタイム電圧周波数制御（RT-VFS：Real-Time Voltage/Frequency Scaling）を紹介します．
RT-VFSのシステムモデル
RT-VFSのシステムモデルは，LiuとLaylandのモデルに周波数セット \(F = \{f_1 < f_2 < ... < f_L = f_{max}\}\)を追加したものです．
また，周波数セットを正規化したspeed factorとして\(\alpha\)（\(0 < \alpha \leq 1\)）と表現することがあります．
※\(\alpha\)が1の場合に\(f_{max}\)になります．
電圧は周波数に比例します．
なので，式（34.1）に示す通り，動的電力\(P_{dynamic}\)は電圧を周波数に置き換えると周波数の3乗に比例（\(fV_{dd}^2 \propto f^3\)）すると仮定します．
RT-VFSのシステムモデルにおける消費エネルギーは，この動的電力のみを想定し，静的電力は想定しない場合が多いです．
※静的電力を想定するのは後述するRT-DPMのシステムモデルとなります．
LiuとLaylandのモデルを振り返りたいあなたはこちらからどうぞ．
RT-VFSは，「Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems」の論文がパイオニアです！
本記事のRT-VFSはこちらの論文の内容をメインに紹介します．
RT-VFSの概要は下図になります．
- 左部：何も周波数を変更しないスケジュール例
- 右上部：リアルタイム静的周波数制御（RT-SVFS：Real-Time Static Voltage/Frequency Scaling）のスケジュール例
- 右下部：リアルタイム動的周波数制御（RT-DVFS：Real-Time Dynamic Voltage/Frequency Scaling）のスケジュール例
電圧周波数制御をするためには，余裕時間（スラック）の計算が必要になります．
スラックの定義はSlack Stealingで利用した式17.1の下式になります．
$$slack_i (t) = d_i - t - c_i (t)$$
- \(d_i\)：タスク\(\tau_i\)の相対デッドライン
- \(t\)：時刻t
- \(c_i(t)\)：時刻tにおけるタスク\(\tau_i\)の残り実行時間
Slack Stealingを振り返りたいあなたはこちらからどうぞ．
スラックには静的スラックと動的スラックがあります．
静的スラックは，すべてのタスクが最大周波数\(f_{max}\)で最悪実行時間\(C_i\)を実行した場合に発生するスラックのことです．
つまり，下図のようにCPU利用率\(U=\sum_i U_i < 1\)の場合，静的スラックは必ず発生します．
これに対して，動的スラックは，タスクが最悪実行時間より早く実行を完了する時に発生するスラックのことです．
動的スラック=WCET - AETになります（BCET ≦ AET ≦ WCET)．
- WCET（Worst Case Execution Time）：最悪実行時間
- AET（Actual Execution Time）：実際実行時間
- BCET（Best Case Execution Time）：最良実行時間
RT-SVFSスケジューリング
RMとEDFにおけるRT-SVFSスケジューリングを紹介します．
RMにおけるRT-SVFSのスケジュール可能性判定RM_test関数の擬似コードは以下になります．
ここで，ceil(T_i, T_k)は\(\left\lceil T_i / T_k \right\rceil\)を意味します．
|
1 2 3 4 5 |
RM_test(α): if (ceil(T_i, T_1) * C_1 + ceil(T_i, T_2) * C_2 + ... + ceil(T_i, T_i) * C_i ≦ α * T_i) return true; else return false; |
EDFにおけるRT-SVFSのスケジュール可能性判定EDF_test関数の擬似コードは以下になります．
|
1 2 3 4 5 |
EDF_test(α): if (C_1 / T_1 + C_2 / T_2 + ... + C_n / T_n ≦ α) return true; else return false |
動作周波数を設定するselect_frequency関数の擬似コードは以下になります．
|
1 2 3 |
select_frequency(): use lowest frequency f_i such that RM_test(f_i / f_L) or EDF_test(f_i / f_L) is true. |
RT-DVFSスケジューリング
RT-DVFSスケジューリングの代表例として，Cycle-Conserving DVFSとLook-Ahead DVFSを紹介します．
Cycle-Conserving DVFS
Cycle-Conserving DVFSはRM/EDF向けのシンプルなDVFSです．
動的なCPU利用率を計算して電圧周波数制御を実行するため，細粒度の周波数セットで効果的です．
Cycle-Conserving DVFS for RM（CC-RM）の擬似コードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
assume f_j is frequency set by static scaling algorithm select_frequency(): set s_m = max_cycles_until_next_deadline(); use lowest frequency f_i such that (d_1 + d_2 + ... + d_n) / s_m ≦ f_i / f_m upon task_release(task_i): set c_left_i = C_i; set s_m = max_cycles_until_next_deadline(); set s_j = s_m * f_j / f_m; allocate_cycles(s_j); select_frequency(); upon task_completion(task_i): set c_left_i = 0; set d_i = 0; select_frequency(); during task_execution(task_i): decrement c_left_i and d_i; allocate_cycles(k): for i = 1 to n, task_i /* tasks sorted by period */ if (c_left_i < k) set d_i = c_left_i; set k = k - c_left_i; else set d_i = k; set k = 0 |
Cycle-Conserving DVFS for EDF（CC-EDF）の擬似コードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 |
select_frequency(): use lowest frequency f_i such that U_1 + U_2 + ... + U_n ≦ f_i / f_L upon task_release(task_i): set U_i to C_i / T_i; select frequency(); upon task_completion(task_i): set U_i to cc_i / T_i; /* cci is the actual cycles used this invocation */ select_frequency(); |
Look-Ahead DVFS
Look-Ahead DVFSは，EDF向けの積極的なDVFSです．
動的スラックが大きいと効果的に消費エネルギーを削減できます．
Look-Ahead DVFS for EDF（LA-EDF）の擬似コードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
select frequency(x): use lowest frequency f_i such that x ≦ f_i / f_m upon task_release(task_i): set c_left_i = C_i; defer(); upon task_completion(task_i): set c_left_i = 0; defer(); during task_execution(task_i): decrement c_left_i; defer(): set U = C_1 / T_1 + C_2 / T_2 + ... + C_n / P_n; set s = 0; for i = 1 to n, T_i /* Note: reverse EDF order of tasks */ set U = U - C_i / P_i; set x = max(0, c_left_i - (1 - U)(D_i - D_n)); set U = U + (c_left_i - x) / (D_i - D_n); set s = s + x; select_frequency(s / (D_n - current_time)); |
リアルタイム動的電力管理（RT-DPM：Real-Time Dynamic Power Management）
リアルタイム動的電力管理（RT-DPM：Real-Time Dynamic Power Management）を紹介します．
RT-DPMの特徴は，RT-VFSでは難しいリーク電流の課題を（ある程度は）解決できることです．
リーク電力は，CPUの製造プロセスの微細化に伴い増加する傾向にあります．
RT-VFSで周波数の低下する場合，タスクの実行時間が長くなり，結果としてリーク電流が増加してしまいます．
この課題を解決するために，RT-DPMが提案されました．
RT-DPMは，リアルタイム性を満たしながら（主に）デバイスの電力状態を制御します．
また，RT-DPMはRT-VFSと統合可能ですので，その統合した代表的なスケジューリングも紹介します．
上図にDPM（左部）とRT-DPM（右部）を示します．
DPMではタスクが実行していない時はアイドル状態になりますが，RT-DPMではスリープ状態に遷移することで消費電力を削減します．
RT-DPMのシステムモデル
RT-DPMのシステムモデルは，LiuとLaylandのモデルに以下を追加したものです．
| 記号 | 説明 |
|---|---|
| \(D = \{D_1, D_2, ..., D_m\}\) | デバイスセット |
| \(\gamma_i\) | \(\tau_i\)の実行中に使用されるデバイスの集合 |
| \(P_a^j\) | アクティブ状態の消費電力 |
| \(P_s^j\) | スリープ状態の消費電力 |
| \(E_{sw}^j\) | a ⇆ sのエネルギーオーバヘッドの合計 |
| \(T_{sw}^j\) | a ⇆ sの時間オーバヘッドの合計 |
| \(B^j = \max \left( T_{sw}^j, \frac{E_{sw}^j - P_s^j * T_{sw}^j}{P_a^j - P_s^j} \right)\) | Break-Even Time |
※jはCPUまたはデバイスID，aはアクティブ状態，sはスリープ状態を表す記号です．
x86-64のAdvanced Configuration and Power Interface（ACPI）とARM64のPower State Coordination Interface（PSCI）
x86-64のAdvanced Configuration and Power Interface（ACPI）とARM64のPower State Coordination Interface（PSCI）を紹介します．
ACPIは，以下の6段階でデバイスの実行状態を遷移します．
深いスリープ状態ほどデバイスの消費電力は小さくなりますが，復帰時間が長くなるというトレードオフが発生します．
- S0：通常の実行状態
- S1：レジスタやキャッシュ，メモリコンテキスト等を保持した状態
- S2：レジスタとキャッシュコンテキストを消失
- S3：メモリ以外のコンテキストを消失
- S4：メモリコンテキストも消失
- S5：完全な電源断状態
これに対して，PSCIはシステムレベル，クラスタレベル（複数のコアを扱うグループ），コアレベルでデバイスの電力状態を制御します．
電力状態には，実行状態，保持状態，電源断状態の3種類があります．
優先度の高い順にシステムレベル，クラスタレベル，コアレベルとなるため，実現可能な電力状態の組み合わせは以下になります．
| システムレベル | クラスタレベル | コアレベル |
|---|---|---|
| 実行状態 | 実行状態 | 実行状態 |
| 実行状態 | 実行状態 | 保持状態 |
| 実行状態 | 実行状態 | 電源断状態 |
| 実行状態 | 保持状態 | 保持状態 |
| 実行状態 | 保持状態 | 電源断状態 |
| 実行状態 | 電源断状態 | 電源断状態 |
| 保持状態 | 保持状態 | 保持状態 |
| 保持状態 | 保持状態 | 電源断状態 |
| 保持状態 | 電源断状態 | 電源断状態 |
| 電源断状態 | 電源断状態 | 電源断状態 |
Break-Even Time
Break-Even Timeとは，アクティブ状態を維持する場合と，スリープ状態に遷移する場合の消費エネルギーが等しくなるような時間Bのことです．
Break-Even Timeの特徴は，深いスリープ時間ほど長いことです．
上図にBreak-Even Timeを考慮したデバイススケジューリングの例を示します．
タスクの優先度は，\(\tau_4 > \tau_1 > \tau_2 > \tau_3\)とします．
また，タスクが使用するデバイスセットは，\(\gamma_1 = \gamma_2 = \emptyset\)，\(\gamma_3 = \gamma_4 = \{D_1\}\)とします．
タスクのリリース，完了にあわせてデバイスを起床，スリープしていることがわかります．
RT-DPMスケジューリング
代表的なRT-DPMスケジューリングは以下になります．
詳細は論文を読みましょう！
- System-Wide Energy-Aware EDF（SYS-EDF）
- RT-DVFSとRT-DPMを統合
- Energy-Efficient Device Scheduling（EEDS）
- RT-DPMのみ
- Device Forbidden Region EDF（DFR-EDF）
- RT-DVFSとRT-DPMを統合
まとめ
今回は省電力スケジューリングを紹介しました．
具体的には，以下の内容を解説しました．
- リアルタイム電圧周波数制御（RT-VFS：Real-Time Voltage/Frequency Scaling）
- リアルタイム動的電力管理（RT-DPM：Real-Time Dynamic Power Management）
リアルタイムシステムで使われているリアルタイムOSは，主にC言語で書かれています．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
