この記事は自作CPU Advent Calendar 2023の24日目の記事です。
みなさんが使っているパソコンのCPUは、そのほとんどがアウトオブオーダー実行をしているはずです。 しかし、アウトオブオーダーCPUの作り方が書かれた教科書はあまりないような気がします。 トマスロのアルゴリズムというものが紹介されることもありますが、これは現代のアウトオブオーダー実行方式とはかなり違います。 この記事では、より洗練された現代的なアウトオブオーダー実行をするプロセッサを作ってみます。
全体的な構成
今回作るプロセッサは、FPGA上で動き、RV32IZmmul命令セットを動かすことができます。 東大のプロセッサ実験と同じルール（命令メモリ32KiB、データメモリ64KiB）で作ります（プロセッサ設計で一番難しいキャッシュを考えなくていいのですごく楽です）。
パイプラインは、以下のように設計しました。
- 分岐予測ステージ
- フェッチステージ
- デコード＋リネーム＋ディスパッチステージ
- スケジュールステージ
- 発行ステージ
- 実行ステージ
- 普通の整数命令のレイテンシは1サイクル
- 乗算命令のレイテンシは2サイクル
- ロード命令のレイテンシは3サイクル
- コミットステージ
今回は、作るのが大変なのでスーパースカラではないアウトオブオーダープロセッサを作ります。 この記事の作り方はスーパースカラであっても適用可能ですが、スーパースカラだといろいろ考えることが多くて大変です。
なお、スーパースカラではないのでIPCはどう頑張っても1.0を超えません。 普通にインオーダーのスーパースカラプロセッサを作ったほうが高いIPCを出せます。 性能が高いプロセッサを作ることが目的なら、こんな面倒なことをしてアウトオブオーダー実行を導入する必要はないです。 今回の話は、今後スーパースカラのアウトオブオーダープロセッサを作る土台作りということでやっています。
以下、各ステージを詳しく見ていきます。 なお、プロセッサが同時に取り扱える命令の数（リオーダーバッファサイズ）は16としました。物理レジスタ数は48です。
分岐予測ステージ
プロセッサの中で性能に最も影響を与えるステージです。
方向分岐予測器には、hashed perceptron分岐予測器を採用しました。 Hashed perceptron分岐予測器は、高性能分岐予測器の中では作るのが最も簡単です。 現在最強と考えられているのはTAGE分岐予測器ですが、hashed perceptron分岐予測器もそれとほとんど変わらないような性能を達成します。 TAGE分岐予測器は実装がとても大変なので、今回はhashed perceptron分岐予測器を使うことにします。
分岐先予測器は、分岐先バッファ（BTB）のみとしました。 置換とかのめんどくさいことを考えたくないので、32KiBの命令メモリに入る8192命令すべてに対して4Byteの飛び先を記録できるだけのBTB（32KiB）を用意しました。 こういう無駄遣いをすることで、アウトオブオーダープロセッサを簡単に作っていきます。 消費資源量の最適化は、正しく動いた後でやりましょう。
精度高く分岐予測するためには、方向分岐予測器で使うグローバル履歴をまだ結果がわかっていないにもかかわらず、予測に基づいて＝投機的に更新する必要があります。 しかも、分岐予測ミスが起こった時にこの投機的更新を正しく取り消さないと、それ以降の分岐予測がめちゃくちゃになります。 これの対策は結構簡単で、グローバル履歴をリングバッファに持っておき、各命令でリングバッファのheadポインタを控えておけばよいです。 今回採用したhashed perceptron分岐予測器の最大分岐履歴長は90にしましたが、グローバル履歴のリングバッファサイズはきりよく128にしました。 これにより、38個までの投機的更新を行っても、それを取り消すことが可能です。 実際には高々16回しか投機的更新は行われないため、全然余裕です。
分岐予測ステージの結果は、
- 次のサイクルの分岐予測の“種”として、分岐予測ステージへ
- 次のサイクルのフェッチするアドレスとして、フェッチステージへ
- 今フェッチした命令の「予測されたnext pc」（これは分岐を実行した時に分岐予測が正しいか判定するために必要）として、デコードステージへ
それぞれ送られます。
フェッチステージ
32KiBの命令メモリから4Byte命令をフェッチするだけで、特に工夫はありません。 命令キャッシュではないため、失敗はありません（常に命令をフェッチすることができます）。
デコード＋リネーム＋ディスパッチステージ
デコード
デコードするだけです。なにもむずかしいことはありません。
今回の作り方では、命令のレイテンシ情報、ソースレジスタを何個持つか、デスティネーションレジスタを持つか、だけをデコードしています。 発行ステージでデコードをする余裕があるため、ALUコードなどはそこでデコードをすることにして、4Byteの命令をそのまま後段に送っています。 このように作ることで、デバッグがやりやすくなっています。
リネーム
レジスタリネーミングを行います。つまり、命令に含まれる論理レジスタ番号を物理レジスタ番号に変換します。 アウトオブオーダー実行した結果を格納するために物理レジスタを使うのが、現代的なアウトオブオーダー実行方式です。
そもそも、アウトオブオーダー実行した結果をそのままアーキテクチャレジスタ（論理レジスタのこと）に書き込んでしまうと分岐予測ミスなどが起こった時に取り返しのつかないことになるので、アウトオブオーダー実行した結果はアーキテクチャレジスタとは別の場所に書いておく必要があります。 これの古典的な実装として、「アウトオブオーダー実行した結果はリオーダーバッファに書き込んでおき、分岐予測ミス等で取り消されないことが確定し次第順番にアーキテクチャレジスタに書き戻す」というものがあります。 しかし、この方式はデータの移動が発生してうれしくないです。 これより優れているのは、アーキテクチャレジスタとアウトオブオーダー実行の結果を書き込むバッファを区別しないで、一体の物理レジスタを使う、という方式です。 論理レジスタの値が物理レジスタのどこに入っているかは、そのポインタだけを記録しておけば、データ本体を動かす必要がなくなります。 「indirectは全てを解決する」というやつです。
ソース論理レジスタ番号を物理レジスタ番号に変換するのは簡単です。 その対応関係が記録された表（レジスタマップテーブル、RMT）を参照するだけです。
デスティネーション論理レジスタ番号は、未使用な物理レジスタ番号に変換される必要があります。 なぜなら、使用中の物理レジスタをデスティネーションとして割り当ててしまうと、他の命令が読もうとしていたデータが上書きされて別のデータに変わってしまい、プロセッサの動作がおかしくなる可能性があるからです。 ここで、「未使用」とか「使用中」とかは、「記録されているデータがもう二度と読まれない」「記録されているデータがまだ読まれる可能性がある」の意味です。
未使用な物理レジスタ番号は、フリーリストとよばれるリングバッファに記録しておくことにして、割り当てが必要になった場合はそこから一つ取り出します。 一般には未使用な物理レジスタが存在しない場合がありますが、今回は十分な物理レジスタを用意しました。 よって、この操作も失敗することがなく、簡単に実装できます。
後続の命令のリネームが正しくなるように、この命令に割り当てられた物理レジスタ番号をRMTに書き込んで更新します。 例えば、この命令のデスティネーション論理レジスタ番号が13だとして、それに物理レジスタ番号41が割り当てられたとします。 RMTにこのことを書いておけば、後続の命令でソース論理レジスタ番号が13の命令は物理レジスタ番号41を読みに行けばいい、と知ることができます。
この書き込みを行う前に、デスティネーション論理レジスタ番号に「今」対応する物理レジスタ番号も読み出しておきます。
これは、この命令がコミット（確定）された時に、永久に読み出されなくなる物理レジスタです。
よって、この命令をコミットするときに、その物理レジスタ番号をフリーリストに記録すれば、「未使用な物理レジスタ番号がフリーリストに入っている」状態を維持できます。
このようにして、物理レジスタのガベージコレクション（といってもstd::unique_ptrと同様に自明ですが）が行われます。
物理レジスタ番号をフリーリストから一つ取得した命令は、そのうち物理レジスタ番号を必ず一つフリーリストへ返却するため、未使用な物理レジスタが枯渇することはありません。
RMTに書き込んでしまうと何を返却すべきかの情報が失われるので、この時点で読み出して保存しておく必要があります。
さて、アウトオブオーダープロセッサで最も面倒くさいのは、分岐予測ミスが起こった時にRMTをその分岐命令の時点の状況に戻さないといけない点です。 今回は贅沢に、すべての命令の時点でのRMTをまるまるコピーしておく（すべての命令でチェックポイントを取っておく）という方法を採用しました。 これはかなり贅沢で、RMTだけで〈6bit×32エントリ×16バージョン〉も必要になっています。 これは物理レジスタファイルに匹敵するサイズであり、しかも大量のコピーが発生しているので「実際のデータを移動させずポインタを変えるだけでいいから優れている」とか言ってたのを満たせていない気がしますが、気にしないことにします。
メモリ依存予測
本来であれば、リネーム（命令間のレジスタを介した依存の解析に相当）に加えて、メモリ依存予測（命令間のメモリを介した依存の解析）を行ったほうが良いです。 アウトオブオーダー実行をしている以上、プログラム順で後にあるロード命令が、プログラム順で前にあるストア命令よりも先に実行されることがあります。 この時、アドレスが一致していれば実行結果がおかしくなっている可能性が大です（メモリ順序違反）。 これを検出する機構は当然搭載されるため、間違った実行結果にはなりません（そういうことが起こったら分岐予測ミス同様にフラッシュしてやりなおします）。 とはいえ、頻繁にフラッシュが発生すると性能に影響があるので、「このロード命令はこのストア命令の後にやった方がいい」みたいな予測（これをメモリ依存予測と言います）をするわけです。
ただ、メモリ依存予測を実装するのはすごく大変なので、今回は実装しないことにしました。 実際の所、まともに最適化が行われていれば、ストアしてすぐロードすることはほぼありません。 したがって、命令ウィンドウ（命令を並べ替える範囲）が小さければ、メモリ順序違反はほぼ発生しないため、メモリ依存予測を行わなくてもそれほど性能が落ちることはありません。
また、メモリ順序違反を検出する機構であるロードストアキューのエントリの確保もこの辺のステージで行うのが普通ですが、今回は十分な数（16）のエントリを用意しました。 よって、確保が失敗することはなく、簡単です。
ディスパッチ
スケジューラ（どの命令が実行可能であるかを判断し、その中から適切なものを選ぶ機構）に命令を登録します。 また、スケジューリングに関係ない情報（命令のPCや即値など）を脇によけておきます（payload RAMに格納しておきます）。 これは、スケジュールステージは一番複雑なステージであり、なるべく小さく作りたいからです。
普通のスケジューラの作り方をすると、「この命令が実行された（のでこの命令に依存している命令は実行可能になった）」という信号は1サイクルしか流れません。 なので、
- ディスパッチをする前に「すでにこの命令は実行されている（のでこの命令に依存している命令はとっくに実行可能である）」という情報を手に入れる必要がある
- しかもこの情報を適切に更新する必要がある
- ディスパッチをするその1サイクルに流れる「この命令が実行された（のでこの命令に依存している命令は実行可能になった）」という情報を逃さないようにする必要がある
という二点をちゃんと作らないといけないので大変です。
今回は、「どの物理レジスタが読み出せる状態になっているかを管理する」という贅沢な方式でスケジューラを作ることで、ディスパッチを大幅に簡単に作れるようにしました。 また、スケジューラに入れられる命令数を16と十分に大きくとったため、ディスパッチが失敗することもなく、やはり簡単に作ることができます。
このステージの結果（高々二つのソース物理レジスタ番号と高々一つのデスティネーション物理レジスタ番号と命令の実行レイテンシ情報）はスケジューラに書き込みます。 また、デスティネーション物理レジスタについて、「この物理レジスタはまだ読み出せる状態ではない」と記録します（表に0を書き込みます）。
スケジュールステージ
スケジューラ内にある高々16命令のうち、どの命令が実行可能であるか判断し、実行可能な命令の中から最も古い命令を一つ選びます。
スケジューラ内にある16の命令は各々、エントリのvalidビットに加え「自分のソース物理レジスタは読み出せる状態か」を二つ確認し、それらのandを取ることで実行可能状態（ready）であるかを判定します。 スケジューラはリングバッファになっていて、古い命令から順番に並んでいます。 よって16本のready信号を確認して、その中で最も古いものがどれかを調べることはそれほど難しくありません。 これにより、実行可能である最も古い命令を一つ選ぶことができます。
選ばれた命令は、自身のエントリのvalidビットを0にすることで、再び選択されることを防ぎます。 その後、選ばれた命令のレイテンシー１サイクルだけ待ってから（つまり、レイテンシが1サイクルの命令なら選ばれたサイクルの終了時に）、選ばれた命令のデスティネーション物理レジスタについて、「この物理レジスタは読み出せる状態である」と記録します（表に1を書き込みます）。
スケジューラが管理してる「物理レジスタは読み出せる状態である」は実際には2サイクル（1サイクル＋発行レイテンシ分）未来の状態を表しています。 普通はこれはレイテンシ予測に基づくもので、未来の状態が本当にそうなるかはわかりません。 未来予測が正しくなくなる典型的なパターンはキャッシュミスした場合です。 キャッシュミスすればデータは得られないので、「物理レジスタは読み出せる状態である」というのは間違いになります（レイテンシ予測ミス）。 間違った未来予測に基づいてスケジュールすると、正しいデータを使って実行できないので、プロセッサの動作がおかしくなります。 したがって、未来予測が間違った場合の対処を考える必要があります。 これは、アウトオブオーダープロセッサを作るうえで、難しい問題です（リザベーションステーションを使った方式はこの問題が起こらないという利点が一応あります。また、レイテンシが不確かなものについては実際にデータが得られるまで表を更新しない（投機的発行しない）という方式もあります）。
しかし、今回はデータキャッシュがなくてレイテンシ予測は完全に当たるので、簡単に作ることができます。
「物理レジスタは読み出せる状態である」の表は48個ある物理レジスタに対して1bitの情報を管理しているだけですが、ポート数がすごく多いので贅沢なつくりになっています（とはいえFPGAを前提にするとこれより小さく作る方法はそう簡単にはなさそうです。この作り方は結構いい方法なのでは？）。 この表は、スケジューラ内の16個の命令が2つのソースについて確認するので、32readになっています。 しかも、ディスパッチの1writeに加えて、レイテンシが1cycle/2cycle/3cycleの三パターンがあるので3writeが必要で、合計で4writeになります。 つまり、この表だけで〈1bit×48エントリ×32read×4write〉が必要になっています。
ここで選ばれた命令（実際にはその命令の情報が格納されているpayload RAMのインデクス番号）は、発行ステージへ送られます。
発行ステージ
Payload RAMを読み出し、PCと命令語などを得ます。 命令語はここでデコードします。 また、物理レジスタからの読み出しを行います（分散RAMで作って非同期読み出しします）。 さらに、必要であればフォワーディングを受け取ります。 そして、それらのうち適切な方をパイプラインレジスタに書き込みます。
実行ステージ
整数命令
命令を実行するだけです。 命令の実行結果は、即フォワーディングネットワークに流します。
一方、レジスタファイルへの書き込みはまだ行いません。 これは、レジスタファイルの書き込みポートを節約するためです（後から考えると、これは「資源を贅沢に使って簡単に作る」に反していました……）。 整数命令の実行レイテンシは1サイクル、最長の実行レイテンシを持つのはロード命令の3サイクル、ということで、差分の2サイクルは待ちます。 これは普通の五段パイプラインと同じ設計です。 レジスタファイルに書き込まれるまでの間は、フォワーディング経由で値を受け取れるので、これが問題になることはありません。
また、レジスタファイルに書き込むのと同時に、リオーダーバッファに実行完了フラグを書き込みます。 リオーダーバッファといっても、実行結果データを書き込むタイプではありません。
もし分岐命令であれば、実行の結果得られたnext pcが予測結果と一致しているかを確認します。
予測結果と一致していてもしていなくても、分岐予測器を学習します。
また、予測結果と一致していなければ、分岐予測ミスです。
例外の発生するサイクルをロードストア命令と合わせるため、第二サイクルで分岐予測ミス信号を送出します。
これは、複数の実行ユニットから出てきた例外の中で最古のものを選ぶ、という面倒事を回避するためです。
さすがに次のサイクルから正しい命令をフェッチするのはレイテンシ的に厳しいため、このサイクルではmispredフリップフロップに1を書き込むのにとどめ、次のサイクルから分岐予測ミスの対処を開始します。
乗算命令
2サイクルかけて乗算を行うだけです。 乗算結果は即フォワーディングネットワークに流しますが、レジスタファイル・リオーダーバッファへの書き込みは、1サイクル待ちます。 ロード命令に合わせて3サイクルにしておけばこの辺やスケジューラを多少簡単にできたので、レイテンシを2サイクルにしたのは失敗でした（乗算の結果をまた乗算に使うということはあまり発生しないので、レイテンシが長くてもIPCへの影響は軽微です）。
ロード命令
第一サイクルではメモリアドレスを計算します。TLBがないので単純です。
第二サイクルではメモリアドレスを使って、データメモリから読み出します。キャッシュがないので単純です。 さらに、メモリアドレスを使って、ロードストアキューを連想検索します。 もし、ロードストアキューに当該メモリアドレスに対するストアが記録されていれば、その中で最新のストア命令の書いた値を読み出します（ストアフォワーディング）。 また、ロードストアキューに、アドレスを記録します。
第三サイクルでは、ロードストアキューを連想検索して値が得られたならそれを、得られなかったならデータメモリから読み出した値を、零拡張または符号拡張します。 その結果は、フォワーディングネットワークに流します。 また、第三サイクルが終わる瞬間にレジスタファイル・リオーダーバッファに書き込みます。 これにより、発行ステージでのレジスタ値の選択が「レジスタファイルから読み出した値」「今完了した整数命令の結果」「今完了した乗算命令の結果/1サイクル前に完了した整数命令の結果」「今完了したロード命令の結果/1サイクル前に完了した乗算命令の結果/2サイクル前に完了した整数命令の結果」の4択になります。
※ストアフォワーディングはパーシャルメモリアクセス（SB命令で1byteストアしたのにLD命令で4byteロードするなど）を考えると面倒です。メモリアドレスの下位2bitごとにロードストアキューを作ることで対処しています。
ストア命令
第一サイクルではメモリアドレスを計算します。TLBがないので単純です。
第二サイクルでは、メモリアドレスとストアデータをロードストアキューに書き込みます。
さらに、メモリアドレスを使って、ロードストアキューを連想検索します。
もし、ロードストアキューに当該メモリアドレスに対するロードが記録されていれば、メモリ順序違反が起こったことを示しています。
その中で最古のロード命令を探し出し、その命令からフェッチしなおします（リフェッチ）。
このサイクルではmispredフリップフロップに1を書き込むにとどめ、次のサイクルからメモリ順序違反の対処を始めます。
第三サイクルは何もする必要がありません。
コミットステージ
アーキテクチャステートを不可逆的に更新するのがコミットステージです。 リオーダーバッファを確認し、最古の命令に対応するエントリに実行完了フラグが立っていればコミットを行います。 ストア命令であれば、ストアキューに書き込まれている値を読み出し、データメモリに書き込みます。 キャッシュがないので、これは確実に成功します。 ストア以外の命令であれば、何もする必要はありません。
その後、リオーダーバッファのheadポインタ*1 を1インクリメントします。 このheadポインタは、以下の情報を得るために使われます。
- リオーダーバッファ中の最古の命令はどれか
- スケジューラ内に入っている命令の中で「新しい命令」と「古い命令」の境界はどこか
また、分岐予測するごとに1インクリメントされるtailポインタと組み合わせて、以下の判定に使われます。
- リオーダーバッファに空きがあるか
- 分岐予測を進めていいかの判定で必要
- ロードストアキューの中で有効な範囲はどこか
- メモリ順序違反が起こったかの判定で必要
本当はここで、記録されている物理レジスタ番号をフリーリストに返却する必要があるはずです。 しかし、実は逆の発想で「リオーダーバッファの（headではなく）tailを進めるときに、物理レジスタ番号をフリーリストに返却」としても大丈夫です。 こうすると物理レジスタ番号がフリーリストに返却されるのが遅くなってうれしくないですが（というか物理レジスタ不足でストールが発生してtailが進められなくなればデッドロックしてしまう）、今回は十分な物理レジスタがあるため問題ありません。 パイプラインフラッシュが起こった時のことを考えるとこうしたほうがやりやすいため、この方式を採用しました。
パイプラインフラッシュの実装
さて、ここまででパイプラインの“正常”動作を書いてきましたが、実際には分岐予測ミスやメモリ順序違反などの投機ミスが起きるので、パイプラインフラッシュが発生します。 この時にプロセッサの状態を正しく戻さないと正しく動かないので、頑張って作ります。 といっても、今まで贅沢に作ってきたのはパイプラインフラッシュが起こった時にほとんど何もしなくていいようにするためなので、実装はそんなに難しくありません。
分岐予測ステージ
- グローバル履歴のリングバッファのポインタを戻す
- 一応、これをちゃんとやらなくてもプロセッサは正しく動くけれど、分岐予測がめちゃくちゃになる
- 次のサイクルの分岐予測の“種”となるPCをセットしなおす
フェッチステージ
- 正しいPCを受け取る（まだフェッチはしない）
デコード・リネーム・ディスパッチステージ
- RMTの状態をチェックポイントから復元する（ポインタを正しい値に修正するだけ）
- 今デコード中の命令は捨てる
スケジュールステージ
- フラッシュの原因となった命令以降の命令のエントリについて、有効な命令が入っているかを修正する（validビットを0にする）
- 物理レジスタのreadyの状態は、戻さなくてよい（ディスパッチ時に正しい値に修正されるので）
発行ステージ
- 何もしなくてよい
実行ステージ
- リオーダーバッファのheadとtailの範囲に無い命令であれば
コミットステージ
- 何もしなくてよい（もともとリオーダーバッファのtailより先をコミットしないので、tailを戻しておけば大丈夫）
物理レジスタのガベージコレクション
分岐予測が行われて命令がリオーダーバッファに格納される（本当はまだ命令がフェッチされていないのでエントリが確保されるだけ）たびに、以下のどちらかを行えばよいです。
- 「フラッシュされた」ビットが立っていれば、その命令が上書きするリオーダーバッファエントリに記録されている命令のデスティネーション物理レジスタ番号をフリーリストに返却（投機ミスからの回復動作）
- 「フラッシュされた」ビットが立っていなければ、その命令が上書きするリオーダーバッファエントリに記録されている命令のデスティネーション論理レジスタにもともと対応していた物理レジスタ番号をフリーリストに返却（通常動作）
こうすることで、フリーリストの書き込みポート数を1のままにすることができます。 というかよく考えると、リオーダーバッファに記録されている情報（フラッシュビット＋旧物理レジスタ番号＋新物理レジスタ番号）がフリーリストの情報を特定するのに十分なものになっているので、フリーリストをわざわざ実装する必要はなかったようです……。
アウトオブオーダープロセッサの実行の様子
スーパースカラでないので、レイテンシが1サイクルの命令が並んでいるところはインオーダープロセッサと同じ感じになります。 CoreMarkというベンチマークを動かしてみたところ、以下の二か所ではアウトオブオーダー実行がうまく働いていそうでした。 パイプラインは、Konataというパイプライン可視化ツールで可視化しました。
まとめ
キャッシュなどの複雑化の要因をなくし、それでも複雑な部分は大量の資源を使って解決することで、簡単にアウトオブオーダープロセッサを作ることができることがわかりました。 来年はちゃんと省資源化（とできればスーパースカラ化）してみたいと思います。
