call順位が高い関数のFSM化が完了したので、次に1度しか呼ばれていない関数もFSM化してみます。これは物量にはほぼ影響はないか若干増加するものの、巨大なFSMループからはずすことで、コンパイル時の競合条件計算量の減少を目的とするものです。まず、6個あるdrawString関数の1つをFSM化します。

まず、オリジナルのコードは、

   function Stmt drawTitle1(); // PLAY SPACE INVADERS
      return (seq
         for (str_idx <= 0; str_idx < 19; str_idx <=  str_idx + 1) seq
            copyGlyph(s1[str_idx]);
            waitTicks(`TICK_WAIT8);
            if (fbutton) break;
         endseq // for
      endseq);
   endfunction

変更後のコードは前回と同様なので省略します。

以下に結果の表を示します。思ったほどはコンパイル時間は減りませんでした。またverilog量は若干減ったものの、物量は想像したとおり増加しています。これは新たに起動、終了待ちが増えるためでしょう。全体としてあまり意味が無さそうなのでこれは中止します。

前のブログ 次のブログ

bugのためかcall順位の上位では出てこなかった関数にdrawLives()がありました。これは自機の残り数を表示するもので、staticには6回呼ばれています。これもFSM化して最適化します。

まず、オリジナルのコードは、

    // 残機表示
   function Stmt drawLives();
      return (seq
         // 残機数字の表示
         copyArea(gun_no*8, 161, 23, 241, 8, 8);
         if (gun_no == 1) seq
            eraseArea(42, 241, 16, 8);
         endseq else if (gun_no > 1) seq
            eraseArea(16*gun_no + 26, 241, 16, 8);
            copyArea(0, 16, 16*gun_no+10, 241, 16, 8);
         endseq // if
      endseq);
   endfunction

ここでgnu_noが自機の数を示します。これを例によってFSM化してメインでは起動し、終了待ちをするだけに変更します。以下が変更後のコードです。

   // 残機表示
   function Stmt drawLives_org();
      return (seq
         // 残機数字の表示
         copyArea(gun_no*8, 161, 23, 241, 8, 8);
         if (gun_no == 1) seq
            eraseArea(42, 241, 16, 8);
         endseq else if (gun_no > 1) seq
            eraseArea(16*gun_no + 26, 241, 16, 8);
            copyArea(0, 16, 16*gun_no+10, 241, 16, 8);
         endseq // if
      endseq);
   endfunction

   // 単一インスタンスのFSMを生成（モジュールスコープ）
   FSM drawLives_fsm <- mkFSM( drawLives_org() );

   // “起動ラッパ”を元の名前に
   function Stmt drawLives();
      return (seq
         `RUN_FSM(drawLives_fsm)
      endseq);
   endfunction

以前作成したマクロは以下のとおりです。

`define RUN_FSM(F)  action F.start(); endaction await(F.done);

以下に結果の表を示します。bsvソース量はほとんど変わらないので表示していません。bscの場合の数が減り、結果の物量は変わらないもののコンパイル時間がかなり減少しています。

前のブログ 次のブログ

次にかなり大きな修正となりますが、OneStageの除去をトライします。もともと外部投稿記事にあるようにGameFSMとSoundFSMの両FSMのタイミング調停を図る目的で1stage FIFOを設けましたが、実はBSVの特徴として、自動ハンドシェーク、すなわちBack pressureを自動的にかける機能があります。

前記事のあたりで検討していたもので、この時はトップでconnectableで接続すれば配線だけになると誤解していました。実際にはconnectableは配線だけではなく、トップでANDを生成します。具体的には図1032.1に示すように、上流モジュールの送信RDYと下流モジュールの受信RDYのANDを最上位でとり、これが通信RDYを意味するわけですが、それを上流モジュールへ送信ENとして配り、かつ下流モジュールへも受信ENとして配るものです。

これはcallerであるトップが2つのcalleeを呼ぶ際に調停ロジックとしてANDゲートを配置するためです。

しかしながら、これだとVivadoのBlock DesignerによりANDゲートを起こさなければいけないためあまりきれいではないので、このANDゲートをwrapperで吸収してもらうようにChatGPTに依頼します。

前のブログ 次のブログ

コール順位4位のsound関数は元々サウンドFSMを構成しており、それを起動するだけなので、このままでOKです。

最後にコール順位6位のketa関数をリファクタします。これは元は10進4桁の数値を表示する関数であり、一桁ずつ10^nを引いて商を求めるものでした。従ってStmtを用いてループを構成しており、汎用FSM起動マクロでもうまく行きましたが、一方で内部変数への競合の回避が困難でした。

ChatGPTに相談したところ、組み合わせ回路で可能とのことで全面リファクタしたものです。

  // 14bit → BCD4（加算+比較のみ、組合せ）
   function Tuple4#(UInt#(4), UInt#(4), UInt#(4), UInt#(4)) dec4_dd (UInt#(14) x);
     Bit#(16) b16 = 0;  // [15:12]=千, [11:8]=百, [7:4]=十, [3:0]=一
     Bit#(14) bx  = pack(x);           // ★ UInt を Bit に変換してからビット参照
     for (Integer i = 13; i >= 0; i = i - 1) begin
       // 各桁 >=5 なら +3
       for (Integer n = 0; n < 4; n = n + 1) begin
         Bit#(4) nib = b16[n*4 + 3 : n*4];
         if (nib >= 5) nib = nib + 3;
         b16[n*4 + 3 : n*4] = nib;
       end
       // 左シフトして次ビットを流し込む
       b16 = { b16[14:0], bx[i] };
     end
     UInt#(4) d0 = unpack(b16[3:0]);
     UInt#(4) d1 = unpack(b16[7:4]);
     UInt#(4) d2 = unpack(b16[11:8]);
     UInt#(4) d3 = unpack(b16[15:12]);
     return tuple4(d3, d2, d1, d0);
   endfunction

よく見ると、dec4_dd関数には=は使われていますが、<=(レジスタ代入)は使われていません。これはdec4_ddには見かけはforループがあるものの、全てstaticに展開され、全体として組み合わせ回路になっていることがわかります。

最後にこれを用いてscoreとhigh_scoreを画面の特定の場所に表示する関数です。

   // Draw Score and High-score
   function Stmt scores;
      match { .s3, .s2, .s1, .s0 } = dec4_dd(score);
      match { .h3, .h2, .h1, .h0 } = dec4_dd(high_score);
      return (seq
         // display score
         if (score > high_score) high_score <= score;
         copyArea(zeroExtend(s3) << 3, 169, 38      , 24, 8, 8);
         copyArea(zeroExtend(s2) << 3, 169, 38 +  8 , 24, 8, 8);
         copyArea(zeroExtend(s1) << 3, 169, 38 + 16 , 24, 8, 8);
         copyArea(zeroExtend(s0) << 3, 169, 38 + 24 , 24, 8, 8);
         copyArea(zeroExtend(h3) << 3, 177, 110      , 24, 8, 8);
         copyArea(zeroExtend(h2) << 3, 177, 110 +  8 , 24, 8, 8);
         copyArea(zeroExtend(h1) << 3, 177, 110 + 16 , 24, 8, 8);
         copyArea(zeroExtend(h0) << 3, 177, 110 + 24 , 24, 8, 8);
      endseq);
   endfunction

このようにバイナリを4桁BCD化する関数を組合わせ回路にしたところ、ワンサイクルなので回路は増加するかと思いきや、以下のように若干減少する結果になりました。組合せ回路は多少増えても10^nを引くループが8回削減された効果が大きいようです。

前のブログ 次のブログ

前記事でコール順位3位のwait_timerを最適化します。

元のwait_timerは単純に60Hzの外部信号ticに同期して動作する関数です。これをまずwait_timer_orgにリネームします。

   // 時間待ち
   function Stmt wait_timer_org(
      UInt#(12) count
   );
      return (seq
         repeat(pack(extend(count))) seq
         await(tic == 0 || (foa && fbutton));
         await((tic == 1 && sreq == 0) || (foa && fbutton));
         endseq
      endseq);
   endfunction

これに対して、FSM wt_fsmを作成し、さらにそれを起動する汎用マクロを用いたタイマFSM起動関数を元の名前で作成します。

  // ラッパ用：引数をラッチするだけ（Reg は1本）
  Reg#(UInt#(12)) wt_count <- mkReg(0);
  // 本体は org を mkFSM 化（count は Reg 値を読ませる）
  FSM wt_fsm <- mkFSM( wait_timer_org(wt_count) );

  // 同名の薄ラッパ：値ラッチ → 1サイクル待つ → start → done 待ち
  function Stmt wait_timer (UInt#(12) count);
    return (seq
      action wt_count <= count; endaction
      `RUN_FSM(wt_fsm)
    endseq);
  endfunction

このようにすれば、wait_timerを読んでもStmtがほとんど増加せずにFSMに起動をかけ、終了を待つだけになります。本体のStmtとしてはやや小さいものの、前ページのように16回呼ばれているため多少の効果はあるようです。

この関数だけのFSM化効果を調べたら以下のようにverilog量(byte数)で10.6%の削減となったので、そこそこの効果はありました。

前のブログ 次のブログ

GameFSM中で2回以上staticに呼ばれているsystem functionではない関数とそのstaticな回数です。

次に比較的多数回呼ばれている時間待ち関数wait_timer()をFSM化します。

前のブログ 次のブログ

従来のcopyAreaをStmtで記述して呼び出す方式(変更前)と今回engine方式によりメインではFSMを起動する方式の2つのbsvとverilogの結果比較です。

BSVソースはスイッチによりオリジナルと小FSM方式を出力し分けるように両方のコードが入っているため却って増大しています。

なお、前記事のfunction _BLIT()においてnoActionをコメントにしている場合の数値であり、その代わりに変数競合の警告がでます。実際には問題ないので警告offにしていますが、警告を消す場合はこのnoActionを入れる必要があります。ただしその分コンパイル時間、物量共増大します。

前のブログ 次のブログ

最後にcopyArea()等の従来関数を引数等の順番や個数を変えずに薄いラッパーで定義します。

   // 同名ラッパは _BLIT を呼ぶだけに
  function Stmt copyArea(U8 sx,U8 sy,U8 dx,U8 dy,U8 w,U8 h);
    return _BLIT(Blit{op:BLIT_COPY, sx:sx, sy:sy, dx:dx, dy:dy, w:w, h:h});
  endfunction
  function Stmt orArea(U8 sx,U8 sy,U8 dx,U8 dy,U8 w,U8 h);
    return _BLIT(Blit{op:BLIT_OR, sx:sx, sy:sy, dx:dx, dy:dy, w:w, h:h});
  endfunction
  function Stmt eraseArea(U8 dx,U8 dy,U8 w,U8 h);
    return _BLIT(Blit{op:BLIT_ERASE, sx:0, sy:0, dx:dx, dy:dy, w:w, h:h});
  endfunction
  function Stmt eraseAreaSP(U8 sx,U8 sy,U8 dx,U8 dy,U8 w,U8 h);
    return _BLIT(Blit{op:BLIT_ANDN, sx:sx, sy:sy, dx:dx, dy:dy, w:w, h:h});
  endfunction
  function Stmt getVdots(U8 x, U8 y);
      return _BLIT(Blit{ op:BLIT_VDOTS, sx:0, sy:0, dx:x, dy:y, w:0, h:0});
  endfunction
  function Stmt getHdots(U8 x, U8 y);
      return _BLIT(Blit{ op:BLIT_HDOTS, sx:0, sy:0, dx:x, dy:y, w:0, h:0});
  endfunction

以上のように、copyArea()等の6種のVRAMアクセス関数は全てFSMを起動し、終了を待つだけの関数に書き換えます。

前のブログ 次のブログ

元はcopyArea()等の4種の関数でしたが、それを統合して内部で振り分けます。これはVRAMへのsingle writer化が目的です。single writer化すると警告が消えるだけでなく、競合条件の数が減るため競合チェック時間も短くなります。

またこれら4種の関数とは別にVRAMアクセスのためのコードも含めています。これもsingle writer化のためです。

  // 元の Stmt を呼び分ける統合 blit（本文は従来の関数をそのまま呼ぶだけ）
  function Stmt blit(Blit b);
    return (seq
      if (b.op == BLIT_COPY)
        copyArea_org(b.sx, b.sy, b.dx, b.dy, b.w, b.h);
      else if (b.op == BLIT_OR)
        orArea_org(b.sx, b.sy, b.dx, b.dy, b.w, b.h);
      else if (b.op == BLIT_ERASE)
        eraseArea_org(b.dx, b.dy, b.w, b.h);
      else if (b.op == BLIT_ANDN)
        eraseAreaSP_org(b.sx, b.sy, b.dx, b.dy, b.w, b.h);
      else if (b.op == BLIT_VDOTS)
        getVdots_org(b.dx, b.dy);
      else // BLIT_HDOTS
        getHdots_org(b.dx, b.dy);
    endseq);
  endfunction

次にコマンド変数とともにFSMを作成します。

  // mkFSM
  Reg#(Blit) blitArg <- mkRegU;
  FSM gfx <- mkFSM( blit(blitArg) ); // FSMの作成

このFSMを起動するRUN_FSMコマンドは汎用に作成されています。fsmを渡すと起動、終了待ちを実行します。

  // FSM起動コマンドの定義
  `define RUN_FSM(F)  seq \
    action F.start(); endaction \
    await(F.done); \
  endseq

  // 起動・完了待ちの薄ラッパ
  function Stmt _BLIT(Blit b);
    return (seq
//      noAction; // read/write競合警告を止めるため
      action blitArg <= b; endaction
      `RUN_FSM(gfx_fsm) // gfx_fsmの起動
    endseq);
  endfunction

_BLIT()はFSMを起動し、終了を待つだけの関数です。

前のブログ 次のブログ

調査の結果、copyAreaがstaticに31回呼ばれ(関連関数だと69回)、それが状態爆発を起こしていることが分かってきました。数年前に開発した時は同じソースで、bsvコンパイルが1時間もかかっていましたが、PCの更新と合わせてbscもアップデートされたことから、現在は16分程度になっています。かなり時間がかかるのはこの巨大なFSMの構築のためです。

これもChatGPT5に相談したところ、メインのStmtからcopyAreaのStmtを31回呼ぶと巨大なFSMのスケジューリングが必要になり時間がかかるとのことでした。対処法は画面アクセスする関数を小FSM化しておき、メインからは起動コマンドを発行するだけにします。

まず、blitEngine()が動作するコマンド種別を定義します。

typedef UInt#(8) U8;

typedef enum { BLIT_COPY, BLIT_OR, BLIT_ERASE, BLIT_ANDN }
  BlitOp deriving (Bits, Eq);

typedef struct {
  BlitOp op;
  U8 sx; U8 sy;   // ソース(prom)のx, yアドレス
  U8 dx; U8 dy;   // デスト(vram)のx, yアドレス
  U8 w; U8 h;      // 図形の幅と高さ
} Blit deriving (Bits, Eq);

前のブログ 次のブログ