Posts Tagged with "pipeline processor"

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

再度テストベンチ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はデキューしても元の値を保持するのが仕様のようです。


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

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 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 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パイプラインタイムチャート


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

posted by sakurai on December 5, 2022 #563

bsimシミュレーション

このソースに対して、以下のようにコンパイル、bsimシミュレーションを実行します。太字が入力部分です。

$ bsc -sim Tb.bsv; bsc -sim -e mkTb -o mkTb.exe
Elaborated module file created: mkTb.ba
Bluesim object created: mkTb.{h,o}
Bluesim object created: model_mkTb.{h,o}
Simulation shared library created: mkTb.exe.so
Simulation executable created: mkTb.exe
$ ./mkTb.exe -V
------
------
pc_if = 0000
------
pc_if = 0004
pc_id = 0000
------
pc_if = 0008
pc_id = 0004
pc_ex = 0000
------
pc_if = 000c
pc_id = 0008
pc_ex = 0004
pc_ma = 0000
------
pc_if = 0010
pc_id = 000c
pc_ex = 0008
pc_ma = 0004
pc_wb = 0000
------
pc_if = 0014
pc_id = 0010
pc_ex = 000c
pc_ma = 0008
pc_wb = 0004

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

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


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

posted by sakurai on December 3, 2022 #562

BSVのFIFO調査

BSVにおいて、パイプラインレジスタとしてFIFOを使用できるか調査します。まず、PCパイプラインを設計します。PCパイプラインとは、各ステージのPCを保持することで、例えば各ステージにおいてEIT(例外、割り込み、トラップ)が起きた場合、EITが起こった命令アドレスをハンドラに正しく伝えるためのものです。

Tb.bsv

  import FIFO::*;

  (* synthesize *)
  module mkTb (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: mkTb

ここで、<PC>は入力レジスタは無いため、ここではFIFOは使用しません(が、後で検討します)。単にPCレジスタを設置するだけです。これは<PC>(PCステージ)のPCということになります。通常はPC<=PC+4ですが、分岐時等ではオフセットが足されます。

各ステージでは、入力されたPCをデキューし、表示し、サイクルの終わりで次のステージにそのPCをエンキューします。

図%-%.1
図562.1 FIFOのDequeuとEnqueueの関係

従って、同一サイクルでエンキューしたものをデキューする(バイパス、パススルー)ことはできません。

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

posted by sakurai on October 28, 2022 #541

<PC>の必要性

従来例を再掲します。作成しようとするパイプラインロジックは大略、前の図540.1のとおりです。ただし図540.1では<PC>が明示されていません。

図%-%.1
図540.1 あるRISC-Vプロセッサのパイプライン図(再掲)

次の命令ストリームの起点であるPCは、基本的に

  1. 分岐が無ければ(有っても投機的に数命令は実行)、現PC+4
  2. PC相対分岐が有ればPC+オフセット
  3. 絶対分岐の場合はその値

を次のPCにセットします。この他にも割り込み、例外処理等で新PCを演算し、次のPCにセットします。これを<PC>を意識した図に書き直すと、図541.1のように判りやすい図となります。図540.1のように、PC演算器やレジスタが窮屈に<IF>の中に折れ曲がることは無く、ストレートフォワードに描かれています。<PC>の入力が<PC>であることも図541.1を見れば明らかです。

図%%.1
図541.1 <PC>の考え方に基づき書き直したパイプライン図

図541.1では分岐の場合は<EX>の結果レジスタがPCであることから元の<EX>と分岐先<PC>が重なり、その次のステージが分岐先<IF>となることが良くわかります。クロックベースが原則のパイプラインを記号で書けば、

   <PC><IF><ID><EX><WB>
          <PC><IF><ID><EX><WB>

となります。分岐先のPC計算を分岐元のEXで代行している様子が良く分かります。

一方、図540.1では<EX>の後にPCレジスタが入り、その次に<IF>ステージとなるので、記号で書くと、

   <IF><ID><EX><WB>
          <IF><ID><EX><WB>

となり、<IF>が湧き出す意味が不明です。<IF>の入力レジスタがPCで、分岐命令の<EX>でそれを生成しているのだからという説明になると思いますが、であればPCを明示したほうが分かりやすいのは言うまでもありません。

逆にPCの生成も含めたパイプラインを理解してしまえば頭の中でできるため、取り立てて<PC>の必要性は感じなくなるので、不思議とも思わないようになりますが、教育的とは言えません。そもそも最も重要なPCの更新ステージはどこなのかが図示されていません。これでは分岐命令の高速化、例えばBTB等による<PC>の物量増加も、どのステージの話なのか理解しづらくなります。

<PC>の制御法

<PC>の必要性が理解できたところで、過去記事でパイプライン制御論理を示しました。<PC>の上流が<PC>だからといって上流に出力するwait信号を自分自身に入れると永久にストールするので、自分自身に入れてはいけません。

また、図示されていませんが、PCレジスタ自体も同じパイプライン制御論理によりパイプラインを流します。その理由は、例外の際には分岐が発生しますが、戻りアドレスをスタックに格納します。その戻りアドレスを上記PCパイプラインから適宜取得するためです。


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


ページ: