【コンピュータアーキテクチャ】RMTとリタイアステージについて

やかんです。

以前、アウトオブオーダ実行について書き殴りました（こちら）。今回はその続きというか、「穴埋め」なことをしたいと思っています。

※内容は僕のパブリックなメモでしかないです。

話の流れ

話の流れとしては、

OoOを実現したい
そのためにレジスタリネーミングを行う
では、具体的にレジスタリネーミングはどのように行われているのか？　← 今回はこれ

といったところです。

もちろん僕も勉強しつつなので、間違い等ご指摘お願い致します。

キーワードとしてはRMT、フリーリスト、リタイアステージあたりだと思っています。

本題に入る前にメモ。

このセメスターは結構抱えてしまったものが多くて大変だった印象です。もちろん、抱えなくていいものも勝手に抱えてしまったので自己責任ではあるんですが。

インターン先の諸々とかね

そんなこんなで、勉強、学習に避ける脳のリソースが不足していたように思います。悔しいと言えば悔しい。。ですが最近はいい感じに脳のリソースがリリースされており、勉強、学習に回せるようになってきました。一度回しちゃえばしばらくリソースを独占できるのでありがたい。

で、焦っても意味がないよな、という結論に至っているのが今の状態。僕の場合、単位時間あたりに理解できる事柄の総量は一定です。

この総量を増やしたいという話もあるのだが。

なので、焦らず、単位時間あたりに理解できる事柄の総量以上に求めないように取り組んでいこうと思います。「継続は力なり」という言葉の所以はこの辺りとも言えるんじゃないかなー、など思ったりもします。

以上、メモでした。

RMT

RMTはRegister Map Tableの略で、レジスタリネーミングにおいて論理レジスタと物理レジスタを対応づけるテーブルのことです。

キャッシュにおけるマッピングや、仮想記憶におけるページテーブルのようなものと思って大丈夫なはず。

具体的な命令群で考えます。論理レベルの命令群は以下としましょう。コンパイラが生成してくれた命令群ですね。機械語じゃなくてアセンブリ言語的ですが、ノリで誤魔化します。

ADDi R1, R0, 1 //（即値）
ADDi R2, R0, 1
ADD R3, R1, R2
ADDi R1, R0, 2
ADD R3, R1, R2

ADDiは即値演算です。R0はいわゆるゼロレジスタで、常に0の値を保持してくれることを期待します。

コンパイラが論理的に上書きしているレジスタは、当然物理レベルでも上書きしてOK

はい。例えば上の命令群ではR1とR3が上書きされています。これは、コンパイラが「R1に今入っている値はもう今後の命令で使わないから、上書いちゃってオッケー」としてくれている、ということです。R3も同様。

レジスタリネーミングは、1つの命令がfetchされる度に順次行われるものである

これが結構重要な話なのでは、と思っています。前述の「コンパイラが論理的に上書きしているレジスタは、当然物理レベルでも上書きしてOK」にもつながってきます。

前回の記事（こちら）でも書きましたが、OoOはいわゆる「fetch, decode, execute, memory,,,」みたいな一連の処理が同一の一つのパイプラインで処理されるわけではありません。スケジューラを挟んでフロントエンドとバックエンド、それぞれが別の独立したパイプラインを構成します。だから

fetch
decode
rename（レジスタリネーミング）
dispatch

↑これがスケジューラより前に行われる処理で、フロントエンドパイプラインを構成し、スケジューラを挟んで以下

execute
memory
retire（リタイアステージ）

↑これがバックエンドパイプラインを構成します。

余談ですが、フロントエンドパイプラインのさらに前段で分岐予測も独立したパイプラインを構成します

つまり、先の例をとる場合、

ADDi R1, R0, 1 //（即値）
ADDi R2, R0, 1
ADD R3, R1, R2
ADDi R1, R0, 2
ADD R3, R1, R2

↑これら全ての命令を取得し、デコードした上で、「この論理レジスタにはこの物理レジスタを対応させて、、、」と処理することはしない、ということです。

じゃどうすんのよ

これが、かなりすごいことだと思うんですが、例えば

ADDi R1, R0, 1 //（即値）

という命令を取得、デコードしただけで、R1にどの物理レジスタを対応づけるか決定します。同様に、

ADDi R2, R0, 1

という命令を取得、デコードした段階で、R2にどの物理レジスタを対応づけるか決定します。その命令以降の命令がどのように論理レジスタを使っているかは考慮しないんですね。

当該命令をデコードした段階で得られる情報のみに基づいて、当該論理レジスタと物理レジスタの対応付が行われます。

フリーリスト

前述の「レジスタリネーミングは、1つの命令がfetchされる度に順次行われるものである」を実現するための考えが、フリーリストです。

フリーリストは、「使用可能な物理レジスタ」をリスト形式で管理しているものです。「使用可能な」というのは、「そもそも値を保持していないレジスタ」や「値を保持しているけどいくらでも上書いちゃっていいレジスタ」です。

そして、RMTの説明においてRMTの構造に全く触れていませんでしたが、

ごめんなさい

RMTは例えば以下のようにイメージして問題ないはず。

RMT = {
        R1: P1, // 論理レジスタ : 物理レジスタ
        R2: P2,
        R3: P3,
        ,,,
      }

論理レジスタと物理レジスタの対応表ですね。

RはRegisterのRで、PはPhysical RegisterのPなんかな？なんでLogical RegisterのLじゃないのか気になりますが、置いときましょう。

で、フリーリストは使用可能なレジスタを管理しているので、以下のようなイメージ。

FreeList = [P5, P6, ... P100, ...]

前述の例をとると、

ADDi R1, R0, 1 //（即値）
ADDi R2, R0, 1
ADD R3, R1, R2
ADDi R1, R0, 2
ADD R3, R1, R2

問題は最初にR1が上書きされるところですね。

ADDi R1, R0, 2

この時、RMTとフリーリストは以下のような感じだとします。

RMT = {
        R1: P1, // 論理レジスタ : 物理レジスタ
        R2: P2,
        R3: P3,
        ,,,
      }

FreeList = [P5, P6, ... P100, ...]

R1の値は、コンパイラが生成してくれた命令群において、コンパイラが「R1は論理的に書き潰しちゃっていいよ」と教えてくれているものになります。つまり、

ADDi R1, R0, 2

↑この命令が実行される直前までR1が保持していた値は、もう今後の命令群の中で参照されることがないわけですね。あるいは、「参照されることがない」ということを、コンパイラが保証してくれているわけです。

この辺の理解が合っているか、教えて欲しいです。

そういうわけなので、RMTをフリーリストに基づき以下のように更新しても問題なさそうです。

RMT = {
        R1: P5, // P1 -> P5
        R2: P2,
        R3: P3,
        ,,,
      }

FreeList = [P6, ... P100, ...] // P5をポップした

こうすれば、R1についての「偽の依存関係」が解消されたことになります。論理レベルでは

ADDi R1, R0, 1 //（即値）
ADDi R2, R0, 1
ADD R3, R1, R2
ADDi R1, R0, 2

↑こうですが、物理レベルでは

ADDi P1, P0, 1 //（即値）
ADDi P2, P0, 1
ADD P3, P1, P2
ADDi P5, P0, 2 // <- ここが「偽の依存関係」を解消したところ

となります。

ADDi P1, P0, 1 //（即値）
ADDi P2, P0, 1
ADD P3, P1, P2

↑これらの依存関係については「真の依存関係」なので前後関係を組み替えることはできませんが、これらの命令群の前に

ADDi P5, P0, 2

を実行してもプログラム全体としておかしなことにはならないわけです。

「OoOを実現したい、、！」というモチベを強く意識することが大事だと思います。

リタイアステージ

以上の説明だけだと、「いつかフリーリストが枯渇するじゃん」というツッコミが待ち構えています。

これについては、バックエンドパイプラインにおけるリタイアステージにおいて、論理レジスタと物理レジスタの対応付を解消していいか（つまり、物理レジスタを解放していいか）の確認が行われます。

確認の結果、「物理レジスタ解放していいよ！」となったらフリーリストにその物理レジスタが追加され、「まだ物理レジスタ解放しちゃダメ！」となったら何も行われない、という流れです。

というわけで、レジスタリネーミングを一通り見たと思います。が、あくまでこれはOoOの一環に過ぎないので、まだまだWake UpロジックなどOoOについて見るべきことは残っているんですけどね。。

とは言え長くなってしまったこともありこちらの記事は終了です。最後までお読みいただき、ありがとうございます。