レジスタ・リネーミング

レジスタ・リネーミング(register renaming)とは、コンピュータのプログラム内でレジスタを再利用しているために不必要な順序依存性が生じているのを、より多くの実在するレジスタを利用して再利用されているレジスタに割り当て、依存を無くす技術である。

詳細：タグインデックス付レジスタファイル

これは、R10000、21264、AMD AthlonのFP部分に使われた形式である。
リネーミング段階では、参照されているアーキテクチャ上のレジスタ全部について、アーキテクチャ上のレジスタ番号でインデックスされたリマップ・ファイルを参照する。
このファイルはタグとレディビットを返す。
そのレジスタに書き込もうとしている命令が実行中で完了していない場合、渡されたタグはレディ状態でないということになる。
読み込みオペランドの場合、タグは命令で指定されたアーキテクチャ上のレジスタ番号と置き換えられる。書き込みオペランドについては、毎回新たなタグをフリータグFIFOから取り出して使用する。
そして、新たなマッピングがリマップ・ファイルに書き込まれ、その後の命令が同じレジスタを読み込む場合にそのタグを得ることになる。タグは命令が実行されていないのでレディでない状態とされている。
以前にそのアーキテクチャ上のレジスタに割り当てられていた物理レジスタは対応する命令と共にReorder Bufferに格納される。
Reorder BufferはFIFOで命令をプログラムの順番通りに並べて格納し、デコードから実行完了までの間保持する。
命令はその後様々な発行キューに置かれる。
命令が実行されると、その結果に関わるタグが全体に通知される。
そのタグをソースタグとして持っている命令が発行キューにあると、そのタグはレディ状態に変化する。
リマップ・ファイルでも同様にマッチしたタグをレディ状態に変更し、対応する物理レジスタが使用可能であることを示す。
発行キュー上の命令の全てのオペランドがレディになると、その命令が実行可能となる。
発行キューはサイクル毎に実行可能となった命令を取り出して機能ユニットに送る。
実行可能になっていない命令はキューに留められる。このように発行キューから順番とは関係なく命令を取り除くことによって性能が向上するのである。
実行される命令はタグインデックス付物理レジスタファイルから読み込んで、処理を実行する。
実行結果はタグインデックス付物理レジスタファイルに書き込まれ、そのタグがレディになったことが全体に通知される。
実行完了すると、結果格納したアーキテクチャ上のレジスタに以前対応していたタグがフリータグFIFOにつながれ再利用される。
例外や分岐予測失敗が発生すると、正しく完了している命令までの結果でリマップ・ファイルを戻す。
この機構があって、いかなるリマップ状態にも戻せるので、分岐予測失敗処理は対応する分岐命令が実行完了する前に完了できる。
そのため分岐予測失敗による遅延は発生しない。
(予測失敗していなければもっと性能向上したのにという話は、まったく別のことである。)

詳細：予約機構(Reservation Stations)

これはAMD K7とK8で整数部分に使われた形式である。
リネーミング段階では、読み込み参照されるアーキテクチャ上のレジスタはアーキテクチャ上の番号でインデックスされたFuture Fileとリネームファイルを参照して得る。
そのレジスタに書き込もうとしている命令がなければ、Future Fileを読めばそのレジスタの値が得られる(つまりその値はレディ状態である)。
命令が発行キューに置かれると、Future Fileから読んだ値は予約機構内の対応するエントリに書き込まれる。
命令によるレジスタへの書き込みは新たなレディでないタグを生成し、リネームファイルに書き込まれる。
タグ番号は命令の順番に付けられる。つまり、フリータグFIFOは不必要となる。
タグインデックス形式と同様、発行キューはレディでないオペランドが全体通知されるタグとマッチするのを待つ。
タグインデックス形式と違うのは、タグがマッチしたときに対応する予約機構のエントリにも値が書き込まれることである。
発行された命令は予約機構から引数を読み、実行する。
前述したように予約機構のレジスタファイルは一般に小さく、8エントリほどしかない。
実行結果はReorder Bufferに書き込まれ、予約機構にも書き込まれ(発行キューのエントリがマッチするタグを持っている場合)、Future Fileにも書き込まれる（それがそのアーキテクチャ上のレジスタをターゲットとした最新の値の場合）。
完了処理ではReorder Bufferからアーキテクチャ上のレジスタファイルに値をコピーする。
アーキテクチャ上のレジスタファイルの唯一の存在理由は例外と分岐予測失敗のリカバリを簡単にするためである。
例外と分岐予測失敗は完了処理で認識され、アーキテクチャ上のレジスタファイルをFuture Fileにコピーして、リネームファイル内のレジスタを全てレディ状態に変更する。
一般にデコードと完了の間の状態の命令についての中間状態を再構築する方法はないので、分岐予測失敗を早めにリカバリすることはできない。

方式の比較

どちらの方式でも命令は順番どおりにキューに追加され、アウト・オブ・オーダーで削除される。
キューに穴ができたとき、後ろから詰めないと使われていないエントリが多くなっていく。
それを防ぐには可変優先度エンコーディング機能が必要とされる。
穴を詰める機能のあるキューは単純な優先度エンコーディングと言えるのだが、キューを詰めるには非常に大きな回路を必要とする。
予約機構はリネームから実行までの遅延時間が短い。なぜならリネーム段階で物理レジスタ番号ではなく値そのものを得ることができるからである。
この遅延時間は分岐予測失敗時の遅延時間の一部となる。
予約機構は命令発行から実行までの遅延時間も短い。なぜならローカルなレジスタファイルがタグインデックス方式より小さいからである。
タグ生成と例外処理も予約機構の方が単純である。これは以下で解説する。
予約機構で使われる物理レジスタファイルは使われていないエントリをつぶすと同時並行して発行キューも処理する。これにより結果としてレジスタファイルが大きいのと同じ効果を生み、性能向上をもたらす。ただしレジスタファイルの回路はタグインデックス形式よりも複雑である。
予約機構の各エントリは結果を書き込むことができるため、8個の発行キューに繋がれた予約機構はタグインデックス形式に比較して9倍もバイパス機構（全体に通知する仕組み）を活用している。
したがって、予約機構形式はタグインデックス形式よりも大きな回路となってしまう。
さらに、予約機構形式は結果を格納するための場所を4箇所（Future File、予約機構、Reorder Buffer、アーキテクチャ上のレジスタファイル）持っている。一方、タグインデックス形式では一箇所だけ（物理レジスタファイル）である。
機能ユニットが結果を通知して書き込む箇所があちこちにあるため、予約機構形式はタグインデックス形式より大きな回路と電力と時間が必要となってしまう。

歴史

初期のアウト・オブ・オーダー実行マシンの、IBM System/360 モデル91 メインフレームは、レジスタ・リネーミングを使用したTomasuloのアルゴリズムを使用した。1990年のPOWER1は、レジスタ・リネーミングとアウト・オブ・オーダー実行を実装した、最初のマイクロプロセッサである。
R10000の本来の設計は実行キューを縮める機能も可変優先度エンコーディングも持っていなかった。そして結果としてリソース欠乏問題に直面した。つまり、リネームすべきレジスタがなくなって命令デコードがストップして、他の命令が実行されるまでキュー上の最も古い命令の実行が行えなかったのである。後のバージョンでは部分的な可変優先度エンコーディングを使ってこの問題に対処した。
初期のアウト・オブ・オーダー実行マシンはリネーミング機構とROB/PRFを分離していなかった。そのため、初期のマシンではスケジューリングとリネーミングとデータ格納域が一体化していたのである。最近のマシンは論理レジスタ番号でインデックスされたマップテーブルをRAMとして持っている。たとえば、P6 がそうなっていて、Future Fileがそれである。他にも同様の構造のデータ格納域を持っている。しかし、初期のマシンはリネーム機構に連想メモリを使っていた。アウト・オブ・オーダー実行のマイクロアーキテクチャは連想メモリを排除することで進化してきたと言える。小さな連想メモリは便利だが、大きな連想メモリは現実的でない。