Posts Tagged with "FIFO"

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

さらに前稿でインスタンスされるパイプラインFIFOであるFIFOL1のverilogライブラリのコードを見てみます。

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

パイプラインFIFOは1段のF/Fなので、基本的にFULLとEMPTYは内部レジスタempty_regの背反ロジックとなりますが、例外的に下流からのDEQ要求がある場合は、仮にFULLであったとしても次のサイクルでFULLが解消されるため、DEQとのORをとり、not full(上位へのenq enable)とします。

    always@(posedge CLK `BSV_ARESET_EDGE_META)
      begin
         if (RST == `BSV_RESET_VALUE)
            begin
              empty_reg <= `BSV_ASSIGNMENT_DELAY 1'b0;
            end
         else
            begin
               if (CLR)
                 begin
                    empty_reg <= `BSV_ASSIGNMENT_DELAY 1'b0;
                 end
               else if (ENQ)
                 begin
                    empty_reg <= `BSV_ASSIGNMENT_DELAY 1'b1;
                 end
               else if (DEQ)
                 begin
                    empty_reg <= `BSV_ASSIGNMENT_DELAY 1'b0;
                  end // if (DEQ)
            end // else: !if(RST == `BSV_RESET_VALUE)
     end // always@ (posedge CLK or `BSV_RESET_EDGE RST)

empty_regはnot emptyを表す内部レジスタであり、ENQするとTrue(=1, not empty)となり、DEQするとFalse(=0, empty)となります。not fullは上位へのenq enable信号であり、not emptyは下位へのdeq enable信号です。当初なぜemptyもfullも負論理なのかと思いましたが、(正論理の)イネーブルの意味がありました。

    always@(posedge CLK `BSV_ARESET_EDGE_HEAD)
      begin
           begin
               if (ENQ)
                 D_OUT     <= `BSV_ASSIGNMENT_DELAY D_IN;
            end // else: !if(RST == `BSV_RESET_VALUE)
      end // always@ (posedge CLK or `BSV_RESET_EDGE RST)

ENQはF/F入力の値を出力に移します。一方DEQはF/Fは何も変化させません。

これまで見たように、bscにより生成された回路を解析することは、論理設計能力の向上の一助となります。


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

posted by sakurai on October 9, 2023 #674

Maybeを使用した制御パイプラインをbscで合成し、生成されたverilogコードの一部を示します。

      // submodule ifs
      assign ifs$D_IN = { 1'd1, pc } ;
      assign ifs$ENQ = ifs$FULL_N ;
      assign ifs$DEQ = WILL_FIRE_RL_if_stage && !if_wait ;
      assign ifs$CLR = 1'b0 ;

      // rule RL_if_stage
      assign WILL_FIRE_RL_if_stage = ids$FULL_N && ifs$EMPTY_N ;

      // submodule ids
      assign ids$D_IN = { !if_wait && ifs$D_OUT[32], ifs$D_OUT[31:0] } ;
      assign ids$ENQ = WILL_FIRE_RL_if_stage ;
      assign ids$DEQ = WILL_FIRE_RL_id_stage  && !mc_wait ;
      assign ids$CLR = 1'b0 ;

      // rule RL_id_stage
      assign WILL_FIRE_RL_id_stage = exs$FULL_N && ids$EMPTY_N ;

図674.2はこのコードを回路図に変換したものです。ハードウエア設計者はHDLコードよりもstaticな回路図のほうが理解し易いです。

図%%.1
図674.1 制御パイプライン構造

各ステージ中のwait信号で上流方向は止めますが(中段左側のAND)、下流方向は止めずに(下段のAND)さらに下流にinvalidを流す(上段のAND)ところが、より単純な図673.1のデータパイプラインとの違いです。


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

posted by sakurai on October 6, 2023 #673

前回まではパイプラインのうち<IF>にwaitを入力しましたが、基本的に<WB>以外のステージにwaitが入る可能性があります。

表673.1 制御パイプラインウエイト制御
ステージ ウエイト信号 ウエイト原因 パイプライン処理
<PC> pc_wait PCの到着が遅れる場合。例えば分岐キャッシュから出力されるPCが遅れる場合。 上流へは同一サイクルでの停止とし、下流へはパイプラインバブルを流す。
<IF> if_wait 命令メモリから出力される命令データの到着が遅れる場合。例えばIキャッシュミスによるブロックインの場合。仮想記憶サポートの場合は、I-TLBミスによるページテーブルウォーク。 上流へは同一サイクルでの停止とし、下流へはパイプラインバブルを流す。
<ID> mc_wait 命令デコーダは1サイクル内で実行できるため、後続を待たせる必要が無いのでid_waitは無し。マルチサイクル命令の場合は内部的にパイプラインストリームを生成する処理。 上流へは同一サイクルでの停止とし、下流へはvalidな命令を内部的に複数生成し、パイプラインで流す。マルチサイクル(かつ複数パイプラインストリーム)動作なのでパイプラインバブルは流さない。
<EX> ex_wait 演算器から出力されるデータの到着が遅れる場合。複数サイクル演算が必要な例えば4サイクル乗算器のような演算。 上流へは同一サイクルでの停止とし、下流へはパイプラインバブルを流す。
<MA> ma_wait データメモリから出力されるデータデータの到着が遅れる場合。例えばDキャッシュミスによるブロックインの場合。仮想記憶サポートの場合は、D-TLBミスによるページテーブルウォーク。 上流へは同一サイクルでの停止とし、下流へはパイプラインバブルを流す。
<WB> --- WBは1サイクル内で実行でき、後続が無いのでwb_waitは無し。 ---

図673.1に各種wait信号を入力したデータパイプライン構造を示します。過去記事で調べた回路にwaitが追加されています。

図%%.1
図673.1 データパイプライン構造

図では信号名を3文字に短縮していますが、$\overline{\text{emp}}$は$\overline{\text{empty}}$の略でdeqのenable信号、$\overline{\text{ful}}$は$\overline{\text{full}}$の略で、enqのenable信号です。


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

posted by sakurai on October 5, 2023 #672

今回設計したFIFOは2段FIFOでした。従って、1つ前の記事のようにif_waitを2サイクルにすると、図672.1で示すとおり0034, 0038とPCが先に進みます。

図%%.1
図672.1 2wait入り2段PCパイプラインの波形

このようにパイプラインが次に進んでしまうということは、演算器等も2段分必要になります。従ってFIFOを1段に修正します。具体的にはmkFIFOmkLFIFOに変更します。

以下に修正箇所を示します。

Processor.bsv

FIFO#(int) ifs    <- mkLFIFO;
FIFO#(int) ids    <- mkLFIFO;
FIFO#(int) exs    <- mkLFIFO;
FIFO#(int) mas    <- mkLFIFO;
FIFO#(int) wbs    <- mkLFIFO;

以下はbsimシミュレーション波形です。図672.1ではif_waitによりPCが止まらずwait中に0038までも進んでしまいましたが、1段FIFO(パイプラインFIFO)に変更することで、if_waitが0030で入力されるとPCはその次のアドレスである0034で正しく止まっています。

図%%.2
図672.2 wait入り1段PCパイプラインの波形

図672.1, 図672.2共、Gtkwaveではtagのinvalidを自動認識しないため、パイプラインバブルのサイクルを手で赤で塗っています。


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

posted by sakurai on September 29, 2023 #671

パイプライン動作において、そのサイクルが有効か無効かは重要な情報です。無効サイクルはパイプラインバブルとも呼ばれます。

そこで、本来PCパイプラインには不要ですが、制御信号パイプラインに必要な、Maybe型を用いてパイプラインを記述します。Maybe型は以下に示すようにtagged unionで定義され、validの場合には値を持ちinvalidの場合には値を持たない型です。

typedef union tagged {
    void Invalid;
    data_t Valid;
} Maybe #(type data_t) deriving (Eq, Bits);

以下に修正箇所を示します。

Processor.bsv

int型のFIFOを設けていたところをMaybe型のFIFOに修正します。int型のペイロードに対して1bitのvalid/invalidを表すtagを付加します。

FIFO#(Maybe#(int)) ifs    <- mkFIFO;
FIFO#(Maybe#(int)) ids    <- mkFIFO;
FIFO#(Maybe#(int)) exs    <- mkFIFO;
FIFO#(Maybe#(int)) mas    <- mkFIFO;
FIFO#(Maybe#(int)) wbs    <- mkFIFO;

次に<IF>においてwaitが来たら上位のdeqと下位のenqを停止していましたが、制御信号の場合はwaitの時、下流にinvalidを流すように変更します。このinvalidはパイプラインバブルです。

 // <IF>
 rule if_stage;
    let pc_if = ifs.first;
    if (!if_wait) begin
       ifs.deq;                             // !waitの場合はデキュー
       $display (" pc_if = %04h", pc_if);
       ids.enq (pc_if);                 // !waitの場合はその値を下流にエンキュー
    end else begin
       ids.enq (tagged Invalid); // waitの場合下流にinvalidを流す
    end
 endrule

コンパイルと起動コマンドは以下のとおりです。

$ bsc -u -sim Tb.bsv; bsc -sim -e mkTb -o mkTb.exe;
$ ./mkTb.exe -V;
$ gtkwave -A dump.vcd

以下はbsimシミュレーション波形です。Maybe型は33bitのデータでありMSBがvalid bitとなっています。 標準ではGtkwaveはMaybeのinvalidを認識せず赤色にならないため、手で赤色に修正しました。

図%%.1
図671.1 wait入りPCパイプラインの波形

以下はverilogシミュレーション波形です。verilogでも同様です。

図%%.2
図671.2 wait入りPCパイプラインの波形

bsimとverilogで全く同じ動作となっています。まとめとして、ステージ中にwaitが入る場合の処理は、

  • 上位へはdeqをサイクル中で停止、するとFIFOがfullでとまる。ただしFIFOは1段。
  • 下流へはデータパイプラインの場合はvalid bitは不要であり、値を保持
  • 下流へは制御パイプラインの場合はinvalid(パイプラインバブル)を流す

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

posted by sakurai on September 27, 2023 #669

次にパイプラインウェイトをテストします。具体的にはテストベンチにのwait信号を設け、途中でアサートします。

Tb.bsv

Tbにはその記述を追加します。

import StmtFSM::*;
import Processor::*;

(* synthesize *)
module mkTb();
    Empty proc <- mkProcessor();
    Stmt main = seq
         proc.if_wait_load(False);
         delay(10);
         proc.if_wait_load(True);
         delay(1);        // ここでif_waitを2サイクルアサート
         proc.if_wait_load(False);
         delay(10);
         $finish;
    endseq;
    mkAutoFSM(main);
endmodule

if_wait信号を1サイクルアサートをさせようとしてdelay(1);を挟みましたが、その前のload(True);により1サイクルアサートされるようです。そのため、1サイクルアサートさせるには以下の表のように、何も挟まないかdelay(0);と記述するようです。

表669.1 BSV構文とwaitアサート期間
BSV構文 waitアサート期間
proc.if_wait_load(True);
proc.if_wait_load(False);
1サイクル
proc.if_wait_load(True);
delay(0);
proc.if_wait_load(False);
1サイクル
proc.if_wait_load(True);
repeat(0) noAction;
proc.if_wait_load(False);
1サイクル
proc.if_wait_load(True);
noAction;
proc.if_wait_load(False);
2サイクル
proc.if_wait_load(True);
delay(1);
proc.if_wait_load(False);
2サイクル
proc.if_wait_load(True);
repeat(1) noAction;
proc.if_wait_load(False);
2サイクル

Processor.bsv

PCパイプラインにインタフェースを設け、そこにif_wait入力を設けます。

Import FIFO::*;

interface Processor_ifc;
    (* prefix="" *)
    method Action if_wait_load(Bool in_if_wait);
endinterface

(* synthesize, always_ready *)
module mkProcessor(Processor_ifc);

if_waitはレジスタで宣言します。

Reg#(Bool) if_wait <- mkReg(False);

<IF>において、waitが来たら上位のdeqと下位のenqを停止します。

 // <IF>
 rule if_stage;
     let pc_if = ifs.first;
     if (!if_wait) begin
         ifs.deq;
         $display (" pc_if = %04h", pc_if);
         ids.enq (pc_if);
     end
 endrule

コンパイルと起動コマンドは以下のとおりです。gtkwaveはここ

$ bsc -u -sim Tb.bsv; bsc -sim -e mkTb -o mkTb.exe;
$ ./mkTb.exe -V;
$ gtkwave -A dump.vcd

以下はbsimシミュレーション波形です。if_waitを1サイクルアサートしようとして、delay(1);とすると2サイクルアサートされるので、1サイクルアサートするにはdelay(0);とするようです。

if_waitにより一旦はinvalidになりますが、そのデータを転送するとvalidになってしまうようです。

図%%.1
図669.1 wait入りPCパイプラインの波形(bsim)

以下はverilogシミュレーション波形です。if_waitによりinvalidになることはありません。

図%%.2
図669.2 wait入りPCパイプラインの波形(verilog)

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

posted by sakurai on September 26, 2023 #668

過去記事で設計したPCパイプラインをモジュールに変更し、その上にテストベンチをかぶせます。以下にテストベンチTb.bsv及びPCパイプラインProcessor.bsvのソースを示します。

Tb.bsv

import StmtFSM::*;
import Processor::*;

(* synthesize *)
module mkTb();
    Empty proc <- mkProcessor();
    Stmt main = seq
        delay(30);
        $finish;
    endseq;
    mkAutoFSM(main);
endmodule

Processor.bsv

import FIFO::*;

(* synthesize, always_ready *)
module mkProcessor(Empty);

    Reg#(int)  pc     <- mkReg(0);
    FIFO#(int) ifs    <- mkFIFO;
    FIFO#(int) ids    <- mkFIFO;
    FIFO#(int) exs    <- mkFIFO;
    FIFO#(int) mas    <- mkFIFO;
    FIFO#(int) wbs    <- mkFIFO;

     // <PC>
     rule pc_stage;
        if (pc > 100) $finish(0);
        $display("------");
        ifs.enq(pc);
        pc <= pc + 4;
     endrule

     // <IF>
     rule if_stage;
        let pc_if = ifs.first;
        ifs.deq;
        $display (" pc_if = %04h", pc_if);
        ids.enq (pc_if);
     endrule

     // <ID>
     rule id_stage;
        let pc_id = ids.first;
        ids.deq;
        $display (" pc_id = %04h", pc_id);
        exs.enq (pc_id);
     endrule

     // <EX>
     rule ex_stage;
        let pc_ex = exs.first;
        exs.deq;
        $display (" pc_ex = %04h", pc_ex);
        mas.enq (pc_ex);
     endrule

     // <MA>
     rule ma_stage;
        let pc_ma = mas.first;
        mas.deq;
        $display (" pc_ma = %04h", pc_ma);
        wbs.enq (pc_ma);
     endrule

     // <WB>
     rule wb_stage;
        let pc_wb = wbs.first;
        wbs.deq;
        $display (" pc_wb = %04h", pc_wb);
     endrule

endmodule: mkProcesso

コンパイルと起動コマンドは以下のとおりです。gtkwaveはここ

$ bsc -u -sim Tb.bsv; bsc -sim -e mkTb -o mkTb.exe;
$ ./mkTb.exe -V;
$ gtkwave -A dump.vcd

図%%.1
図668.1 PCパイプラインの波形

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

posted by sakurai on December 23, 2022 #576

制御パイプライン

1段FIFOのDEQ修正ではうまく行かないと勘違いして2段FIFOを検討してきましたが、記事で述べたように、LFIFOというパイプライン動作するFIFOと論理が同じであり、それを使用することで正常動作することが判明しました。

さてPC等のデータパイプラインの設計が確定したところで、制御パイプラインを設計します。どこが異なるかと言うと、データパイプラインにはvalid bitが無いのに対して、制御パイプラインにはvalid bitが存在することです。さらにvalid bitの制御は、ウエイトするステージの上流ステージはパイプラインを止める制御行いvalid bitは変更しませんが、下流ステージに対してはinvalidを流す必要があることです。こうしないとウエイトで加算命令が止まっている場合に、加算器がウエイトの回数だけ加算し続けるという現象が起きます。これを防止するために、ウエイト時は下流にinvalidを「流し」ます。$\dagger$

BSVはデータおよびその有効性を示すビット(valid bit)の組をMayBeという「曖昧な用語」できちんと定義します。MayBeな制御データに対して有効か無効かを判定するにはisValid()メソッドを使用します。またMayBeが有効である場合に制御データを取り出す場合はfromMayBe()メソッドを使用します。

これを具体的なタイムチャートで示します。

図%%.1
図576.1 パイプラインシミュレーション

その後、full/emptyの動作がverilogと不一致となる等おかしかったので、Bluespecに報告したところ、LFIFOは古いので、PipelinedFIFOを使用するように勧められました。


$\dagger$:パイプライン用語で、(パイプラインに沿って)「流す」という用語は、下流に向かっては次のステージは次のサイクル先頭でラッチし、その次のステージは、その次のサイクル先頭でラッチすることを意味します。下流に向かってはクロックは停止せず、valid bitで制御します。一方で上流に向かっては「同一サイクルで止める」という言い方をします。この場合はクロックを停止するかサイクルを再実行することになります。上流へと下流へでは制御のやり方が変わってくるわけです。


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

posted by sakurai on December 21, 2022 #575

2段FIFOの修正

前記事で記載したようなウエイト制御を行えば、実質的に2段FIFOのd1は使用することはないはずです。従ってFIFO2.vからd1の本体及び関連制御信号を削除してしまいます。これによりウエイトシミュレーションを実施しましたが、結果は同様でした。これで実質FIFO1を設計することができました。

違いは、元のFIFO1ではempty=!fullというロジックだったものが、新FIFO1ではemptyとfullが3状態を取るようになったことです。しかし、1段しか無いということは永久にfullにはならないということなので、元のFIFO1でfullをFalse固定としても動作しそうです。

早速元のFIFO1を修正してシミュレーションしてみました。

図%%.1
図575.1 パイプラインシミュレーション

同じく、読み取りにくいので表にしてみます。

表575.1 PCアドレス表
ステージ 0 1 2 3 4 5 6
PC 006c 0070 0070 0070 0074 0078 007c
IF 0068 006c 006c 006c 0070 0074 0078
ID 0064 0068 0068 0068 006c 0070 0074
EX 0060 0064 0064 0064 0068 006c 0070
MA 005c 0060 0064 0064 0064 0068 006c
WB 0058 005c 0060 0064 0064 0064 0068

オリジナルFIFO2と全く同じ結果となりました。


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

posted by sakurai on December 20, 2022 #574

2段FIFOの修正

さらにFIFO2に変えて各ステージにウエイトを入れる修正を行いました。<WB>だけはウエイト要因が無いためウエイト信号はありません。他のステージでも検討の結果無くなる可能性はあります。

  • <PC>: pc_wait
  • <IF>: if_wait
  • <ID>: id_wait
  • <EX>: ex_wait
  • <MA>: ma_wait

これをシミュレーションした結果、あるステージでウエイトがかかると当然そのステージの上位からENQできなくなるはずですが、FIFOが2段のため、もう1個は受け付けるようになります。これは制御が複雑になるものの性能は向上しないので過去記事で検討したように、あるステージからは上位にウエイトを上げるような接続にします。それぞれのステージ固有のウエイト信号です。

  • <PC>: pc_wait
  • <IF>: if_wait
  • <ID>: id_wait
  • <EX>: ex_wait
  • <MA>: ma_wait

これらを下記のように上位へ伝える結線を行います。

     let mas_wait = ma_wait;
     let exs_wait = ex_wait || mas_wait;
     let ids_wait = id_wait || exs_wait;
     let ifs_wait = if_wait || ids_wait;
     let pcs_wait = pc_wait || ifs_wait;

これによりBluespec謹製FIFO2.vと修正版FIFO2.vでシミュレーションを実行しました。これは<ID>にウエイトが2サイクル入った場合のタイミングですが、微妙な差が出ています。まずBluespec謹製版です。

図%%.1
図574.1 パイプラインシミュレーション

次に弊社での修正版です。

図%%.2
図574.2 パイプラインシミュレーション

読み取りにくいので、表にしてみます。まずBluespec版です。<ID>の2, 3サイクル目に2サイクルのid_wait信号がアサートされた場合です。直接アサートされたサイクルをライトグリーンで、それが同一サイクル内で上流に伝わったステージをライトブルーで塗っています。

表574.1 PCアドレス表
ステージ 0 1 2 3 4 5 6
PC 006c 0070 0070 0070 0074 0078 007c
IF 0068 006c 006c 006c 0070 0074 0078
ID 0064 0068 0068 0068 006c 0070 0074
EX 0060 0064 0064 0064 0068 006c 0070
MA 005c 0060 0064 0064 0064 0068 006c
WB 0058 005c 0060 0064 0064 0064 0068

次に弊社版です。表574.1と相違する部分をライトグレーで塗りました。

表574.2 PCアドレス表
ステージ 0 1 2 3 4 5 6
PC 006c 0070 0070 0070 0074 0078 007c
IF 0068 006c 006c 006c 0070 0074 0078
ID 0064 0068 0068 0068 006c 0070 0074
EX 0060 0064 0068 0000 0068 006c 0070
MA 005c 0060 0064 0068 0000 0068 006c
WB 0058 005c 0060 0064 0068 0000 0068

これで見るとわかるように、ウエイトが入った場合に下流のPC値が相違しています。

本来、パイプラインストールで停止したステージの下流のステージはいわゆるパイプラインバブルとなり、PC値は保証されないはずです。別に設ける予定のバリッドビットが値の妥当性を決めるため、PC値は不定で良いはずです。

パイプラインステージの再実行かと言えば、例えば64番地の命令は繰り返す必要は有りませんし、繰り返してはいけません。例えば64番地の<EX>がデータインクリメント(+1)だった場合には3回の再実行により+3を加算することになり、明らかに誤りです。再実行されるのは、パイプラインウェイトが入ったステージとその上流である68番地以降の再実行となります。

プロセッサではウエイトが入った場合は結果が保証されないのですが、シストリックアレイのような応用ではデキューされた後の状態が同じ状態であって欲しいのかもしれません。そうなると、1, 3, 4, 7も保持(d0)する必要があるかもしれません。試しにd0hに1, 3, 4, 7のケースを加え、反対にd0diに3, 7を加えていたものを引けば、Bluespecと一致する論理となりました。

結論としては推測となりますが、BluespecのFIFO2はデキューしても元の値を保持するのが仕様のようです。


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


ページ: