実行結果

次は、ファンクションの中にシーケンスを組み込み、ゲームFSMの設計トライアルを行います。 シーケンスを人手で分解することは、なるべくしたくありません。ファンクションでシーケンスが定義できれば、インベーダ動作、自機動作等のファンクションを作成し、順番にそれらを呼び出せば良いはずです。

import StmtFSM::*;

interface TestFSM_ifc;
   method Action inp(UInt#(8) inx);
endinterface

(* synthesize *)
module mkTestFSM(TestFSM_ifc);

Reg#(UInt#(8)) i <- mkRegU;
Reg#(UInt#(8)) x <- mkRegU;

function Stmt test1;
   return (seq
      $display("%3d 1-1", $time);
      delay(5);
      $display("%3d 1-2", $time);
   endseq);
endfunction

function Stmt test2(UInt#(8) xx);
   return (seq
      $display("%3d 2-1", $time);
      for (i <= 0; i < xx; i <= i + 1)
         $display("%3d 2-loop-%1d", $time, i);
      $display("%3d 2-2", $time);
   endseq);
endfunction

   Stmt main =
   seq
      $display("%3d fsm1.start", $time);
      test1;
      $display("%3d fsm2.start", $time);
      test2(x);
   endseq;

   mkAutoFSM(main);

   method Action inp(UInt#(8) inx);
     x <= inx;
   endmethod

endmodule: mkTestFSM

このためのテストベンチを示します。あえてモジュール外部からループ回数を入れているのは、ループ回数がダイナミックに(実行時に)決定できるかを確認するためです。ファンクションのループを8回呼び出してみます。

import StmtFSM::*;
import TestFSM::*;

(* synthesize, always_ready, always_enabled *)
module mkTb (Empty);
  TestFSM_ifc test <- mkTestFSM();
  Reg#(UInt#(8)) count <- mkReg(8);

   Stmt main =
      seq
         test.inp(count);
         repeat(40) noAction;
      endseq;

      mkAutoFSM(main);
  
endmodule

実行結果を示します。test1の次にtest2が呼び出され、ループが8回回ったことを示しています。

 20 fsm1.start
 30 1-1
 90 1-2
100 fsm2.start
110 2-1
130 2-loop-0
150 2-loop-1
170 2-loop-2
190 2-loop-3
210 2-loop-4
230 2-loop-5
250 2-loop-6
270 2-loop-7
290 2-2

---

前のブログ 次のブログ

実行結果

以下に実行結果を示します。

senderFSM    20 FSM started
receiverFSM  20 receiver FSM started
senderFSM    30 Enq 10
senderFSM    40 Enq 20
receiverFSM     40 FIFO popped data 10
senderFSM    50 Enq 30
receiverFSM  70 FIFO popped data 20
receiverFSM  100 FIFO popped data 30

10nsずつ見ていきます。最初の10nsはリセット期間なので、20nsからFSM動作を開始します。

senderFSM    20 FSM started
receiverFSM  20 receiver FSM started

同時にセンダーFSMとレシーバーFSMが動作を開始しました。

senderFSM    30 Enq 10

センダーFSMがデータ10をエンキューしました。FIFOには1段のデータがあるはずです。

senderFSM    40 Enq 20
receiverFSM  40 FIFO popped data 10

レシーバーFSMが10をデキューすると同時にセンダーFSMがデータ20をエンキューしました。FIFOには差し引き1段のデータがあるはずです。

senderFSM    50 Enq 30

センダーFSMのレイテンシは1サイクル10nsなので次々に(FIFO FULLにならない限り)エンキューします。これが最後のデータです。FIFOには2段のデータがあるはずです。

receiverFSM  70 FIFO popped data 20

レシーバーFSMのレイテンシは3サイクル30nsなので、70nsにならないと次データの20がデキューできません。FIFOには1段のデータがあるはずです。

receiverFSM  100 FIFO popped data 30

レイテンシである3サイクル後にレシーバーFSMがデキューしました。FIFOには0段のデータがあるはずです。つまりFIFOは空になったはずです。

波形で見たほうが判りやすいです。エンキュー動作(オレンジの信号)はFIFOがフルでない限り1サイクルで行われるのに対してデキュー動作(ブルーの信号)は3サイクル毎に実行されています。

図252.1 センダーFSMとレシーバーFSM

以上はデータを3つエンキューした場合ですが、ここで4つ目をエンキューすると動作が異なります。図252.2に示すように、3つまではレイテンシ1でエンキューできていましたが、3つめでFIFO FULLとなり、その後はレシーバーFSMのレイテンシが見えてきます。つまりエンキュー動作もレイテンシが3となります。

図252.2 センダーFSMとレシーバーFSM 図252.1でもFIFOがFULLになっているのですが、その時にエンキューが無いのでレシーバー側のレイテンシが見えませんでした。図252.2ではFIFOがFULL状態でエンキューしようとして待たされています。FIFOは2段だということが分かります。

実は、FIFO段数もコントロール可能であり、任意の段数のFIFOを作成するにはmkSizedFIFOFを使用します。

      FIFOF#(Bit#(8)) fifo <- mkSizedFIFOF(2);

mkSizedFIFOFの引数サイズを2とすると、上記と同じ動作を行います。サイズを1にすると、デキューするまでエンキューが待たされる、図252.3のような動作となります。

図252.3 　FIFOが1段の場合の動作 bscは良くできていて、FIFOフルの場合等、FIFO がデータを受け取れない場合には自動的にエンキュー動作が抑止されます。普通ならFULLで無い条件でエンキュー動作を行う記述を書かなければいけませんが、その必要がありません。これは自動ハンドシェーク機能と呼ばれます。

---

前のブログ 次のブログ

StmtFSM

前稿ではBSVにより、ステートベースのFSMを設計しました。ステートベースとは、シーケンスを人手でステートに分解し、一つ一つのステートに対してルールを書くもので、基本的にはverilogと同程度の工数がかかります。一方、BSVにはステートマシンを効率的に設計できる、StmtFSMというライブラリが存在します。

検証用FSM

このライブラリの検証用のために検証用FSMを作成します。検証用FSMは2つのコンカレントなFSMを持ち、一方のSenderFSMがFIFOにデータを詰め(エンキュー)、他方のReceiverFSMがFIFOからデータを取り出す(デキュー)ものとします。コンカレントであり、エンキューとデキューは同時に起こります。

図251.1 センダーFSMとレシーバーFSM FSMはそれぞれ別に書き、その内部ではステートメントはシーケンシャルに実行されます。このシーケンシャルの動きはBSCにより管理され、隠れた(設計者から見えない)ステートが割り付けられます。以下にBSVのコードを示します。

package Tb;
import StmtFSM::*;
import FIFOF::*;

(* synthesize *)
module mkTb (Empty);
   FIFOF#(Bit#(8)) fifo <- mkFIFOF;

   Stmt sender =
      seq
         $display("senderFSM  %4d FSM started", $time);
         action
            $display("senderFSM  %4d Enq 10", $time);
            fifo.enq(10);
         endaction
         action
            $display("senderFSM  %4d Enq 20", $time);
            fifo.enq(20);
         endaction
         action
            $display("senderFSM  %4d Enq 30", $time);
            fifo.enq(30);
         endaction
         repeat (8) noAction;
      endseq;
      FSM senderFSM <- mkFSM(sender);

      Stmt receiver =
         seq
            $display("receiverFSM %4d receiver FSM started", $time);
            while(True) seq
               action
                  $display("receiverFSM %4d FIFO popped data", $time, fifo.first());
                  fifo.deq();
               endaction
               repeat (2) noAction;
            endseq
         endseq;
         FSM receiverFSM <- mkFSM(receiver);

      rule startit;
         senderFSM.start();
         receiverFSM.start();
      endrule

      rule finish (senderFSM.done() && !receiverFSM.done());
         $finish;
      endrule
   endmodule
endpackage

コードに示すように、エンキューはレイテンシ1で実行され、デキューはレイテンシ3で実行されます。各々のFSMは、エンキューデータ、デキューデータをそれぞれ表示します。

---

前のブログ 次のブログ

レジスタ配列によるリターンスタック

前稿のリターンスタックrsはベクター配列で構成しましたが、最初に戻りレジスタ配列を試してみます。当初から配列で試したところ、うまく行っていませんでしたが、成功したのでその方法を記述します。まずリターンスタックrsを配列宣言します。

       // return stack
       Reg#(State_t) rs[3];

次に、リターンスタックrsを3段レジスタによりインスタンシエートします。これが無かったため、今まで動作しませんでした。ちなみにverilogでは宣言しただけで使用できますが、BSVでは宣言し、次にインスタンシエートが必要です。

       for (int i = 0; i < 3; i = i + 1)
          rs[i] <- mkRegU;

マクロ命令定義はベクター配列と同じ配列によるアクセス法を用います。

`define call(SUB)        `_pushNext; state <= State_t {func:SUB, step:S0}
`define _pushNext        rs[sp] <= State_t {func:state.func, step:nextStep()}; sp <= sp + 1
`define return           state <= rs[sp-1]; sp <= sp - 1
`define next             state.step <= nextStep()

説明は表248.1と同一です。これを用いて、前稿の検証FSMを実行してみます。

$ bsc -sim -u TestFSM4.bsv
checking package dependencies
compiling TestFSM3.bsv
code generation for mkTestFSM starts
Elaborated module file created: mkTestFSM.ba
All packages are up to date.
$ bsc -sim -e mkTestFSM -o mkTestFSM
Bluesim object created: mkTestFSM.{h,o}
Bluesim object created: model_mkTestFSM.{h,o}
Simulation shared library created: mkTestFSM.so
Simulation executable created: mkTestFSM
$ ./mkTestFSM -m 15 -V dump.vcd | tee result
L1 S0
L1 S1
　L2 S0
　L2 S1
　L2 S2
　　L3 S0
　　L3 S1
　　　L4 S0
　　　L4 S1
　　L3 S2
　L2 S3
　L2 S4
L1 S2
L1 S2
$

正しく実行することが検証できました。波形を図250.1に示します。内部信号を見ると、ベクター配列と同様、rs_0, rs_1, rs_2という3個のレジスタインスタンスが生成されています。

図250.1 検証用FSMのBsim波形(レジスタ配列使用)

合成結果

Vivadoによる合成結果は21 LUTのサイズでした。レジスタ配列とベクター配列は同様のサイズであったため、今後は最も素直なこの方式を採用します。

ソフトウェアの場合は高速なレジスタと低速なメモリがあるため、リターンレジスタ等の実装が必要ですが、FSMではよほどのことが無い限り全てレジスタなので、リターンレジスタを使用しない、この実装を基本的に使用していきます。

---

前のブログ 次のブログ

ベクター配列によるリターンスタック

前稿までのリターンスタックrsはレジスタファイルで構成しましたが、別法のベクター配列を試してみます。 まずベクターをインポートします。

import Vector::*;

次に、リターンスタックrsを3段インスタンシエートします。

   // return stack
   Vector#(3, Reg#(State_t)) rs <- replicateM(mkRegU);

さらにマクロ命令定義を書き換えます。ベクター配列はrs[sp]として扱えるので、直感的に分かりやすいです。

`define call(SUB)          `_pushNext; state <= State_t {func:SUB, step:S0}
`define _pushNext          rs[sp] <= State_t {func:state.func, step:nextStep()}; sp <= sp + 1
`define return             state <= rs[sp-1]; sp <= sp - 1
`define next               state.step <= nextStep()

説明は表248.1と同一です。これを用いて、前稿の検証FSMを実行してみます。

$ bsc -sim -u TestFSM3.bsv
checking package dependencies
compiling TestFSM3.bsv
code generation for mkTestFSM starts
Elaborated module file created: mkTestFSM.ba
All packages are up to date.
$ bsc -sim -e mkTestFSM -o mkTestFSM
Bluesim object created: mkTestFSM.{h,o}
Bluesim object created: model_mkTestFSM.{h,o}
Simulation shared library created: mkTestFSM.so
Simulation executable created: mkTestFSM
$ ./mkTestFSM -m 15 -V dump.vcd | tee result
L1 S0
L1 S1
　L2 S0
　L2 S1
　L2 S2
　　L3 S0
　　L3 S1
　　　L4 S0
　　　L4 S1
　　L3 S2
　L2 S3
　L2 S4
L1 S2
L1 S2
$

正しく実行することが検証できました。波形を図249.1に示します。内部信号を見ると、rs_0, rs_1, rs_2という3個のレジスタインスタンスが生成されています。これが3段のリターンスタックを構成しています。

図249.1 検証用FSMのBsim波形(ベクター配列使用)

合成結果

Vivadoによる合成結果は21 LUTのサイズでした。レジスタファイルよりもベクター配列のほうが、わずかに小さくなることが分かりました。レジスタファイルは下位モジュールのレジスタファイルをインスタンスする必要がありますが、ベクター配列は上記のようにレジスタが展開されるだけです。従って、インタフェースが簡略化されるため、小さくなると考えられます。

---

前のブログ 次のブログ

マクロ命令定義

以上の議論から再定義したマクロ命令のコードです。

`define call(SUB)           `_pushNext; state <= State_t {func:SUB, step:S0}
`define _pushNext           rs.upd(sp, State_t {func:state.func, step:nextStep()}); sp <= sp + 1
`define pushCall(FUNC,SUB)  _pushFunc(FUNC); state <= State_t {func:SUB, step:S0}
`define _pushFunc(FUNC)     rs.upd(sp, State_t {func:FUNC, step:S0}); sp <= sp + 1
`define nextFunc            state <= State_t {func:nextFunc(), step:S0}
`define return              state <= rs.sub(sp-1); sp <= sp - 1
`define next                state.step <= nextStep()

今回、アプリ(インベーダサウンドFSM)の必要上pushCallを定義しています。これは、call命令の一般化であり、次ステートではなく任意のファンクションに戻るコールを実装するものです。以上のマクロ命令の説明を表248.1に示します。

表248.1　マクロ命令の説明

マクロ命令名	説明
call(SUB)	サブルーチンコールです。次ステートをプッシュして、サブルーチンSUBをコールします。
_pushNext	callに使用されており、次のステートをプッシュする内部マクロ命令です。nextStep()関数を使用しています。ユーザは陽に使う必要は無いため、先頭にアンダースコアを付けています。
pushCall(FUNC,SUB)	サブルーチンコールです。戻り先ファンクションFUNCをプッシュして、サブルーチンSUBをコールします。戻り先は指定されたファンクションFUNCの先頭S0となります。
_pushFunc(FUNC)	pushCallに使用されており、戻り先ファンクションFUNCをプッシュする内部マクロ命令です。ユーザは陽に使う必要は無いため、先頭にアンダースコアを付けています。
nextFunc	次のファンクションに進めるためのマクロ命令です。nextFunc()関数を使用しています。
return	呼び出し元(の次のステート)に戻るためのマクロ命令です。
next	次のステートに進めるためのマクロ命令です。nextStep()関数を使用しています。

合成結果

Vivadoによる合成結果は22 LUTのサイズでした。

---

前のブログ 次のブログ

リファクタリング(1)(プッシュとリターンの統合)

前稿でpushRetとcallをまとめるアイデアを記載しましたが、それを実装してみます。まとめたマクロ命令をpushCallと名付けます。

`define _pushRet          rs.upd(sp, ret); sp <= sp + 1
`define popRet            state <= rs.sub(sp-1); sp <= sp - 1
`define pushCall(SUB)     `_pushRet; `_saveNext; state <= State_t {func:SUB, step:S0}
`define _saveNext         ret <= State_t {func:state.func, step:nextStep()}
`define return            state <= ret

非リーフでのコールとリターンが完成したので動作確認を行います。非リーフでのcallをpushCallに、リターンはそのままpopRetとします。リーフではcallは無く、リターンはそのままreturnとします。

ソースコード内のpushRetを削除し、それぞれのcallをL1ルール内において、

             `pushCall(L2);

L2ルール内において、

             `pushCall(L3);

L3ルール内において、

             `pushCall(L4);

のように修正します。動作確認した結果、expectedと一致し正常動作が確認されました。

リファクタリング(2)(リーフと非リーフの共通化)

そもそもリターンレジスタのretがあるためリーフと非リーフの区別がありました。スタック操作はハードウエアであり、性能へのインパクトがほとんど無いことから、リーフ・非リーフで統一したやり方を考えます。それにはretレジスタを廃止します。従って、callとreturnは以下のようにリターンスタックのみで操作します。 retレジスタの削除の他、マクロの修正を次のように行います。

`define return           state <= rs.sub(sp-1); sp <= sp - 1
`define call(SUB)        `_pushNext; state <= State_t {func:SUB, step:S0}
`define _pushNext        rs.upd(sp, State_t {func:state.func, step:nextStep()}); sp <= sp + 1
`define next             state.step <= nextStep()

としました。これにより、サブルーチンコールの場合は常にcall()を用い、リターンの場合は常にreturnを用います。このように修正した結果、正常動作することを確認しました。ただし、returnレジスタを削除したため、rsはL1~L3で使用により3段、従ってspは2bitとなりました。

以上から、内部マクロを除くユーザーに見えるマクロは、call()、return、nextの3種となります。

---

前のブログ 次のブログ

コンパイルと実行

ソースプログラムをコンパイルします。

$ bsc -u -sim TestFSM.bsv
checking package dependencies
compiling TestFSM.bsv
code generation for mkTestFSM starts
Elaborated module file created: mkTestFSM.ba
All packages are up to date.

次にリンクします。

$ bsc -sim -e mkTestFSM -o mkTestFSM
Bluesim object created: mkTestFSM.{h,o}
Bluesim object created: model_mkTestFSM.{h,o}
Simulation shared library created: mkTestFSM.so
Simulation executable created: mkTestFSM

15サイクル実行します。

$  ./mkTestFSM -V dump.vcd -m 15 | tee result
L1 S0
L1 S1
　L2 S0
　L2 S1
　L2 S2
　　L3 S0
　　L3 S1
　　　L4 S0
　　　L4 S1
　　L3 S2
　L2 S3
　L2 S4
L1 S2
L1 S2

検証結果

結果を比較することにより検証します。

$ diff -c result expected

出力結果がサイクルベースで一致したことにより、正しく動作していることが検証されました。実は階層が4レベルあってもL1では戻り先が無いのでスタックを使いませんし、L4もリーフなのでスタックを使いません。従ってL2とL3だけでpush/popするため、スタックは2段(retを含めて3段)となり、spは1bitで良いことになります。これはたまたま前稿と同じ設計です。

このように変更し、上記のコンパイル、実行、一致検証まで実施したところ、期待した動作をすることが確認されました。rsが2段の場合のBsimの波形を図246.2に示します。spは1bitしかないので、sp==2の際にsp==0という不正な値となっていますが、sp==2の場合のspは使用しないため、問題ありません。

図246.2 検証用FSMのBsim波形 次にiverilogによるVerilogシミュレーション波形を図246.3示します。Bsimではrsを見ることができませんでしたが、verilogでは下位モジュールにrsがRAMとして配置されるので、push時にはステート'h08(L2 S0)とステート'h10(L3 S0)の2回、RAMのWEがアサートされていることが分かります。 図246.3 検証用FSMのIverilog波形

---

前のブログ 次のブログ

マクロ命令の使用

過去記事のCalee Savedコールリターンを前稿で作成したマクロ命令を使用して書き直すと、図245.1のようになります。青字がマクロ命令です。Caller Savedでは入らなかった余分なpushRetがルーチン先頭に入っています。あるいは次のcallとまとめてしまい、非リーフからのcallを別に設ければこれは見かけ上無くなります。こうすれば、リーフと非リーフで、コールもリターンも別になるのでかえってすっきりするかもしれません。

図245.1 マクロ命令を使用したサブルーチン呼び出し

検証用FSMソースコード

検証用FSMのBSVの全ソースコードを示します(既紹介部分は除く)。

import RegFile::*;

(* synthesize, always_ready, always_enabled *)
module mkTestFSM();

   Reg#(State_t) state <- mkReg(State_t{func:L1, step:S0}),
                 ret <- mkRegU;

   // L1
   rule rule_L1 (state.func == L1);
      rule rule_S0 (state.step == S0);
         $display("L1 S%d", state.step);
         `next;
      endrule // S0
      rule rule_S1 (state.step == S1);
         $display("L1 S%d", state.step);
         `call(L2);
      endrule // S1
      rule rule_S2 (state.step == S2);
         $display("L1 S%d", state.step);
      endrule // S2
   endrule // L1

   // L2
   rule rule_L2 (state.func == L2);
      rule rule_S0 (state.step == S0);
         $display("  L2 S%d", state.step);
         `pushRet; // L2 is not a leaf routine
         `next;
      endrule // S0
      rule rule_S1 (state.step == S1);
         $display("  L2 S%d", state.step);
         `next;
      endrule // S1
      rule rule_S2 (state.step == S2);
         $display("  L2 S%d", state.step);
         `call(L3);
      endrule // S2
      rule rule_S3 (state.step == S3);
         $display("  L2 S%d", state.step);
         `next;
      endrule // S3
      rule rule_S4 (state.step == S4);
         $display("  L2 S%d", state.step);
         `popRet;
      endrule // S4
   endrule // L2

   // L3
   rule rule_L3 (state.func == L3);
      rule rule_S0 (state.step == S0);
         $display("    L3 S%d", state.step);
         `pushRet; // L3 is not a leaf routine
         `next;
      endrule // S0
      rule rule_S1 (state.step == S1);
         $display("    L3 S%d", state.step);
         `call(L4);
      endrule // S1
      rule rule_S2 (state.step == S2);
         $display("    L3 S%d", state.step);
         `popRet;
      endrule // S2
   endrule // L3

   // L4 (Leaf)
   rule rule_L4 (state.func == L4);
      rule rule_S0 (state.step == S0);
         $display("      L4 S%d", state.step);
         `next;
      endrule // S0
      rule rule_S1 (state.step == S1);
         $display("      L4 S%d", state.step);
         `return;
      endrule // S1
   endrule // L4

endmodule: mkTestFSM

---

前のブログ 次のブログ

BSVコード

nextStep()関数は以下のとおりです。

    function nextStep;
       case (state.step)
          S0: nextStep = S1;
          S1: nextStep = S2;
          S2: nextStep = S3;
          S3: nextStep = S4;
       endcase
    endfunction: nextStep

以下に4段のスタックとスタックポインタの実装(インスタンシエーション)を示します。

    // return stack
    RegFile#(UInt#(2), State_t) rs <- mkRegFile(0, 3);
    // stack pointer
    Reg#(UInt#(2)) sp <- mkReg(0);

検証用FSMの設計

これらのステート遷移の検証用FSMを設計します。全部でL1~L4の4レベルのコールネスティング関係を持ち、各ステートでは、主にステート変数の表示を行います。図244.1～図244.4に、レベル1からレベル4のステート遷移図を図示します。

図244.1 L1ステート遷移

図244.2 L2ステート遷移

図244.3 L3ステート遷移

図244.4 L4ステート遷移

検証結果の作成

expectedというファイル名で実行結果を作成しておきます。レベルとステートをサイクル毎に表示するFSMの動きを示します。

    L1 S0
    L1 S1
      L2 S0
      L2 S1
      L2 S2
        L3 S0
        L3 S1
          L4 S0
          L4 S1
        L3 S2
      L2 S3
      L2 S4
    L1 S2
    L1 S2

---

前のブログ 次のブログ