Brainf*ckを直接実行できるCPUを作った (その4) BTB(Branch Target Buffer)の実装【いろいろなコンピューター Advent Calendar 2023 13日目】
この記事はいろいろなコンピューター Advent Calendar 2023の13日目の記事です。年跨いだけど気にしない。 adventar.org
この記事は12日目の記事の続きです。ぜひ先にそちらをご覧ください。 primenumber.hatenadiary.jp
前回の記事では、パイプライン化に成功し、自分のFPGAでは170MHz程度が最大動作周波数でした。 そのあと、命令メモリの回路構成を少し見直すことで、250MHzくらいまで出せるようになりました。
今回は、Brainf*ck CPUにBTB(Branch Target Buffer, 分岐先キャッシュ)を実装していきます。
Brainf*ck CPUにおける分岐の扱い
通常の命令セットのCPUであれば、命令自体に絶対・相対アドレスが入っていたり、レジスタの値を元にジャンプするので、少なくとも命令を実行する時点ではどこにジャンプすればよいかが判明します*1。
しかし、Brainf*ckではそうはいきません。
[ ] によるジャンプが発生したとき、ジャンプ先は対応する ] [ になります。
対応する ] [ の位置は命令列を見ないとわからないため、その位置を探索する必要があります。
前回の記事の時点では、分岐が発生するたびに、命令列を走査して対応する] [を探していました。
これには、ジャンプする距離に比例するサイクル数が必要になってしまいます。
前回パイプライン化まで実装したことで、] [の探索が実行時間の半分以上を占める*2ようになってしまいました。
結合テスト・ベンチマークで用いているHanoi4.bfの実行では、命令実行に14803サイクル、ジャンプ先探索に21352サイクルかかっていました。
分岐先のキャッシュ
Brainf*ck CPUでは、分岐先を求めるのが高コストな一方で、あるアドレスから分岐するとき、その分岐先アドレスはプログラム実行中常に一定です。 そこで、分岐先を探索後、探索結果を保存することで、次回同じ場所で分岐したときに、探索の代わりに保存した結果を使うことで、探索を省略できるようにできます。
分岐先アドレスを保存するこの機構をBranch Target Buffer(BTB)、あるいはBranch Target Address Cache(BTAC)と呼びます。
通常の命令セットのCPUでは、分岐元のアドレスが同じでも分岐先が変わることがあり得ますが、Brainf*ck CPUでは変化しないため、比較的簡単に実装できます。
BTBの実装
できたものがこちらになります
BTBの実装はBTB.scalaにあります。
BTBは小さなメモリに探索結果を保存することで実現します。
分岐元アドレスの下位ビットをキャッシュメモリのアドレスとして用います。 もし下位ビットが同じで上位ビットが異なるアドレスについてキャッシュに書き込むと、以前の内容は消えてしまいますが、そのときは再度探索を行うことにします。
下位ビットを元に直接保存場所が決定する方式のキャッシュを、ダイレクトマップ方式といいます。 実装は簡単ですが、セットアソシアティブ方式等に比べるとキャッシュミスが増加してしまいます。
実験の結果、ダイレクトマップ方式でも十分な性能向上が得られたため、ダイレクトマップ方式のままでいくことにしました。
キャッシュメモリにはvalidフラグ、分岐元アドレスの上位ビット(キャッシュメモリのアドレスとして使わなかった部分)、分岐先アドレスを保存します。
validフラグは、キャッシュメモリから読んできた内容が有効かを判定するのに必要です。 キャッシュメモリを最初validが0のデータで埋めておき、キャッシュに書き込むときにはvalidが1のデータを書き込むことで、内容の有効性を判定できます。
分岐先アドレスの上位ビットは、キャッシュメモリから読んできた内容が欲しいアドレスの内容かどうかを判定するのに必要です。
命令フェッチのレイテンシーの隠蔽
命令フェッチには現状2サイクル必要です。分岐命令を処理した次のサイクルでは、分岐後の命令がまだフェッチできていないため、このままでは1サイクルストールする必要があります。
そこで、BTBに分岐先アドレスだけでなく、ジャンプ後の次の命令も一緒に保存することにします。
BTBヒット時には、命令メモリから命令がやってくるのを待たずに、BTBに保存した命令を使うことで、命令フェッチのレイテンシーを隠蔽し、パイプラインを止めることなく分岐が可能になりました。
ベンチマーク
ベンチマークに用いているHanoi4.bfでの結果をまとめてみました。Hanoi4.bfは455bytesであるため、512エントリあれば衝突は絶対に発生しなくなります。
| BTBエントリ数 | 命令実行サイクル数 | ジャンプ先探索サイクル数 |
|---|---|---|
| なし | 14803 | 21352 |
| 2 | 14803 | 12224 |
| 4 | 14803 | 12172 |
| 8 | 14803 | 11491 |
| 16 | 14803 | 7776 |
| 32 | 14803 | 1957 |
| 64 | 14803 | 1643 |
| 128 | 14803 | 1643 |
| 256 | 14803 | 1643 |
| 512 | 14803 | 1643 |
エントリ数がそれなりにあれば、ジャンプ先探索にかかるサイクル数が、BTBがない状態と比べて1/10未満になっています！ 全体でも半分以下のサイクル数になっており、すばらしい性能向上です。
また、64エントリ以上はサイクル数がかわっていないことから、衝突が起きていないことが分かります。
ちなみに、BTBの追加でUltra96-V2 | Avnet Boardsでの最大動作周波数は220MHz程度と、若干下がってしまいました。 それでもサイクル数の削減の効果の方が圧倒的に大きいため、実時間ベースでも約半減になっています。 動作周波数を上げるボトルネックになっているクリティカルパスは、命令アドレス生成・命令フェッチまわりのようです。 これはちょっとすぐには解決が難しそうです。
今後の展望
ここまでの改良で、（BTBエントリが衝突しない限り）1サイクルあたり1命令実行に限りなく近づけることができました。 個人的にここまでは実装したいな、と思っていたのでよかったです。
ここからさらに性能を向上させるには、2通りのアプローチがあります。
- 1サイクルの間に1命令より多くの命令を処理する
- op fusionとfusion済み命令キャッシュの実装
- スーパースカラ実行の実装
- 動作周波数を上げる
- パイプラインステージの分割
構造の複雑化で、最大動作周波数が下がってきているので、パイプラインステージの分割はぜひともやりたいところです。 命令デコードと実行をステージ分割することで、op fusionにつなげられるとよりうれしいですが、果たして…
スーパースカラ実行は、Brainf*ckの命令レベルの並列性のなさが原因で、圧倒的に難易度が上がりそうで、実装できるかちょっと自信がないです。
