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-Push, Multi-Pop FIFO: Pointer, Count and Space Management (FIFO Series, Part 7)

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

Part 4 widened the write side of a FIFO and Part 5 widened the read side. Put them together and you get a queue that takes up to M entries and gives up to N entries in the same cycle. Each side is easy on its own. The care goes into how the two sides agree on how full the queue is when both pointers jump by a variable amount in the same cycle, and how much of the other side's activity each decision is allowed to see.

This is Part 7 of the FIFO Series: the multi-push, multi-pop FIFO. We reuse the lane logic from Parts 4 and 5, replace the pointer subtraction with a registered occupancy count, and look closely at one design decision that controls both throughput and timing: whether a push may use the space freed by a pop in the same cycle.

Key takeaways

  • A multi-push, multi-pop FIFO moves the write pointer by the number of entries pushed and the read pointer by the number popped, both in the same cycle.
  • A registered count, updated by n_push - n_pop, gives the valid bits, the space output and both accept decisions straight from flops, and lets the pointers drop the wrap bit.
  • The key choice is space accounting. Without pop credit, the push decision depends only on registers. With pop credit, a full FIFO keeps streaming, but the late pop count feeds the push accept.
  • Without pop credit, the slots written in a cycle can never be slots popped in that cycle, which removes a whole class of same-address hazards.
  • For memory-based storage, B interleaved banks with one read and one write port each, where B is at least M and at least N, keep every cycle conflict-free.

In this part

What problem it solves

Wide pipelines rarely have a wide producer and a narrow consumer for long. A fetch unit that delivers four instructions a cycle into a decode queue is usually drained by a decoder that also takes several per cycle. A router port that receives several flits per cycle forwards several per cycle. If either side of the FIFO is narrower than its neighbor, the FIFO becomes the bottleneck.

The multi-push, multi-pop FIFO keeps one ordered queue between two wide neighbors. Both sides move by variable amounts every cycle, and the structure has to stay correct and fast at every combination, including both sides at full width while the queue is nearly full or nearly empty.

The interface

Hand-drawn block diagram of a multi-push, multi-pop FIFO: four push data lanes and a push count enter the storage, four rdata and rvalid lanes leave it, a pop count comes back from the consumer, and a count block updates cnt by n_push minus n_pop and outputs space.

The write side has push_data[M] and push_cnt from 0 to M, meaning lanes 0 to push_cnt - 1 are valid. Part 4 accepted any valid pattern; a count is used here because it is narrower and most wide producers already compact their lanes. The FIFO outputs space. The read side is Part 5's head window: rdata[N], a thermometer rvalid[N], and pop_cnt from 0 to N.

Pointer and count management

Each pointer moves by its own count: wptr += n_push and rptr += n_pop. Lane i of the push writes slot wptr + i, and lane i of the window shows slot rptr + i. In the example below, an eight-entry FIFO holds A to D with the read pointer at 5. In one cycle the consumer pops two and the producer pushes three. The read pointer moves from 5 to 7, the write pointer from 1 to 4, and the count goes from 4 to 4 + 3 - 2 = 5.

Hand-drawn before and after view of an eight-entry FIFO: before, A, B, C and D are stored from slot 5 around to slot 0; after a push of three and a pop of two in the same cycle, C and D remain and E, F and G occupy slots 1 to 3, with the read pointer at 7, the write pointer at 4 and the count at 5.

With two variable steps per cycle, deriving the count from the pointers each cycle means a subtraction followed by compares on the valid bits and space, all on the output path. A registered count is cheaper in time and simple to update. Once the count holds the occupancy, the pointers no longer need the extra wrap bit from Part 1, because full and empty are read from the count.

Space accounting: with or without pop credit

Hand-drawn comparison of two space rules: conservative, where room is DEPTH minus cnt and the push decision comes from flops only, and pop credit, where room adds the same-cycle pop count, giving full throughput near the top at the cost of a late pop count feeding the push accept.

The push side must decide whether push_cnt entries fit. There are two rules.

  • Conservative: room is DEPTH - cnt. The decision comes from a register and the producer's own count, so it is fast and the producer can even use a registered space a cycle early. The price is that pops in the current cycle are not counted, so a nearly full FIFO refuses a push that would have fit after the pop.
  • Pop credit: room is DEPTH - cnt + n_pop. A full FIFO with a consumer popping every cycle keeps accepting pushes at full rate. The price is that the pop count, which usually arrives late from the consumer's logic, now feeds the push accept and the write enables.

There is a second, quieter benefit to the conservative rule. Writes go only to free slots and pops only to stored ones, so without pop credit the slots written in a cycle are never the slots popped in that cycle. With pop credit they can be, and the storage must return the old value for the window in that cycle, which flops do but some memories do not.

RTL sketch

Flip-flop storage, a power-of-two depth, a registered count, all-or-nothing accept on both sides, and a parameter that selects the space rule:

module mpmp_fifo #(
  parameter int W          = 32,
  parameter int M          = 4,            // push lanes
  parameter int N          = 4,            // pop lanes
  parameter int DEPTH      = 16,           // power of two, at least M and N
  parameter bit POP_CREDIT = 1'b0,
  localparam int AW = $clog2(DEPTH),
  localparam int CW = $clog2(DEPTH + 1),
  localparam int MW = $clog2(M + 1),
  localparam int NW = $clog2(N + 1)
) (
  input  logic                clk,
  input  logic                rst_n,
  input  logic [MW-1:0]       push_cnt,    // lanes 0 .. push_cnt-1 valid
  input  logic [M-1:0][W-1:0] push_data,
  output logic [CW-1:0]       space,
  output logic [N-1:0]        rvalid,      // thermometer, lane 0 oldest
  output logic [N-1:0][W-1:0] rdata,
  input  logic [NW-1:0]       pop_cnt
);
  logic [W-1:0]  mem [DEPTH];
  logic [AW-1:0] wptr, rptr;               // no wrap bit: cnt holds occupancy
  logic [CW-1:0] cnt;

  assign space = DEPTH - cnt;

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

  wire          do_pop  = (pop_cnt <= cnt);
  wire [NW-1:0] n_pop   = do_pop ? pop_cnt : '0;
  wire [CW:0]   room    = space + (POP_CREDIT ? n_pop : '0);
  wire          do_push = (push_cnt <= room);
  wire [MW-1:0] n_push  = do_push ? push_cnt : '0;

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      wptr <= '0;
      rptr <= '0;
      cnt  <= '0;
    end else begin
      wptr <= wptr + n_push;
      rptr <= rptr + n_pop;
      cnt  <= cnt + n_push - n_pop;
    end

  always_ff @(posedge clk)
    for (int i = 0; i < M; i++)
      if (i < n_push) mem[AW'(wptr + i)] <= push_data[i];
endmodule

A refused pop (an over-ask) also removes its credit, so the push side never counts space that was not freed. The window is read combinationally and the writes land at the clock edge, so with pop credit a slot that is popped and rewritten in the same cycle still shows the popped entry to the consumer.

Corner cases

  • Full and both sides at full width. Without pop credit the push is refused for a cycle and the queue drains below full; with it, M entries enter as N leave. Check that the count never exceeds DEPTH in either mode.
  • Empty and both sides active. A push into an empty FIFO is not visible in the window in the same cycle, so a pop count above zero is refused. Bypassing new entries into the window is possible but puts the push lanes on the output path.
  • Both pointers wrapping in one cycle. With variable steps, both can cross the end of the array together. Index arithmetic truncated to the index width handles it; the registered count makes full and empty independent of the wrap.
  • M and N different. With M of 4 and N of 2, the FIFO fills whenever the producer runs at full rate. That is the producer's problem to throttle, through space.

Timing, area and power

  • Accept paths. Without pop credit, push_cnt against space is a short compare from flops. With pop credit, add the pop count path; the precompute-and-select trick from Part 6 applies here too, with candidates for each pop size.
  • Count update. cnt + n_push - n_pop is a three-input add. For wide counts, compute cnt + j - k for all small j and k in parallel and select.
  • Storage. Flip-flops need M write muxes per entry and N window muxes. For memory, use B banks interleaved by the low index bits, with B at least max(M, N) and one read and one write port per bank; M consecutive writes and N consecutive reads then never collide within a bank's ports.
  • Power. Only written entries are enabled. The window muxes toggle with every read pointer move, which is significant at large N.

Verification checklist

  • A reference queue, checked every cycle on every window lane and valid bit and on space, then updated with the accepted pops and pushes in that order.
  • Assertions:
    a_cnt_max: assert property (@(posedge clk) disable iff (!rst_n)
                 cnt <= DEPTH);
    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_cnt <= space + (POP_CREDIT ? pop_cnt : 0));
  • Run every test in both POP_CREDIT modes. Cover full with both sides at full width, credit actually used, refused pushes and pops, and both pointers wrapping in the same cycle.
  • Traffic phases that fill, drain and run both sides at maximum, so the boundaries are hit at every pointer position.

Interview questions

1. Why keep a registered count instead of subtracting pointers?

A strong answer points to the variable steps on both pointers, the subtraction and compares on the output path, and the fact that a count also removes the wrap bit.

2. Should a push be allowed to use space freed by a pop in the same cycle?

A strong answer weighs throughput near full against the late pop path into the push accept, and mentions the same-slot read and write case that pop credit creates.

3. How many banks do you need for M pushes and N pops per cycle?

A strong answer gives at least max(M, N) banks with one read and one write port each, interleaved by the low index bits, and explains why consecutive slots never collide.

4. Can a pushed entry be popped in the same cycle?

A strong answer says not in this design, explains the bypass that would allow it, and names the timing cost of putting push lanes on the output path.

5. How do you verify all the combinations?

A strong answer uses a reference queue, both parameter settings, phase-based traffic, and coverage crosses of push count, pop count and occupancy near the boundaries.

Where it is used in real chips

Queues with several entries in and out per cycle sit between the fetch and decode stages of wide processors, in issue and load-store queues, in network-on-chip routers with wide internal datapaths, in DMA engines that both gather and scatter several beats per cycle, and between the stages of accelerators that process several elements per cycle.

The rest of the series

Part 6 worked through the Multi-Pop FIFO challenge, with a thermometer-coded pop and a focus on timing and area.

Part 8 drops the power-of-two assumption: the non-power-of-two FIFO, with explicit wraparound and exact capacity.

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!