これはBrainf*ck Advent Calendar 2019 - Adventar25日目の記事です。
Brainfuck命令セットを実行するCPUをVerilog HDLで記述し、FPGAで動かしてみた記録になります。
まず、ハードウェアを意識しつつ命令セットシミュレータ（というかインタプリタ）を作成しました。
ハードウェアを意識しつつ、というのは、インタプリタのメインループの中には一サイクルで完結しそうなものしか書かない、くらいの意味です。
Brainfuckの場合、「対応する[に飛ぶ」のような命令がありますが、これは一サイクルでは終わらないでしょうから、そういったものをどう処理するかを考えながら書くということになります。
以下にC++で書かれた、ハードウェアを意識したBrainfuck命令セットシミュレータを載せます。
実装の都合上、Brainfuckの,命令はサポートしていません。
#include <iostream> #include <array> struct State { size_t ip; size_t dp; int depth; }; std::array<unsigned char, 30000> ram; const char* rom = #include "mandelbrot.bf" ; State update( const State& state ) { State new_state; if( state.depth == 0 ) { if( rom[state.ip] == 0x5B && ram[state.dp] == 0 ) { new_state.depth = 1; } else if( rom[state.ip] == 0x5D && ram[state.dp] != 0 ) { new_state.depth = -1; } else { new_state.depth = 0; } } else { new_state.depth = state.depth + (rom[state.ip] == 0x5B) - (rom[state.ip] == 0x5D); } new_state.ip = new_state.depth < 0 ? state.ip - 1 : state.ip + 1; new_state.dp = rom[state.ip] == 0x3E && state.depth == 0 ? state.dp + 1 : rom[state.ip] == 0x3C && state.depth == 0 ? state.dp - 1 : state.dp; const bool we = (rom[state.ip] == 0x2B || rom[state.ip] == 0x2D) && state.depth == 0; if (we) ram[state.dp] = rom[state.ip] == 0x2D ? ram[state.dp] - 1 : ram[state.dp] + 1; if( rom[state.ip] == 0x2E && state.depth == 0 ) { putchar(ram[state.dp]); } return new_state; } int main() { for( State state { 0, 0, 0 }; rom[state.ip]; ) { state = update( state ); } }
これをほとんどそのままVerilog HDLの記述にすると、Brainfuck CPUの完成です。
module cpu(uart_wr, uart_data, clk, rstn); output wire uart_wr; output wire[7:0] uart_data; input wire clk; input wire rstn; // state reg[14:0] ip; reg[14:0] dp; reg[14:0] depth; reg sync_rstn; wire[14:0] next_ip; wire[14:0] next_dp; wire[14:0] next_depth; // temporary wire executing; // module wire[7:0] insn; wire[7:0] rdata; wire we; wire[7:0] wdata; insnmem insnmem0(next_ip, insn, clk); datamem datamem0(next_dp, rdata, we, wdata, clk); // logic assign executing = depth == 0; assign next_depth = !sync_rstn ? 0 : executing ? insn == 8'h5B && rdata == 0 ? 1 : insn == 8'h5D && rdata != 0 ? -1 : 0 : depth + (insn == 8'h5B) - (insn == 8'h5D); assign next_ip = !sync_rstn ? 0 : next_depth[14] ? ip - 1 : ip + 1; assign next_dp = !sync_rstn ? 0 : insn == 8'h3E && executing ? dp + 1 : insn == 8'h3C && executing ? dp - 1 : dp; assign we = (insn == 8'h2B || insn == 8'h2D) && executing; assign wdata = insn == 8'h2D ? rdata - 1 : rdata + 1; assign uart_wr = insn == 8'h2E && executing; assign uart_data = rdata; // flip-flop always @(posedge clk) begin ip <= next_ip; dp <= next_dp; depth <= next_depth; sync_rstn <= rstn; end endmodule module insnmem(next_ip, insn, clk); input wire[14:0] next_ip; output reg [7:0] insn; input wire clk; reg[7:0] mem[0:32767]; initial $readmemb("D:/vivado/brainfuck/project_1/mandelbrot.bin", mem); always @(posedge clk) begin insn <= mem[next_ip]; end endmodule module datamem(addr, rdata, we, wdata, clk); input wire[14:0] addr; output reg [7:0] rdata; input wire we; input wire [7:0] wdata; input wire clk; reg[7:0] mem[0:32767]; reg[31:0] i; initial for(i=0; i<32768;i=i+1) mem[i] = 0; always @(posedge clk) begin if (we) begin rdata <= wdata; mem[addr] <= wdata; end else begin rdata <= mem[addr]; end end endmodule
const教みたいな記述方法になっているので普通のVerilog HDLコードを見慣れている方には奇異なコードに映るかもしれません。
以下、このVerilog HDLコードを解説していきます。
まず、このCPUから出ていく信号線には、uart_wrとuart_dataがあります。これは、外にUART通信を行うモジュールを作る予定で、そこに送るデータになっています。
このCPUに入ってくる信号線はclkとrstnです。それぞれ、クロック信号、負論理リセット信号（1になっている状態がリセット、0になっている状態が通常状態という意味で、負論理を意味するnが末尾についています）になっています。
reg変数はこのCPUのステートです。ip、dp、depthは、もとのC++ソースコードにあったものと同じ役割です。
その他、同期化された負論理リセット信号であるsync_rstn用のフリップフロップを加えました。
cpuモジュールの残りの部分はC++コードとほぼ同一なので説明は不要でしょう。
リセットがかかっている間はip、dp、depthを0にすること、クロックに同期してCPUのステートを（一度に）更新すること、などがHDL特有の点でしょうか。
insnmemモジュールは、命令メモリモジュールです。
クロック同期でデータが読み出せるごく普通のROMになっています。
実行すべきプログラムはCPUを論理合成するときに読み込みます。
一つのプログラムしか動かせないCPUが出来上がるということです。
datamemモジュールは、データメモリモジュールです。
データの書き込みも読み出しもクロック同期のRAMになっています。
rdata <= wdataのような一見変に見える記述は、書き込んだデータを即読み出せるようにするためです。
特筆すべきは、アドレス線が一本しかないことです。 通常、読み書きできるRAMには、読み出し用のアドレス線と書き込み用のアドレス線の二つがあるはずです。 Brainfuckの命令セットには「読んで更新して書き込む (read-modify-write)」命令が存在し、複雑に見えますが、アドレス線自体は一本で十分なのです。 また、命令を読み出さなくてもどの番地を読み出せばよいかが決まるため、何も工夫しなくてもシングルサイクルプロセッサ（一クロックで一命令を処理するプロセッサ）が作れます。
次に、後回しにしていたUART通信モジュールを作りました。
module top(sysclk, cpu_resetn, uart_rx_out); input wire sysclk; input wire cpu_resetn; output wire uart_rx_out; wire uart_wr; wire[7:0] uart_data; cpu cpu0(uart_wr, uart_data, sysclk, cpu_resetn); uart uart0(uart_rx_out, uart_wr, uart_data, sysclk, cpu_resetn); endmodule module uart(uart_tx, uart_wr, uart_data, clk, rstn); output reg uart_tx; input wire uart_wr; input wire[7:0] uart_data; input wire clk; input wire rstn; reg[28:0] div_clk; reg[10:0] shifter; always @(posedge clk or negedge rstn) begin if (!rstn) begin uart_tx <= 1; shifter <= 0; div_clk <= 0; end else begin if (shifter != 0 && !div_clk[28]) begin uart_tx <= shifter[0]; shifter <= shifter >> 1; end else if (shifter == 0 && uart_wr) begin shifter <= { 2'b11, uart_data[7:0], 1'b0 }; end div_clk <= div_clk[28] ? div_clk + 115200 : div_clk + 115200 - 100000000; end end endmodule
UART通信のボーレートは115200Hzを使用することにします。 このCPUは後述するように100MHzで動くので、そのクロックを分周することで115200Hzのクロックを作り出します。 UARTのプロトコルに従うと、送るべきデータは、順に0、8bitデータの下位から上位に向かって1bitずつ、1、1、の11bitです。
さて、このVerilog HDLコードを論理合成し、FPGAに書き込みます。 論理合成～配置配線はVivado 2019.2で行いました。 FPGAは、Xilinx社Artix-7シリーズのNexys Videoというものを使いました。 Vivadoのタイミング解析によれば、合成結果はちょうど100MHzで動作するらしいです。
FPGAにmandelbrot.bf*1が内蔵されたCPUを書き込み、実際に動かし、UARTで送られてくる信号をTeraTerm*2で見てみると、確かに動作していることがわかります。
FPGAでCPUを動かせばさぞ速いだろうと思っていたのですが、さすがにBrainfuckくらい簡単な命令セットだと、数GHzで動くCPU上でシミュレーションしたほうが高速です。 なんとかもっと速いBrainfuckCPUを作れないでしょうか？
ここで普通に考えるのは、パイプライン化されたCPUを作るというものです。 上記HDLコードのクリティカルパス（動作周波数を決定する、最も遅延の長いパス）は、命令メモリ読み出し→デコード→next_depth計算（≒分岐判定）→次サイクルIP決定→IP配送、になっています。
しかし、Brainfuckコードには大量の分岐命令が存在するため、安易にパイプライン化をするとストール（パイプラインに仕事を供給できないサイクル）が頻発し、性能が上がらないという事態になります。 この問題に対処するために分岐予測を取り入れた場合、クリティカルパスは、分岐予測器メモリ読み出し→何らかの比較→予測された次サイクルIP決定→IP配送、となりますが、このパスも結構時間がかかり、それほどクロック周波数は上がらないのです。 よって、パイプライン化による性能向上は限られています。
それよりも、BrainfuckCPUの実行効率を落としている、「分岐の飛び先が命令の情報だけでわからない」という部分を解決するハードウェアを追加したほうが、高速化に貢献します。 この目的には、通常のCPUにも搭載されている、Branch Target Buffer (BTB)とまったく同じものが使えます。 なお、分岐方向は予測によるのではなく、実際の実行によって得られる方向を採用します。
BTBを実装したBrainfuckCPUのコードが以下になります。
module top(sysclk, cpu_resetn, uart_rx_out); input wire sysclk; input wire cpu_resetn; output wire uart_rx_out; wire uart_busy; wire uart_wr; wire[7:0] uart_data; cpu cpu0(uart_busy, uart_wr, uart_data, sysclk, cpu_resetn); uart uart0(uart_rx_out, uart_busy, uart_wr, uart_data, sysclk, cpu_resetn); endmodule module uart(uart_tx, busy, uart_wr, uart_data, clk, rstn); output reg uart_tx; output wire busy; input wire uart_wr; input wire[7:0] uart_data; input wire clk; input wire rstn; reg[28:0] div_clk; reg[10:0] shifter; assign busy = shifter != 0; always @(posedge clk or negedge rstn) begin if (!rstn) begin uart_tx <= 1; shifter <= 0; div_clk <= 0; end else begin if (busy && !div_clk[28]) begin uart_tx <= shifter[0]; shifter <= shifter >> 1; end else if (!busy && uart_wr) begin shifter <= { 2'b11, uart_data[7:0], 1'b0 }; end div_clk <= div_clk[28] ? div_clk + 115200 : div_clk + 115200 - 100000000; end end endmodule module cpu(uart_busy, uart_wr, uart_data, clk, rstn); input wire uart_busy; output wire uart_wr; output wire[7:0] uart_data; input wire clk; input wire rstn; // state reg[14:0] ip; reg[14:0] dp; reg[14:0] depth; reg[14:0] jump_ip; reg sync_rstn; wire[14:0] next_ip; wire[14:0] next_dp; wire[14:0] next_depth; wire[14:0] next_jump_ip; // temporary wire executing; wire taken; wire[14:0] next_depth_temp; // module wire[7:0] insn; wire[7:0] rdata; wire we; wire[7:0] wdata; wire btb_hit; wire[14:0] btb_target; wire btb_we; wire[14:0] btb_write_ip; wire[14:0] btb_write_target; insnmem insnmem0(next_ip, insn, clk); datamem datamem0(next_dp, rdata, we, wdata, clk); btb btb0(next_ip, btb_hit, btb_target, btb_we, btb_write_ip, btb_write_target, clk); // logic assign executing = depth == 0; assign next_depth_temp = executing ? insn == 8'h5B & rdata == 0 ? 1 : insn == 8'h5D & rdata != 0 ? -1 : 0 : depth + (insn == 8'h5B) - (insn == 8'h5D); assign taken = executing && next_depth_temp != 0; assign next_depth = !sync_rstn ? 0 : taken && btb_hit ? 0 : next_depth_temp; assign next_ip = !sync_rstn ? 0 : taken && btb_hit ? btb_target : uart_busy && uart_wr ? ip : next_depth_temp[14] ? ip - 1 : ip + 1; assign next_dp = !sync_rstn ? 0 : insn == 8'h3E && executing ? dp + 1 : insn == 8'h3C && executing ? dp - 1 : dp; assign next_jump_ip = !sync_rstn ? 0 : taken ? ip : jump_ip; assign we = (insn == 8'h2B || insn == 8'h2D) && executing; assign wdata = insn == 8'h2D ? rdata - 1 : rdata + 1; assign btb_we = next_depth_temp == 0 && !executing; assign btb_write_ip = jump_ip; assign btb_write_target = next_ip; assign uart_wr = insn == 8'h2E && executing; assign uart_data = rdata; // flip-flop always @(posedge clk) begin ip <= next_ip; dp <= next_dp; depth <= next_depth; jump_ip <= next_jump_ip; sync_rstn <= rstn; end endmodule module btb(next_ip, hit, target, we, write_ip, write_target, clk); input wire[14:0] next_ip; output wire hit; output wire[14:0] target; input wire we; input wire[14:0] write_ip; input wire[14:0] write_target; input wire clk; reg before_we; reg[14:0] ip; wire[9:0] partial_addr; wire[20:0] rdata; wire[20:0] wdata; btbmem btbmem0(partial_addr, rdata, we, wdata, clk); assign hit = !before_we && rdata[20] && rdata[19:15] == ip[14:10]; assign target = rdata[14:0]; assign partial_addr = we ? write_ip[9:0] : next_ip[9:0]; assign wdata = { 1'b1, write_ip[14:10], write_target }; always @(posedge clk) begin before_we <= we; ip <= next_ip; end endmodule module btbmem(addr, rdata, we, wdata, clk); input wire [9:0] addr; output reg [20:0] rdata; input wire we; input wire[20:0] wdata; input wire clk; reg[20:0] mem[0:1023]; integer i; initial for(i=0; i<1024;i=i+1) mem[i] = 0; always @(posedge clk) begin if (we) begin rdata <= wdata; mem[addr] <= wdata; end else begin rdata <= mem[addr]; end end endmodule module insnmem(next_ip, insn, clk); input wire[14:0] next_ip; output reg [7:0] insn; input wire clk; reg[7:0] mem[0:32767]; initial $readmemb("D:/vivado/brainfuck/project_1/mandelbrot.bin", mem); always @(posedge clk) begin insn <= mem[next_ip]; end endmodule module datamem(addr, rdata, we, wdata, clk); input wire[14:0] addr; output reg [7:0] rdata; input wire we; input wire [7:0] wdata; input wire clk; reg[7:0] mem[0:32767]; integer i; initial for(i=0; i<32768;i=i+1) mem[i] = 0; always @(posedge clk) begin if (we) begin rdata <= wdata; mem[addr] <= wdata; end else begin rdata <= mem[addr]; end end endmodule
BTBは1024エントリ、ダイレクトマップのものを作りました。エントリ数は、件のFPGAに乗っているBrockRAM一つ（36Kbit）に収まるように決定しました。 ポート数をケチるため*3、書き込みポートと読み出しポートを共有化し、BTBに書き込むサイクルの次サイクルではBTBからの読み出しができない（常にBTBミスとなる）ものとしました。BTBへの書き込みは頻繁には起こらない（BTBミスしたときのみBTBに書き込む）ため、これはそれほど問題になりません。 BTBのエントリは、上位ビットから、validビット（1bit）、タグ（5bit）、分岐先（15bit）、の計21bitです。
validビットが0であるか、タグが一致しなかった場合は、BTBミスとなり、元のCPUとまったく同じ動作になります。
BTBヒットであっても、直ちにその値が次のサイクルのIPになるわけではありません。データメモリを読み出した値によっては分岐不成立となり、IP+1が次のサイクルのIPになります。
BTBヒットかつ分岐成立の場合のみ、記録されている分岐先が次のサイクルのIPとなります（taken && btb_hit ? btb_target :）。
BTBを実装しても、動作周波数は変わらず、100MHzになりました。
なお、Brainfuck命令の実行が速くなりすぎ、UART送信にかかる時間よりも短い時間間隔で二つの.命令が実行されてしまうことがあり、送信データに欠けが発生しました。
そのため、UART送信中に.命令が実行されそうになった場合はCPU全体を止めるというuart_busy && uart_wr ? ip :を追加しました。
実際にFPGAに書き込んで動作させてみると、結構早くなった印象を受けました。
C++で書かれたシミュレータで確認したところ、最初のBrainfuckCPUは10521107970命令を31892362997サイクルで実行していました。 BTBを追加したBrainfuckCPUでは、（UART送信に伴うストールを除けば）10521107970命令を10824019551サイクルで実行できるようになりました。 約三倍の高速化です！
まとめ
FPGA上で動く、BTBつきのシングルサイクルBrainfuckCPU（100MHz動作）を作った話でした。
今後の課題
UART受信回路を載せて、プログラムを後から書き込めたり、,命令を実行できたりするCPUを作ったりしていきたいです。
