FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://sites.google.com/site/fpgadevelopindex/

プロセッサにおけるアウトオブオーダの考え方について(リネームレジスタの例外時の処理について)

http://www-personal.umich.edu/~rovinski/images/die_shot.jpg

趣味でCPUを作るのは楽しいもので、自作CPUを作成してベンチマーキングし、性能最適化していったり、高速化していくのは趣味の一つとして楽しめるものだと思う。 CPUを理解するのに、アウトオブオーダ処理、レジスタリネーミングについて理解するのは必須だ。自作CPUを作成するにあたり、そのあたりは基本的な知識ともいえる。 ここでは、現在設計しているCPUのまとめのためにも、アウトオブオーダの基本的な考え方について復習してみる。

プロセッサの高速化のために読んでおきたい本

ヘネシー&パターソン コンピュータアーキテクチャ 定量的アプローチ 第5版

ヘネシー&パターソン コンピュータアーキテクチャ 定量的アプローチ 第5版

コンピュータアーキテクチャのもっとも有名な本。自作プロセッサを開発するならば、シングルスレッドの高速化の章はマスターしておきたい。 メモリ階層についての知識も、基礎的な内容を理解するのに丁度よい。

  • スーパスカラ マイクロプロセッサ

スーパースカラ・プロセッサ

スーパースカラ・プロセッサ

こちらもマスターしておきたい。絶版になってしまったが、古本で売られていた時にとっさに購入した。スーパスカラプロセッサに焦点を当てた高速化の技術について全般的に紹介している。 この本を読むと、サイクル精度の命令セットシミュレータによる性能評価がいかに大切かということとが分かる。

  • 高性能コンピュータ技術の基礎

高性能コンピュータ技術の基礎

高性能コンピュータ技術の基礎

こちらも分かりやすい。しっかり書いてあるし、図も比較的多め。しっかり読むと基礎的な部分はカバーできる。

  • Understanding the detailed Architecture of AMD's 64 bit Core

Chip Architect: Detailed Architecture of AMD's Opteron

こちらも実プロセッサをベースにアウトオブオーダの処理について書かれているので、一読することをお勧め。

レジスタリネーミングのために必要な要素

レジスタリネーミングは、レジスタ間の依存によるCPUのパイプラインストールを避けるための技術だ。 例えば、CPUが以下のような命令を実行する場合、2番目の命令は1番目の命令の結果であるR1を必要とするため待ち合わせをする。

R1 = R2+R3
R4 = R1-R5
R1 = R3–R2

一方で3番目の命令は、1番目と2番目の命令と直接関係は無いものの、2番目の命令が1番目の命令が生成したR1の値を取得するまで、R1を上書きすることができない。 実際には、3番目の命令はR1を早く書き込みできるはずなのに、2番目の命令が古いR1の値を読みたいがばっかりに、アウトオブオーダ実行できないというわけだ。 これをWAW(Write After Write)ハザードと呼ぶ。 これを回避するのがレジスタリネーミングで、レジスタリネーミングにより物理的(アーキテクチャとして定義された)レジスタ名を、仮想的なレジスタアレイに再マッピングする。

これを実現するためには、簡単に言って以下の要素が必要だ。 まずはアーキテクチャレジスタを格納するためのアーキテクチャタグアレイ(図ではArchitecture Registers(Pointer)と記述している)。 右側に表示しているN個のレジスタが、実際にレジスタ値を格納するためのレジスタアレイだ。これは通常RISCプロセッサが持つ32本を超えるレジスタを持っており、これによりレジスタリネーミングを実現する。

また、当然アウトオブオーダ実行になると、途中で例外が発生したり、分岐予測ミスにより実行した命令を取りやめなければならないことが多い。 このために、投機的タグアレイ(図ではSpeculative Registers(Pointer)と記述している)が必要になる。

さらに、レジスタリネーミングではアーキテクチャレジスタをリネームレジスタの空いている場所にリネームすることになるのだが、どのリネームレジスタの場所が空いているのかを示すFreeListというものも必要になる。 各命令は、自分の書き込み先のリネームレジスタのインデックスを取得するために、FreeListからインデックスを1つ取り出し、リネームレジスタを空き場所を確保するというわけだ。

f:id:msyksphinz:20160424025346p:plain

実際にリネーミングしたときの様子

実際に上記に示した3つの命令をリネーム処理したときの例が下記になる。

f:id:msyksphinz:20160424025934p:plain

まず、3つの命令はすべて書き込みレジスタが必要なため、フリーリストの先頭からそれぞれリネームレジスタの空き場所インデックスを獲得する。 1命令目はP31、2命令目はP32、3命令目はP33を確保する。

それと同時に、Speculative Registerに現在の最新のアーキテクチャレジスタとリネームレジスタの対応表を書き込む。

  1. 1命令目を実行すると、書き込み先(R1)レジスタは実際にはリネームレジスタのP31を参照すれば手に入る。
  2. 2命令目を実行すると、書き込み先(R4)レジスタは実際にはリネームレジスタのP32を参照すれば手に入る。
  3. 3命令目を実行すると、書き込み先(R1)レジスタは実際にはリネームレジスタのP33を参照すればよく、P31は古いため使用できない。したがってSpeculative Registerのインデックス値を書き直す。

これにより、2命令目が必要とするソースオペランドR1は、Speculative Registerを参照することによりP31を使えばよいということが分かる。 また、3命令目の書き込み先はR1だがリネームレジスタは重なっていないため、WAWハザードが起きることはない。3命令目以降がR1をソースオペランドとしたいときは、P33をアクセスすればよいだけの話だ。

最終的に演算を終えた時の状態は以下になる。例外など発生せず、3命令が無事に実行完了した場合は、Architectural Register側のポインタも更新される。 肝となるのは、このArchitectural Registerのポインタは、該当する命令が例外などでフラッシュされることがないことが確定するまで、決して更新されることはないということである。

f:id:msyksphinz:20160424030043p:plain

逆に言えば、例外が発生してしまっても、Speculative Registerをフラッシュすれば、安全な場所までロールバックすることができるということだ。 以下は、例えば3命令目が例外を発生し無効化された例だが、その時点でArchitectural RegisterのR1のインデックスはまだP31を指している。 Speculative Registerは3命令目がリネームした瞬間にR1のポインタをP33に書き換えているわけだが、それは無かったことにしたい。 したがって、Speculative Registersをすべてフラッシュして、Architectural Registersを参照するようにすれば、例外が発生する前までの状態に戻すことができるというわけだ。

f:id:msyksphinz:20160424030352p:plain

次回は、リオーダバッファの構成と役割についてまとめたい。