巨大 FSM のダイエット計画

はじめに

Hardware Description Language (HDL) 用のアドベント5日目は、Bluespec SystemVerilog (BSV) の巨大 Finite State Machine (FSM) をダイエットする企画です。BSV は HDL の一種で、SystemVerilog の上位版を目指して設計された言語です。ただし実際には SystemVerilog との互換性はあまり高くありません。むしろ Verilog の高級版 と捉えた方がイメージしやすいと思います。

BSV の開発元は Bluespec で、同社は現在では RISC-V の IP に専念しています。その結果として、かつて商用だった BSVコンパイラ(bsc) やシミュレータなどの開発環境がフリーで公開され、誰でも無償で試せるようになりました。

新しい言語は、ある程度使い込まないと評価が難しい一方で、そのためだけにライセンス費を払うのは会社でも腰が重く、アマチュアにはほぼ不可能です。いまは BSV の開発環境一式がフリー公開されているにもかかわらず、使う人はそれほど増えていません。

もし開発環境やツールが商用のままだったなら、なおさら普及していなかったはずです。それだけに、BSV のように優れた言語がフリーで使えるにもかかわらず、ほとんど使われていない現状はもったいなく感じます。実際にアプリケーションを開発してみた経験から BSV はとてもすばらしいと感じており、その理由を探る意味も込めて継続して開発を続けています。

テーマ

今年のアドベントのテーマは巨大 Stmt FSMのダイエット計画です。

まず Stmt とは何かですが、Stmt は C のような手続き型言語と同じ感覚でシーケンスを記述できる BSV の構文です。BSV では、この Stmt から FSM を自動生成してくれる機能 が用意されています。通常 RTL で FSM を設計する場合は、まずシーケンスを考え、それを一つずつステートに分解しますが、BSV の Stmt を使えば、その作業をコンパイラが肩代わりしてくれます。

以前 BSV で スペースインベーダ を設計しました。インベーダゲームの処理はかなり複雑で、1/60 秒の間に

• 自機処理（左右移動）
• 自弾処理（上方移動および衝突判定）
• 敵処理（横および下方移動）
• 敵弾処理（下方移動および衝突判定）
• UFO 処理（移動）
• スコア表示
• タイマー処理

といった処理を実行します。これはwhileやifが入り組んだ複雑なシーケンスで、その一部を C ライクに書くと次のようになります。

if (弾爆発タイマ >= 1) {   // 弾爆発中
    弾爆発タイマ++;
    if (弾爆発タイマ == MAX) {
        弾削除;            // 論理的な消去
        弾爆発マーク消去;
        弾爆発タイマ停止;
    }
} else {
    if (弾が出ていない and 弾生成条件) {
        弾生成処理;
        弾発射音;     // 自弾のみ、敵弾は発射音無し
    }
    if (弾存在) {
        衝突判定;
        if (対象物に衝突) {  // 自弾の場合はインベーダ及びUFO、敵弾の場合は自機
            弾削除;          // 論理的な消去
            弾マーク消去;     // 物理的な消去
            対象物ステート <= 爆発;
            対象物爆発タイマ <= 0;
        } else if (上下ハズレ || ベース || 弾) { // 弾:自弾の場合は敵弾、敵弾の場合は自弾
            弾マーク消去;     // 物理的な消去
            弾爆発マーク;
            弾爆発タイマ <= 1;
        } else {        // 衝突していない場合
            弾を進める;
        }
    }
}

このようなシーケンスを手書きの FSM に落とすのはかなり大変で、過去に手で分解したときにはゲーム全体で 130 ステートにもなりました。Verilog RTL は for ループなど高級言語の制御構造を直接サポートしていません。 そのため、自分でループカウンタを用意してデクリメントし、元のステートに戻るような実装になります。ブロックの概念が無いので、結果として goto が並んだようなステートマシンになりがちです。

また Verilog はサブルーチン呼び出しもサポートしていません。少しでも高位の感覚で RTL を書きたかったため、当時シーケンスを共用する「共通シーケンス」という仕組みを考えました。共通シーケンスを呼び出すときは簡易スタックを設けてそこに戻りステートを積み、マクロ化したリターンで戻るようにしました。

だいぶ効率化できたものの、それでも 1 ステップずつ状態を割り当てていく作業は重く、BSV コンパイラの有り難みを非常に感じています。

前回のシーケンス構築の経験

シミュレータだけでもある程度のデバッグはできますが、ゲームなので最終的には実機で遊びながらの調整が欠かせません。ところが当時は 1 回のコンパイルに 1 時間もかかるのが最大の問題でした。デバッグのたびに気軽に回せる時間ではありません。

では、なぜここまでコンパイル時間が伸びてしまうのか。大きな要因のひとつがよく使う関数のインライン展開です。BSV では、関数をメインシーケンスから呼び出せますが、実際のハードウエアではインライン展開された回路になります。そのため画面へのインベーダ表示のように、ある関数が $n$ 回呼ばれていれば、その分だけおおよそ $n$ 倍のハードウエアが複製されます。

さらに、これらの処理は一回転が 1/60 秒となるロジックを記述した Stmt として記述され、それが 1 個の巨大 FSM に合成されます。多数のステートから同じVRAM やレジスタ等のリソースにアクセスする形になります。コンパイラはこれらのステート間でリソース競合が起きないようにスケジューリングを行うため、ステートやアクセス箇所が増えるほど、検証する組合せが爆発的に増えていきます。

巨大なシーケンスが簡単に書けるのは BSV の大きな利点ですが、一方で結果として生成される FSM は回路規模もコンパイル時間も肥大化し、小さな修正一つに対しても時間がかかる構造になっていました。そこでこのシーケンスの塊のコンパイル時間と回路規模を減らしたいというのが、今回のダイエット企画の動機です。

今回の改良点

巨大な Stmt で構成された FSM の中から、とくにコール頻度の高い Stmt で書かれた関数を切り出し、小さな FSM としました。メイン側からは、そのモジュールに対して「開始」と「終了待ち」だけを行う形にします。重たいシーケンスをメインの Stmt から外に逃がすことで、メイン FSM が抱えるステート数と共有リソースの競合パターンを減らし、コンパイル時間と回路規模の双方を削ることを狙いました。

図にすると次のようなイメージです。

左の大きい輪が従来ソースで、巨大な FSM が一枚岩になっています。色付きの部分が、たとえば copyArea のようなキャラクタ表示関数で、通常は $n$ 回呼ばれます。これを小 FSM として切り出し、メインシーケンスから起動して終了だけ待つ形にすると、この部分の回路規模はおよそ$1/n$ に抑えられます。

コードの実際

もっとも効果が大きかったのは copyArea 関数です。インベーダや UFO などのパターンを持つ ROM から VRAM へ領域コピーを行う関数で、静的に数えただけでも 60 回以上呼ばれています。ソース上は関数として独立していますが、ハードウエアとしてはインライン展開されるため、その回数分だけコピーが生成され、コンパイル時間も回路規模も一気に増えます。

数年前の BSV による開発時には、1 回のコンパイルに 1 時間もかかり、バグを 1 個直すだけでも一苦労でした。PC とコンパイラの性能向上により、いまは同じソースでもおよそ 16 分まで短くなっていますが、それでも頻繁に回すには重い時間です。

なんとかコンパイル時間を短縮したいと思い、ChatGPT に相談してみました。すると先ほどの図のように、その部分を小さな FSM に切り出し、メインからは FSM の起動と終了待ちだけを行う構成が提案されました。copyArea は少し複雑なので、ここではコール頻度 3 位で静的に 16 回呼ばれている wait_timer のコードを例として示します。

これは tic という 60 Hz のフレーム信号の立ち上がりに同期するための待ちルーチンで、引数には待つフレーム数を渡します。

   // 時間待ち
   function Stmt wait_timer(
      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

続いて追加修正する改良版のコードですが、まずこの wait_timer 関数に対して同名のラッパ関数 wait_timer を以下のように新たに起こし、今の wait_timer をオリジナルという意味で wait_timer_org に改名してラッパからコールします。ラッパの機能は先に述べた通り、FSM 化した本体の起動をかけ、戻るのを待つだけのものです。

  // ラッパ用：引数をラッチするだけ（Reg は1本）
  Reg#(UInt#(12)) wt_count <- mkReg(0);
  // 本体は org を mkFSM 化（count は Reg 値を読ませる）
  FSM wt_fsm <- mkFSM( wait_timer_org(wt_count) );
  // FSM起動マクロ seq - endseqで挟んで呼ぶこと
  `define RUN_FSM(F) action F.start(); endaction await(F.done);
  // 同名の薄ラッパ：値ラッチ → 1サイクル待つ → start → done 待ち
  function Stmt wait_timer (UInt#(12) count);
    return (seq
      action wt_count <= count; endaction
      `RUN_FSM(wt_fsm)
    endseq);
  endfunction

こんな簡単な変更でも、この 1 箇所だけで以下のような効果が得られました。

		前	後	比較
BSV合成	コンパイル時間	2'36''	2'10''	▲16.7%
Verilog合成	ファイルサイズ[KB]	9,394	8,395	▲10.6%
Vivado	合成時間	0'51''	0'51''	0.0%
Vivado	LUT数	5,992	5,901	▲1.5%
Vivado	FF数	1,871	1,812	▲3.2%

さて、他の関数も合わせて頻出関数である 7 種類の関数をこの方式に置き換えた結果、コンパイル時間は 16 分強から 51 秒と 95% 削減され、回路規模も 23.8% 減と大きな効果が得られました。

回路規模が減るのは、前述のようにインライン展開されていた関数がサブルーチン化されて共用されるようになったためで、ソフトウエアにおけるサブルーチン化と同じ原理です。
コンパイル時間が減るのは、ハードウエア合成言語ならではの事情で、コンパイラがリソース競合を解析しているからだと考えています。巨大なステートマシンの複数箇所から VRAM など同一リソースへアクセスする場合、その干渉を検証する時間が削減されるわけです。

さいごに

アルゴリズムが固まった今だからこそ最適化に手を入れられましたが、本来はアルゴリズムをデバッグしている段階のコンパイル時間こそ短くしたいところで、要求が相反する皮肉な結果でもあります。

今後はこの RUN_FSM マクロをなるべく初期から活用して、BSV のデバッグ効率をさらに高めていきたいと考えています。