01signal.com

レジスタ追加による FIFO のタイミング改善

概要

このページは、FIFO に関する一連のページの最後のページです。既存の FIFO を別のタイプの FIFO に変換する方法を示します。最初に「スタンダード FIFO」を FWFT FIFO に変換する方法、次にその逆の変換方法を説明します。その後、FIFO のタイミングを改善する、つまりより高い周波数で動作させるための、より高度な方法を紹介します。

実用的な観点では、タイミング制約(timing constraints)を達成できない問題があり、かつその問題が FIFO に関係しているのでなければ、このページを読む意味はほとんどありません。このページの内容は難しく、FIFO の一般的な使用には必要ありません。ただし、ロジック設計、特にデータを処理するロジックを設計する際に使う能力を鍛える練習としては、読む価値があるかもしれません。

直接の関連はありませんが、別のページでは、外部メモリ(通常は DDR メモリですが、AXI インターフェースでラップされたものであれば何でも構いません)を利用して、非常に深い FIFO を作成する方法を紹介しています。この手法の優れた点は、この巨大な FIFO が使用する外部メモリと同じくらいの深さを持てるにもかかわらず、そのすべてがアプリケーションロジックからは透過的に見えることです。ベースライン FIFO と同じインターフェースを持ちます。

このページの Verilog コードはかなり前に書いたものなので、コーディングスタイルが現在と少し異なることをお断りしておきます。

スタンダード FIFO から FWFT FIFO への変換

まず、以前のページで説明した FWFT FIFO について簡単におさらいします。「スタンダード FIFO」では、@empty(空)が Low のとき、クロックの立ち上がりエッジで @rd_en を High にすると、有効なデータが FIFO の出力に現れます。FWFT FIFO は、データが利用可能になるとすぐに出力に提示します。したがって、@empty(空)が Low のときは、出力のデータが有効であることを意味します。

@rd_en の意味も異なります。「スタンダード FIFO」では「データを持ってこい」という意味ですが、FWFT FIFO では「今のデータを使ったので、次のデータがあれば持ってこい」というような意味になります。

というわけで、以下が「スタンダード FIFO」を FWFT FIFO に変換するモジュールです。当然ながら、@rd_en と @empty(空)を操作しているだけです。他の信号はそのまま通過します。

module basic_fwft_fifo(rst,
                       rd_clk, rd_en, dout, empty,
                       wr_clk, wr_en, din, full);

   parameter width = 8;

   input                 rst;
   input                 rd_clk;
   input                 rd_en;
   input                 wr_clk;
   input                 wr_en;
   input [(width-1):0]   din;
   output                empty;
   output                full;
   output [(width-1):0]  dout;

   reg                   dout_valid;
   wire                  fifo_rd_en, fifo_empty;

   // orig_fifo is just a normal (non-FWFT) synchronous or asynchronous FIFO
   fifo orig_fifo
      (
       .rst(rst),
       .rd_clk(rd_clk),
       .rd_en(fifo_rd_en),
       .dout(dout),
       .empty(fifo_empty),
       .wr_clk(wr_clk),
       .wr_en(wr_en),
       .din(din),
       .full(full)
       );

   assign fifo_rd_en = !fifo_empty && (!dout_valid || rd_en);
   assign empty = !dout_valid;

   always @(posedge rd_clk or posedge rst)
      if (rst)
         dout_valid <= 0;
      else
         begin
            if (fifo_rd_en)
               dout_valid <= 1;
            else if (rd_en)
               dout_valid <= 0;
         end
endmodule

通常ならここでコードの説明をするのですが、それは前のページで FWFT FIFO について説明した内容の繰り返しになってしまいます。

FWFT FIFO からスタンダード FIFO への変換

これは本当に単純です。FWFT FIFO では @empty(空)が Low のとき、出力ポートにデータが存在することを意味します。そこで、@rd_en が High のときにこのデータを取り込むレジスタを作成します。

つまり、次のようになります。

module standard_fifo(rst,
                     rd_clk, rd_en, dout, empty,
                     wr_clk, wr_en, din, full);

   parameter width = 8;

   input                 rst;
   input                 rd_clk;
   input                 rd_en;
   input                 wr_clk;
   input                 wr_en;
   input [(width-1):0]   din;
   output                empty;
   output                full;
   output [(width-1):0]  dout;

   reg [(width-1):0]     dout;
   wire [(width-1):0]    dout_w;

   always @(posedge rd_clk)
     if (rd_en && !empty)
       dout <= dout_w;

   fwft_fifo wrapper
     (
      .wr_clk(wr_clk),
      .rd_clk(rd_clk),
      .rst(rst),
      .din(din),
      .wr_en(wr_en),
      .rd_en(rd_en && !empty),
      .dout(dout_w),
      .full(full),
      .empty(empty)
      );
endmodule

操作しているのは @dout だけであることに注意してください。@empty(空)はそのまま通過します。@empty(空)が High なら @dout_w は無効なので、@dout はその値を取り込めません。

タイミング改善のテクニック

いよいよ、FIFO に関するこれら一連のページの大トリです。ここがおそらく最も読み応えのある部分です。

FPGA 設計がタイミング制約(timing constraints)を満たさない(つまり目標のクロック周波数に達しない)原因を調べていると、クリティカルパス(critical path)が FIFO で始まっている、または FIFO で終わっている、あるいはその両方であることが判明することがあります。まず、簡単に解決できるケースから説明し、最後に難しいケースに取り組みましょう。

@empty や @full がクリティカルパス上にある場合

@empty 信号と @full 信号は、特に @wr_en や @rd_en がこれらの組み合わせ論理(combinatorial logic)の関数である場合に、クリティカルパス(critical path)上に現れることがあります。これは主に、これらの信号が FIFO への書き込み要求や読み出し要求に使われるだけでなく、データを消費または生成するアプリケーションロジックに対するイネーブル信号としても働くことが多いためです。データが流れなければ、ロジックも停止してしまうからです。

したがって、@wr_en と @rd_en に依存する論理式が多数存在し、しかもその論理関数がかなり複雑になることがよくあります。その結果、ファンアウト(fan-out)が大きくなります。これらすべてが、伝搬遅延(propagation delay)の問題につながります。

正しく書かれた FIFO では、@empty と @full はフリップフロップの出力です。したがって、そこに改善の余地はあまりありません。しかし、FPGA のソフトウェアは FIFO を合成済みネットリストとして提供することが多いため、ファンアウト(fan-out)を減らす目的でこれらのレジスタを複製することは不可能(少なくとも困難)です。さらに、これらのレジスタと、その出力値を使うアプリケーションロジックとの間には、FPGA のロジックファブリック上に大きな物理的距離が存在することがあります。大規模な FPGA では、これがパスの遅延に決定的な寄与をすることがあります。

この問題の修正方法は、@almost_empty と @almost_full を説明したときにすでに示しました(前述のページを参照)。これらのポートを使えば、@wr_en と @rd_en の出力をレジスタにできます。これにより、組み合わせ論理(combinatorial logic)の問題は解決し、これらの信号のファンアウト(fan-out)を制御することもできます。さらに、これらのレジスタを、その値を使うロジックの近くに配置しやすくなるため、伝搬遅延(propagation delay)の削減にも役立ちます。

@wr_en や @din がクリティカルパス上にある場合

この状況は、間違いなく最も簡単に解決できます。レジスタの層を 1 つ追加するだけです。たとえば、次のようにします。

always @(posedge wr_clk)
  begin
    wr_en_reg <= wr_en;
    din_reg <= din;
  end

そして、@wr_en_reg と @din_reg を FIFO に接続します。FIFO のオーバーフロー(overflow)を防ぐには、@full(満杯)の代わりに @almost_full を使うべきです。より一般的に言えば、FIFO を満たすための閾値を 1 つ分下げる必要があります。

@rd_en や @dout がクリティカルパス上にある場合

ここからが本番です。これは比較的解決が難しい問題であるだけでなく、最も発生しやすい問題でもあります。その理由はいくつかあります。

次に @dout について考えます。

つまり、@rd_en から FIFO のロジックに至る組み合わせ論理(combinatorial logic)の経路をなくし、@dout についても同様にすることが目標です。

@dout の組み合わせ論理パスのみを切り離す場合

これを解決策として提示するつもりはあまりありませんが、次のステップを理解するための準備として、この議論は役立つかもしれません。もし混乱するだけなら、このセクションは読み飛ばしてください。

たとえば、@dout の組み合わせ論理(combinatorial logic)パスだけを切り離したいとしましょう。FWFT FIFO を「スタンダード FIFO」に変換するラッパーモジュール(上で示したもの)は、まさにこの処理を行います。つまり、レジスタを 1 つ追加することで、@dout の組み合わせ論理パスを終端させます。ただし、出発点として FWFT FIFO が必要です。

一方で、「スタンダード FIFO」を FWFT FIFO に変換するラッパーモジュールもありました。では、FIFO を行ったり来たり変換すればよいのでしょうか。それとも、同等の処理を行う単一のモジュールを書けばよいのでしょうか。どちらの方法でも、この種の解決策は @rd_en に関する状況を悪化させます。

しかし、この解決策はもう少し詳しく見る価値があります。FWFT FIFO への変換は、ラップされた FIFO の @dout がいつ有効かを追跡し、@dout が無効なとき(および/または外部の @rd_en が High のとき)に @fifo_rd_en を High に保つ、というだけのことでした。

「スタンダード FIFO」への逆変換は、@rd_en が High のときに、ラップされた FIFO の @dout の値をレジスタにコピーすることで実現しました。

つまり、最初の仕組みは、可能なときにラップされた FIFO の @dout を有効に保ち、2 つ目の仕組みは、外部の @rd_en が要求したときに @dout を別のレジスタにコピーしていたのです。

しかし、これでは @rd_en の組み合わせ論理(combinatorial logic)パスの問題は解決しません。連続読み出しを可能にするには、外部の @rd_en が High である各クロックで、元の FIFO からワードを読み出さなければなりません。そうしないと、FWFT の @dout は、消費されたにもかかわらず更新されないため、無効になってしまいます。したがって、この内部 FIFO の @rd_en は、外部の @rd_en の組み合わせ論理(combinatorial logic)の関数にならざるを得ません。これを変えたい場合は、次に示すように、@dout の経路にもう 1 つレジスタを追加する必要があります。

reg_fifo による両方の組み合わせ論理パスの切り離し

前置きはこれくらいにして、@rd_en と @dout の組み合わせ論理(combinatorial logic)パスの両方を切り離す reg_fifo モジュールを示します。

module reg_fifo(rst,
                rd_clk, rd_en, dout, empty,
                wr_clk, wr_en, din, full);

   parameter width = 8;

   input                 rst;
   input                 rd_clk;
   input                 rd_en;
   input                 wr_clk;
   input                 wr_en;
   input [(width-1):0]   din;
   output                empty;
   output                full;
   output [(width-1):0]  dout;

   reg                   fifo_valid, middle_valid;
   reg [(width-1):0]     dout, middle_dout;

   wire [(width-1):0]    fifo_dout;
   wire                  fifo_empty, fifo_rd_en;
   wire                  will_update_middle, will_update_dout;

   // orig_fifo is "standard" (non-FWFT) FIFO
   fifo orig_fifo
      (
       .rst(rst),
       .rd_clk(rd_clk),
       .rd_en(fifo_rd_en),
       .dout(fifo_dout),
       .empty(fifo_empty),
       .wr_clk(wr_clk),
       .wr_en(wr_en),
       .din(din),
       .full(full)
       );

   assign will_update_middle = fifo_valid && (middle_valid == will_update_dout);
   assign will_update_dout = rd_en && !empty;
   assign fifo_rd_en = !fifo_empty && !(middle_valid && fifo_valid);
   assign empty = !(fifo_valid || middle_valid);

   always @(posedge rd_clk)
      if (rst)
         begin
            fifo_valid <= 0;
            middle_valid <= 0;
            dout <= 0;
            middle_dout <= 0;
         end
      else
         begin
            if (will_update_middle)
               middle_dout <= fifo_dout;

            if (will_update_dout)
               dout <= middle_valid ? middle_dout : fifo_dout;

            if (fifo_rd_en)
               fifo_valid <= 1;
            else if (will_update_middle || will_update_dout)
               fifo_valid <= 0;

            if (will_update_middle)
               middle_valid <= 1;
            else if (will_update_dout)
               middle_valid <= 0;
         end
endmodule

まず注意すべき点は、@dout はこのモジュール内で定義されたレジスタであり、@rd_en によって更新されることです。この @dout や @rd_en と、内部の FIFO に接続されている類似の信号(@fifo_dout や @fifo_rd_en)とを混同しないようにしてください。

それでは、このモジュールの動作を見ていきましょう。

パイプラインの理解

この構造は、本質的にスキッドバッファ(skid buffer)です。有効フラグ付きの 2 段パイプライン(pipeline)であり、データフローを連続的に保ちながら、外部の @rd_en を内部 FIFO の読み出しイネーブルから切り離しています。

FWFT FIFO への変換器と同様に、通常の FIFO(orig_fifo)のインスタンシエーション(instantiation)があります。reg_fifo モジュール内のロジックは、@fifo_dout に有効な値が入っていないときに orig_fifo からワードを読み出すことで、@fifo_dout の値を有効に保とうとします。それに加えて、@middle_dout という 2 つ目のレジスタがあります。ロジックは、可能なときは @fifo_dout の値をそこに取り込んで、このレジスタも有効に保とうとします。

つまり、@fifo_dout、@middle_dout、@dout は、orig_fifo 内のデータを前方へ進めるパイプライン(pipeline)と見なせます。

これらのパイプライン段がいつ有効かを追跡するレジスタが 2 つあります。@fifo_valid は @fifo_dout が有効なときに High、@middle_valid は @middle_dout が有効なときに High になります。

このパイプラインの目的は、中間段をバイパスできることです。@rd_en が High(かつ @empty(空)が Low)のとき、@dout は @middle_dout か @fifo_dout のどちらかから新しい値を取りますが、常に @middle_dout を優先します。言い換えれば、@middle_dout が有効なら @dout は @middle_dout を使い、そうでなければ @fifo_dout を使います。これが @rd_en の組み合わせ論理(combinatorial logic)パスを切り離す鍵になる理由については、後ほど説明します。

まず、実装の詳細を見てみましょう。FIFO のデータ出力から reg_fifo の出力レジスタへは、2 つの独立した経路があります。これら 2 つの経路は、図の左側と右側に分けて示されています。

Data flow with extra registers

2 つのパイプライン段(@fifo_dout と @middle_dout)のどちらも有効でない場合、@empty(空)が High になり、データを取り出せるところがないことを示します。

assign empty = !(fifo_valid || middle_valid);

これらのパイプライン段を有効に保とうとする試みは、次の代入に反映されています。

assign fifo_rd_en = !fifo_empty && !(middle_valid && fifo_valid);

これは、2 つのパイプライン段のいずれかが無効であれば、可能な限り orig_fifo から読み出すことを意味します。@fifo_dout がすでに有効な場合、@fifo_dout が更新されるのと同時に、その値が @middle_dout にコピーされます(これについては後ほど詳しく説明します)。

次に、@will_update_* のペアの定義を見てみましょう。

assign will_update_middle = fifo_valid && (middle_valid == will_update_dout);
assign will_update_dout = rd_en && !empty;

まず、@will_update_dout は、@rd_en に対し、@empty(空)が High のときに reg_fifo から読み出さないための安全ガードを付けたものに等しいことに注意してください。

次に、@middle_dout の更新を制御する @will_update_middle は、次のようになります。

always @(posedge rd_clk)
  if (will_update_middle)
     middle_dout <= fifo_dout;

上記の @will_update_middle の定義を見ると、@middle_dout を更新する条件は 2 つあります。1 つは @fifo_dout の値が有効であること(これは明らかです)、もう 1 つは (middle_valid == will_update_dout) という式です。この式を 4 つのケースに分けて説明します。これにより、この仕組み全体がどう動くかがわかります。ここで説明するすべては、@fifo_dout が有効な場合にのみ関係することに留意してください。

@middle_valid と @fifo_valid が同時に High のとき、@fifo_rd_en は Low になることに注意してください。その結果、最後の 2 つのケースが発生するときは、orig_fifo からデータは読み出されません。

特に、2 つのパイプライン段が両方とも有効で、@rd_en が High の場合、@fifo_dout の値は @middle_dout にコピーされます。そして、@fifo_rd_en が Low であるため、@fifo_valid は次のクロックサイクルで Low に変わります。これは問題ありません。@middle_valid は High のままなので、必要であれば次のクロックサイクルでデータを供給できます。その次のクロックサイクルには、@fifo_valid は再び High になります(orig_fifo にデータがあればです)。

では、この特定の状況で @fifo_dout を有効に保つように @fifo_rd_en を定義しないのはなぜでしょうか。そうすると、@fifo_rd_en が @rd_en の組み合わせ論理(combinatorial logic)の関数になってしまうからです。この 2 段パイプライン(pipeline)は、まさにそれを避けるために設計されています。

これを踏まえて、@dout がどのように定義されているかを見てみましょう。リセットを除くと、定義は次のとおりです。

always @(posedge rd_clk)
  if (will_update_dout)
    dout <= middle_valid ? middle_dout : fifo_dout;

@will_update_dout をその定義に置き換えると、次のようになります。

always @(posedge rd_clk)
  if (rd_en && !empty)
    dout <= middle_valid ? middle_dout : fifo_dout;

これは、FWFT FIFO を「スタンダード FIFO」に変換する場合と似ています。ただし、選択できるソースが 2 つあります。@middle_dout に有効な値が入っていれば、それが使われます。そうでなければ @fifo_dout が使われます。どちらも有効でなければ @empty(空)が High になるため、何も起こりません。

なぜこれが役立つのでしょうか。出力タイミングについては、@dout は明らかにレジスタです。@rd_en については、@fifo_rd_en は @middle_valid と @fifo_valid にのみ依存することに注意してください。これらは両方ともレジスタです。さらに @fifo_empty にも依存しますが、これは orig_fifo 自体の出力です(この組み合わせ論理(combinatorial logic)パスは避けられません)。したがって、@fifo_rd_en は外部の @rd_en には依存せず、@rd_en から orig_fifo への組み合わせ論理パスは存在しません。

パイプライン段のレジスタの有効性の追跡

全体像を補完しておきましょう。2 つの *_valid フラグは、対応するレジスタに有効なデータが入っているかどうかを示します。@fifo_valid については、次のとおりです。

 if (fifo_rd_en)
   fifo_valid <= 1;
 else if (will_update_middle || will_update_dout)
   fifo_valid <= 0;

これは、前述の「スタンダード FIFO」から FWFT FIFO への変換における @dout_valid の定義と同じです。立ち上がりエッジで @fifo_rd_en が High の場合、その結果として @fifo_valid が High になります。これは当然です。orig_fifo からデータを読み出したのであれば、その出力は有効と見なされるからです。しかし、@fifo_rd_en が Low で、データが @middle_dout か @dout のどちらかにコピーされた場合、@fifo_dout はもはや有効とは見なされません。FIFO の出力は使われたばかりであり、FIFO はそれを新しいデータで置き換えていないからです。

@middle_valid も同じロジックに従います。

 if (will_update_middle)
   middle_valid <= 1;
 else if (will_update_dout)
   middle_valid <= 0;

@will_update_middle が High のとき、データが @middle_dout にコピーされるため、@middle_valid も High になります。そうでなく、@middle_dout のデータが @dout にコピーされる場合、@middle_valid は Low に変わります。@dout は可能な場合に @middle_dout からコピーすることを優先するため、@will_update_dout はこのための十分条件となります(前述のとおりです)。

本当に動作するのか?

このモジュールは複雑なので、動作することのほぼ形式的な証明とも言えるものが必要です。そのひとつの方法は、2 つのパイプライン段(@fifo_dout と @middle_dout)のうち、いくつが有効かを問うことです。この値は reg_fifo モジュールでは定義されていませんが、次のように定義することもできたはずです

wire [1:0] valid_count;
assign valid_count = fifo_valid + middle_valid;

この架空の @valid_count は、当然 0、1、2 のいずれかの値を取ります。この値は次のように増減します。

論理式を確認して、この 3 つの記述が正しいことを確かめてください。

では、orig_fifo にデータがあり、アプリケーションロジックが連続して読み出したい場合に何が起こるかを見てみましょう。

reg_fifo のロジックは、orig_fifo から読み出すことで @valid_count を 2 に向かって増やそうとします。一方、@valid_count が 0 でなければ @empty(空)は Low なので、@valid_count が 1 になった時点で @rd_en を High にしてかまいません。したがって、@valid_count が 1 のとき、@valid_count は 2 ではないため、@fifo_rd_en は High になります。

しかし、@rd_en が High のままであるため、@valid_count は 2 には達しません。その結果、@fifo_rd_en と @rd_en の両方が High に保たれたままデータが流れ、@valid_count は 1 のままになります。最初の部分を除き、データは @fifo_dout から @dout へコピーされます。

この均衡が崩れるのは、orig_fifo が empty(空)になったときです。この場合、@fifo_rd_en を High にできなくなるため、@valid_count は 0 になります。もうひとつの均衡の崩れ方は、FIFO が empty(空)ではなく、アプリケーションロジックがもう読みたくないために @rd_en が Low になった場合です。この場合、@valid_count は 2 に上昇し、その状態を保ちます。

その後、@rd_en が再び High になると、@valid_count は 1 に下がり、その時点で初めて @fifo_rd_en が High に変わります(orig_fifo が empty(空)でなければ)。

繰り返しますが、@valid_count は理論上の信号であり、モジュールには実装されていません。この説明が、なぜ 2 つの追加パイプライン段がデータフローの連続性を保証するのかを理解する助けになれば幸いです。

使用上の注意

このモジュールは、ラップしている「スタンダード FIFO」の置き換えとしてそのまま使用できます。機能的な観点では、何も変わりません。ただし、orig_fifo から見ると、@rd_en、@dout、@empty(空)の動作が少し変わります。orig_fifo が FIFO として正しく動作する限り(これは安全な仮定です)、問題にはなりません。書き込み関連のポートはそのまま通過させているので、こちらにはまったく変更はありません。

このモジュールはパイプライン(pipeline)段をいくつか追加するため、orig_fifo のフィルカウンタ(fill counters)は、reg_fifo 全体に格納されているワード数(つまり orig_fifo 内のワード数とパイプライン段内のワード数を合わせた数)よりも小さい値を示すことがあります。したがって、orig_fifo で @almost_empty や類似のポートを有効にしている場合、それらは悲観的な状況を示す可能性があります。

reg_fifo の小さな欠点は、その @empty(空)出力がレジスタ出力ではなく、2 つのレジスタの組み合わせ論理(combinatorial logic)出力であることです。タイミングには最適ではありませんが、ほとんどの用途では影響は最小限です。これは、このページで示した @next_words_in_ram と同じ発想で、@next_fifo_valid や @next_middle_valid のような組み合わせレジスタを定義すれば修正できます。ここでは実装していません。主な理由は、reg_fifo がこれで十分複雑だからです。

タイミングを改善した FWFT FIFO

タイミングを改善した FWFT FIFO が必要な場合は、簡単です。前述の basic_fwft_fifo の例を使い、通常の FIFO のインスタンシエーション(instantiation)の代わりに reg_fifo を使用します。この方法ではレジスタがもう 1 つ余分に必要になりますが、これは小さなコストです。

以上で、FIFO に関するこのシリーズは終わりです。

このページは英語から機械翻訳されたものです。不明な点があれば、原文を参照してください。
Copyright © 2021-2026. All rights reserved. (dcc38493)