Posts Tagged with "BSV"

既に発行済みのブログであっても適宜修正・追加することがあります。
We may make changes and additions to blogs already published.
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はデキューしても元の値を保持するのが仕様のようです。


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

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共変化無し。

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


ページ: