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

Non-Power-of-Two FIFO Design: Explicit Wraparound and Exact Capacity (FIFO Series, Part 8)

The Semiconductor Hub
by
0
Share Facebook X LinkedIn WhatsApp Email
Hand-drawn cover card for FIFO Series Part 8, Non-Power-of-Two FIFO, with a sketch of entries moving from push to pop.

Every FIFO so far in this series had a power-of-two depth, and that was not an accident. With 16 entries, a 4-bit index wraps from 15 to 0 by itself, and one extra pointer bit tells full from empty for free. Real requirements are not always that kind. A buffer sized to cover a link round trip might need 12 entries, a line buffer might need exactly as many entries as there are pixels in a tile, and rounding a wide SRAM-based FIFO from 40 entries up to 64 wastes a lot of area.

This is Part 8 of the FIFO Series: the non-power-of-two FIFO. We make the wraparound explicit, replace the free wrap bit with a phase bit that we flip ourselves, work out the count, and then look at the harder version of the problem, an asynchronous FIFO whose Gray-coded pointers must wrap at a value that is not a power of two.

Key takeaways

  • With a non-power-of-two depth, the index no longer wraps by overflow. Compare it with DEPTH - 1 and reset it to zero explicitly.
  • A phase bit per pointer, flipped on every wrap, does the job of Part 1's extra wrap bit: equal indexes with equal phases mean empty, and with different phases mean full.
  • The count needs a case split: widx - ridx when the phases match, DEPTH - ridx + widx when they differ. A registered counter avoids the split.
  • For asynchronous FIFOs, a plain Gray counter cannot wrap at an arbitrary value with a one-bit change. Taking 2 x DEPTH consecutive codes from the middle of a larger Gray sequence works, because the sequence is symmetric.
  • The cost is small: a compare with a constant per pointer. The saving can be large when it lets a memory shrink to the size the design actually needs.

In this part

What problem it solves

Depth is a requirement, not a style choice. It comes from a burst size, a latency to cover, or a credit count agreed with the other end of a link. When the answer is 12, rounding up to 16 costs a third more storage, and for a deep or wide FIFO built from memory that is real area and leakage. Sometimes the exact depth also matters functionally: a credit-based interface may advertise exactly as many credits as there are entries, and the receiver must never have spare entries the sender does not know about, or fewer.

The non-power-of-two FIFO gives the exact capacity at the cost of a little pointer logic.

The interface

Nothing changes from Part 1: push, wdata and full on the write side, pop, rdata and empty on the read side, and optionally a count. The only visible difference is that DEPTH may be any value of 2 or more, and count needs $clog2(DEPTH + 1) bits.

Explicit wraparound and the phase bit

Hand-drawn pointer logic for a non-power-of-two FIFO: the write index goes through a compare that resets it to zero at DEPTH minus one, a phase bit flips on the wrap, the read side is the same, empty means equal indexes and phases, full means equal indexes and different phases, and the count formula has two cases.

In a 16-entry FIFO, the 5-bit pointer counts 0 to 31 and the low four bits are the index. In a 12-entry FIFO that trick fails: a 4-bit index would happily count to 13, 14 and 15, which do not exist. So each pointer becomes two pieces: an index that counts 0 to DEPTH - 1 and is reset to zero after the last entry, and a phase bit that flips each time the index wraps.

The phase bit has exactly the meaning of the extra wrap bit in Part 1. When the indexes are equal, the FIFO is either empty or full, and the phases decide: equal phases mean the writer and reader are on the same lap, so it is empty, and different phases mean the writer is one lap ahead, so it is full.

Hand-drawn view of a six-entry FIFO in three states: empty with equal indexes and phases, four entries with the read index at 4, the write index at 2 and different phases, and full with equal indexes and different phases.

The count needs care. In the middle example above, the read index is 4 with phase 0 and the write index is 2 with phase 1. A plain widx - ridx gives -2. Because the phases differ, the writer has wrapped, so the count is DEPTH - ridx + widx = 6 - 4 + 2 = 4. If the design needs count or an almost-full threshold every cycle, an up and down counter is simpler and faster than this two-case subtraction.

RTL sketch

A synchronous FIFO of any depth from 2 up, with explicit index wrap, phase bits, a push accepted at full when a pop happens in the same cycle, and a registered read:

module npot_fifo #(
  parameter int W     = 32,
  parameter int DEPTH = 12,               // any value, 2 or more
  localparam int AW   = $clog2(DEPTH),
  localparam int CW   = $clog2(DEPTH + 1)
) (
  input  logic          clk,
  input  logic          rst_n,
  input  logic          push,
  input  logic [W-1:0]  wdata,
  output logic          full,
  input  logic          pop,
  output logic [W-1:0]  rdata,
  output logic          empty,
  output logic [CW-1:0] count
);
  logic [W-1:0]  mem [DEPTH];
  logic [AW-1:0] widx, ridx;
  logic          wph, rph;                // flip on every wrap

  assign empty = (widx == ridx) && (wph == rph);
  assign full  = (widx == ridx) && (wph != rph);
  assign count = (wph == rph) ? CW'(widx - ridx)
                              : CW'(DEPTH - ridx + widx);

  wire do_pop  = pop  && !empty;
  wire do_push = push && (!full || do_pop);
  wire wlast   = (widx == AW'(DEPTH - 1));
  wire rlast   = (ridx == AW'(DEPTH - 1));

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      widx <= '0; wph <= 1'b0;
      ridx <= '0; rph <= 1'b0;
    end else begin
      if (do_push) begin
        widx <= wlast ? '0 : widx + 1'b1;
        if (wlast) wph <= !wph;
      end
      if (do_pop) begin
        ridx <= rlast ? '0 : ridx + 1'b1;
        if (rlast) rph <= !rph;
      end
    end

  always_ff @(posedge clk) begin
    if (do_push) mem[widx] <= wdata;
    if (do_pop)  rdata <= mem[ridx];
  end
endmodule

The same code works for a power-of-two depth, where wlast fires at the natural overflow point, so a team can keep one FIFO module for all depths. Synthesis turns the compare with a constant into a small AND of index bits.

The asynchronous case

Part 2 crossed clock domains with Gray-coded pointers, because a Gray counter changes one bit per step. A plain Gray counter of n bits only has that property around the whole cycle of 2 to the n values. If a pointer must wrap after 12 values, jumping from Gray(11) back to Gray(0) changes several bits, and the synchronizer can capture a value that never existed.

Hand-drawn table of the sixteen 4-bit Gray codes, with the middle twelve, codes 2 to 13, used as pointer values 0 to 11 for a depth-6 asynchronous FIFO, showing that the wrap from pointer 11, code 1011, back to pointer 0, code 0011, changes one bit.

A well-known fix uses the symmetry of the reflected Gray code. A pointer for a depth-D asynchronous FIFO needs 2D values (the index plus a lap bit). Take 2D consecutive codes from the middle of a Gray sequence large enough to hold them, centered so that the same number of codes is skipped at each end. The first and last codes chosen are mirror images across the middle, and they differ in exactly one bit. In the figure, a depth-6 FIFO uses codes 2 to 13 of the 16 four-bit codes, and the wrap from 1011 back to 0011 is a one-bit step like every other. Since 2D is always even, this works for any depth.

The pointer is kept in binary for addressing, offset and converted to Gray before it crosses, and converted back to binary and un-offset on the far side before the full and empty compares. The Gray-domain shortcut for full from Part 2 no longer applies directly, so compare in binary after conversion. The synchronized pointers still lag, and the flags are still pessimistic, which is the property that matters.

Corner cases

  • Push and pop at the last index. Both pointers can wrap in the same cycle. Each flips its own phase, so their relationship is unchanged and the count holds.
  • Push and pop when full. The read and write index are equal; the registered read returns the old value, the right one, exactly as in Part 1.
  • DEPTH of 2 or 3. Small depths exercise wrap almost every other cycle and are the best place to find off-by-one mistakes in the wrap compare.
  • Count width. With DEPTH of 12, the count runs 0 to 12 and needs four bits; with DEPTH of 16 it needs five. Size it with $clog2(DEPTH + 1), not $clog2(DEPTH).
  • SRAM row count. Some memory compilers only offer certain row counts. Check that the depth you want exists, or use the nearest larger memory and wrap at your depth anyway to keep the exact capacity.

Timing, area and power

  • Pointer logic. The wrap compare with a constant adds a gate level ahead of the index register's input mux. It is rarely critical, and the compare can be precomputed: register a "next is last" flag along with the index.
  • Count. The two-case subtraction is a mux after two adders. If count is used on a critical path, keep a registered counter instead.
  • Area. The point of the exercise. A 40-entry FIFO stays at 40 entries instead of 64, and the pointer overhead is a few gates.
  • Power. No change from Part 1: write only the addressed entry and gate the storage clock when idle.

Verification checklist

  • A reference queue of exactly DEPTH entries, checked on every pop, with full, empty and count compared every cycle.
  • Assertions:
    a_idx_range: assert property (@(posedge clk) disable iff (!rst_n)
                   widx < DEPTH && ridx < DEPTH);
    a_count_max: assert property (@(posedge clk) disable iff (!rst_n)
                   count <= DEPTH);
    a_flags:     assert property (@(posedge clk) disable iff (!rst_n)
                   !(full && empty));
  • Run the same tests at several depths, including odd and prime ones (3, 5, 7, 13) as well as a power of two, so that a test that only passes by luck at 16 is caught.
  • For an asynchronous version, check in simulation that every pointer step, including the wrap, changes exactly one Gray bit, and use the metastability model from Part 2.

Interview questions

1. Why does the extra-bit trick from a power-of-two FIFO fail at depth 12?

A strong answer explains that a 4-bit index overflows at 16, not 12, so the index must be compared and reset explicitly, and then shows the phase bit as the replacement for the wrap bit.

2. Write the count for a non-power-of-two FIFO.

A strong answer gives both cases based on the phase bits, works a short example, and mentions a registered counter as the faster option.

3. You need an asynchronous FIFO of depth 6. What do you do about the Gray pointers?

A strong answer describes taking 12 symmetric codes from the middle of a 16-code Gray sequence, explains why the wrap stays a one-bit step, and notes that the flags are computed after converting back to binary.

4. Is it worth it, or should you just round up to a power of two?

A strong answer weighs a few gates of pointer logic against storage area, mentions exact credit counts as a functional reason, and says it depends on width, depth and memory options.

5. How do you test it?

A strong answer runs the same tests at odd, prime and power-of-two depths, checks the index range and count, and covers simultaneous wraps of both pointers.

Where it is used in real chips

Non-power-of-two FIFOs appear in credit-based interfaces such as PCIe and network-on-chip links, where the buffer depth equals the advertised credits, in video and image pipelines with line or tile buffers sized to a resolution, in DMA engines and accelerators sized to a latency, and in any memory-based buffer where rounding up would waste significant area.

The rest of the series

Part 7 covered the multi-push, multi-pop FIFO and its count and space management.

Part 9 looks at the circular FIFO: wraparound with simultaneous operations, and the overwrite-oldest mode used by trace and log buffers.

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!