アウトオブオーダ処理
現在、CSの勉強のために、コンピュータアーキテクチャ (電子情報通信レクチャーシリーズ)を読んでいる。
アウトオブオーダ処理とは
プログラムにおいて、実行結果が変わらないように配慮し、データなどの依存関係から見て処理可能な命令について、命令実行・完了の順番を変更することで、並列度をあげ、性能を向上させる手法。
- アウトオブオーダ処理（out of order）：命令を動的に入れ替えて、依存関係がない順で順次実行する方式。
- インオーダ処理（in order）：命令を読み込んだ順番通りに実行する方式。
順番を入れ替えるタイミングで2種類ある。
- アウトオブオーダー実行（out of order execution）
- 命令をEXステージに入れる順番を入れ替える
- アウトオブオーダー完了（out of order completion）
- 実行結果をレジスタに格納する順番を入れ替える
例）以下の実行環境下での次のプログラムの実行時間を計算する。
- ALU（加減算・論理演算）：2つ / 演算時間：1
- 乗算ユニット：2つ / 演算時間：3
- 命令フェッチは同時に2命令
- レジスタは同時に4出力2入力
インオーダ実行 / インオーダ完了
実行時間：12クロック
インオーダ実行 / アウトオブオーダ完了
実行時間：11クロック
アウトオブオーダ実行 / インオーダ完了
実行時間：10クロック （但し、HWの追加変更を行なっている）
アウトオブオーダ実行 / アウトオブオーダ完了
実行時間：9クロック （但し、HWの追加変更を行なっている）
データ依存再考
データ依存性の分類
- フロー依存（flow dependence）
- 命令Aで書き込んだ値を後続の命令Bで読み出すことで起こる A => B の依存関係
- プログラム固有の依存であり、真の依存関係
- （解決策1）フォワーディング
- ハードウェアでAの結果出力からBの演算入力までのデータ遅延（latency）を出来るだけ短くする
- （解決策2）値予測
- Aの結果を予測する技術
- 逆依存（anti dependence）
- 命令Aで読み出したレジスタ（メモリ語）に後続の命令Bが書き込みを行うことで起こる A => B の依存関係
- 主にレジスタの不足からくる依存
- （解決策）レジストリネーミング
- 出力依存（output dependence）
- 命令Aで書き込んだレジスタ（メモリ語）に後続の命令Bが再度書き込みを行うことで起こる A => B の依存関係
- 主にレジスタの不足からくる依存
- （解決策）レジストリネーミング
（2）と（3）は、主にレジスタ数の不足からくる依存である。特にインオーダ処理用のコンパイラ最適化がなされた機械語プログラムでは、レジスタ数が最小化されている場合が多く、インオーダ処理をしている限りは問題にならない。しかしながら、アウトオブオーダ処理ではこれが障害になる。
データ依存とデータハザードの関係性
| データ依存 | データハザード |
|---|---|
| フロー依存 | RAW（read after write）ハザード |
| 逆依存 | WAR（write after read）ハザード |
| 出力依存 | WAW（write after write）ハザード |
上記の3つの依存関係が現れるプログラムを示す。
また、以下の条件下で動作させる場合のパイプラインを考えてみる。
- ALU（加減算・論理演算）：2つ / 演算時間：1
- 乗算ユニット：2つ / 演算時間：3（3段階のステージで分割）
- 命令フェッチは同時に2命令
- レジスタは同時に4出力2入力
アウトオブオーダ実行が可能であっても、データ依存性からくるハザードによって、実行時の並列度が下がることがある。
アウトオブオーダ処理の機構
アウトオブオーダ処理のためには、多数の命令の中で現在実行可能な命令がどれかを選択する必要がある。そのためには、現在実行中の命令とまだ実行していない命令の間の依存関係を検出して、依存関係による待ちがない命令を選んで実行する必要がある。
実行可能な命令を選び出すための機構を「命令ウィンドウ（Instruction Window）」という。命令ウィンドウはデコードが終わった複数の命令を入れておくバッファであり、その中で依存関係と資源競合による待ちがなくなった命令を取り出す機構を備えている。
逆依存と出力依存はレジストリネーミングによって解決されるので、命令ウィンドウではフロー依存のみを解決すればよい。フロー依存を検出するために、各命令の入力データの入出力が揃ったか否かを明示するフラグを命令ウィンドウに持たせる。
命令ウィンドウの種類
- 集中形
- 命令ウィンドウをプロセッサ全体に1個置く
- メリット
- 無駄にメモリを確保する必要がない
- デメリット
- 回路が複雑になる
- 遅延が大きくなる可能性がある
- 分散形
- 各演算ユニットの前段に命令ウィンドウを分散配置する
- 分散配置した命令ウィンドウをリザベーションステーション（reservation station）と呼ぶ
- メリット
- 各リザベーションステーションの規模が小さくて済むため、高速動作が可能
- デメリット
- 分散配置するため、全体として回路規模が大きくなってしまう
レジストリネーミング
逆依存と出力依存は、レジスタ番号の衝突によるものであり、レジスタ数さえ十分にあれば、依存関係を継承することができる。レジスタ番号の置き換えによって並列性を向上させることを、レジストリネーミング（register renaming）と呼ぶ。
ソフトウェアによるレジストリネーミング
以前は実行時間が12クロックだったが、ソフトウェアによるレジスタ番号の置き換えを行うことで、実行時間が9クロックになった。レジストリネーミングにより3クロック短縮することができた。
マッピングテーブル
命令がフェッチされると、当該命令が書き込むレジスタの論理アドレスに対するマッピングテーブルのエントリに、1個の物理レジスタアドレスが書き込まれる。以後、この物理レジスタアドレスを使って計算が進められる。
実行時間は10クロックになった。ソフトウェアによるレジストリネーミングに追加で、リネームのステージが追加されている。
リオーダバッファ
図のようにレジスタと並べて、命令の実行結果を格納するメモリ、リオーダバッファを設ける。リオーダバッファのエントリには、命令が書き込むレジスタのアドレスと、その値の組が格納される。命令がフェッチされると、リオーダバッファに新しいエントリが確保され、当該命令が書き込むレジスタアドレスとwaitタグが書き込まれる。また、命令はリオーダバッファから、このレジスタが読み出すレジスタのアドレスが含まれるエントリのうちで最新の値を読み出す。
命令はリオーダバッファを用いて整形され、レジスタ番号はリオーダバッファのエントリ番号に置き換えられ、命令ウィンドウに送られる。命令ウィンドウは、オペランドデータが全て揃った命令の中で適当なものを実行ユニットに送る。オペランドがwaitタグの場合、データが揃わないので実行ユニットに送られない。命令実行結果をフォワーディングすることにより、データが揃った時点で実行ユニットに送られる。
エントリ番号は命令ごとに異なるため、逆依存や出力依存は発生せず、WARハザード、WAWハザードは起こらない。
また、リオーダバッファのエントリは以下の2つの条件を満たした時に、値をリオーダバッファからレジスタに移す。
- このエントリに書き込んだ命令以前の命令が終了した
- このエントリのレジスタ値が確定し、書き込まれた
まとめ
命令を動的に入れ替えて、依存関係がない順で順次実行する、アウトオブオーダ処理について理解を深めることができた。
効率のいいアウトオブオーダ処理は、命令ウィンドウとレジスタリネーミングによって実現されていることがわかった。
