ASIC Point Explore

← RTL Design Interviews

Interview Question · Code Writing

Sizing a FIFO from Burst Arithmetic

L1 JuniorL2 Mid-Levelfifodepthflow control

The interviewer asks

A source writes a burst of 32 words, one per cycle. The reader waits 4 cycles before its first read, then reads one word every 2 cycles. How deep must the FIFO be? Write the calculation so it works for any burst.

Reveal the Model Answer

The FIFO must hold the highest level reached during the burst. Count words written minus words read, cycle by cycle, and take the peak. Here 32 words go in and 14 come out during the burst, so the depth is 18. The run writes that count as a function, then simulates the traffic and sees a peak of 18 with no overflow.

Two Rates and a Buffer Between ThemArrows carry words. The accept logic decides both transfers of a cycle from the count before the edge.
Two rates and a buffer between themArrows carry words. The accept logic decides both transfers of a cycle from the count before the edge. component Producer B words, one percycle queue FIFO DEPTH slots component Consumer waits S, then one perC cycles logic Accept logic full and empty beforethe edge writereadcount
  1. Burst

    For B cycles a word arrives every cycle. The consumer takes one every C cycles, so the count climbs by B - B / C over the burst.

  2. Peak

    The count peaks when the last word arrives. After that the FIFO only drains.

  3. Last word

    If the FIFO is full before the edge where the last word arrives, the accept logic refuses it, even when a word leaves at that edge.

Read the diagram as text
  • Producer: B words, one per cycle
  • FIFO: DEPTH slots
  • Consumer: waits S, then one per C cycles
  • Accept logic: full and empty before the edge
  • Producer → FIFO: write
  • FIFO → Consumer: read
  • FIFO → Accept logic: count

The depth covers the peak of arrivals minus departures, plus what the accept rule needs.

The depth function, and a simulation of two traffic patterns at the depth it gives.

RUNIcarus Verilog · in your browser
Edit the code, then run it

        
Expected: B=32 S=4 P=2: depth_for=18, DEPTH=18, peak level=18, overflow=0, words in order=32 of 32 B=20 S=3 P=3: depth_for=14, DEPTH=14, peak level=14, overflow=0, words in order=20 of 20

        
        
      

          
Self-Check
Tick each key point you covered in your answer.


What Interviewers Listen For (Junior)
A good junior answer counts writes and reads cycle by cycle and gets 18. It notices that the 4-cycle wait matters.


        

      

    

    
  

    

    

    
Cross-Questions

    
Where the interviewer goes next. Open a node to practise that follow-up.

    
WhyWhat IfProve ItCompare

    
    
      
  1. Sizing a FIFO from Burst Arithmetic
    2. 
      
  2. 
    
    WhyWhy a FIFO Needs a Maximum BurstL1 Junior
      
    
      
    Why can no FIFO depth be correct if the writer is faster than the reader forever?
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    A FIFO stores the difference between what came in and what went out. If the writer is faster on average, that difference grows without limit. A FIFO only absorbs bursts: periods of faster writing followed by idle time. For a steady rate mismatch you need backpressure, not depth.
    
    
    A Burst of 16 into a Half-Rate ConsumerCycles 0 to 23 of the burst at DEPTH 16. The ramp climbs while words arrive and drains after the burst ends.
    

    
    
    
  01234567891011121314151617181920212223clkwrite_enread_enused123456787654
    1. Cycle 1
      Cycle 1: a word leaves for the first time. Every two cycles, two arrive and one leaves.
    2. Cycle 15
      Cycle 15: the last of 16 words arrives while the eighth word leaves. The peak is 8, which is 16 - 16 / 2.
    3. Cycle 23
      Cycle 23: with no arrivals, the FIFO drains one word every two cycles. It is empty at cycle 31.
    
    
    Measured with a probe of the lesson's design at DEPTH 16. No word is lost.
    
    
  
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Misconception
    
    
    "A big enough FIFO fixes any rate mismatch."
    
    
    Only a temporary one. The average write rate must not exceed the average read rate, or the FIFO eventually fills.
    
    
    Source Lesson P1.6 review claims (flow control: backpressure, FIFO depth and credits)
    
  
    
    
    3. 

  3. 
    
    What IfFIFO Depth Across Two ClocksL2 Mid-Level
      
    
      
    What if the writer runs at 200 MHz and the reader at 150 MHz, with a 120-word burst?
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    Work in time, not cycles. The burst lasts 120 / 200 MHz = 600 ns. In that time the reader takes about 150 MHz x 600 ns = 90 words, so about 30 must be stored. In an asynchronous FIFO, add the synchronizer delay on the pointers. That is a few cycles in which the reader cannot see new data yet.
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Half-Truth
    
    
    "Divide the two frequencies and multiply by the burst."
    
    
    The ratio alone gives the words read, not the words stored, and it leaves out the pointer-crossing delay. Write both steps down.
    
    
    Source Mehta, ASIC/SoC Functional Design Verification (2018) ch. 8.3.5 Design of an asynchronous FIFO using Gray code counters
    
  
    
    
    4. 

  4. 
    
    WhyWhy Async FIFO Flags Are Late but SafeL2 Mid-Level
      
    
      
    Why is it acceptable that the write side sees the read pointer a few cycles late?
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    A late read pointer looks like fewer reads than really happened. So the write side thinks the FIFO is fuller than it is, and full may stay high a little too long. It never thinks there is space that is not there. The same reasoning makes empty late but safe on the read side.
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Misconception
    
    
    "The delay can make the FIFO overflow."
    
    
    A stale read pointer can only make full assert early or release late. Overflow would need the write side to see reads that have not happened.
    
    
    Source Mehta, ASIC/SoC Functional Design Verification (2018) ch. 8.3.5 Design of an asynchronous FIFO using Gray code counters
    
  
    
    
    5. 

  5. 
    
    What IfSetting an Almost-Full ThresholdL2 Mid-LevelL3 Senior
      
    
      
    What if the source needs a warning before full, because it takes 3 cycles to stop?
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    Raise almost-full when the free space drops to the number of words the source can still send after the warning. Here that is 3, plus any cycles the flag itself takes to reach the source. In an asynchronous FIFO, the flag is already pessimistic, which adds a little margin at no extra cost.
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Delivery
    
    
    "Almost-full at half depth is a good default."
    
    
    The threshold must come from the source's stopping delay. Half depth either wastes space or, for a slow-to-stop source, is not enough.
    
  
    
    
    6. 

  6. 
    
    CompareA Deeper FIFO Versus BackpressureL2 Mid-Level
      
    
      
    Compare sizing the FIFO for the worst burst with letting it apply backpressure to the source.
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    A FIFO sized for the worst burst never stalls the source, which matters when the source cannot wait, such as a sensor. Backpressure keeps the FIFO small, but the source must be able to pause, and throughput drops while it waits. Many designs use both: enough depth for normal bursts, and a ready or credit signal for the rest.
    
    
    The Consumer Stops; the FIFO Fills; the Source Is HeldA 4-entry FIFO between a source that offers one beat per cycle and a consumer that stops for four cycles.
    

    
    validdatareadyouttakeSourceone beat per cycleFIFO4 entriesConsumerstops for 4 cycles
    A lit wire carries a 1. A pill is a transfer in that cycle; slots are the entries held.
    
    
  01234567891011validdataxb0b1b2b3b4b5b6xreadyout_validout_dataxb0b1b2b3b4b5take
    1. Cycle 2
      One beat in, one beat out: the FIFO holds a single beat.
    2. Cycle 3
      The consumer stops. Beats keep arriving, so the FIFO fills.
    3. Cycle 6
      Full. ready drops and the source holds b5: that is backpressure.
    4. Cycle 7
      The consumer takes b1. Room appears only after this edge, so ready is still 0.
    5. Cycle 8
      ready is back and b5 moves. Nothing was lost; the stall cost the source two cycles.
    
    
    Backpressure moves the stall upstream instead of losing data. The source pays with its own cycles.
    
    
    
  
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Half-Truth
    
    
    "Backpressure is always the better design."
    
    
    A camera or ADC produces data whether or not you are ready. For such sources, the only choice is a FIFO deep enough, or lost data.
    
    
    Source Problem R5.2.2 brief (a sensor keeps pushing when the FIFO is full and the extra words are lost)
    
  
    
    
    7. 

  7. 
    
    Prove ItSolve R5.3.1: The Buffer One Stall Too SmallSimulator-graded
      
    Show it, don't just say it: this Silicon Lab problem is graded by the simulator.
    Open Problem R5.3.1
    
    
    8. 
    

  

    
What People Get Wrong
Common wrong answers and why they fail. Run It shows the wrong belief failing on a real simulator.

    
Misconception

    
"Depth = burst x (1 - read rate / write rate) = 32 x (1 - 1/2) = 16."

    
The rate formula ignores the 4 cycles before the first read. Two words are written with nobody reading, so 16 overflows.

    
Run It
      
The same traffic into a FIFO sized by the rate formula.

        
RUNIcarus Verilog · in your browser

        
Edit the code, then run it

          

          

          

        
Expected: B=32 S=4 P=2: depth_for=18, DEPTH=16, peak level=16, overflow=1, words in order=28 of 32 FAIL: the rate formula gave 16 but the wait before the first read needs 18; words were lost

        
        
      

      
See the Fix
// A FIFO of any depth with a level count and a sticky overflow flag.
module sfifo #(parameter int DEPTH = 18, W = 8) (
  input  logic         clk, rst_n, wr_en, rd_en,
  input  logic [W-1:0] wr_data,
  output logic [W-1:0] rd_data,
  output logic         empty, overflow,
  output int           level
);
  logic [W-1:0] mem [0:DEPTH-1];
  int wp, rp;
  logic full;
  assign full    = (level == DEPTH);
  assign empty   = (level == 0);
  assign rd_data = mem[rp];
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      wp <= 0; rp <= 0; level <= 0; overflow <= 0;
    end else begin
      if (wr_en && full) overflow <= 1;          // a word is lost
      if (wr_en && !full) begin mem[wp] <= wr_data; wp <= (wp + 1) % DEPTH; end
      if (rd_en && !empty) rp <= (rp + 1) % DEPTH;
      level <= level + (wr_en && !full) - (rd_en && !empty);
    end
endmodule
module tb;
  // Depth needed = the highest level the FIFO must hold, counted before each write's edge
  // (a write needs room even if a read happens at the same edge).
  function automatic int depth_for(int B, int S, int P);
    int level = 0, peak = 0;
    for (int c = 0; c < B; c++) begin
      level++;                                   // the write of cycle c
      if (level > peak) peak = level;
      if (c >= S && (c - S) % P == 0) level--;   // the read of cycle c
    end
    return peak;
  endfunction
  bench #(.B(32), .S(4), .P(2), .DEPTH(18)) b0 ();
  initial begin
    #2000;
    $display("B=32 S=4 P=2: depth_for=%0d, DEPTH=%0d, peak level=%0d, overflow=%b, words in order=%0d of 32", depth_for(32, 4, 2), b0.DEPTH, b0.peak, b0.overflow, b0.good);
    if (!b0.overflow && b0.good == 32) $display("PASS: depth 18 from the cycle count holds the whole burst");
    $finish;
  end
endmodule
module bench #(parameter int B = 32, S = 4, P = 2, DEPTH = 18) ();
  logic clk = 0, rst_n = 0, wr_en = 0, rd_en = 0, empty, overflow;
  logic [7:0] wr_data = 0, rd_data, want = 0;
  int level, peak = 0, good = 0, c = 0, rd_c = 0;
  always #5 clk = ~clk;
  sfifo #(.DEPTH(DEPTH)) f (.*);
  initial begin
    #12 rst_n = 1;
    repeat (150) begin
      @(negedge clk);
      wr_en = (c < B); wr_data = c;
      rd_en = (c >= S) && ((c - S) % P == 0 || c >= B);   // after the burst, drain every cycle
      #1 if (rd_en && !empty) begin if (rd_data == want) good++; want++; end   // the word this edge reads
      @(posedge clk); #1;
      if (level > peak) peak = level;
      c++;
    end
  end
endmodule

Prints: B=32 S=4 P=2: depth_for=18, DEPTH=18, peak level=18, overflow=0, words in order=32 of 32 PASS: depth 18 from the cycle count holds the whole burst

    

  

    
Delivery

    
"Make it 64 to be safe."

    
Flop-based FIFOs cost area for every entry. A designer must give the number and its reason; a safety factor needs a stated cause, such as an unknown stall.

  

    
Half-Truth

    
"The depth only depends on the two rates."

    
It also depends on the burst length, the reader's start delay, and whether bursts come back to back. Without a maximum burst, no finite depth is enough.

    
Source Lesson R5.3 review claims (depth from burst arithmetic, verified by measurement)

  

    
Learn It, Then Prove It