TDEB Top Bar

Trending
Semiconductor Industry News — The Digital Electronics Blog
Follow Us

TDEB Masthead

The Semiconductor Hub

Semiconductors.  Chips and Systems.  Innovation.

Indexed by leading Search Engines, AI and referenced by Engineers worldwide 500+ Articles 10M+ Pageviews 30+ Reports 50+ Citations

First-Word Fall-Through FIFO: Head Register, Bypass and Valid-Ready Output (FIFO Series, Part 3)

The Semiconductor Hub
by
0
Share Facebook X LinkedIn WhatsApp Email
Hand-drawn cover card for FIFO Series Part 3, First-Word Fall-Through FIFO, with a sketch of entries moving from push to pop.

The FIFOs in Part 1 and Part 2 make the reader ask for data first. The consumer raises pop, and the entry appears on rdata a cycle later. Many consumers do not want to work that way. A decoder wants to look at the next header before deciding whether to take it, an arbiter wants to see the request it is about to grant, and a streaming interface with a valid and ready handshake expects the data to be on the wires while valid is high.

This is Part 3 of the FIFO Series: the first-word fall-through FIFO, often shortened to FWFT or "show-ahead". The oldest entry is already on the output whenever the FIFO is not empty, and pop becomes an acknowledgment that says "I have taken this one, show me the next".

Key takeaways

  • In an FWFT FIFO, rdata holds the oldest entry whenever valid is high. A pop consumes the entry that is already visible.
  • The cheap version reads the storage combinationally at the read pointer. The fast version adds a head register in front of the storage, which gives a clean flop output.
  • A head register needs a bypass: when the storage is empty, a new push goes straight into the head register so the entry is visible the next cycle.
  • The head register adds one entry of capacity. With a storage of DEPTH entries, the FIFO holds DEPTH + 1.
  • FWFT maps directly onto a valid and ready interface: valid is not empty, and a pop is valid and ready in the same cycle.

In this part

What problem it solves

A standard FIFO with a registered read has a one-cycle gap between the request and the data. The consumer must either pop speculatively and hold the data in its own register, or wait a cycle each time it wants to look at the next entry. Both cost something: an extra register and control in every consumer, or lost throughput.

An FWFT FIFO moves that register inside the FIFO, once. The consumer sees the head entry for free, decides in the same cycle, and acknowledges with pop. The timing diagram below runs the same two pushes through both styles. In the Part 1 FIFO, entry A appears on rdata in cycle 3, after the pop. In the FWFT FIFO it is there in cycle 2, before any pop.

Hand-drawn timing diagram comparing a Part 1 FIFO and an FWFT FIFO on the same two pushes: the FWFT FIFO shows entry A on rdata one cycle after the push, before any pop, while the standard FIFO shows it only after the pop.

The interface

The write side is unchanged: push, wdata and full. The read side changes meaning. valid (the inverse of empty) says the head entry on rdata is real. pop says the consumer has taken it. A pop when valid is low is either an error or ignored, the same choice as in Part 1.

In valid and ready terms, the FIFO output is the source: out_valid = valid, out_data = rdata, and pop = out_valid && out_ready. One rule matters for protocols like AXI: once valid is high, the data must stay stable until it is taken. An FWFT FIFO meets that naturally, because the head only changes on a pop.

Micro-architecture: three ways to show the head

Hand-drawn block diagram of an FWFT FIFO: storage with push, wdata and full, a mux that selects either the storage entry at the read pointer or a bypass from wdata, and a head register that drives rdata and valid, refilled on a pop.
  • Combinational read. Drive rdata = mem[rptr] directly and make valid the inverse of empty. It is the smallest version and is common for small flip-flop FIFOs. The cost is timing: rdata comes through a DEPTH-to-1 mux from the pointer register, which is a long path in a deep or wide FIFO and leaves the consumer little time.
  • Head register with bypass. Keep a separate output register and a valid bit. Whenever the head register is free or being popped, refill it from the storage at the read pointer, or, if the storage is empty and a push arrives, straight from wdata. This gives a flop output and is the version in the RTL sketch below.
  • Prefetch from SRAM. An SRAM has a one-cycle read latency, so the head register cannot be refilled in the same cycle as the pop. The usual fix is a small prefetch buffer of two entries behind the SRAM, so a read is always in flight. That is a skid buffer in front of a standard FIFO, and Part 10 covers skid buffers in depth.

With the head register, the oldest entry can be in one of two places. The figure below shows the three states for a small FIFO: empty, one entry that came in by the bypass and sits in the head register, and three entries where A waits on rdata while B and C are in the storage.

Hand-drawn view of an FWFT FIFO in three states: empty with an empty head register, one entry A in the head register after a bypass, and three entries with A in the head register and B and C in storage.

RTL sketch

A power-of-two storage, the pointer scheme from Part 1, and a head register with a bypass. The head register is refilled whenever it is empty or being popped:

module fwft_fifo #(
  parameter int W     = 32,
  parameter int DEPTH = 16,               // storage entries, power of two
  localparam int AW   = $clog2(DEPTH)
) (
  input  logic         clk,
  input  logic         rst_n,
  input  logic         push,
  input  logic [W-1:0] wdata,
  output logic         full,
  input  logic         pop,               // acknowledge the head entry
  output logic [W-1:0] rdata,
  output logic         valid
);
  logic [W-1:0] mem [DEPTH];
  logic [AW:0]  wptr, rptr;
  logic         out_valid;
  logic [W-1:0] out_data;

  wire int_empty = (wptr == rptr);
  wire int_full  = (wptr[AW-1:0] == rptr[AW-1:0]) && (wptr[AW] != rptr[AW]);

  wire do_pop  = pop && out_valid;
  wire refill  = !out_valid || do_pop;           // head register free next cycle
  wire do_push = push && (!int_full || do_pop);
  wire bypass  = refill && int_empty && do_push;  // straight to the head
  wire load    = refill && !int_empty;           // oldest stored entry to the head

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      wptr      <= '0;
      rptr      <= '0;
      out_valid <= 1'b0;
    end else begin
      if (do_push && !bypass) wptr <= wptr + 1'b1;
      if (load)               rptr <= rptr + 1'b1;
      if (refill)             out_valid <= load || bypass;
    end

  always_ff @(posedge clk) begin
    if (do_push && !bypass) mem[wptr[AW-1:0]] <= wdata;
    if (load)               out_data <= mem[rptr[AW-1:0]];
    else if (bypass)        out_data <= wdata;
  end

  assign rdata = out_data;
  assign valid = out_valid;
  assign full  = int_full;                       // DEPTH + 1 entries in total
endmodule

Two invariants keep this correct. If the head register is empty, the storage is empty too, because any stored entry would have been loaded. And an entry only goes to the storage when the head register is occupied and staying occupied, so order is kept: everything in the storage is younger than the head.

Corner cases

  • Push into an empty FIFO. The entry takes the bypass and is visible on rdata the next cycle. A design without the bypass would write it to storage and load it a cycle later, adding a cycle of latency at exactly the moment the consumer is idle and waiting.
  • Push and pop with only the head occupied. The head is popped, the storage is empty, and the new entry goes through the bypass into the head register. Throughput stays at one entry per cycle.
  • Push and pop when full. The pop frees the head, the oldest stored entry moves into it, and the push writes to the slot just vacated. As in Part 1, the storage read and write hit the same index, and the registered load reads the old value, which is the right one.
  • Pop with valid low. do_pop masks it. If your convention says it is an error, add an assertion rather than relying on the mask.
  • Reset. out_valid must be reset. The head data register does not need a reset, but some teams reset it anyway so that X values do not leak into a consumer that samples rdata without checking valid.

Timing, area and power

  • Output timing. With the head register, rdata and valid come straight from flops, which is the main reason to build it this way. The consumer gets almost a full cycle for its own logic.
  • Input timing. The cost moves to pop. It now drives refill, which selects the mux and enables the head register and the read pointer in the same cycle. If pop arrives late from deep consumer logic, this is the path to watch, and a skid buffer that registers the ready signal is the usual fix.
  • Area. One extra W-bit register, a 2-to-1 mux and a few gates. Since the head register is a real entry, you can reduce the storage by one if the total capacity is what matters, though that breaks the power-of-two depth.
  • Power. The head register loads only on a refill. Gate its clock with load || bypass in wide designs.

Verification checklist

  • A reference queue of DEPTH + 1 entries. Every cycle: valid equals "queue not empty", rdata equals the queue head while valid, and full equals "queue holds DEPTH + 1".
  • Stability assertions for valid and ready consumers:
    a_hold:   assert property (@(posedge clk) disable iff (!rst_n)
                valid && !pop |=> valid && $stable(rdata));
    a_no_udf: assert property (@(posedge clk) disable iff (!rst_n)
                !(pop && !valid));
    a_bypass: assert property (@(posedge clk) disable iff (!rst_n)
                !valid && push |=> valid);
  • Coverage of the bypass from empty, the bypass with a same-cycle pop, push and pop when full, and long stalls with valid high.
  • Random traffic with a consumer that sometimes waits many cycles while valid is high, to prove the head entry does not change under it.

Interview questions

1. What is the difference between a standard FIFO and an FWFT FIFO from the consumer's point of view?

A strong answer says the standard FIFO returns data after a pop request while the FWFT FIFO shows the head entry whenever it is not empty, so pop becomes an acknowledgment, and relates this to valid and ready.

2. Why add a head register instead of reading the storage combinationally?

A strong answer talks about the DEPTH-to-1 read mux on the output path, the consumer's timing budget, and the fact that a head register gives flop outputs at the cost of one register and a bypass.

3. What happens when you push into an empty FWFT FIFO?

A strong answer describes the bypass into the head register, the one-cycle visibility, and what the latency would be without it.

4. How would you build FWFT on top of an SRAM with one cycle of read latency?

A strong answer explains why the head cannot be refilled in the pop cycle, proposes a two-entry prefetch buffer that keeps a read in flight, and mentions the extra capacity it adds.

5. What is the total capacity of your design, and does it matter?

A strong answer says DEPTH + 1 for a head register design, explains why, and notes when the extra entry must be counted, for example in credit-based flow control.

Where it is used in real chips

FWFT behavior is the default wherever a FIFO feeds a valid and ready interface: AXI and AXI-Stream channel buffers, network-on-chip router input queues that must show the head flit to the route and arbitration logic, PCIe transaction layer queues that inspect a header before granting it, DMA descriptor queues, and command queues in front of accelerators and memory controllers. Many FPGA FIFO generators offer it as a standard option.

The rest of the series

Part 2 covered the asynchronous FIFO: Gray-coded pointers, synchronizers and flags that are never wrong.

Part 4 is the multi-push FIFO, which accepts several entries in one cycle and keeps them in order.

Share Facebook X LinkedIn WhatsApp Email

Post a Comment

0 Comments

Your comments will be moderated before it appears here.

Post a Comment (0)

#buttons=(Ok, Go it!) #days=(20)

Our website uses cookies to enhance your experience. Learn more
Ok, Go it!