【コンピュータアーキテクチャ】アウトオブオーダ実行

やかんです。

今日も今日とてコンピュータアーキテクチャの復習です。今回はいわゆるOOOの復習になります。

OOOとは？

アウトオブオーダ実行のことです。だから、OOO（Out Of Order）よりもOoO（Out of Order）の方が適当なんですかね。わかりませんが。

文脈としては、パイプラインの高性能化だと思われます。データハザードに負けたくないよねっていう。

先日の高位合成の授業でも扱われましたが（授業メモはこちら）、やはりOoOはCPUにとって必須の技術と言えるんですね。CPUあるいはプロセッサはやはり「汎用性」という重要な使命があるようで、その点でハードウェアで実装する場合に比べて制約があると理解しています。「制約がある中でどのように効率化を図ろうか」といった場合に、OoOなしに効率化を考えることは難しそうです。

あとは、個人的にOoOがソフトウェア制御じゃなくてハードウェア制御な点がかなりアツいのでは、と感じています。

OoOを実現するには、OoOが実現可能なようにお膳立てしてあげる必要があるよねっていう話。

コンパイラなどが頑張ってくれるおかげで、一連のプログラムは32あるいは64bit長の命令群として存在してくれます。これ自体意味がわからないほど天才的ですが、OoOしようと思った時にこれら命令群をテキトーに並べ替えることはできないわけなので、何らか工夫する必要があります。

それが、レジスタリネーミング。

レジスタリーミングはOoOのパイプラインにおいてフロントエンドにて行われます。これに対してスケジューラを挟んで「向こう側」がバックエンドですね。

というわけで、まずはレジスタリーネミングの説明を試みながら、自分の理解の解像度を上げていきたいと思います。

レジスタリネーミングの概要

レジスタリネーミングは、「プログラムをコンパイラが機械語にしてくれて、それをCPUが一生懸命実行してくれる」という文脈に沿って理解したいと思っています。

コンパイラは、デバイス（というかCPU）に積まれたレジスタ数も変数に取りつつ、機械語を出力する関数的なポジションです。だから、生成された機械語はレジスタ数に依存するわけです。

レジスタという有限な資源が複数命令間で共有されるわけで、そのため「依存関係」が生じます。依存関係は賢い人が以下の4つに整理してくれています、ありがたいですね。

1. Read After Read（読んでから読む）
2. Read After Write（書いてから読む）
3. Write After Read（読んでから書く）
4. Write After Write（書いてから書く）

↑こちらの4つ。1つずつ見ていきます。

まず、Read After Read。これは、同じレジスタの値を2つの命令が読むだけなので、資源共有による不都合は生じないですね。無視します。

次にRead After Write。これは、Aという名前のレジスタにある値を書き込み、のちにAというレジスタからその値を読み出す、という場合の依存関係です。これは、順序を逆にしてしまうと意味をなさなくなってしまいますね。例えばAレジスタに3という値を保持してその値を読む、という処理をしたいのに、3という値を書き込む前にAレジスタを読んでも意味ないですね。これは「真の依存」と呼ばれます。

次にWrite After Read。これは、読んだ後に、そのレジスタの値を上書くパターンです。だから、値を読むまでは上書きされちゃ困るわけですが、そもそもレジスタ数が「読まれる値を格納しているレジスタ」と「値を書き込む先のレジスタ」の最低2つあれば、依存関係は生じないわけです。これはリソースを（見かけ上）増やせば解決する依存関係ということで、「偽の依存」と呼ばれます。

最後にWrite After Write。これもWrite After Readと同じ話で、2回あるWrite命令がそれぞれ別のレジスタを書き込み先として指定していれば解決される依存関係です。リソース不足によって生じているわけなので、こちらも「偽の依存」ですね。

ふう。大変ですね。レジスタリネーミングの話に戻ると、そもそも「依存関係があると命令の実行順序を固定せざるを得ない、つまりOoOを実現できない」というのが嫌なわけなので、何とかこの依存関係を解消していきたいわけです。

ここで、偽の依存は「リソース不足（レジスタ数の不足）」によって生じていた点を強く意識します。真の依存はどうしようもない（つまり命令の実行順序を維持するほかない）ように思えますが、偽の依存は、見かけ上のリソース（レジスタ数）を増やすことで依存関係を解消することができそうです。

で、その「見かけ上のレジスタ数を増やす」手法がレジスタリネーミングです、、合ってるよね？？？

レジスタリネーミングのちょっとだけ詳細

どこかの記事も書いた通り、こういう概念系のお話は「自分でどこまで説明できますか」っていうのを大事にしながら進めたいと思っています。

いろいろ細かいことは置いといて、まず具体的にレジスタリネーミングをざっくり見てみましょう。命令群として以下を考えます。この時、以下に示しているのはリネーミング前の命令群だという点を強く意識します。コンパイラが生成してくれた「出来立てほやほや」の命令群ってわけですね。

ADD R1, R2, R3
SUB R4, R1, R5
ADD R1, R6, R7

Rxというのは、x番の論理レジスタという意味です。アセンブリ言語みたいな感じで、例えばADD R1, R2, R3は、レジスタR2の値とレジスタR3の値をADDした結果をレジスタR1に格納する、と読みます。

さて、レジスタR1に着目しましょう。R1の値は最初のADD命令で値が書き込まれ、次のSUB命令で値が読み出され、最後のADD命令でさらに値が上書きされています。OoOを実現する際、例えば最初のADDと最後のADDを入れ替えてしまうと全く命令の意味が変わってきちゃうわけです。

SUB命令と最後のADD命令に着目すると、R1について両者はWrite After Readの関係にあります（SUBにおいてReadした後にADDでWriteする）。「偽の依存関係」ですね。つまり、レジスタが豊富にあった場合には生じない依存関係ということです。

では、話も長くなってきたのでここでレジスタリネーミングを行います。以下の命令群が、上記の命令群に対してレジスタリネーミングを行ったものです。

ADD P1, P2, P3
SUB P4, P1, P5
ADD P100, P6, P7

Pxというのは、x番の物理レジスタという意味です。論理レジスタを物理レジスタに対応させたわけですね。注目すべきは、最初のADD命令と最後のADD命令で書き込む先の物理レジスタに異なるレジスタが用いられている点です。こうすることで、例えば以下のように命令の実行順序を入れ替えたとしても正常に動作してくれるはずです。

ADD P100, P6, P7
ADD P1, P2, P3
SUB P4, P1, P5

「偽の依存関係」が解消されたわけですね。この時、P1を利用したADD命令とSUB命令はRead After Writeの「真の依存関係」にあるため順序の入れ替えは不可能になっています。

前述の通りレジスタリネーミングは「偽の依存」を解消することでOoOの実現に寄与する仕組みです。この時、「真の依存」は名前の通り「真（まこと）」の依存なので、如何様にしても解消することは難しいという理解です。甘んじて受け入れようというスタンスですね、多分。

なんか騙されてないか？

騙されてはないんですが、以上の説明だとちょっとおかしな点というか、舌足らずな点が残っています。

「コンパイラは、物理レジスタ数の制約を加味した上で各命令に論理レジスタを割り振ってくれている。それにも関わらず、制約の温床である物理レジスタに論理レジスタを対応づけることで、見かけのレジスタ数が増えるというのは矛盾しているのでは？」

というような話です。

これには、RMT（Register Map Table）とフリーリスト、また「リタイアステージ」の説明が必要になってきます。

が、長くなってきたのと僕も頭を整理したいのとで今回はこの辺で終えておきます。

書きながら生じた疑問点

• OOOは構造ハザードに対するアプローチとしても考えられないか？

ということで、長くなってしまいましたが今回はこれにて終了です。この記事は以下のgpt-4oくんとのチャットも参考にしています。

https://chatgpt.com/share/5c4ae43d-846e-4bfb-bd01-101e534ce552

では、最後までお読みいただき、ありがとうございます。