Posts Tagged with "FIFO"

既に発行済みのブログであっても適宜修正・追加することがあります。
We may make changes and additions to blogs already published.
posted by sakurai on December 19, 2022 #573

1段FIFOの検討

FIFOどうしを上位で接続する場合の結線を見ると、図573.1のようになっています。

図%%.1
図573.1 FIFO間の結線

上位ステージFIFOにデータが存在し(!empty)かつ下位ステージFIFOがフルでなければ(!full)上位ステージFIFOのDEQと下位ステージFIFOのENQが同時に実行されます。1段FIFOの実現性を考えると、下位のDEQが有れば上位に!fullになるように制御すれば良さそうです。

修正前の1サイクルおきの動作を示します。

図%-%.1
図573.1 1段FIFOの動作(修正前)

元の論理はemptyとfullは背反論理であり、

     assign FULL_N = !empty_reg;
     assign EMPTY_N = empty_reg ;

このようになっていましたが、これに対して、

     assign FULL_N = !empty_reg || DEQ;
     assign EMPTY_N = empty_reg ;

のように修正したシミュレーション結果を示します。

図%-%.2
図573.2 1段FIFOの動作(修正後)

このように正しく動作しました。なお、この論理はパイプラインFIFOと呼ばれるLFIFOと全く同じであり、ソースに対して

     FIFO#(int) ifs    <- mkLFIFO;

のようにパイプラインFIFOを生成しても全く同じ動作を行います。


左矢前のブログ 次のブログ右矢

posted by sakurai on December 16, 2022 #572

1段FIFOの検討

全く同様に1段FIFOを検討します。ここでの改善点はFullになっている場合にDEQ$ \cap $ENQを実行すると、1サイクル毎にアップデート可能な制御を行うことです。

図%-%.1
図572.1 1段FIFOの動作

表572.1 FIFO段制御表
No. State DEQ/ENQ d0入力制御
0 --- CLR D.C.
1 State0(E:1, F:0) !DEQ$ \cap $!ENQ D.C.
2 !DEQ$ \cap $ENQ d_in
3 DEQ$ \cap !$ENQ D.C.
4 DEQ$ \cap $ENQ D.C.
9 State1(E:0, F:1) !DEQ$ \cap $!ENQ d0
10 !DEQ$ \cap $ENQ D.C.
11 DEQ$ \cap !$ENQ D.C.
12 DEQ$ \cap $ENQ d_in

表より、ENQがアサートされたらd_inを入力する制御とします。

次にステート遷移表です。

表572.2 ステート遷移表
No. Current State ENQ/DEQ Next State
0 --- CLR State0(E:1, F:0)
1 State0(E:1, F:0) !DEQ$ \cap $!ENQ State0(E:1, F:0)
2 !DEQ$ \cap $ENQ State1(E:0, F:1)
3 DEQ$ \cap $!ENQ ERROR
4 DEQ$ \cap $ENQ ERROR
9 State1(E:0, F:1) !DEQ$ \cap $!ENQ State1(E:0, F:1)
10 !DEQ$ \cap $ENQ ERROR
11 DEQ$ \cap $!ENQ State0(E:1, F:0)
12 DEQ$ \cap $ENQ State1(E:0, F:1)

これをこのまま実装するとState1の時にENQをアサートしようとしても、既にfullであるため、キューに入らない事態になります。これをfull=0として見せてやれば同時にDEQする時に限りキューに入れることができます。


左矢前のブログ 次のブログ右矢

posted by sakurai on December 15, 2022 #571

2段FIFOの検討(4)

ここまでで自作FIFO2.vの論理が確定しました。そこでBluespec作成のライブラリであるverilogの論理FIFO2.vと一致するかを確認します。

d0diの論理の手圧縮の結果はd0di = (ENQ && empty == 1) || (DEQ && full == 0)です。一方、Bluespec製verilogソースは、

$BLUESPECDIR/Verilog/FIFO2.v

wire                   d0di = (ENQ && ! empty_reg ) || ( ENQ && DEQ && full_reg ) ;

です。empty_regは不論理のemptyなのでBluespecと1項目は一致しています。

一方2項目目は不一致です。Bluespecには若干無駄があるようです。これをケース分解すれば、2項目は4, 8ですがさらにD.C.である3と7を加えることができます。ちなみにBluespecではempty_reg及びfull_regはなぜか負論理なので、!empty_regはemptyを、full_regは!fullを意味します。

次にd0d1の論理は、d0d1 = DEQ && full == 1ですがBluespec製verilogソースは、

wire                   d0d1 = DEQ && ! full_reg ;

であり、完全一致しました。

次に、d0hの論理は、d0h = !DEQ && empty == 0ですがBluespec製verilogソースは、

wire                   d0h = ((! DEQ) && (! ENQ )) || (!DEQ && empty_reg ) || ( ! ENQ &&full_reg) ;

であり、かなり無駄があるようです。

Bluespec製verilogソースをケース分解すれば、1項目は1,5,9、2項目は5,6,9,10、3項目は1,3,5,7です。必要なのは5,6,9だけなので2項目のみで全てを満たしているのですが、BluespecはState0でもホールドするとして1項目を加えたようです。State0ではデータは無効なのでホールドの必要はありませんがState0で何も起きない場合のホールドである1と、State1からDEQされた場合の7が追加されています。

3項目はState0, 1でENQとならない場合という意味ですが、そもそもState0では無効データのためホールドの必要は無いし、State1でもDEQの場合(7)はホールド不要です。

【追記】無効データではあるものの、DEQされた場合やENQもDEQも無い場合は、前の値を保持するというのがBluespecの仕様のようです。

最後にd1diの論理は、d1di = ENQ && empty == 0ですがBluespec製verilogソースは、

wire                   d1di = ENQ & empty_reg ;

であり、完全一致しました。弊社の論理に変更したFIFOライブラリを用いてシミュレーションを実行しましたが、正常に動作しました。

さらに、ステート遷移は、手圧縮では、

  • CLRのとき、empty = 1, full = 0
  • !DEQ && ENQのとき、empty = 0, full = !emtpy
  • DEQ && !ENQのとき、empty = !full, full = 0
  • 上記以外のときはホールド。emtpy, full共変化無し。

となりましたが、Bluespec製verilogソースでは、

begin
    if (CLR)
       begin
          empty_reg <= `BSV_ASSIGNMENT_DELAY 1'b0;
          full_reg  <= `BSV_ASSIGNMENT_DELAY 1'b1;
       end // if (CLR)
     else if ( ENQ && ! DEQ ) // just enq
       begin
          empty_reg <= `BSV_ASSIGNMENT_DELAY 1'b1;
          full_reg <= `BSV_ASSIGNMENT_DELAY ! empty_reg ;
       end
     else if ( DEQ && ! ENQ )
       begin
          full_reg  <= `BSV_ASSIGNMENT_DELAY 1'b1;
          empty_reg <= `BSV_ASSIGNMENT_DELAY ! full_reg;
       end // if ( DEQ && ! ENQ )
  end // else: !if(RST == `BSV_RESET_VALUE)

となっており、完全一致しました。


左矢前のブログ 次のブログ右矢

posted by sakurai on December 14, 2022 #570

2段FIFOの検討(4)

過去記事で紹介したPLDツールのcuplを用いてespressoによる論理圧縮を行い、手で実施した論理圧縮が合っているかを確認します。

d0diの入力ファイルです。d0diはNo.2とNo.8の時にアサートなので、

d0di =   (!deq & enq  & empty  & !full)   /* 2 */
           # (deq  & enq  & !empty & !full);  /* 8 */

とします。ただしそれ以外にもD.C.となる場合は多く、No.2に対してはNo.4, 14, 16、No.8に対してはNo. 4, 7, 3を加えて論理圧縮をかけます。ただし、論理圧縮は機械でできるものの、有効なD.C.ケースを加える部分は手で行う必要があります。

d0didc = (!deq & enq  & empty  & !full)   /* 2 */
           # (deq  & enq  & empty  & !full)   /* 4 */
           # (!deq & enq  & empty  & full)    /* 14 */
           # (deq  & enq  & empty  & full)    /* 16 */

           # (deq  & enq  & !empty  & !full)  /* 8 */
           # (deq  & enq  & empty   & !full)  /* 4 */
           # (deq  & !enq & !empty  & !full)  /* 7 */
           # (deq  & !enq & empty   & !full); /* 3 */

cuplの圧縮結果を示します。

d0di =>
    deq & !empty & enq & !full
  # !deq & empty & enq & !full

d0didc =>
    deq & !full
  # empty & enq

これは手圧縮の前ページの結果d0di = (ENQ && empty == 1) || (DEQ && full == 0)と一致しています。しかしながら、両方共D.C.ケースを手で加える部分は共通なのでその妥当性は証明されず、論理圧縮のみを検証したことになります。

以下同様に、d0d1の入力は11ですが、これにD.C.ケースである12, 15, 16を加え論理を簡単化します。

d0d1 =   (deq  & !enq & !empty  & full);  /* 11 */

d0d1dc = (deq  & !enq & !empty  & full)   /* 11 */
           # (deq  & enq  & !empty  & full)   /* 12 */
           # (deq  & !enq & empty  & full)    /* 15 */
           # (deq  & enq  & empty  & full);   /* 16 */

cuplの圧縮結果を示します。

d0d1 =>
    deq & !empty & !enq & full

d0d1dc =>
    deq & full

これは、手圧縮の結果d0d1 = DEQ && full == 1と一致しています。

次にd0hの論理は5, 6, 9ですが、これにD.C.ケースである10を加え論理を簡単化します。

d0h =    (!deq & !enq & !empty  & !full)  /* 5 */
           # (!deq & enq  & !empty  & !full)  /* 6 */
           # (!deq & !enq & !empty  & full);  /* 9 */

d0hdc =  (!deq & !enq & !empty  & !full)  /* 5 */
           # (!deq & enq  & !empty  & !full)  /* 6 */
           # (!deq & !enq & !empty  & full)   /* 9 */
           # (!deq & enq  & !empty  & full);  /* 10 */

cuplの圧縮結果を示します。

d0h =>
    !deq & !empty & !full
  # !deq & !empty & !enq & full

d0hdc =>
    !deq & !empty

これは手圧縮の結果d0h = !DEQ && empty == 0と一致しています。

最後にd1diの論理は6, 12ですが、これにD.C.ケースである8, 10を加え論理を簡単化します。

d1di =   (!deq & enq  & !empty  & !full)  /* 6 */
           # (deq  & enq  & !empty  & full);  /* 12 */

d1didc = (!deq & enq  & !empty  & !full)  /* 6 */
           # (deq  & enq  & !empty  & full)   /* 12 */
           # (deq  & enq  & !empty  & !full)  /* 8 */
           # (!deq & enq  & !empty  & full);  /* 10 */

cuplの圧縮結果を示します。

d1di =>
    !deq & !empty & enq & !full
  # deq & !empty & enq & full

d1didc =>
    !empty & enq

これは手圧縮の結果d1di = ENQ && empty == 0と一致しています。


左矢前のブログ 次のブログ右矢

posted by sakurai on December 13, 2022 #569

2段FIFOの検討(3)

ここまでで全ての場合を尽くしたので、d0とdの入力条件を集め、表569.1にまとめます。

表569.1 FIFO段制御表
No. State DEQ/ENQ d0入力制御 d1入力制御
0 --- CLR D.C. D.C.
1 State0(E:1, F:0) !DEQ$ \cap $!ENQ D.C. D.C.
2 !DEQ$ \cap $ENQ d_in D.C.
3 DEQ$ \cap !$ENQ D.C. D.C.
4 DEQ$ \cap $ENQ D.C. D.C.
5 State1(E:0, F:0) !DEQ$ \cap $!ENQ d0 D.C.
6 !DEQ$ \cap $ENQ d0 d_in
7 DEQ$ \cap !$ENQ D.C. D.C.
8 DEQ$ \cap $ENQ d_in D.C.
9 State2(E:0, F:1) !DEQ$ \cap $!ENQ d0 D.C.
10 !DEQ$ \cap $ENQ D.C. D.C.
11 DEQ$ \cap !$ENQ d1 D.C.
12 DEQ$ \cap $ENQ D.C. d_in
13 Undefined(E:1, F:1) !DEQ$ \cap $!ENQ D.C. D.C.
14 !DEQ$ \cap $ENQ D.C. D.C.
15 DEQ$ \cap !$ENQ D.C. D.C.
16 DEQ$ \cap $ENQ D.C. D.C.
D.C.=Don't care

  • d0に対してd_inからの入力条件をd0diとすると、表のd0入力制御の2, 8より
    d0di = (!DEQ && ENQ && empty == 1 && full == 0) /* 2 */ || (DEQ && ENQ && emtpry == 0 && full == 0) /* 8 */
    となるが、2に対して4, 14, 16、及び8に対して3, 4, 7のようなD.C.条件を加えて手で論理圧縮すれば、
    d0di = (ENQ && empty == 1) || (DEQ && full == 0)
  • d0に対してd1からの入力条件をd0d1とすると、表のd0入力制御の11より
    d0d1 = (DEQ && !ENQ && empty == 0 && full == 1) /* 11 */
    となるが、11に対して12, 15, 16を加えて論理圧縮すれば、
    d0d1 = DEQ && full == 1
  • d0に対してd0からの入力条件をd0h(old)とすると、表のd0入力制御の5, 6, 9より
    d0h = (!DEQ && empty == 0 && full == 0) /* 5, 6 */ || (!DEQ && !ENQ && emtpry == 0 && full == 1) /* 9 */
    となるが、5, 6, 9に対して10を加えて論理圧縮すれば、
    d0h = !DEQ && empty == 0
  • d1に対してd_inからの入力条件をd1diとすると、表のd1入力制御の6, 12より
    d1di = (!DEQ && ENQ && empty == 0 && full == 0) /* 6 */ || (DEQ && ENQ && emptry == 0 && full == 1) /* 12 */
    となるが、6, 12に対して8, 10を加えて論理圧縮すれば、
    d1di = ENQ && empty == 0

次にステート遷移表です。

表569.2 ステート遷移表表
No. Current State DEQ/ENQ Next State
0 --- CLR State0(E:1, F:0)
1 State0(E:1, F:0) !DEQ$ \cap $!ENQ State0(E:1, F:0)
2 !DEQ$ \cap $ENQ State1(E:0, F:0)
3 DEQ$ \cap $!ENQ ERROR
4 DEQ$ \cap $ENQ ERROR
5 State1(E:0, F:0) !DEQ$ \cap $!ENQ State1(E:0, F:0)
6 !DEQ$ \cap $ENQ State2(E:0, F:1)
7 DEQ$ \cap $!ENQ State0(E:1, F:0)
8 DEQ$ \cap $ENQ State1(E:0, F:0)
9 State2(E:0, F:1) !DEQ$ \cap $!ENQ State2(E:0, F:1)
10 !DEQ$ \cap $ENQ ERROR
11 DEQ$ \cap $!ENQ State1(E:0, F:0)
12 DEQ$ \cap $ENQ State2(E:0, F:1)
13 Undefined(E:1, F:1) !DEQ$ \cap $!ENQ D.C.
14 !DEQ$ \cap $ENQ D.C.
15 DEQ$ \cap $!ENQ D.C.
16 DEQ$ \cap $ENQ D.C.
D.C.=Don't care

この表を、DEQ/ENQ条件をキーとして並べ変えます。

表569.3 ステート遷移表表
No. Current State DEQ/ENQ Next State
0 --- CLR State0(E:1, F:0)
1 State0(E:1, F:0) !DEQ$ \cap $!ENQ State0(E:1, F:0)
5 State1(E:0, F:0) State1(E:0, F:0)
9 State2(E:0, F:1) State2(E:0, F:1)
13 Undefined(E:1, F:1) D.C.
2 State0(E:1, F:0) !DEQ$ \cap $ENQ State1(E:0, F:0)
6 State1(E:0, F:0) State2(E:0, F:1)
10 State2(E:0, F:1) ERROR
14 Undefined(E:1, F:1) D.C.
3 State0(E:1, F:0) DEQ$ \cap $!ENQ ERROR
7 State1(E:0, F:0) State0(E:1, F:0)
11 State2(E:0, F:1) State1(E:0, F:0)
15 Undefined(E:1, F:1) D.C.
4 State0(E:1, F:0) DEQ$ \cap $ENQ ERROR
8 State1(E:0, F:0) State1(E:0, F:0)
12 State2(E:0, F:1) State2(E:0, F:1)
16 Undefined(E:1, F:1) D.C.
D.C.=Don't care

ERRORの場合もステートはD.C.とし、別にエラー信号を出力するものとします。従ってD.C.を活用してステートを決定すれば、ステートはemptyとfullの組み合わせで表現できるため、

  • CLRのとき、empty = 1, full = 0
  • !DEQ && ENQのとき(2, 6)、empty = 0, full = !emtpy
  • DEQ && !ENQのとき(7, 11)、empty = !full, full = 0
  • 上記以外のときはホールド。emtpy, full共変化無し。

左矢前のブログ 次のブログ右矢

posted by sakurai on December 12, 2022 #568

2段FIFOの検討(2)

今までENQとDEQを別々に検討しましたが、次にENQとDEQが同時にアサートされる場合を考えます。 ここで思い出すのが図562.1であり、あるサイクルにおいてENQとDEQが同時とは、サイクルの最初でDEQを行い、サイクルの最後でENQを行うということであり、DEQ⇒ENQの順序が重要です。従って、1サイクル中にENQを行ったデータをDEQすることはできません。これができるのはBypassFIFOという特殊なFIFOを用いた時に限られるようです。

この原則を守れば、State0ではENQ/DEQの同時実行を考える必要は無くなります。State0でまずDEQをするのでエラーとなるからです。

図%%.1
図568.1 State0でENQ$\cap$DEQの時の動作

次にState1ではまずDEQを実行し、d0のデータを外に移します。本来はd0は無効化されますが、続いて外からENQされるので有効のままです。最終的にState1にとどまります。

図%%.2
図568.2 State1でENQ$\cap$DEQの時の動作

最後にState2ではまずDEQを実行し、d0のデータを外に移します。同時にd1のデータをd0に移します。同様にd0は無効化されず、続いて外からENQされるので有効のままです。最終的にState2にとどまります。

図%%.3
図568.3 State2でENQ$\cap$DEQの時の動作

左矢前のブログ 次のブログ右矢

posted by sakurai on December 9, 2022 #567

2段FIFOの検討

BSVのデフォルトである2段FIFOの動作を、新規設計するつもりで一から検討します。

2段FIFOなのでレジスタを2段持ち、それぞれd0とd1と名前を付けます。ライブラリと同様にd0からFIFO出力を固定的に出力するものとします。

図%-%.1
図567.1 2段FIFOの動作
図567.1の説明を以下に示します。
  • 2段FIFOのFIFOの有効段の数は0個、1個、2個なので、その数をステートと扱えば、サブシステムのステートにはState0~State2の3種類があることになります。
  • 一度に2個をキューに入れることはできないので、エンキュー(以下ENQ)の場合は、State0⇒State1⇒State2のように遷移します。
  • 逆にデキュー(以下DEQ)の場合はState2⇒State1⇒State0のように遷移します。
  • State0のときにDEQ、State2のときにENQが起きるとエラーとなります(赤色で表現)。
  • DEQの場合に後段へデータを出力しますが、必ずd0から出力するように制御します。そのため、ENQの際にはステートにより格納する段が変わります。
  • 具体的にはState0のときにENQであればd0に格納
  • State1のときにENQであればd1に格納
  • State2のときにENQであればエラー(前述)、DEQであればd0を外に移してd1をd0に移し、d1を無効化
  • State1のときにDEQであればd0を外に移してd0を無効化
  • 上記無効化のフラグビットは不要です。ステート遷移先はステートと遷移条件で決まり、ステートにより有効段はあらかじめ確定しているためです。具体的にはState0は有効段無し、State1は有効段はd0のみ、State2は有効段はd0とd1と定まっています。

左矢前のブログ 次のブログ右矢

posted by sakurai on December 8, 2022 #566

1段FIFOのシミュレーション

本来はFIFOは1段で良いはずですが、なぜ2段となっているのでしょうか?ここだけ見ると物量が倍になってしまいます。たいした物量ではないものの、1段で済ませないかを検討します。

前述のように、bscが出力するシミュレーションモデルではFIFO2という2段FIFOを使用しています。このモデルを1段FIFOに入れ替えたいのですが、bsimモデルは触ることができないので、verilogモデルのほうを修正します。上位において次のようにFIFO2を呼び出しているところをテキストエディタでFIFO1に修正します。

// submodule exs
FIFO2 #(.width(32'd32), .guarded(32'd1)) exs(.RST(RST_N),
                                             .CLK(CLK),
                                             .D_IN(exs$D_IN),
                                             .ENQ(exs$ENQ),
                                             .DEQ(exs$DEQ),
                                             .CLR(exs$CLR),
                                             .D_OUT(exs$D_OUT),
                                             .FULL_N(exs$FULL_N),
                                             .EMPTY_N(exs$EMPTY_N));

次にverilogシミュレーションを行うと、以下のような波形が得られます。

図%%.1
図566.1 PCパイプラインタイムチャート

1ステージのレイテンシが2サイクルとなってしまいます。

これは、emtpyやfullは1サイクルおきにアサートされ、そのため2サイクルに1度しかキューに投入できないためです。従ってスループットが半分、レイテンシが倍になってしまいます。FIFOの動作上、空でないと上位からは詰められず、一方で詰まってないと下位からは引き取れないので、交互動作になるのは当然です。

通常のパイプラインはエンキューとデキューが同時に行えるので、これは改善できるかもしれません。


左矢前のブログ 次のブログ右矢

posted by sakurai on December 7, 2022 #565

verilogシミュレーション

verilogのソースを覗いてみると、FIFO2というモジュールがインスタンスされていました。ソースの一部を示します。

// submodule ifs
FIFO2 #(.width(32'd32), .guarded(32'd1)) ifs(.RST(RST_N),
                                       .CLK(CLK),
                                        .D_IN(ifs$D_IN),
                                        .ENQ(ifs$ENQ),
                                        .DEQ(ifs$DEQ),
                                        .CLR(ifs$CLR),
                                        .D_OUT(ifs$D_OUT),
                                        .FULL_N(ifs$FULL_N),
                                        .EMPTY_N(ifs$EMPTY_N));

ライブラリ中のFIFO2($BLUESPECDIR/Verilog/FIFO2.v)のソースを見ると、中心部分は以下のようになっており、レジスタ2段によるFIFOです。

  data0_reg  <= `BSV_ASSIGNMENT_DELAY
                {width{d0di}} & D_IN | {width{d0d1}} & data1_reg | {width{d0h}} & data0_reg ;
  data1_reg <= `BSV_ASSIGNMENT_DELAY
               d1di ? D_IN : data1_reg ;

ただし、FIFOなので、2段とはいってもレイテンシが必ず2サイクルになるわけではありません。First-In, First-Outなので、1段目に入れたものをデキューしようとすると、そのまま1段目から供給するロジックとなっています。上記のように、data0は入力か、1段目か、0段目の選択となっており、data1が入力か1段目の選択となっています。

assign                 D_OUT = data0_reg ;

であることから、data0が出力側レジスタであることがわかります。一方、data1がD_INを入力とする場合は、d1diという信号がTrueの時であり、その論理は、

wire                   d1di = ENQ & empty_reg ;

となっています。これはFIFOがemtpy(負論理なので)でなく、かつENQされたときというように読めますが、後で条件を調査します。


左矢前のブログ 次のブログ右矢

posted by sakurai on December 6, 2022 #564

verilogシミュレーション

ついでにverilogでもシミュレーションしてみます。

$ bsc -verilog Tb.bsv
Verilog file created: mkTb.v
$ iverilog top.v mkTb.v -y /usr/local/lib/Bluespec/Verilog/ -o mkTb.exev
$ ./mkTb.exev
VCD info: dumpfile verilog.vcd opened for output.
------
------
 pc_if = 00000000
------
 pc_if = 00000004
 pc_id = 00000000
------
 pc_if = 00000008
 pc_id = 00000004
 pc_ex = 00000000
------
 pc_if = 0000000c
 pc_id = 00000008
 pc_ex = 00000004
 pc_ma = 00000000
------
 pc_if = 00000010
 pc_id = 0000000c
 pc_ex = 00000008
 pc_ma = 00000004
 pc_wb = 00000000
------
 pc_if = 00000014
 pc_id = 00000010
 pc_ex = 0000000c
 pc_ma = 00000008
 pc_wb = 00000004

のように正しくパイプラインが動作しました。また、gtkwaveで取得したタイムチャートを図564.1に示します。

gtkwファイルはここ

図%-%.1
図564.1 PCパイプラインタイムチャート

左矢前のブログ 次のブログ右矢


ページ: