コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

Tomasuloのアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Tomasulo のアルゴリズムとは、1967 年にIBMのRobert Tomasuloによって考案されたコンピュータハードウェアのためのアルゴリズムで、連続した複数の命令が互いの依存関係が解けるまで実行できないような状況で、順序を入れ替えることにより実行できるようにする (アウト・オブ・オーダー実行)ためのものである。このアルゴリズムは、IBM System/360 Model 91 の浮動小数点演算ユニットで最初に実装された。

このアルゴリズムは レジスタ・リネーミングを用いるという点で、CDC 6600のScoreboardingとは異なる。Scoreboardingは、書き込み後の書き込み (WAW) と 読み込み後の書き込み (WAR) によるハザードを、命令の実行を一時停止させることで解決するが、レジスタリネーミングでは命令を連続して発行し続けることが可能である。また、Tomasuloのアルゴリズムは計算結果を必要とするすべての Reservation Station に対してブロードキャストを行うcommon data bus (CDB) と呼ばれる仕組みを用いる。これによって、Scoreboardingを用いた場合には停止してしまうような命令列が、より多く並列実行可能になる。

Robert Tomasuloは、1997年このアルゴリズムによりエッカート・モークリー賞を受賞した。

実装に必要な考え方

[編集]

以下は、Tomasulo のアルゴリズムを実装する上で必要となる考え方である。

  • 命令列の及ぼす結果（例外の発生など）がパイプライン化されないプロセッサと同一であるよう、命令は順序どおりに発行される（ただし、実行は順序どおりではない）。
  • 全ての汎用レジスタおよび Reservation Station レジスタは、「実際の値(real value)」あるいは「仮想的な値(virtual value)」を格納する。命令の発行の過程で、演算結果を出力するレジスタが利用できない場合、最初は仮想的な値が用いられる。また実際の値を計算している機能ユニットは、仮想的な値として割り当てられ、機能ユニットが演算を完了すると、仮想レジスタの値が実際の値に変換される。
  • 機能ユニットはReservation Stationを複数のスロットで使用する。各スロットは、演算の種類や、演算対象のデータなど、一つの命令を実行するために必要な情報を保持する。機能ユニットは命令に必要な入力データが全て「実際の値」になると実行を開始する。

命令のライフサイクル

[編集]

各命令は、発行した時から実行が完了する時まで以下の3つのステージを流れる。

ステージ 1: 発行

[編集]

発行のステージでは、全てのデータとreservation stationの準備ができていれば命令が実行にまわされ、そうでなければ一時停止する。レジスタの名前はこの時点で変更され、WAR と WAW によるハザードを発生させないようにする。

  • 命令キューの先頭から次の命令を取り出す
  • 命令で処理するデータがレジスタに入っている場合
    • 使用していない reservation station がある(すなわち機能ユニットが利用できる)場合
      • 命令を発行
    • 使用していない reservation station がない(すなわち機能ユニットが利用できない)場合
      • reservation station やバッファの準備ができるまで命令の実行を停止
  • 命令で処理するデータがレジスタに入っていない場合
    • 仮想的な値を使用して、結果を計算する機能ユニットの状態を追跡

ステージ 2: 実行

[編集]

実行のステージでは、命令が実際に実行される。命令は全ての操作対象が利用可能になるまで待機し、RAW のハザードを発生しないようにする。メモリによるハザードを防止するためのアドレス演算の過程で、プログラムの結果が正しいことが保証される。

  • 操作対象のデータのうち利用できないものがある場合
    • common data bus (CDB) を監視し、計算が完了するようになるまで待機
    • 操作対象のデータが利用可能になると、対応する reservation station にこのデータを配置
  • 操作対象のデータが全て利用可能になると
    • 命令がロードかストアの場合
      • ベースアドレスが利用可能であれば、実効アドレスを計算
      • 実効アドレスをロードないしストアのバッファに格納
      • 命令がロードの場合
        • メモリユニットが利用可能になり次第、命令を実行
      • 命令がストアの場合
        • メモリユニットに送る前に、値が格納されるまで待機
    • それ以外の場合には、ALU の操作
      • 対応する機能ユニットで命令を実行

ステージ 3: 結果の書き出し

[編集]

結果の書き出しのステージでは、ALU の操作による結果がレジスタに書き戻され、またストア命令のメモリへの書き出しが行われる。

  • 命令が ALU の操作の場合
    • 結果が利用可能になっていれば
      • CDBに書き込み、CDB から結果を待つレジスタや reservation station に書き込み
  • ストアの場合
    • この段階でデータをメモリに書き込み

関連項目

[編集]

外部リンク

[編集]

参考文献

[編集]
「https://ja-two.iwiki.icu/w/index.php?title=Tomasuloのアルゴリズム&oldid=77090749」から取得