単一クロック FIFO のポインタと境界条件の方針

データを移動せずに順序を守る

FIFO^{iFIFO 先に入れたデータを先に取り出すキューです。満杯・空・同時読出しと書込みの許可規則も動作の取り決めに含まれます。} は先に入れたデータを先に取り出す。単一クロックでは、読み出しと書き込みを同じ立ち上がりエッジで決定する。この講義では DEPTH=4、データ幅 8 ビットに固定する。rptr は次に取り出す位置、wptr は次に入れる位置を指す。それぞれ 2 ビットなので、3 の次は自然に 0 へ戻る。occupancy は格納数 0～4 を表す必要があるため、3 ビットを要する。

rptr=wptr は empty でも full でも起こり得る。そのため、アドレスの一致だけで empty を決めると、満杯のデータを失ってしまう。ここでは個数 $C$ を別に管理し、$\mathrm{empty}=(C=0)$、$\mathrm{full}=(C=4)$ で区別する。深さ $D=4$ のとき、アドレス幅 $W_{\mathrm{addr}}$ と個数幅 $W_{\mathrm{count}}$ は次のとおりである。

要求と受け付けを区別する境界条件

push と pop は要求である。p と q をそれぞれ実際の push・pop の受け付けとすると、reset でないエッジの直前状態から次のように計算する。

empty で両方の要求が来ても、pop できる既存データがないため push だけを受け付ける。新しいデータがそのエッジで直ちに出力されるわけではない。full で両方の要求が来ると、以前の先頭を取り出して場所を空けられるため両方を受け付ける。full は「現在 4 個格納されている」という状態であり、この方針では無条件の push 禁止信号ではない。

クロックを進めて境界条件を確認する

最初は push と pop を同時に要求してみよう。空なので push だけが受け付けられるはずである。次は pop を無効にして 4 スロットを満たし、新しい入力値とともに両要求を再び有効にする。占有数は 4 のまま、出力には以前の先頭、記憶領域には新しい末尾が残るはずである。

図は各立ち上がりエッジ^{i立上りエッジ クロックが 0 から 1 に変わる瞬間です。CLK=1 の区間全体を指すレベルとは区別します。 詳しく見る}直後の状態を示す教育用モデルである。pop が受け付けられると output valid が 1 になる。次のエッジで pop が受け付けられなければ、出力レジスタ^{iレジスタ 複数ビットの状態を記憶する回路です。このコースの同期式レジスタは、クロックエッジで定められた入力を記憶します。 詳しく見る}の値は保持されるが valid は 0 になる。空のスロットに残る古いビットは表示しない。「最初から」は実習全体を初期化する機能であり、RTL のメモリリセット^{iリセット 状態を仕様で定めた初期値に戻す制御です。同期式か非同期式か、他の制御より優先されるかを合わせて定めます。 詳しく見る}動作を表してはいない。

レジスタ付き出力まで含めた RTL

module fifo4 (
  input  logic       clk, rst, push, pop,
  input  logic [7:0] din,
  output logic [7:0] dout,
  output logic       dout_valid, full, empty,
  output logic [2:0] occupancy
);
  timeunit 1ns;
  timeprecision 1ps;
  logic [7:0] mem [0:3];
  logic [1:0] rptr, wptr;
  logic take_push, take_pop;

  assign empty = (occupancy == 3'd0);
  assign full  = (occupancy == 3'd4);
  assign take_pop  = !rst && pop && !empty;
  assign take_push = !rst && push && (!full || take_pop);

  always_ff @(posedge clk) begin
    if (rst) begin
      rptr <= 2'd0;
      wptr <= 2'd0;
      occupancy <= 3'd0;
      dout_valid <= 1'b0;
    end else begin
      dout_valid <= take_pop;
      if (take_push) begin
        mem[wptr] <= din;
        wptr <= wptr + 2'd1;
      end
      if (take_pop) begin
        dout <= mem[rptr];
        rptr <= rptr + 2'd1;
      end
      case ({take_push, take_pop})
        2'b10: occupancy <= occupancy + 3'd1;
        2'b01: occupancy <= occupancy - 3'd1;
        default: occupancy <= occupancy;
      endcase
    end
  end
endmodule

occupancy の増加と減少を、独立した二つの if で代入していない。同時受け付けのとき、同じレジスタへノンブロッキング^{iノンブロッキング代入 順序 RTL で <= と書く代入です。右辺を評価して更新を予約するので、同じエッジのレジスタが更新前の状態に基づいて計算できます。 詳しく見る}代入を二度行うと、最後の代入だけが残るためである。二つのポインタはそれぞれの受け付けで進むが、個数は四つの組み合わせをまとめて一度だけ決める。受け付け条件によって、0 からの減少と 4 からの増加も防ぐ。

full で同じアドレスを読み書きする場合

A、B、C、D を順に入れると、rptr=wptr=0、occupancy=4 になる。ここで pop=push=1、din=E とすると、エッジ後は dout=A、dout_valid=1、論理的な内容は [B,C,D,E] になる。両ポインタは 1 となり、個数は 4 を保つ。mem[0] は E に変わるが、dout へのノンブロッキング代入の右辺は以前の A を読む。この read-first の競合動作は、full 時の入れ替え方針に不可欠である。

その次に push=0、pop=1 とすると B が出て、個数は 3 になる。一方、empty で din=Z と両要求を与えると、個数だけが 1 になり、dout_valid=0 のままである。Z を出力するには次のエッジで pop を要求する必要がある。empty 時の即時転送と full 時の入れ替えは、別々の設計上の選択である。

rst はアクティブ High の同期 reset であり、ポインタ、個数、dout_valid を初期化する。メモリと dout の値は消さない。reset 後に古いビットが残っていても、empty が pop を阻止し、新しい push が書いた位置だけを後で読むため、正常動作に配列全体の reset は不要である。dout_valid=0 の値は消費しない。valid=1 の出力は受け付けた pop の応答であり、出力側に別の ready はないので、消費側はその応答を受け取る必要がある。

DEPTH が 2 の累乗でない場合、単純な 2 ビットのオーバーフローは再利用できない。例えば深さ 3 では、アドレス 2 の次に明示的に 0 へ戻す。この例の合成結果が RAM を使うなら、同一アドレスで以前のデータを返す動作に対応するかも確認する。このコードは単一クロック用であり、異なるクロックを使う FIFO のポインタ同期へそのまま適用するものではない。