アウトオブオーダ実行とTomasuloアルゴリズム

なぜ順不同に実行するのか

インオーダ実行のパイプラインは、ある命令がオペランドを待って止まると、その後ろにある独立した命令まで道連れに止まります。パイプラインのハザードで見たストールが、依存のない命令にまで波及してしまうわけです。

メモリ参照のように完了まで数十〜数百サイクルかかる命令の後ろには、本来なら先に進められる命令が大量に並んでいます。アウトオブオーダ実行は、オペランドの揃った命令から順序を入れ替えて先に実行し、長レイテンシ命令の陰でほかの仕事を進めて空きサイクルを埋める手法です。鍵は「どの順序入れ替えなら結果が変わらないか」を正しく見抜くことにあります。

3種類の依存と、消せる依存

命令間の依存は次の3種類に分けられます。実行順を入れ替えてよいかは、どの依存かで決まります。

RAW（Read After Write）は、後の命令が前の命令の生成値そのものを必要とする真のデータ依存で、これだけは順序を守らねば結果が壊れます。一方 WAR と WAW は、たまたま同じアーキテクチャレジスタという名前を再利用したことで生じる見かけの依存です。値の流れは無関係なので、別の物理的な置き場を割り当てて名前の衝突を解消すれば消せます。これがレジスタリネーミングです。

Tomasuloアルゴリズムの構成要素

1967年にIBM System/360 Model 91のためにRobert Tomasuloが考案した方式が、現代の動的スケジューリングの原型です。中心は次の3つです。

• リザベーションステーション（RS）：各実行ユニットの前段にある命令の待合所。命令をオペランドが揃うまで保持する。
• レジスタリネーミング：RSのエントリ番号を「値の生産者の名札」として使い、偽の依存を消す。
• コモンデータバス（CDB）：実行結果を、その値を待つすべてのRSとレジスタへ一斉にブロードキャストする共有配線。

各RSエントリは、オペランドの「値」または「まだ無いならその値を生産するRSの番号（タグ）」を保持します。発行（issue）時点でオペランドがレジスタにあればその値を、まだ計算中ならそのタグをコピーします。

RSエントリ（概念）
[ Op | Vj | Vk | Qj | Qk | Busy ]
  Vj,Vk : 揃ったオペランドの値
  Qj,Qk : 未到着オペランドを生産するRSのタグ（0なら値が有効）

オペランドはどう揃い、どう発行されるか

動作は次のサイクルに分かれます。

1. Issue（発行）  : 命令をRSへ。オペランドが有効なら値を、
                    未到着ならその生産者のタグをQj/Qkへ記録。
                    書き先レジスタのリネームタグを「このRS」に更新。
2. Execute（実行） : Qj/Qkが両方ゼロ（値が揃った）になった
                    命令から、ユニットが空き次第、順不同で実行。
3. Write（書込み） : 結果をCDBへ。タグの一致するRS/レジスタが
                    値を取り込み、対応するQをゼロにする。

要は、各RSが自分の待つタグをCDB上のタグと照合し、一致した瞬間に値を吸い上げて起動条件を満たしていく、というデータフロー駆動です。レジスタファイルを介さず生産者から消費者へ値が直接渡るので、WARもWAWも介在しません。順序はオペランドの到着、すなわちRAW依存だけが決めます。

ROBによる順序付きリタイア

オリジナルのTomasuloは結果を即レジスタへ書くため、順不同に書き込んだ後で例外や分岐予測ミスが起きると、状態を巻き戻せません。これを解決するのが**リオーダバッファ（ROB）**です。

ROBはプログラム順に並んだFIFOリングで、発行時に末尾へ1エントリ確保し、リネームの行き先を物理レジスタではなくROBエントリにします。命令はROBに完了結果を一時的に溜め、先頭（最古）の命令が完了済みになって初めてアーキテクチャ状態へ反映され、ROBから取り除かれます。これが**リタイア（コミット）**です。

Issue → Execute → Write（ROBへ） → Commit（先頭から順番に）
                                    ↑ ここだけは厳密にプログラム順

順不同に実行しても、外から観測できる状態の更新は厳密にプログラム順という二段構えが、正しさと性能を両立させる核心です。実行は乱しても、コミットは乱さない――この分離がアウトオブオーダ実行の設計判断の要です。

並列度を決めるのはウィンドウの広さ

どれだけ命令を先読みして並べ替えられるかは、命令ウィンドウ（ROBやRSや物理レジスタの数）の大きさで決まります。ウィンドウが広いほど独立命令を多く拾え、長レイテンシ命令の陰を埋められます。

しかしウィンドウを広げるコストは線形では済みません。RSのタグ照合は全エントリ並列のため、エントリ数を増やすと比較器とCDB配線が増え、配線遅延と消費電力が膨らみます。物理レジスタも増やすほどポート数が要り、面積が効きます。「ウィンドウを倍にしても性能は倍にならない」逓減があり、ここに動的スケジューリングの設計上の上限が生まれます。長レイテンシの根源であるキャッシュの原理を併せて抑えることが、実効性能では同じくらい重要になります。

まとめ

• アウトオブオーダ実行は、RAW（真の依存）だけを守り、WAR/WAW（名前の衝突）はレジスタリネーミングで消して並列度を引き出す。
• Tomasuloアルゴリズムは、リザベーションステーションでオペランドの到着を待ち、CDBで結果を待ち手へ一斉配送するデータフロー駆動で動く。
• ROBは完了結果を一時保持し、プログラム順にコミットすることで、投機実行や例外があっても観測状態を逐次実行と一致させる。
• 並列度は命令ウィンドウの広さで決まるが、タグ照合・CDB・レジスタポートのコストが逓減を生み、設計上の上限となる。