レジスタ・リネーミング

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

解決すべき問題

プログラムは、何らかの値に何らかの操作をする命令が並んだものである。命令がそれらの値を区別するために、それぞれの値に名前をつける。たとえば、「X と Y を足して、結果を Z に置く」という命令では、X、Y、Zが格納場所の名前である。

命令をコンパクトにまとめるため、多くのプロセッサの命令セットでは直接名前を指定でき、かつ高速に読み書きできる特別な場所を少しだけ用意している。これをレジスタと呼ぶ。

たとえば、x86 命令セットアーキテクチャでは8個の整数レジスタがあり、x86の64ビット版（AMD64）では16個、PowerPCや多くのRISCでは32個、そしてIA-64では128個用意している。小さなプロセッサでは、これらの場所の名前は直接レジスタファイルの中の場所に対応している。

一方、命令の種類が違えば、その処理にかかる時間も異なる。たとえばプロセッサはメモリからロードしようとしている間に何百という命令を実行できるかもしれない。短い命令を時間のかかるロードを待っている間に行うと、命令がプログラムが本来指定している順番とは違った順番で進行していることになる。このようなアウト・オブ・オーダー実行は性能向上のために最近の高性能CPUでよく行われている。

上述を踏まえ、以下のようなコードをアウト・オブ・オーダー実行CPUで動作させることを考える。

レジスタ・リネーミング適用前
#	命令	オペレーション
1	ロード	メモリ1024番地からレジスタ1へ
2	加算	レジスタ1へ数値 2 を加算
3	ストア	レジスタ1の内容を1032番地へ
4	ロード	2048番地からレジスタ1へ
5	加算	レジスタ1へ数値4 を加算
6	ストア	レジスタ1の内容を2056番地へ

#4, 5, 6 の命令は #1, 2, 3 の命令とはやろうとしていることに依存関係はない。しかし、命令#4 は命令#3 が完了しないと実行できない。さもなくば、命令#3 は間違った値を書き込んでしまうかもしれないからである。具体的には、レジスタ1の内容が、命令#3で読み取っている最中に命令#4で書き換えられてしまう可能性がある。

これは、レジスタの名前を変えるだけで解決可能である。

レジスタ・リネーミング適用後
#	命令	オペレーション
1	ロード	メモリ1024番地からレジスタ1へ
2	加算	レジスタ1へ数値 2 を加算
3	ストア	レジスタ1の内容を1032番地へ
4	ロード	2048番地からレジスタ2へ
5	加算	レジスタ2へ数値4 を加算
6	ストア	レジスタ2の内容を2056番地へ

これで命令#4,5,6 と命令#1,2,3は並行して実行できるようになり、プログラムが高速化される。

レジスタ・リネーミングで並行実行可能に成る
#	命令(X)	オペレーション(X)	命令(Y)	オペレーション(Y)
1	ロード	メモリ1024番地からレジスタ1へ	NOP	（メモリからの読み出しは並行実行不可）
2	加算	レジスタ1へ数値 2 を加算	ロード	2048番地からレジスタ2へ
3	ストア	レジスタ1の内容を1032番地へ	加算	レジスタ2へ数値4 を加算
4	NOP	休止	ストア	レジスタ2の内容を2056番地へ

可能ならば、コンパイラはこの種のリネーミングを行う工夫を行う。しかしレジスタ数はどのプロセッサでも少ないため、コンパイラ(ソフトウェア)でできることは限られる。

多くの高性能CPUは、公開されている仕様より多くの実レジスタを持っていて、レジスタをいわば仮想化し命令が示すレジスタと実レジスタの対応をハードウェアで動的に切り替えて( レジスタリネーミングして )いる。このようなリネーミングにより並列性を高めている。

ハザードとリネーミング

複数の命令がオペランドとしてある特定の場所を（入力、出力に関わらず）参照しているとき、それらの命令を本来のプログラムとは異なる順番で実行しようとすると、ハザードと呼ばれる三種類の問題が発生する。

リード・アフター・ライト (RAW): 書き込み後の読み込み; レジスタやメモリから読み込む場合、その値はプログラムの順番上最も後にその場所に書き込まれた値でなければならない。これは真の依存性と言われ、命令をプログラムの順番通りに実行することを要求するものである。
ライト・アフター・ライト (WAW): 書き込み後の書き込み; 同じレジスタまたはメモリアドレスへの書き込みが二回あった場合、二回目の書き込み内容が最終的に格納されていなければならない。これは一つ目の書き込みを必要に応じて実質的に無いものとすれば解決できる。
ライト・アフター・リード (WAR): 読み込み後の書き込み; レジスタやメモリからの読み込みでは最後にその場所に書かれた内容が得られなければならず、プログラム上その読み込みより後の書き込みの内容が読み込まれたりしてはならない。このような偽の依存性はリネーミングで対処できる。

全ての読み込みが終わるまで書き込みを遅らせる代わりに、その場所に関してふたつのコピーを用意し、一方に古い値を格納し、もう一方に新しい値を格納する。(プログラム上の順番で)新しい値を書き込む前の読み込みは古い値を格納した方を使い、書き込み後の読み込みは新しい値を格納した方を使用する。偽の依存性はなくなり、アウト・オブ・オーダー実行がさらに効果的に行われるようになった。古い値を必要とする読み込みが全て実行し終えたら、そのコピーを捨てればよい。これがレジスタ・リネーミングの基本的な概念である。

読み書き可能なものは何でもリネーミング可能である。一般には汎用レジスタや浮動小数点レジスタが議論されるが、フラグやステータスレジスタ、さらに個別のステータスビットまでリネーミングが可能である。

メモリもリネーミングが可能であるが、レジスタ・リネーミングのように一般的に行われているわけではない。トランスメタのCrusoeプロセッサはストアバッファを持っていて、これが一種のメモリ・リネーミングになっている。

プログラムがレジスタの再利用をやめれば、レジスタ・リネーミングの必要はなくなる。いくつかの命令セット(たとえばIA-64)では、非常に多くのレジスタが使えるようになっているが、それは主にレジスタ・リネーミングをしないためである。この手法には下記の問題がある。

コンパイラにとってはレジスタを再利用しないことはコード量の増大を招く。ループ処理では、ループするたびに違うレジスタを使用しなければならなくなり、コードが複雑になってしまう（ただし、IA-64ではレジスタローテーションという技法でこれを回避している）
レジスタ数が増えるとそれを識別するためのビット数が増え、命令ワードが大きくなってしまう。
多くの命令セットが歴史的に少数のレジスタを使っており、いまさら変更できない。

コードサイズが増えるというのは重要で、そのために命令キャッシュでキャッシュミスが起きやすくなり、結果としてパイプラインがストールすることが多くなってしまう。（同じ命令キャッシュサイズの場合）

アーキテクチャ上のレジスタと実際のレジスタ

機械語のプログラムでは命令セットアーキテクチャ (ISA) によって規定された数のレジスタで読み書きを行う。たとえば、AlphaのISAは32本の64ビット整数レジスタと32本の64ビット浮動小数点レジスタを規定している。これらはアーキテクチャ上のレジスタである。 Alpha命令セットの動作するプロセッサのためのプログラムはそれら64本のレジスタを読み書きする命令から成っている。プログラマがデバッガを使ってプログラムの実行を中断すると、それら64本のレジスタの内容を知ることができる。

Alpha 21264 はこのISAを実装しているプロセッサのひとつであるが、物理的には 80本の整数レジスタと 72本の浮動小数点レジスタを持っている。つまり、Alpha 21264 は整数処理の結果を格納できる80の分離した格納場所を持ち、浮動小数点演算結果を格納できる72の分離した格納場所を持っている。（実際にはそれ以上の格納場所があるのだが、それらはレジスタ・リネーミングとは無関係である。）

以下では、レジスタ・リネーミングのふたつの手法を説明していく。これらはデータ格納回路の構成で区別される。

すべてのリネーミング手法では、命令が参照しているアーキテクチャ上のレジスタをタグに変換する。アーキテクチャ上のレジスタが3ビットから5ビットで識別される(8～32コのレジスタを識別できる)としたら、タグは一般に6から8ビットとなる。リネームファイルはサイクル毎に命令を入力ポートから読み込んで、リネームを施した(若干長くなった)命令を出力ポートに出力する。レジスタファイルはポート数の二乗に比例して回路が大きくなるため、物理的に大きく、電力も消費する。

タグインデックス付レジスタファイルという形式では、データ格納のための大きなひとつのレジスタファイルがあり、タグ毎にひとつのレジスタを持っている。たとえば、マシンが80本のレジスタを物理的に持っていたら、タグは7ビットとなり、タグ値のうち48種類は使用されない。またこの形式では、命令が実行ユニットに発行されると、ソースレジスタのタグが物理レジスタファイルに送られ、それらのタグに対応したレジスタの内容が実行ユニットに渡される。

予約機構(Reservation Stations)という形式では、より小さなレジスタファイルが複数存在し、それぞれが個々の実行ユニットに対応している。各命令の各オペランドはそれらレジスタファイルのいずれかの場所に対応している。この形式では、実行ユニットに命令が発行されると、その実行ユニットに対応したレジスタファイルからオペランドに指定されたレジスタ内容が実行ユニットに送られる。

アーキテクチャ上のレジスタファイル
または Retirement Register File (RRF): コミットされたマシンの状態。; 論理レジスタ番号でインデックスされたRAM。; 典型的にはリオーダーバッファからリタイアあるはコミットされて出てきた値が書き込まれる。
Future File: 最も投機的に使用されているレジスタ状態。; 論理レジスタ番号でインデックスされたRAM。
Active Register File: インテル P6 グループでの Future File の呼び方。
History Buffer: Future File と組み合わせて使われる。; 上書きされるレジスタの古い値を格納。; その古い値を作った命令が実行中なら、それはHistory Bufferの番号でインデックスされたRAMかもしれない。; 分岐予測が失敗した場合、History Buffer を使って古い内容を新しいものとしてコピーするかFuture Fileを読めなくする。; History Buffer は論理レジスタ番号でインデックスされる連想メモリ (Content Addressable Memory) である。
Reorder Buffer (ROB): 実行中の命令に関する様々な情報が順番に並ぶ。ただし、History Bufferとは異なり、Redorder BufferはFuture FileとRRFの間に存在する。; Reorder Bufferはデータ無しバージョンとデータ有りバージョンがある。; WillametteのROBの各エントリは物理レジスタファイル(PRF)内のレジスタを指しており、他にも様々な簿記的情報を格納している。; P6のROBでは、各エントリがデータを持っている。PRFは分離されていない。ROBのデータはリタイア時にRRFにコピーされる。

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

これは、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がそれである。他にも同様の構造のデータ格納域を持っている。しかし、初期のマシンはリネーム機構に連想メモリを使っていた。アウト・オブ・オーダー実行のマイクロアーキテクチャは連想メモリを排除することで進化してきたと言える。小さな連想メモリは便利だが、大きな連想メモリは現実的でない。