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

Multi-Pop FIFO Design: Up to N Oldest Entries Out per Cycle (FIFO Series, Part 5)

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

Part 4 let a producer push several entries in one cycle. The mirror image is just as common. A wide consumer, such as a decoder that handles up to four instructions a cycle, a packer that fills a wide output word from narrow entries, or a scheduler that issues several requests at once, wants to take more than one entry from the head of a queue per cycle, and how many it takes depends on what it finds there.

This is Part 5 of the FIFO Series: the multi-pop FIFO. It keeps one push per cycle, shows the consumer a window of the N oldest entries, and lets it pop any number from zero to N of them in a single cycle, always from the head and always in order.

Key takeaways

  • A multi-pop FIFO shows the oldest N entries on N output lanes, each with its own valid bit, and pops up to N of them per cycle.
  • Pops always come from the head in order, so the consumer only says how many it takes. Lane i is valid when the count is greater than i.
  • The read pointer moves by the pop count and wraps as usual. The output window crosses the end of the array whenever the head is near it.
  • A pop count larger than the number of valid entries must be either refused or clamped, and the spec should say which.
  • The cost is on the read side: N read muxes, or N interleaved banks with an output rotator, plus a pop count that arrives late from consumer logic.

In this part

What problem it solves

A consumer that can process several entries a cycle is wasted on a single-pop FIFO. The usual workaround, a few cycles of popping into a local buffer before processing, adds latency and a second buffer that must itself be sized and verified. Several FIFOs in parallel lose the global order, just as on the write side.

The multi-pop FIFO gives the consumer what it actually needs: a look at the next N entries in age order, and the right to take a variable number of them. Variable is the key word. A decoder may take three entries this cycle because the fourth depends on the third, and one entry next cycle. The FIFO must follow that without gaps or reordering.

The interface

Hand-drawn block diagram of a multi-pop FIFO: one push lane with full, storage with the oldest N entries highlighted, a window mux at the read pointer plus i that drives rdata and rvalid on four output lanes, and a pop count input that advances the read pointer.

The write side is the same as Part 1: push, wdata and full. The read side has rdata[N] and rvalid[N], where lane 0 is the oldest entry, and an input pop_cnt from 0 to N. The window behaves like the first-word fall-through FIFO of Part 3: the entries are visible before they are popped, and a pop acknowledges what the consumer has already seen.

The valid bits always form a thermometer: if lane 2 is valid, lanes 0 and 1 are too. That makes them easy to use downstream, and it means the consumer cannot create holes. Some interfaces encode the pop as a thermometer as well, one bit per lane, which is the form Part 6 uses. Here we use a binary count, which is narrower and easier to generate when the consumer already computes "how many".

Micro-architecture: the head window

Lane i shows the entry at rptr + i. In a flip-flop FIFO that is N read multiplexers, each DEPTH to 1, with select inputs that are the read pointer plus a constant. The pointer then moves by the number popped, using the same extra wrap bit as Part 1.

Hand-drawn before and after view of an eight-entry multi-pop FIFO: before, the read pointer is at 6 and the window shows A, B, C and D across the wrap; after popping three and pushing F, the read pointer is at slot 1 and the window shows D, E and F with three valid lanes.

The figure shows the case that catches most first attempts. The read pointer is at slot 6 of an eight-entry FIFO, so the window covers slots 6, 7, 0 and 1. A pop of three removes A, B and C, the read pointer moves from 6 to 9 (slot 1 with the wrap bit set), and in the same cycle F is pushed into slot 3. Next cycle the window shows D, E and F, and only three lanes are valid.

For larger FIFOs, the read side can be banked the same way Part 4 banked the write side: N banks interleaved by the low index bits, so the N window entries always come from N different banks. Each bank reads one entry, and an N-input rotator by rptr mod N puts them back in lane order. This is how a multi-pop queue is built on single-read-port memory.

RTL sketch

Flip-flop storage, a combinational head window, a binary pop count that is refused when it asks for more than is stored, and one push per cycle that is accepted at full when at least one entry is popped:

module multi_pop_fifo #(
  parameter int W     = 32,
  parameter int N     = 4,                // pop lanes
  parameter int DEPTH = 16,               // power of two, DEPTH >= N
  localparam int AW   = $clog2(DEPTH),
  localparam int CW   = $clog2(N + 1)
) (
  input  logic                clk,
  input  logic                rst_n,
  input  logic                push,
  input  logic [W-1:0]        wdata,
  output logic                full,
  output logic [N-1:0]        rvalid,     // thermometer, lane 0 oldest
  output logic [N-1:0][W-1:0] rdata,
  input  logic [CW-1:0]       pop_cnt     // 0 to N
);
  logic [W-1:0] mem [DEPTH];
  logic [AW:0]  wptr, rptr;

  wire [AW:0] count = wptr - rptr;
  assign      full  = (count == DEPTH);

  always_comb
    for (int i = 0; i < N; i++) begin
      rvalid[i] = (count > i);
      rdata[i]  = mem[AW'(rptr + i)];
    end

  wire          do_pop  = (pop_cnt <= count);   // refuse an over-ask
  wire [CW-1:0] n_pop   = do_pop ? pop_cnt : '0;
  wire          do_push = push && (!full || n_pop != '0);

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      wptr <= '0;
      rptr <= '0;
    end else begin
      if (do_push) wptr <= wptr + 1'b1;
      rptr <= rptr + n_pop;
    end

  always_ff @(posedge clk)
    if (do_push) mem[wptr[AW-1:0]] <= wdata;
endmodule

When the FIFO is full and the consumer pops, the push writes the slot at wptr, which is the same slot as the window's lane 0. The window is read combinationally in that cycle and the write lands at the clock edge, so the consumer sees the old entry it is popping, and the new one is stored behind the rest.

Corner cases

Hand-drawn timing diagram of a depth-8, four-lane multi-pop FIFO: five pushes raise the count to five, a pop of three drops it to two, a pop of two with a push leaves one, a pop of four with one entry stored is refused, and a pop of one drains it, with the rvalid thermometer shown each cycle.
  • Over-asking. In cycle 7 of the timing diagram the consumer asks for four with only one stored. The sketch refuses the whole pop, which makes the error visible in simulation. Clamping to the count is the forgiving alternative, but it can hide a consumer that misreads rvalid. Either way, add an assertion.
  • The window across the wrap. Lane addresses are rptr + i truncated to the index width. A design that computes them without the truncation reads past the end of the array.
  • Push into the window. A new entry pushed while the FIFO holds fewer than N entries lands inside the window, and appears on its lane the next cycle. It is not visible in the push cycle in this sketch; showing it at once would need a bypass, as in Part 3.
  • Push and pop at full. Allowed when at least one entry pops, as covered above.
  • Pop count of zero. Nothing changes. Make sure the pointer adder does not cause needless toggling when the count is zero.

Timing, area and power

  • Read window. N read multiplexers of DEPTH to 1 is the main area and the main output delay. Banking reduces each bank's mux to DEPTH/N to 1 and adds an N-input rotator.
  • Pop count path. pop_cnt usually comes late from consumer logic that has just examined the window. It drives the compare against count, the pointer adder, and the push accept at full. Precomputing rptr + k for every k and selecting with the late count is a standard fix, and Part 6 builds on it.
  • Count. A registered count removes the pointer subtraction from the valid bits and the compare.
  • Power. The window muxes toggle whenever the read pointer moves. Registering the window output trades a cycle of latency for less glitching downstream.

Verification checklist

  • A reference queue. Every cycle, check every rvalid[i] against "queue holds more than i entries" and every valid rdata[i] against queue element i. Then pop the requested number from the reference.
  • Assertions:
    a_thermo:  assert property (@(posedge clk) disable iff (!rst_n)
                 ((rvalid + 1'b1) & rvalid) == '0);
    a_no_udf:  assert property (@(posedge clk) disable iff (!rst_n)
                 pop_cnt <= $countones(rvalid));
    a_no_ovf:  assert property (@(posedge clk) disable iff (!rst_n)
                 !(push && full && pop_cnt == '0));
  • Coverage of every pop count from 0 to N, pops that cross the end of the array, over-asks, push and pop at full, and the window partly filled.
  • A consumer model that alternates long idle phases (filling the FIFO) with greedy drain phases, so pops of the full N actually happen at every pointer position.

Interview questions

1. How does the consumer tell which window lanes are valid?

A strong answer gives rvalid[i] = count > i, notes that the result is a thermometer, and explains why that prevents holes in the pop.

2. The read pointer is at the last slot. Which entries are in the window?

A strong answer walks through the wrap with truncated addresses and shows the pointer update with the extra wrap bit.

3. What if the consumer asks for more entries than are valid?

A strong answer compares refusing with clamping, and adds an assertion so that the condition is found in simulation rather than hidden.

4. How would you build this on memory with one read port?

A strong answer interleaves N banks by the low index bits, reads one entry per bank, and rotates by rptr mod N, and mentions the matching write side from a multi-push design.

5. The pop count arrives late. What do you change?

A strong answer precomputes the possible next pointers and uses the late count only as a final mux select, and considers a registered count and valid vector.

Where it is used in real chips

Multi-pop queues feed wide decoders and issue logic in processors, packers that assemble wide bus beats from narrow entries in DMA engines and network interfaces, retire logic that removes several completed entries per cycle, and accelerator command queues that dispatch several operations to parallel units. Width-conversion FIFOs, covered in Part 15, are a close relative.

The rest of the series

Part 4 covered the multi-push FIFO, with N entries in per cycle written in lane order.

Part 6 takes the same idea under tight constraints: Rahul Behl's Multi-Pop FIFO challenge, where the pop arrives as a thermometer code and timing and area are what count.

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!