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 Challenge: Thermometer Pop, Timing and Area (FIFO Series, Part 6)

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

This part is built on a challenge from Rahul Behl of Tenstorrent. In a LinkedIn post about how he interviews RTL and DV engineers, he shared three FIFO problems, and he has published all three as PPA challenges on QuickSilicon, where every run comes back with a synthesis and timing report. The first is the Multi-Pop FIFO: one push per cycle, but up to N of the oldest entries can be popped in the same cycle, with the pop given as a thermometer code. The analysis below is our own.

Part 5 built a multi-pop FIFO for correctness: a window of the oldest N entries, a binary pop count, and a pointer that moves by the count. This is Part 6 of the FIFO Series, and here the question changes. The function is the same, but now the pop arrives as a thermometer, and what matters is how fast and how small the design is. That changes where the logic goes.

Key takeaways

  • A thermometer pop needs no popcount. The edge of the thermometer, pop[k-1] && !pop[k], is a one-hot select of the pop size, and "any pop" is simply pop[0].
  • The pop usually arrives late, because the consumer computes it from the window it has just seen. Compute every possible next state for every pop size from registers in advance, and let the pop drive only a final AND-OR select.
  • Keep a registered occupancy count, registered valid bits and a registered full flag. Then the outputs come from flops and the pointers no longer need a wrap bit.
  • A circular buffer moves the pointer and pays for N read muxes. A collapsing queue moves the data and pays for a mux on every entry. The synthesis and timing reports, not intuition, should pick between them.
  • Write down the legality rules for the pop vector (a thermometer, never wider than the valid entries) and check them with assertions.

In this part

The challenge and what it really tests

A working multi-pop FIFO is not hard; Part 5 has one. What a PPA challenge tests is whether you can see where the time and area go. In a multi-pop FIFO there are three costs: the read window (N entries read every cycle), the pointer and count update (which depends on how many were popped), and the flags (valid bits and full, which depend on the new count). The pop input touches the last two, and it is usually the latest-arriving signal in the design, because the consumer decides how many to take after looking at the window.

So the main goal is to keep the path from pop to the registers as short as possible, and the secondary goal is to keep the read window cheap. The thermometer encoding helps with the first, if you use it the right way.

The interface

The write side is a single push with push, wdata and full. The read side shows rdata[N] and a thermometer rvalid[N], as in Part 5. The pop is a vector pop[N-1:0]: setting pop[i] pops lane i, and since only the oldest entries can leave, a legal pop is always a thermometer such as 0000, 0001, 0011 or 0111, and never wider than rvalid. A push at full is accepted when at least one entry pops.

Decoding the thermometer

Hand-drawn table mapping four-bit thermometer pop values 0000 to 1111 to pops of 0 to 4 and to a five-bit one-hot select, with the rules sel[0] equals not pop[0], sel[k] equals pop[k-1] and not pop[k], sel[N] equals pop[N-1], and the note that any pop equals pop[0].

A binary pop count is natural for an adder: rptr + pop_cnt. A thermometer is not, and the first instinct is to convert it to binary with a popcount and then add. That puts a popcount and an adder in series on the latest signal in the design.

The better reading is that the thermometer already tells you the answer, one-hot, at its edge. The pop size is k exactly when bit k-1 is set and bit k is clear. That is one two-input AND gate per possible size, all in parallel, with no carry chain. Two further gifts come for free. Whether anything pops is just pop[0], which is what the push-at-full rule needs. And a pop of the full N is just pop[N-1].

Precompute and select late

Hand-drawn datapath: registers for the read pointer, count, valid bits and full, plus the early push, feed N plus one candidate blocks for pop sizes 0 to N, an AND-OR mux selected by the late pop produces the next state, and the pop only drives the last level.

Once the pop size is a one-hot select, the rest follows. For every possible size k from 0 to N, compute the complete next state from registers alone: the read pointer rptr + k, the count cnt - k plus the push, the valid bits of that count, and its full flag. The push is known early, and its effect on each candidate is fixed: for k of 1 or more, at least one entry pops, so the push is always accepted; for k of 0, it is accepted only when not full. None of the candidates depends on the pop.

The pop then drives a single AND-OR select of width N + 1 in front of each register. The path from pop to a flop is one AND gate for the edge decode and an OR tree of depth about log2(N + 1). Area grows with N times the state width, which is small: a few pointer-wide adders and a handful of N-bit valid vectors.

RTL sketch

A circular buffer with registered count, valid bits and full, all next-state values precomputed per pop size, and the thermometer used only as the final select:

module multi_pop_thermo #(
  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(DEPTH + 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 [N-1:0]        pop          // thermometer, never wider than rvalid
);
  logic [W-1:0]  mem [DEPTH];
  logic [AW-1:0] wptr, rptr;               // no wrap bit: cnt holds occupancy
  logic [CW-1:0] cnt;
  logic [N-1:0]  vld_q;
  logic          full_q;

  // every outcome, from registers and push only
  logic [AW-1:0] rptr_c [N+1];
  logic [CW-1:0] cnt_c  [N+1];
  logic [N-1:0]  vld_c  [N+1];
  logic          full_c [N+1];
  always_comb
    for (int k = 0; k <= N; k++) begin
      rptr_c[k] = rptr + AW'(k);
      cnt_c[k]  = cnt - CW'(k) + CW'((k == 0) ? (push && !full_q) : push);
      for (int i = 0; i < N; i++) vld_c[k][i] = (cnt_c[k] > i);
      full_c[k] = (cnt_c[k] == DEPTH);
    end

  // late pop: the thermometer edge is a one-hot select
  logic [N:0] sel;
  always_comb begin
    sel[0] = !pop[0];
    for (int k = 1; k < N; k++) sel[k] = pop[k-1] && !pop[k];
    sel[N] = pop[N-1];
  end

  logic [AW-1:0] rptr_nx;
  logic [CW-1:0] cnt_nx;
  logic [N-1:0]  vld_nx;
  logic          full_nx;
  always_comb begin
    rptr_nx = '0; cnt_nx = '0; vld_nx = '0; full_nx = 1'b0;
    for (int k = 0; k <= N; k++) begin
      rptr_nx |= {AW{sel[k]}} & rptr_c[k];
      cnt_nx  |= {CW{sel[k]}} & cnt_c[k];
      vld_nx  |= {N{sel[k]}}  & vld_c[k];
      full_nx |= sel[k] & full_c[k];
    end
  end

  wire do_push = push && (!full_q || pop[0]);

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      wptr <= '0; rptr <= '0; cnt <= '0;
      vld_q <= '0; full_q <= 1'b0;
    end else begin
      wptr <= wptr + do_push;
      rptr <= rptr_nx; cnt <= cnt_nx;
      vld_q <= vld_nx; full_q <= full_nx;
    end

  always_ff @(posedge clk)
    if (do_push) mem[wptr] <= wdata;

  always_comb
    for (int i = 0; i < N; i++) rdata[i] = mem[AW'(rptr + i)];
  assign rvalid = vld_q;
  assign full   = full_q;
endmodule

Three choices matter here. The count is a register, so the valid bits and full are flop outputs instead of a pointer subtraction and compare. Because the count carries occupancy, the pointers are plain index-width counters with no wrap bit. And the push path, do_push, depends on pop[0] only through one gate, which keeps the write enable fast even at full.

Circular buffer or collapsing queue

Hand-drawn comparison of a circular buffer, where entries stay put and the read pointer moves, costing N window muxes on the read side, and a collapsing queue, where the head is always entry 0 and all entries shift by k on a pop, costing an N plus one to one mux per entry but giving rdata straight from flops.

The sketch keeps the entries in place and moves a pointer. The output window is then N multiplexers of DEPTH to 1, driven from the registered read pointer. That path starts at a flop and does not involve the pop, but for a deep FIFO it is long and it sits on the consumer's side of the interface.

The alternative is a collapsing queue: the oldest entry always lives in entry 0, and on a pop of k every entry takes the value of the entry k places above it. The same one-hot select from the thermometer drives an N + 1 to 1 mux on every entry. The window is then just entries 0 to N-1, straight from flops, which is the fastest possible output. The cost is a wide mux on every entry, a write position that moves with the count, and power, because every stored entry toggles on every pop.

For a shallow FIFO with a tight output budget, the collapsing queue often wins. For a deep or wide one, the circular buffer is usually smaller and cooler. A challenge that reports area and timing after every run is a good place to measure that crossover for yourself instead of guessing.

Corner cases

  • Illegal pop vectors. A pattern like 0101 decodes to two select bits, and the AND-OR mux would merge two candidates into nonsense. The design relies on the interface rule, so assert it.
  • Pop wider than valid. Popping lane 3 with two entries stored selects a candidate whose count has underflowed. Again an interface rule with an assertion, not extra logic on the late path.
  • Push and pop at full. Any pop with pop[0] set allows the push. The candidates for k of 1 or more already include the push, so the count stays consistent.
  • N equal to DEPTH. The window covers the whole array and a full pop empties it. The candidate for k equal to N then has a pointer that wraps exactly once.

Verification checklist

  • A reference queue checked every cycle against every rvalid bit, every valid rdata lane and full.
  • Interface assertions on the pop and an internal one on the select:
    a_thermo: assert property (@(posedge clk) disable iff (!rst_n)
                ((pop + 1'b1) & pop) == '0);
    a_legal:  assert property (@(posedge clk) disable iff (!rst_n)
                (pop & ~rvalid) == '0);
    a_onehot: assert property (@(posedge clk) disable iff (!rst_n)
                $onehot(sel));
  • Coverage of every pop size at every read pointer position, pops that wrap, push and pop at full, and a full N pop.
  • An equivalence check between the precomputed design and the straightforward Part 5 style design is a strong addition: the two must produce the same outputs for every legal input sequence.

Interview questions

1. How do you turn a thermometer pop into a pointer update without a popcount?

A strong answer finds the edge of the thermometer as a one-hot select and uses it to choose among precomputed pointers, then notes that "any pop" is pop[0].

2. The pop arrives at 70 percent of the cycle. What do you move?

A strong answer precomputes every next state from registers and early inputs, leaves only the final select on the pop path, and registers count, valid bits and full.

3. Circular buffer or collapsing queue?

A strong answer compares read window muxes against per-entry shift muxes, output timing against area and toggle power, and says it would let synthesis and timing reports decide for the given depth and width.

4. What happens with a pop of 0101?

A strong answer shows that the one-hot select breaks, explains why the design should not pay for protection on the late path, and adds an interface assertion.

5. How would you prove the optimized design matches a simple one?

A strong answer proposes a reference queue in simulation plus a formal equivalence or property check against a plain multi-pop model.

Where it is used in real chips

Thermometer-style pops are natural wherever a consumer handles lanes in order and stops at the first one it cannot take: decode and issue stages that consume a prefix of a fetch queue, retire logic that removes completed entries up to the first incomplete one, packet and flit packers in network-on-chip interfaces, and accelerator front ends that dispatch a prefix of a command queue each cycle.

The rest of the series

Part 5 covered the general multi-pop FIFO with a binary pop count and the head window.

Part 7 combines both sides: the multi-push, multi-pop FIFO and its pointer and space management.

If you want to test your own version against a synthesis and timing report, try Rahul Behl's Multi-Pop FIFO challenge on QuickSilicon.

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!