Moiz's journal

プログラミングやFPGAなどの技術系の趣味に関するブログです

FPGAで動作するBrainf**k CPUをパイプライン化、スーパースカラー化もどきして、ベンチマークをとってみた

はじめに

前回のエントリーで紹介したFPGAで動作するBrainf**k CPU(BF CPU)を高速化しました。
高速化にあたっては

  • 明らかに無駄なところを直す
  • パイプライン化
  • スーパースカラー的な並列化

の3つを試してみました。また各段階毎にごく簡単なベンチマークをとってみました

Brainf**kについては、Wikipediaなどを参照ください
Brainfuck - Wikipedia

今回アップデートしたVerilog HDLとQuartus用プロジェクトファイルはgithubで公開してあります
github.com

明らかに無駄なところを直す

前回作成したBF CPUはループの終わりに来ると、わざわざ1バイトずつ戻ってループの先頭を探していました。
f:id:uzusayuu:20170520133646p:plain

これは、なるべく簡単な回路構成からはじめて少しずつ機能を増やしていくという方針のためにこうしたのですが、探索している時間は明らかにむだです。専用のスタックを導入することで、]に到達したら1クロックで対応する[に戻るようにしたところ、約2倍の高速化が実現できました。
ベンチマークとして、こちらのページのπを計算するプログラムyapi.bを使いました。*1
copy.sh

まずは最初の状態
www.youtube.com
目を疑うほど遅いですが、これでも50MHzで動作しています。次に高速化したもの
www.youtube.com

だいぶ速くなりました。約2倍の速度です。

パイプライン化

古典的なCPUの高速化の定番といえばパイプライン化です。BF CPUはデータフローも単純な上、もともとステージ構成もパイプライン化を念頭において作ってあったので、比較的容易にパイプライン化できます。フェッチ、実行、メモリーアクセス、の3段パイプラインです。各命令ごとの各パイプライン段での処理は以下のようになっています。

命令 フェッチ 実行 モリーアクセス
命令フェッチ、PC+1 ポインタ先+1 ポインタ先に書き込み
命令フェッチ、PC+1 ポインタ先-1 ポインタ先に書き込み
命令フェッチ、PC+1 ポインタ値+1 ポインタ先から読み込み
命令フェッチ、PC+1 ポインタ値-1 ポインタ先から読み込み
命令フェッチ、PC+1 処理なし ポインタ先の値をを出力
命令フェッチ、PC+1 処理なし ポインタ先へ入力
命令フェッチ、PC+1、ポインタ値がゼロなら探索モードへ 処理なし 処理なし
命令フェッチ、PC+1、ポインタ値がゼロなら[へジャンプ 処理なし 処理無し

ここで、+-の時はパイプライン3段目でメモリへの書き込みが、><の時は読み込みが発生します。+-では事前に読んだものをキャッシュしておいて、そこに演算を行うことでメモリー読み込みを回避しています。
パイプライン設計でまず必要なのはパイプラインハザードの回避です。今回はメモリーとして1サイクルで読み書きができる内蔵RAM/ROMを使用しているのでメモリートールはありませんが、データの依存によるストールは可能性があります。依存性のある部分を書き出してみると

条件 先の処理 次の処理
>又は< +又はー又は.
2 +又はー又は, [又は]
3 >又は< [又は]

条件1の回避のために、命令が>+などのようになっている場合(ポインタを1動かして、ポインタ先を+1)、メモリーから読んだ値を実行ユニットにフォワードします。
条件2の回避のために、実行ユニットの実行結果がフェッチユニットにフォワードされるようにしてあります。したがって、>-]のような処理(ポインタを+1して、ポインタ先を-1し、結果がゼロならジャンプ)の場合は、メモリーから読んだ値に同クロックで演算を行い、その結果を同クロック内で参照してジャンプの判定をしています。タイミング的に苦しいかとも思いましたが、FPGAでも実行できているので良しとします。
条件3はどうやっても1クロック待たないとデータが来ないので、実行を遅らせる必要があります。この場合[又は]の前にNOP命令を挿入して、ハザードを回避しています。

ここでまた先程のπ計算をやってみます。
www.youtube.com

だいぶ速くなりました。前回から約3倍。最初の状態から約6倍弱の速度です。

スーパースカラー的な命令並列化

次に考えられるのはスーパースカラー化ですが、なにしろBrainf**kには命令が8つしかなく、同時に扱う変数も一つなのでどうしても命令間の依存性が大きくなります。
並列化できるのはつながった+-をまとめる、又はつながった<>をまとめる、という程度です。しかも両者間には依存性があるので並列化はかなり面倒になります。
さらに、例えば++++をまとめる場合、+1実行ユニットを4つならべるよりも、1から4の値を増加(減少)できる演算ユニットを作成するほうが素直な実装になりそうです。
本来スーパースカラーというのは処理ユニットを複数おいて同時に実行することをいうのですが、これでは実行ユニットは一つのままなのでスーパースカラーとは言えません。ただ、一部の複数命令を同時に実行しているのは確かなので、ここでは「スーパースカラー化もどき」、とでも呼んでおきます。

実装上、今回は変更点は割と多くなり、以下のような点がかわりました

  • プログラムROMのデータ幅を8ビットから32ビットに変更(4命令同時読み込み)
  • フェッチステージで最大4つの命令をまとめて発行(+-か<>のどちらかの種類のみ)
  • これまで、各命令のアスキーコードをプロセッサ内でもオペコードとして使用してきたが、内部専用命令コードを作成
    • 内部命令は+>,.][とNOPとHALT*2の8種類(3ビット)
    • フェッチで命令と同時に、加算用の値(-4から+4)を生成(3ビット)
  • 実行ユニットでは、+1/-1の代わりに、受け渡された-4から+4までの値をポインタ値またはポインタに足す
  • 分岐命令]でジャンプした場合、1サイクルパイプラインをストールし、命令を先読みする(常時4命令以上参照できるようにするため)

またCPUとは直接関係ありませんが、32bit幅のデータの記述がうまく行かなかったのでROMの内容を示すFPGA用のデータファイルのフォーマットをIntel Hexから、Altera MIF形式に変更しました。*3
さて、これでどれだけ速くなったかというと、
www.youtube.com
ほとんど変わりません。次にベンチマークの結果を載せますが、約10%程度の増加です。かなりの作業量を費やした割に効果が薄く残念です。

ベンチマーク結果

これまでのベンチマークの結果をまとめるとこのようになります。計測はModelSimによるシミュレーションで行い、リセットから9桁目の数字がCPUから出力されるクロックまでの時間を測定しました。

バージョン 時間 (ms)
オリジナル 860
ジャンプ用スタック 458
パイプライン化 153
命令並列化 135

グラフではこうなります。
f:id:uzusayuu:20170520163616p:plain
こうしてみると、命令並列化のコストパフォーマンスの悪さがわかります。殆どのコードを書き直したので残念です。

他の高速化

他の高速化手法としてはこんなものが考えられます

  • 分岐時の投機実行
    • >]のようなケースで1クロックかせげる可能性があります
  • 本当にスーパースカラー
    • >と+など、異なる種類の命令を同時に実行できるようにします
  • 高クロック化

最後の高クロック化以外は労多くしてという感じなので、ちょっと考え中です。

まとめ

前回制作したFPGA用のBrainf**k CPUにパイプライン化などの高速化を行いました。
命令並列化の効果が低すぎるのが納得いかないので原因を調べてみようと思います

*1:このプログラムを動作させるためにポインター値のビット幅を16ビットに拡張したが、高速化とは直接関係ないので省略

*2:命令としてゼロが来るとHAL

*3:今は両方インテルですが