Brainf*ckを直接実行できるCPUを作った (その1)【いろいろなコンピューター Advent Calendar 2023 9日目】【Scala Advent Calendar 2023 9日目】
この記事はいろいろなコンピューター Advent Calendar 2023の9日目の記事です。
Brainf*ckとは
Brainf*ck(この記事では一部伏字にして表記しています)は難解プログラミング言語のひとつです。
コンパイラがなるべく単純になるように設計されており、わずか8種の命令+ - > < [ ] . ,のみが存在する手続き型プログラミング言語です*1。
詳しい言語仕様等はEsolang wikiの記事 brainfuck - Esolang 等を参考にしてください。
仕様は単純ですが、チューリング完全なので、理論上はどんな計算でもすることができます。
Brainf*ck CPUを作る
今回は、Brainf*ckのコンパイラでもインタプリタでもなく、ソースコードを直接実行できるCPUを作りました。
できたものがこちらになります。
この記事の時点での実装はこちら:
ChiselというScalaのDSLで実装しました。ChiselはSystemVerilogやVHDLと同じRTL(Register Transfer Level)の回路設計言語ですが*2、Scalaによるリッチで現代的な書き味が特徴です。 もっとも、私はまだScalaそのものにもChiselにもRTLにもあまり慣れていないため、その恩恵をあまり活用できていないですが…*3
この記事の時点では最適化等のない、単純な実装になっています。 今後の記事で徐々に高速化や高機能化を進めていきます。
BFCPUの動作
命令メモリにソースコードが格納されており、コアがソースコードを直接解釈・実行します。
外部にin/outのストリームI/Oが生えており、ここから標準入出力を行うことができます。 reset/ready/start/finishedというコントロール用のI/Oも生えており、ここから実行をキックしたり終了したかの状態を得たりできます（現時点ではリセットは信号としては存在するが、データメモリを初期化しないため、正しく動作しない）。 主にデバッグ用にステータスを出力するI/Oもあります。
コアの実装
ここからは内部の実装を解説していきます。
Core.scala bfcpu/src/main/scala/bfcpu/Core.scala at 862664008b6adf9b455a4b2eaed0e14198037698 · primenumber/bfcpu · GitHubがコア部分の実装です。
state という実行状態を管理するレジスタがあり、実行中、実行待機、対応する[を走査中、実行完了などの状態に応じて挙動の変わるステートマシンとなっています。
sExecuting が実行中に対応する状態です。
実行部分は、パイプライン化等はされていない、1命令1サイクル実行となっています。 読んできた命令の内容に応じて、命令ポインタ、データポインタ、データの内容等を更新していきます。
現時点では、[ や ] によるジャンプでは、対応する ] [ まで1文字ずつ移動していく実装になっています。
このため、実行にかかるサイクル数は実行する命令数よりもかなり多くなります。
命令・データ用にそれぞれメモリが用意されていますが、今はシングルサイクル実装なので、アドレスを入力すると、次のクロックで即座にアクセスできることが前提の実装になっています。 このため、現時点ではFPGAのBlock RAM等を使うことができません。 また、命令メモリを実行直前に書き換える方法を用意していないため、合成時に用意したソースコードをメモリに埋め込んで実行しています。
今後の改良ポイント
今後、数記事にわたって改良を施していく予定です（記事執筆時点では完全に未着手）。 現時点でやりたいことをリストアップしてみました。
- マルチサイクルCPUにして、メモリにFPGAのBlock RAMを使えるようにし、FPGAで使えるようにする
- 命令メモリを実行直前に外から書き換えられるようにする
- パイプライン化で動作周波数を上げる
[]のジャンプ先をキャッシュして実行サイクル数を削減する- スーパースカラ実行で1サイクルに複数命令処理する
- op fusionによる最適化: 例えば
[-]はデータを0クリアするイディオムで、これを1サイクルで実行できると大幅な高速化が可能。
後半は難易度が高いですが、がんばってチャレンジしていきます！
(追記) その2はこちら
