Brainf*ckを直接実行できるCPUを作った (その3) パイプライン化とデータキャッシュ【いろいろなコンピューター Advent Calendar 2023 12日目】
この記事はいろいろなコンピューター Advent Calendar 2023の12日目の記事です（大遅刻）。
この記事は10日目の記事の続きです。ぜひ先にそちらをご覧ください。
10日目の記事で実装したいとしていた
- 命令書き込みモードを作る
[によるジャンプと]によるジャンプで状態を分けているが、進む向きが違うだけなので共通化する
はすぐにできたので、この記事ではついにCPUのパイプライン化を実現します。
Brainf*ck CPUにおけるデータハザード
Brainf*ck CPUをパイプライン化するうえでもっとも困難なことは、データハザードです。
1命令でメモリからのデータの読み込み→計算→メモリへのデータの書き込みを行うため、メモリアクセスを含めてパイプライン化する必要があります。 連続で+や-を行った場合、当然読み書きするアドレスは同じです。 そこをなにも考えずにパイプライン化すると、直前の命令で得られた結果をメモリに書き込む前に、次の命令が必要とするデータの読み込みが発生*1してしまい、内容が壊れてしまいます。 これをデータハザードといいます。
レジスタマシン（今日一般的なCPUのアーキテクチャ）では、EXステージの結果をレジスタに書き込むと同時に、（必要なら）次の命令の入力に直接渡す、フォワーディングと呼ばれる方法が使われています。
Brainf*ck CPUでも、直前に使ったアドレスと同じアドレスにアクセスするのなら、そのデータをフォワーディングすることでデータハザードを回避できます。
しかし、アクセスするアドレスが変わるとデータを読み直す必要があり、このときはメモリからデータがやってくるまで待つ（ストールする）ことになります。 これでは頻繁にストールしてしまい、あまり性能が出なくなってしまいます。
データキャッシュの実装
そこで、メモリの内容を一部だけCPU内に保持することにします。 つまりデータキャッシュを実装すればよいことになります。
一般的なCPUに対するデータキャッシュでは、アクセス先を予測することは困難であるため、効率の良いキャッシュの実装はかなり難易度が高いです。 幸いにも、Brainf*ckではデータアクセス先は1命令あたり高々1byteずつしか動かないため、データポインタの周囲数bytesを保持しておくだけでよいです。
今回は、データメモリに1サイクル後にアクセスできる想定で、データポインタの指す先とその前後1byteずつ、合計3bytesを保持するキャッシュを実装しました。
挙動としては、データポインタをインクリメントするときは、(データポインタ+2)番地のメモリを読みに行き、デクリメントするときは(データポインタ-2)番地のメモリを読みに行きます。
こうすることで、データポインタを移動させていったときに、データが欲しいときには常にキャッシュに載っているようにすることができます。
また、毎サイクルデータポインタの指す場所にキャッシュの内容を書き込みます。
データキャッシュの実装はDCache.scalaにあります。
パイプライン化
これで無事データハザードが解決できると、あとは比較的スムーズにパイプライン化することができました（デコード/実行が1ステージになっているなど、3ステージしかないのも楽な理由）。
分岐予測等は実装していないので、分岐（ジャンプ）が発生したときには、素直に命令フェッチからやり直します。
できたものがこちらになります。
今後の展望
直近で実装したいのは次の二つの機能です。
分岐先キャッシュの実装
パイプライン化の結果、実行時間の多くを[ ]命令の対応する] [を探すことに費やすようになりました。
ジャンプ先アドレス（とジャンプ先からの数命令）をキャッシュすることで、即座にジャンプできるようになると、大幅な高速化が期待できます。
パイプラインステージの追加
FPGAのBlock RAMは読みだしたデータを一旦レジスタに受けることで、アクセスまでのサイクル数増加と引き換えに、最大動作周波数の向上を狙うことができます。 現状ではレジスタで受けていないため、動作周波数をあまり上げることができません。
今の設計では、私の持っている Ultra96-V2 | Avnet Boards では170MHz程度が上限のようでした。
メモリからの読み込みをレジスタで受け、追加のパイプラインステージを追加することで、最大動作周波数を向上させ、トータルの性能向上を狙っていきたいです。 場合によっては、命令デコードと命令実行をステージ分割することで、さらなる最大動作周波数の向上が可能かもしれません。
(追記) その4はこちら
*1:図における命令Bのloadが命令Aのwritebackに先行してしまう
