Tomasuloのアルゴリズム

Tomasulo のアルゴリズムとは、1967 年にIBMのによって考案されたコンピュータハードウェアのためのアルゴリズムで、連続した複数の命令が互いの依存関係が解けるまで実行できないような状況で、順序を入れ替えることにより実行できるようにする (アウト・オブ・オーダー実行)ためのものである。このアルゴリズムは、IBM System/360 Model 91 の浮動小数点演算ユニットで最初に実装された。
このアルゴリズムは レジスタ・リネーミングを用いるという点で、CDC 6600のScoreboardingとは異なる。Scoreboardingは、書き込み後の書き込み (WAW) と 読み込み後の書き込み (WAR) によるハザードを、命令の実行を一時停止させることで解決するが、レジスタリネーミングでは命令を連続して発行し続けることが可能である。また、Tomasuloのアルゴリズムは計算結果を必要とするすべての Reservation Station に対してブロードキャストを行うcommon data bus (CDB) と呼ばれる仕組みを用いる。これによって、Scoreboardingを用いた場合には停止してしまうような命令列が、より多く並列実行可能になる。
Robert Tomasuloは、1997年このアルゴリズムによりエッカート・モークリー賞を受賞した。
実装に必要な考え方.
以下は、Tomasulo のアルゴリズムを実装する上で必要となる考え方である。
命令のライフサイクル.
各命令は、発行した時から実行が完了する時まで以下の3つのステージを流れる。
ステージ 1: 発行.
発行のステージでは、全てのデータとreservation stationの準備ができていれば命令が実行にまわされ、そうでなければ一時停止する。レジスタの名前はこの時点で変更され、WAR と WAW によるハザードを発生させないようにする。
ステージ 2: 実行.
実行のステージでは、命令が実際に実行される。命令は全ての操作対象が利用可能になるまで待機し、RAW のハザードを発生しないようにする。メモリによるハザードを防止するためのアドレス演算の過程で、プログラムの結果が正しいことが保証される。
ステージ 3: 結果の書き出し.
結果の書き出しのステージでは、ALU の操作による結果がレジスタに書き戻され、またストア命令のメモリへの書き出しが行われる。