FPGAで動作するBrainf**k CPUの詳細 #FPGA

FPGA上で動作するBrainf**k CPU

先日GitHubにFPGA(Terasic DE0)で動作し、Brainf**k言語を直接処理するCPUのVerilog HDLによるコードとQuartus II 13.1用のプロジェクトファイルを公開しました。
github.com/moizumi99/brainf__k_CPU

自分のブログでも紹介しましたが、こんな感じで動作します

スペック

クロック 50MHz (ボードの制約による)
ROMアドレス 12bit (4K Byte)
RAMアドレス 12bit (4K Byte)
入力 8bit (ボード上のスイッチ）
出力 8bit (LCDにアスキーコードに対応する文字を表示)

開発環境

*Quartus II 13.1

Brainf**kについて

Esolang WikiのBrainf**kの項などをご覧ください

ブロック図

全体のブロック図はこのようになります

CPUのコード

以下CPUのコア部分のコードを紹介します。

ステートマシーン

CPUのコードのうち、中心になるステートマシーンは以下のようになります。

この部分の記述は以下のとおりです。


   // state machine 
   always @(posedge clk or posedge rst) begin
      if (rst)
        cur_state <= INIT;
      else if (s_rst)
        cur_state <= INIT;
      else
        cur_state <= nxt_state;
   end

   // state machine next state
   always @(cur_state or op_den or mread or data_den or s_rst or init_cnt or mem_cnt or data_w_wait) begin
      if (s_rst)
        nxt_state <= INIT;
      else begin
         case (cur_state)
           INIT:
             if (init_cnt == INIT_WAIT)
               nxt_state <= MEMI;
             else
               nxt_state <= INIT;
           MEMI: // メモリーの初期化
             if (mem_cnt == MEM_MAX)
               nxt_state <= IDLE; // 初期化終了
             else
               nxt_state <= MEMI;
           IDLE: //命令フェッチの準備
             nxt_state <= FETCH;
           FETCH: //命令フェッチ        
             if (op_den == 1) //命令の読み込み完了
               nxt_state <= MEMR;
             else
               nxt_state <= FETCH;
           MEMR:
             if (mread==0 | data_den == 1'b1) //メモリー読み込みが無いか、データ読み込みが終わった
               nxt_state <= MEMW;
             else
               nxt_state <= MEMR;
           MEMW: //データ書き込み
             if (data_w_wait==0) //データ書き込みが終わった
               nxt_state <= FETCH;
             else
               nxt_state <= MEMW;
           default: nxt_state <= FETCH; // IDLE
         endcase // case (cur_state)
      end // else: !if(s_rst)
   end

'['と']'に伴う探索

読み込んだ命令が'['又は']'の場合、条件によって探索モードに入ります。探索モードでは対応する']'又は'['が見つかるまでPCを+1('['の場合)又は-1(']'の場合）し続けます。


   // Decoder for [ and ]
   always @(posedge clk or posedge rst) begin
      if (rst)
        begin
           mov <= 0;
           mov_dir<= 0;
           p_cnt <= 0;
        end
      else if (s_rst)
        begin
           mov <= 0;
           mov_dir<= 0;
           p_cnt <= 0;
        end
      else if (cur_state==MEMR)
        if (mov == 1) // movは探索モードを示す
          begin
             if       ((mov_dir==0 & cur_op==8'h5B) | (mov_dir==1 & cur_op==8'h5D)) 
             // mov_dirは探索の方向 0:前進, 1:後退
             // 前方探索で[(x5B), 広報探索で](h5D)が見つかったら
               p_cnt <= p_cnt+12'b1; // ネスト深度を+1
             else if (((mov_dir==0 & cur_op==8'h5D) | (mov_dir==1 & cur_op==8'h5B)) & (p_cnt==0))
             // 前方探索で](x5B), 広報探索で[(h5D)が見つかり、ネスト深度が0なら
               mov <= 0;
             else if  ((mov_dir==0 & cur_op==8'h5D) | (mov_dir==1 & cur_op==8'h5B))
             // 前方探索で](x5B), 広報探索で[(h5D)が見つかり、ネスト深度が>0なら
               p_cnt = p_cnt-12'b1; //ネスト深度を-1
          end
        else if (data_den == 1'b1 & cur_op==8'h5B & data_in==0)
             //命令が[で、データが0なら次の]にジャンプ。
          begin
             mov <= 1; //探索モード開始
             mov_dir <= 0; //前方探索
             p_cnt <= 0; //ネスト深度0
          end
        else if (data_den == 1'b1 & cur_op==8'h5D & data_in!=0)
             //命令が]で、データが0でないなら対応する[にジャンプ。
          begin
             mov <=1; //探索モード開始
             mov_dir <= 1; //後方探索
             p_cnt <= 0; //ネスト深度0
          end
   end

   // decoder for PC change  
   always @(cur_state or mov or mov_dir) begin
      case (cur_state)
        IDLE:
          begin
             pc_inc <= 1;
             pc_dec <= 1;
             // 両方１の時は次のクロックで初期値をリード
          end
        MEMW:
          begin
             pc_inc <= (mov==0 | mov_dir==0) ? 1'b1 : 1'b0;
             //通常モード又は前方探索なら、PC++
             pc_dec <= (mov==0 | mov_dir==0) ? 1'b0 : 1'b1;
             //探索モードで後方探索なら、PC--
          end
        default:
          begin
             pc_inc <= 0;
             pc_dec <= 0;
          end
      endcase
   end  

// pc change
   always @(pc_inc or pc_dec or pc_reg) begin
      if (pc_inc==1 & pc_dec==0)
        pc_nxt <= pc_reg + 12'b1;
      else if (pc_inc==0 & pc_dec==1)
        pc_nxt <= pc_reg - 12'b1;
      else
        pc_nxt <= pc_reg;
   end

   always @(posedge clk or posedge rst) begin
      if (rst)
        pc_reg <= 0;
      else if (s_rst)
        pc_reg <= 0;
      else
        pc_reg <= pc_nxt;
   end


   // pc_read
   always @(pc_inc or pc_dec or pc_nxt or pc_reg) begin
      op_r_req <= pc_inc | pc_dec;
      if (pc_inc | pc_dec)
        pc <= pc_nxt;
      else
        pc <= pc_reg;
   end

Brainf**kのコードと実行結果

今回はBrainf**k Interpreterを利用してBrainf**kのサンプルコードを作りました。”BF Rocks!"と表示するコードはこうなります。（最後の[]はCPUを無限ループに入れるために追加）

++++[++++>---<]>-.++++.[-->+<]>---.>-[--->+<]>---.--[--->+<]>-.------------.++++++++.++++++++.+[-->+++++<]>-.[]

これを、toolsフォルダのtxt2hexを使いQuartus IIがコンパイルできる形式に変換します。

:100000002b2b2b2b5b2b2b2b2b3e2d2d2d3c5d3ea1
:100010002d2e2b2b2b2b2e5b2d2d3e2b3c5d3e2d89
:100020002d2d2e3e2d5b2d2d2d3e2b3c5d3e2d2d61
:100030002d2e2d2d5b2d2d2d3e2b3c5d3e2d2e2d61
:100040002d2d2d2d2d2d2d2d2d2d2d2e2b2b2b2be7
:100050002b2b2b2b2e2b2b2b2b2b2b2b2b2e2b5bba
:100060002d2d3e2b2b2b2b2b3c5d3e2d2e5b5d0a2d
:00000001FF

これを実行した結果が、冒頭の写真の図になります。

まとめ

Brainf**kの命令を直接実行するCPUをFPGAで動作させることができました。今後の課題としては

メモリーの拡張
SDRAMの対応
(SDAM対応後）キャッシュの導入
パイプライン化
スーパースカラー化

などを考えています。
また、FPGAで作っているので出力に応じて処理を行うようにすればなんでもできるのですが、その場合Brainf**k CPUと呼んで良いのかちょっとわかりません。悩むよりもとりあえず上記の改良を行ってみようと思います。

追記

その後、パイプライン化と、命令の並列実行を行った際の内容をブログで紹介しました。ベンチマークもとってあります
http://uzusayuu.hatenadiary.jp/entry/2017/05/20/165918