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 FIFO Design: N Entries In per Cycle, Still in Order (FIFO Series, Part 4)

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

Parts 1 to 3 moved one entry per cycle on each side. That is enough for many blocks, but not for a wide front end that decodes four instructions a cycle, a network interface that splits a wide bus into several narrow flits, or a gather engine that collects several results at once. All of them need to put more than one entry into a FIFO in the same cycle, and they need those entries to come out in the order the lanes define.

This is Part 4 of the FIFO Series: the multi-push FIFO. We add N write lanes to the synchronous FIFO from Part 1, work out where each lane's entry goes when only some lanes are valid, and look at how to build the storage so that N writes per cycle do not cost N write ports on every entry.

Key takeaways

  • A multi-push FIFO accepts up to N entries per cycle. Lane order defines age: lane 0 is the oldest of the cycle, then lane 1, and so on.
  • Each valid lane writes to wptr + offset, where the offset is the number of valid lanes below it. A prefix popcount turns any valid pattern into gap-free, in-order writes.
  • The write pointer moves by the number of valid lanes, not by N, and wraps with the same extra bit as in Part 1.
  • Flow control is about space, not a single full flag. Expose a free-entry count, and decide whether a push that does not fit is rejected whole or split.
  • Interleaving the storage across N banks means N consecutive slots always land in N different banks, so each bank needs only one write port.

In this part

What problem it solves

If a producer can generate four entries a cycle and the FIFO only accepts one, the producer needs its own serializer and loses three quarters of its bandwidth whenever it is busy. Putting four single-push FIFOs side by side does not help either, because the order between them is lost: the consumer cannot tell whether the next oldest entry sits in FIFO 2 or FIFO 3 without extra bookkeeping.

A multi-push FIFO keeps one queue and one order, and simply lets several entries enter it in the same cycle. The consumer side can stay a plain single pop, as in this part, or become multi-pop, which is Part 5.

The interface

Hand-drawn block diagram of a multi-push FIFO: four push lanes with valid and data enter a prefix popcount block that produces per-lane offsets and a lane count, the storage receives writes at the write pointer plus 0, 1 and 2, a single pop side gives rdata and empty, and the pointer block outputs space.

The write side has push_vld[N-1:0] and push_data[N]. The read side is the same as Part 1: pop, rdata and empty. In place of a single full, the FIFO outputs space, the number of free entries. The producer may push at most space entries in a cycle.

Two questions need an answer in the spec. First, must the valid lanes be contiguous from lane 0, or can any pattern appear? Allowing any pattern costs a small prefix count, and saves every producer from compacting its own lanes, so we allow it. Second, what happens if the producer sends more entries than there is space for? The sketch below rejects the whole vector, which keeps the producer's retry logic simple. Accepting the first space lanes and returning a per-lane ready is the other option; it uses the space better but makes the producer track partial acceptance.

Micro-architecture: offsets and storage

Every valid lane needs a distinct, consecutive slot. The offset of lane i is the number of valid lanes with a lower index, which is a prefix popcount of the valid vector. Lane i writes to wptr + off[i], and the write pointer moves forward by the total count. The figure works through one cycle with lanes 0, 1 and 3 valid and the write pointer at 6 in an eight-entry FIFO: a goes to slot 6, b to slot 7, and d wraps to slot 0. Lane 2 is invalid, so it leaves no gap.

Hand-drawn worked example: push_vld is 1011, lanes 0, 1 and 3 get offsets 0, 1 and 2, and with the write pointer at 6 in an eight-entry FIFO their data goes to slots 6, 7 and 0, wrapping, with the next write pointer at 9.

The storage is the interesting part. With flip-flops, the straightforward version gives every entry an N-to-1 write mux: entry k takes lane i if wptr + off[i] equals k. That works and is fine for small FIFOs, but the decode and mux grow with DEPTH times N.

The banked version splits the storage into N banks by the low bits of the index, so slot k lives in bank k mod N. Since a cycle writes at most N consecutive slots, each bank receives at most one write. The lanes are first compacted (lane order by offset), then rotated by wptr mod N, and each bank takes one rotated lane at one address. The rotation is a barrel shifter of N inputs, and every bank keeps a single write port. This is also how a multi-push FIFO is built on SRAM, where extra write ports are very expensive.

Hand-drawn view of a four-bank storage: the compacted lanes a, b and d are rotated by the write pointer mod 4, which is 2, so bank 2 gets a, bank 3 gets b, bank 0 gets d and bank 1 gets nothing, each bank needing a single write port.

RTL sketch

Flip-flop storage, any valid pattern, all-or-nothing accept, and a registered single pop. DEPTH is a power of two and at least N:

module multi_push_fifo #(
  parameter int W     = 32,
  parameter int N     = 4,                // push 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 [N-1:0]        push_vld,   // any pattern; lane 0 is oldest
  input  logic [N-1:0][W-1:0] push_data,
  output logic [AW:0]         space,      // free entries
  input  logic                pop,
  output logic [W-1:0]        rdata,
  output logic                empty
);
  logic [W-1:0]  mem [DEPTH];
  logic [AW:0]   wptr, rptr;
  logic [CW-1:0] off [N];
  logic [CW-1:0] cnt_in;

  always_comb begin                        // prefix popcount
    cnt_in = '0;
    for (int i = 0; i < N; i++) begin
      off[i] = cnt_in;
      cnt_in = cnt_in + push_vld[i];
    end
  end

  wire [AW:0] count   = wptr - rptr;
  assign      space   = DEPTH - count;
  assign      empty   = (count == '0);
  wire        do_push = (cnt_in != '0) && (cnt_in <= space);
  wire        do_pop  = pop && !empty;

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

  always_ff @(posedge clk) begin
    for (int i = 0; i < N; i++)
      if (do_push && push_vld[i])
        mem[AW'(wptr + off[i])] <= push_data[i];
    if (do_pop) rdata <= mem[rptr[AW-1:0]];
  end
endmodule

The AW'(...) cast truncates the sum to the index width, which is the wraparound. The writes in one cycle always go to distinct free slots, so the loop never writes the same entry twice, and it never touches the slot being read, because a pop needs at least one stored entry and the writes only go to free slots.

Corner cases

  • Sparse valid patterns. Patterns like 1010 or 1000 must produce gap-free writes. A design that writes lane i to wptr + i leaves holes that the reader will later pop as garbage.
  • Writes that wrap. A multi-entry write can straddle the end of the array, as in the example. The wrap bit flips once even though only some of the lanes crossed.
  • Not enough space. With all-or-nothing accept, three valid lanes and two free entries means nothing is written that cycle. The producer must see that and hold its data. An assertion on the producer side catches pushes beyond space.
  • Same-cycle pop. The sketch computes space without the pop of the same cycle, which is simple and slightly conservative. Counting the pop raises throughput near full, at the cost of a longer path from pop to the accept decision.
  • Zero valid lanes. do_push is low, and nothing changes. Make sure no write enable fires for an all-zero vector in a banked design either.

Timing, area and power

  • Prefix count. For N of 4 or 8, a ripple of small adders is short. For wider N, use a parallel prefix structure. The offsets feed the write address of every lane, so this is on the write path.
  • Accept decision. cnt_in <= space needs both the popcount and the pointer subtraction. A registered space or a registered "room for N" flag shortens it, and many producers only need the latter.
  • Write muxing. The per-entry N-to-1 mux is the main area cost of a flip-flop version. Banking replaces it with one N-input rotator and plain single-port banks.
  • Power. Only the written entries or banks should be enabled. In the banked version, a bank with no lane this cycle stays idle.

Verification checklist

  • A reference queue that appends valid lanes in lane order each accepted cycle, and checks every pop against it.
  • Assertions:
    a_no_ovf:  assert property (@(posedge clk) disable iff (!rst_n)
                 $countones(push_vld) <= space);
    a_no_udf:  assert property (@(posedge clk) disable iff (!rst_n)
                 !(pop && empty));
    a_space:   assert property (@(posedge clk) disable iff (!rst_n)
                 space <= DEPTH);
  • Coverage of every valid pattern (2 to the N of them), writes that wrap, pushes rejected for lack of space, all N lanes at once, and push with a same-cycle pop at the boundary.
  • In a banked design, an assertion that no bank receives two writes in a cycle.

Interview questions

1. Lanes 0 and 2 are valid and lane 1 is not. Where does lane 2 go?

A strong answer computes the offset as the number of valid lanes below, so lane 2 goes to wptr + 1, and explains that this is a prefix popcount.

2. How do you avoid N write ports on every entry?

A strong answer describes banking by the low index bits, explains why N consecutive slots hit N different banks, and describes the compaction and rotation in front of the banks.

3. What does the producer see when there is room for two entries but it has three?

A strong answer compares all-or-nothing accept with partial accept and per-lane ready, and talks about the producer's retry logic in each case.

4. Where is the critical path?

A strong answer names the prefix count feeding the write addresses and the accept compare against space, and suggests registered space or a registered "room for N" flag.

5. How would you verify ordering?

A strong answer uses a reference queue appended in lane order, covers all valid patterns and wrap cases, and adds a bank-conflict assertion for a banked build.

Where it is used in real chips

Multi-push FIFOs appear wherever a wide producer feeds an ordered queue: instruction fetch and decode queues in processors, load and store queues that allocate several entries per cycle, network-on-chip interfaces that split a wide packet into flits, DMA engines that gather several completions, and accelerators that collect results from parallel lanes into one output stream.

The rest of the series

Part 3 covered the first-word fall-through FIFO, with the head entry on the output before any pop.

Part 5 turns the problem around: the multi-pop FIFO, which releases up to N of the oldest entries in one cycle.

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!