RTL Design Patterns · Chapter 7 · FIFO Design
FIFO Depth Calculation
How deep should a FIFO be? A FIFO exists to absorb the mismatch between a producer and a consumer that do not run at the same instantaneous rate, so the depth is not a guess or a round number. It is a rate-matching calculation over the worst-case burst window. During that burst the FIFO must hold every word that arrives faster than it drains, so the minimum depth is the words written during the window minus the words read during it, rounded up and usually pushed to a power of two for the pointer scheme. Size it by the average rate instead of the burst and the FIFO overflows on exactly the burst it was built to absorb, while passing every steady-state test. This lesson derives the formula, works an example, and proves the depth with a stress testbench, in SystemVerilog, Verilog, and VHDL.
Intermediate14 min readRTL Design PatternsFIFODepth CalculationRate MatchingBurst SizingOverflow
Chapter 7 · Section 7.4 · FIFO Design
1. The Engineering Problem
You are dropping a FIFO between two blocks and someone has to fill in one parameter: DEPTH. In 7.1 you built the circular buffer that holds those DEPTH words; in 7.2 you built the full and empty flags that guard the boundary. Neither told you what DEPTH should be — they both assumed it was already chosen. Now it is your call, and it is the call that actually decides whether the FIFO does its job, because a FIFO that is one slot too shallow drops data and a FIFO that is far too deep wastes silicon on every instance you place.
Here is the concrete situation. A framing block hands words to a compressor over a shared datapath. When a frame arrives, the framer streams a burst — one word every cycle for twelve cycles straight — and then goes quiet until the next frame. The compressor is slower per word: it takes three cycles to fold each word in, so it drains one word every three cycles. Both sit on the same clock. Averaged over a whole frame the compressor keeps up easily — it consumes far fewer than one word per cycle and the framer is idle most of the time — so the naive read is "the reader keeps up, a couple of buffer slots will do."
That read is exactly the trap. Averages describe the long run; the FIFO lives and dies on the burst. During those twelve back-to-back writes the framer produces one word per cycle while the compressor drains only one word every three cycles, so words pile up faster than they leave for the entire length of the burst. If the buffer is too small to hold the pile-up, the framer's next write has nowhere to go: full is asserted, the write is refused, and a word is lost — silently, because nothing in the FIFO raises an error when a producer's write is blocked. The only cure is to make DEPTH large enough to hold the worst-case pile-up. So the question "how deep?" is really the question "how many words can arrive faster than they drain, in the worst window the system can produce?" — and that is a calculation, not a guess.
// Framer streams a BURST: 1 word/cycle for BURST cycles, then idle.
// BURST = 12 words back-to-back
// Compressor DRAINS 1 word every RD_EVERY cycles during the burst.
// RD_EVERY = 3 -> it takes 1 word out every 3 cycles
// WRONG - size by the AVERAGE rate ("reader keeps up, a few slots is plenty"):
// localparam DEPTH = 4; // works on average -> OVERFLOWS on the burst
// RIGHT - size by the WORST-CASE burst: hold every word that arrives faster than
// it drains, over the burst window.
// words in during burst = BURST = 12
// words out during burst = floor(BURST/RD_EVERY) = floor(12/3) = 4
// min depth = words_in - words_out = 12 - 4 = 8
// localparam DEPTH = 8; // exactly holds the worst-case pile-up
// The depth comes from the SYSTEM rates (BURST, RD_EVERY), not from the FIFO.2. Mental Model
3. Pattern Anatomy
The calculation has one shape — words in minus words out over the worst-case window — and three canonical forms depending on how the traffic is described. Learn the shape once; the forms are the same subtraction wearing different units.
Form (a) — same-clock, burst length and drain interval. The producer writes one word per cycle for BURST cycles (a back-to-back burst), and the consumer drains one word every RD_EVERY cycles. Over the burst window the words written are BURST; the words drained are how many read-events fit in the window, which is floor(BURST / RD_EVERY). So the minimum depth is BURST minus floor(BURST / RD_EVERY). For the running example — BURST = 12, RD_EVERY = 3 — that is 12 minus floor(12/3) = 12 minus 4 = 8. This is the form interviewers use because the arithmetic is exact and the window is unambiguous: the reader drains during the burst, and the floor is because a partial read-interval at the end of the window has not completed a pop.
Form (b) — rate ratio over a burst duration. When the traffic is given as rates, the producer writes at Wr words per unit time, the consumer reads at Rd words per unit time, and the burst lasts T. The pile-up is the excess fill rate times the duration: min depth = ceil((Wr minus Rd) times T). For example a source pushing 100 Mwords/s into a sink draining 75 Mwords/s over a 2 microsecond burst needs ceil((100 minus 75) times 2) = 50 words, rounded up to a power of two: 64. Form (a) is just form (b) with Wr = 1 word/cycle and Rd = 1/RD_EVERY words/cycle over T = BURST cycles.
Form (c) — idle-cycle / duty-cycle patterns. Real producers are rarely a clean back-to-back burst; a source might present a valid word W of every P cycles (a duty cycle) while the reader takes one every RD_EVERY. The rule is unchanged — count words in and words out over the busiest window the traffic allows — but you must find that busiest window, which is where the producer's valid-cycle pattern is densest against the reader's slowest drain. Getting the window wrong here is the classic over/under-size error (§6).
Depth is a rate-mismatch calculation — from system rates to a power-of-two DEPTH
data flowThe heart of the whole page is why the peak occupancy equals that subtraction, and it is worth watching the occupancy rise and fall across the burst. During the burst the producer adds one word per cycle and the consumer removes one word every RD_EVERY cycles, so the net fill is positive and the occupancy climbs; it reaches its peak at the end of the burst, the instant before the producer goes idle; then the producer stops but the consumer keeps draining, so the occupancy falls back to zero. The peak — and only the peak — is what the depth must cover.
Occupancy during the burst — it fills, peaks at the required depth, then drains
data flowTwo anatomy details close the picture. First, the floor in form (a) is not a rounding convenience — it is because a read-interval that has not fully elapsed by the end of the burst has not produced a pop, so it does not count against the pile-up; miscounting it is a real off-by-one (§7's second row). Second, the depth you compute is a minimum: it is the smallest FIFO that survives one worst-case burst with the reader draining as modelled. Production depths add margin on top — for back-to-back bursts with no idle gap, for a reader that occasionally stalls longer than nominal, and for the power-of-two rounding the pointer scheme wants. The formula gives the floor of the answer; engineering judgment sets the ceiling.
4. Real RTL Implementation
This is the core of the page. We build three things — (a) the depth FORMULA expressed in code (a localparam/function that computes DEPTH from BURST and RD_EVERY), (b) a parameterized FIFO (the 7.1 architecture, DEPTH generic) instantiated at that computed depth, and (c) a STRESS testbench that drives the worst-case write-burst / read-drain pattern and self-checks no overflow at DEPTH and overflow at DEPTH-1 — and each is shown in SystemVerilog, Verilog, and VHDL with RTL and a self-checking clocked testbench. The reasoning is identical in all three; only the syntax differs.
One discipline runs through every block: the FIFO's own full gate is what converts an under-size into a visible overflow. A correctly gated FIFO never corrupts data — when it is too shallow it refuses the write and asserts an overflow strobe (a dropped-write indicator). So the stress test does not look for corrupted memory; it looks for a refused write during the burst, which is exactly a dropped word. At the right DEPTH no write is ever refused; at DEPTH-1 the peak-word write is refused and overflow fires.
4a. The depth formula and the parameterized FIFO
The FIFO is the 7.1 circular buffer with WIDTH and DEPTH generic, plus one addition: an overflow output that pulses whenever a write is requested while full (a word that would have been dropped). The depth itself is computed by a localparam/function from the traffic parameters BURST and RD_EVERY, so changing the system rates re-sizes the FIFO automatically.
First, the formula alone — a pure, reusable function that turns the worst-case traffic into a minimum depth. It is words_in minus words_out over the burst, with integer division supplying the floor; a caller then rounds up to a power of two for the pointer scheme.
// min depth = BURST - floor(BURST/RD_EVERY). This is the ENTIRE calculation:
// words written during the burst, minus words the reader drains during the burst.
function automatic int fifo_min_depth(int burst, int rd_every);
return burst - (burst / rd_every); // integer division floors -> words_out
endfunction
// Round the minimum UP to a power of two for the 7.2 extra-MSB pointer scheme.
function automatic int round_pow2(int n);
int p = 1;
while (p < n) p <<= 1; // smallest 2**k >= n
return p;
endfunction
// For BURST=12, RD_EVERY=3: fifo_min_depth = 12 - 4 = 8; round_pow2(8) = 8 (already 2**3).
// For BURST=20, RD_EVERY=4: fifo_min_depth = 20 - 5 = 15; round_pow2(15) = 16.Now the parameterized FIFO, sized to that computed depth and carrying the overflow strobe.
// The depth FORMULA in code: min depth = BURST - floor(BURST/RD_EVERY), the
// worst-case pile-up over the burst window. A function makes the intent explicit.
package fifo_depth_pkg;
function automatic int fifo_min_depth(int burst, int rd_every);
// words written during the burst = burst;
// words drained during the burst = burst / rd_every (integer floor);
return burst - (burst / rd_every); // words_in - words_out
endfunction
endpackage
module sync_fifo import fifo_depth_pkg::*; #(
parameter int WIDTH = 8,
parameter int BURST = 12, // producer streams BURST words 1/cycle
parameter int RD_EVERY = 3, // consumer drains 1 word / RD_EVERY cycles
// DEPTH is DERIVED from the system rates, then bumped to a power of two elsewhere.
parameter int DEPTH = fifo_min_depth(BURST, RD_EVERY), // = 12 - 4 = 8
localparam int AW = $clog2(DEPTH)
)(
input logic clk,
input logic rst, // synchronous, active-high
input logic wr_en,
input logic [WIDTH-1:0] wr_data,
output logic full,
output logic overflow, // pulses on a REFUSED write = dropped word
input logic rd_en,
output logic [WIDTH-1:0] rd_data,
output logic empty
);
logic [WIDTH-1:0] mem [DEPTH];
logic [AW-1:0] wptr, rptr;
logic [AW:0] count; // occupancy 0..DEPTH (AW+1 bits)
assign full = (count == DEPTH[AW:0]);
assign empty = (count == '0);
// overflow = a write was requested with no room. A correctly-sized FIFO never
// asserts this; an under-sized one asserts it on the worst-case burst.
assign overflow = wr_en & full;
wire do_write = wr_en & ~full;
wire do_read = rd_en & ~empty;
always_ff @(posedge clk) begin
if (rst) begin
wptr <= '0; rptr <= '0; count <= '0;
end else begin
if (do_write) begin
mem[wptr] <= wr_data;
wptr <= wptr + 1'b1;
end
if (do_read)
rptr <= rptr + 1'b1;
case ({do_write, do_read})
2'b10: count <= count + 1'b1;
2'b01: count <= count - 1'b1;
default: count <= count;
endcase
end
end
assign rd_data = mem[rptr]; // FWFT-style combinational read
endmoduleThe stress testbench is where the flagship claim is proven. It drives the exact worst-case pattern — wr_en high for BURST back-to-back cycles while rd_en fires once every RD_EVERY cycles — and it does this twice: once against the FIFO sized to the computed DEPTH (expecting no overflow), and once against a FIFO one slot shallower (expecting overflow). It also tracks a reference occupancy and asserts the observed peak equals the predicted DEPTH.
module fifo_depth_tb import fifo_depth_pkg::*;;
localparam int WIDTH = 8;
localparam int BURST = 12;
localparam int RD_EVERY = 3;
localparam int DEPTH = fifo_min_depth(BURST, RD_EVERY); // 8
int errors = 0;
// Two DUTs driven by the SAME stimulus: one at DEPTH, one at DEPTH-1.
logic clk = 0, rst = 1, wr_en = 0, rd_en = 0;
logic [WIDTH-1:0] wr_data;
logic full_ok, empty_ok, ovf_ok, full_sm, empty_sm, ovf_sm;
logic [WIDTH-1:0] rd_ok, rd_sm;
sync_fifo #(.WIDTH(WIDTH), .BURST(BURST), .RD_EVERY(RD_EVERY), .DEPTH(DEPTH)) dut_ok (
.clk(clk), .rst(rst), .wr_en(wr_en), .wr_data(wr_data), .full(full_ok),
.overflow(ovf_ok), .rd_en(rd_en), .rd_data(rd_ok), .empty(empty_ok));
sync_fifo #(.WIDTH(WIDTH), .BURST(BURST), .RD_EVERY(RD_EVERY), .DEPTH(DEPTH-1)) dut_small (
.clk(clk), .rst(rst), .wr_en(wr_en), .wr_data(wr_data), .full(full_sm),
.overflow(ovf_sm), .rd_en(rd_en), .rd_data(rd_sm), .empty(empty_sm));
always #5 clk = ~clk;
// Latch whether EITHER FIFO ever refused a write during the run.
logic ovf_seen_ok = 0, ovf_seen_sm = 0;
int occ_model = 0, peak_model = 0; // reference occupancy of the correct FIFO
always @(posedge clk) if (!rst) begin
if (ovf_ok) ovf_seen_ok <= 1;
if (ovf_sm) ovf_seen_sm <= 1;
// reference occupancy: +1 on an accepted write, -1 on an accepted read
if ((wr_en && !full_ok) && !(rd_en && !empty_ok)) occ_model <= occ_model + 1;
else if ((rd_en && !empty_ok) && !(wr_en && !full_ok)) occ_model <= occ_model - 1;
if (occ_model > peak_model) peak_model <= occ_model;
end
initial begin
@(negedge clk); rst = 0;
// WORST-CASE PATTERN: wr_en high for BURST cycles; rd_en once every RD_EVERY.
for (int t = 0; t < BURST; t++) begin
@(negedge clk);
wr_en = 1'b1;
wr_data = t[WIDTH-1:0];
rd_en = ((t + 1) % RD_EVERY == 0); // a completed read every RD_EVERY cycles
end
@(negedge clk); wr_en = 0;
// Let the reader drain the rest.
for (int t = 0; t < BURST; t++) begin
@(negedge clk); rd_en = ((t + 1) % RD_EVERY == 0);
end
@(negedge clk); rd_en = 0;
// ASSERTIONS: the computed DEPTH is SUFFICIENT (no overflow) and MINIMAL (DEPTH-1 overflows).
assert (!ovf_seen_ok)
else begin $error("DEPTH=%0d overflowed on the worst-case burst - under-sized", DEPTH); errors++; end
assert (ovf_seen_sm)
else begin $error("DEPTH-1=%0d did NOT overflow - depth is not minimal / model wrong", DEPTH-1); errors++; end
assert (peak_model == DEPTH)
else begin $error("peak occupancy %0d != predicted DEPTH %0d", peak_model, DEPTH); errors++; end
if (errors == 0)
$display("PASS: no overflow at DEPTH=%0d, overflow at DEPTH-1=%0d, peak occupancy == DEPTH", DEPTH, DEPTH-1);
else
$display("FAIL: %0d errors", errors);
$finish;
end
endmoduleThe Verilog form is the same in intent; AW is passed as a parameter, the depth is a localparam computed with integer arithmetic, and the two-DUT stress test uses $display("FAIL") instead of assert. The overflow strobe and the worst-case pattern are identical.
module sync_fifo #(
parameter WIDTH = 8,
parameter BURST = 12,
parameter RD_EVERY = 3,
// min depth = BURST - floor(BURST/RD_EVERY); integer division floors automatically.
parameter DEPTH = BURST - (BURST / RD_EVERY), // = 12 - 4 = 8
parameter AW = 3 // = clog2(DEPTH); set by instantiator
)(
input wire clk,
input wire rst,
input wire wr_en,
input wire [WIDTH-1:0] wr_data,
output wire full,
output wire overflow, // pulses on a refused write
input wire rd_en,
output wire [WIDTH-1:0] rd_data,
output wire empty
);
reg [WIDTH-1:0] mem [0:DEPTH-1];
reg [AW-1:0] wptr, rptr;
reg [AW:0] count; // 0..DEPTH
assign full = (count == DEPTH[AW:0]);
assign empty = (count == {(AW+1){1'b0}});
assign overflow = wr_en & full; // a dropped word
wire do_write = wr_en & ~full;
wire do_read = rd_en & ~empty;
always @(posedge clk) begin
if (rst) begin
wptr <= {AW{1'b0}}; rptr <= {AW{1'b0}}; count <= {(AW+1){1'b0}};
end else begin
if (do_write) begin mem[wptr] <= wr_data; wptr <= wptr + 1'b1; end
if (do_read) rptr <= rptr + 1'b1;
case ({do_write, do_read})
2'b10: count <= count + 1'b1;
2'b01: count <= count - 1'b1;
default: count <= count;
endcase
end
end
assign rd_data = mem[rptr];
endmodule module fifo_depth_tb;
parameter WIDTH = 8;
parameter BURST = 12;
parameter RD_EVERY = 3;
parameter DEPTH = BURST - (BURST / RD_EVERY); // 8
reg clk, rst, wr_en, rd_en;
reg [WIDTH-1:0] wr_data;
wire full_ok, empty_ok, ovf_ok, full_sm, empty_sm, ovf_sm;
wire [WIDTH-1:0] rd_ok, rd_sm;
reg ovf_seen_ok, ovf_seen_sm;
integer t, errors, occ_model, peak_model;
sync_fifo #(.WIDTH(WIDTH), .BURST(BURST), .RD_EVERY(RD_EVERY), .DEPTH(DEPTH), .AW(3)) dut_ok (
.clk(clk), .rst(rst), .wr_en(wr_en), .wr_data(wr_data), .full(full_ok),
.overflow(ovf_ok), .rd_en(rd_en), .rd_data(rd_ok), .empty(empty_ok));
sync_fifo #(.WIDTH(WIDTH), .BURST(BURST), .RD_EVERY(RD_EVERY), .DEPTH(DEPTH-1), .AW(3)) dut_small (
.clk(clk), .rst(rst), .wr_en(wr_en), .wr_data(wr_data), .full(full_sm),
.overflow(ovf_sm), .rd_en(rd_en), .rd_data(rd_sm), .empty(empty_sm));
always #5 clk = ~clk;
always @(posedge clk) if (!rst) begin
if (ovf_ok) ovf_seen_ok <= 1'b1;
if (ovf_sm) ovf_seen_sm <= 1'b1;
if ((wr_en && !full_ok) && !(rd_en && !empty_ok)) occ_model = occ_model + 1;
else if ((rd_en && !empty_ok) && !(wr_en && !full_ok)) occ_model = occ_model - 1;
if (occ_model > peak_model) peak_model = occ_model;
end
initial begin
clk = 0; rst = 1; wr_en = 0; rd_en = 0; wr_data = 0;
errors = 0; occ_model = 0; peak_model = 0; ovf_seen_ok = 0; ovf_seen_sm = 0;
@(negedge clk); rst = 0;
// Worst-case pattern: BURST back-to-back writes, 1 read every RD_EVERY cycles.
for (t = 0; t < BURST; t = t + 1) begin
@(negedge clk); wr_en = 1'b1; wr_data = t;
rd_en = (((t + 1) % RD_EVERY) == 0);
end
@(negedge clk); wr_en = 0;
for (t = 0; t < BURST; t = t + 1) begin
@(negedge clk); rd_en = (((t + 1) % RD_EVERY) == 0);
end
@(negedge clk); rd_en = 0;
if (ovf_seen_ok) begin
$display("FAIL: DEPTH=%0d overflowed on the burst (under-sized)", DEPTH); errors = errors + 1;
end
if (!ovf_seen_sm) begin
$display("FAIL: DEPTH-1=%0d did not overflow (not minimal)", DEPTH-1); errors = errors + 1;
end
if (peak_model !== DEPTH) begin
$display("FAIL: peak occupancy %0d != DEPTH %0d", peak_model, DEPTH); errors = errors + 1;
end
if (errors == 0)
$display("PASS: no overflow at DEPTH=%0d, overflow at DEPTH-1, peak == DEPTH", DEPTH);
else
$display("FAIL: %0d errors", errors);
$finish;
end
endmoduleIn VHDL the depth is a constant computed in the generic list, the FIFO uses numeric_std, and the stress process asserts no overflow at DEPTH and overflow at DEPTH-1 with severity error. Integer division in VHDL floors toward zero for non-negative operands, matching the floor in the formula. As in the SystemVerilog case, the formula is worth isolating as a pure function first.
-- min depth = BURST - floor(BURST/RD_EVERY). "/" on non-negative integers floors,
-- so the reader's drained-word count over the burst falls out directly.
function fifo_min_depth(burst, rd_every : positive) return positive is
begin
return burst - (burst / rd_every); -- words_in - words_out
end function;
-- Round the minimum UP to a power of two for the 7.2 extra-MSB pointer scheme.
function round_pow2(n : positive) return positive is
variable p : positive := 1;
begin
while p < n loop
p := p * 2; -- smallest 2**k >= n
end loop;
return p;
end function;
-- BURST=12, RD_EVERY=3 -> fifo_min_depth = 8, round_pow2(8) = 8. library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity sync_fifo is
generic (
WIDTH : positive := 8;
BURST : positive := 12;
RD_EVERY : positive := 3;
-- min depth = BURST - floor(BURST/RD_EVERY); "/" floors for non-negative ints.
DEPTH : positive := 12 - (12 / 3); -- = 8
AW : positive := 3 -- = clog2(DEPTH)
);
port (
clk : in std_logic;
rst : in std_logic; -- synchronous, active-high
wr_en : in std_logic;
wr_data : in std_logic_vector(WIDTH-1 downto 0);
full : out std_logic;
overflow : out std_logic; -- pulses on a refused write
rd_en : in std_logic;
rd_data : out std_logic_vector(WIDTH-1 downto 0);
empty : out std_logic
);
end entity;
architecture rtl of sync_fifo is
type mem_t is array (0 to DEPTH-1) of std_logic_vector(WIDTH-1 downto 0);
signal mem : mem_t;
signal wptr : unsigned(AW-1 downto 0) := (others => '0');
signal rptr : unsigned(AW-1 downto 0) := (others => '0');
signal count : unsigned(AW downto 0) := (others => '0'); -- 0..DEPTH
signal full_i : std_logic;
signal empty_i : std_logic;
signal do_wr : std_logic;
signal do_rd : std_logic;
begin
full_i <= '1' when count = to_unsigned(DEPTH, count'length) else '0';
empty_i <= '1' when count = 0 else '0';
full <= full_i;
empty <= empty_i;
overflow <= wr_en and full_i; -- a dropped word
do_wr <= wr_en and not full_i;
do_rd <= rd_en and not empty_i;
process (clk)
begin
if rising_edge(clk) then
if rst = '1' then
wptr <= (others => '0'); rptr <= (others => '0'); count <= (others => '0');
else
if do_wr = '1' then
mem(to_integer(wptr)) <= wr_data;
wptr <= wptr + 1;
end if;
if do_rd = '1' then
rptr <= rptr + 1;
end if;
if (do_wr = '1') and (do_rd = '0') then
count <= count + 1;
elsif (do_wr = '0') and (do_rd = '1') then
count <= count - 1;
end if;
end if;
end if;
end process;
rd_data <= mem(to_integer(rptr));
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fifo_depth_tb is
end entity;
architecture sim of fifo_depth_tb is
constant WIDTH : positive := 8;
constant BURST : positive := 12;
constant RD_EVERY : positive := 3;
constant DEPTH : positive := BURST - (BURST / RD_EVERY); -- 8
signal clk : std_logic := '0';
signal rst : std_logic := '1';
signal wr_en : std_logic := '0';
signal rd_en : std_logic := '0';
signal wr_data : std_logic_vector(WIDTH-1 downto 0) := (others => '0');
signal full_ok, empty_ok, ovf_ok : std_logic;
signal full_sm, empty_sm, ovf_sm : std_logic;
signal rd_ok, rd_sm : std_logic_vector(WIDTH-1 downto 0);
signal ovf_seen_ok, ovf_seen_sm : std_logic := '0';
begin
dut_ok : entity work.sync_fifo
generic map (WIDTH => WIDTH, BURST => BURST, RD_EVERY => RD_EVERY, DEPTH => DEPTH, AW => 3)
port map (clk => clk, rst => rst, wr_en => wr_en, wr_data => wr_data, full => full_ok,
overflow => ovf_ok, rd_en => rd_en, rd_data => rd_ok, empty => empty_ok);
dut_small : entity work.sync_fifo
generic map (WIDTH => WIDTH, BURST => BURST, RD_EVERY => RD_EVERY, DEPTH => DEPTH-1, AW => 3)
port map (clk => clk, rst => rst, wr_en => wr_en, wr_data => wr_data, full => full_sm,
overflow => ovf_sm, rd_en => rd_en, rd_data => rd_sm, empty => empty_sm);
clk <= not clk after 5 ns;
-- Latch whether either FIFO ever refused a write.
watch : process (clk)
begin
if rising_edge(clk) and rst = '0' then
if ovf_ok = '1' then ovf_seen_ok <= '1'; end if;
if ovf_sm = '1' then ovf_seen_sm <= '1'; end if;
end if;
end process;
stim : process
begin
wait until falling_edge(clk); rst <= '0';
-- Worst-case pattern: BURST back-to-back writes, 1 read every RD_EVERY cycles.
for t in 0 to BURST-1 loop
wait until falling_edge(clk);
wr_en <= '1';
wr_data <= std_logic_vector(to_unsigned(t, WIDTH));
if ((t + 1) mod RD_EVERY) = 0 then rd_en <= '1'; else rd_en <= '0'; end if;
end loop;
wait until falling_edge(clk); wr_en <= '0';
-- Drain the remainder.
for t in 0 to BURST-1 loop
wait until falling_edge(clk);
if ((t + 1) mod RD_EVERY) = 0 then rd_en <= '1'; else rd_en <= '0'; end if;
end loop;
wait until falling_edge(clk); rd_en <= '0';
-- DEPTH must be sufficient (no overflow) and minimal (DEPTH-1 overflows).
assert ovf_seen_ok = '0'
report "DEPTH overflowed on the worst-case burst - under-sized" severity error;
assert ovf_seen_sm = '1'
report "DEPTH-1 did not overflow - depth is not minimal" severity error;
report "fifo_depth stress complete: sized at DEPTH = BURST - floor(BURST/RD_EVERY)" severity note;
wait;
end process;
end architecture;5. Verification Strategy
Depth is a claim about the system, so verification is not "does the FIFO store and retrieve" (that is 7.1) but "is this depth exactly right for the traffic." Three tiers.
Tier 1 — the sufficiency test. Drive the worst-case traffic the system can produce — the maximum burst against the minimum drain — and assert the FIFO never refuses a write (overflow never fires) for the whole run. This is the go/no-go: if it overflows, the depth is too small, full stop. The §4 stress testbench is exactly this test, driving BURST back-to-back writes with a read every RD_EVERY cycles.
Tier 2 — the minimality test. Re-run the same worst-case traffic against a FIFO one slot shallower (DEPTH-1) and assert it does overflow. This proves the depth is not merely big enough but right — that you have not silently oversized. A depth that passes tier 1 but also passes tier 1 at DEPTH-1 is wasting a slot (and possibly a lot more). Together, tiers 1 and 2 pin the number: sufficient at DEPTH, insufficient at DEPTH-1.
Tier 3 — peak-occupancy and rate sweeps. Track a reference occupancy alongside the DUT and assert the observed peak equals the predicted depth — that catches a formula that happens to pass tiers 1 and 2 for the wrong reason. Then sweep the rates: vary BURST and RD_EVERY, recompute the expected depth from the formula, and confirm the stress test still shows no-overflow-at-DEPTH / overflow-at-DEPTH-1 for each. If the depth formula is correct, this holds across the whole rate space; if it is off by a term, some rate combination breaks it. Finally, add the negative case that matters most in the field: a back-to-back burst (two worst-case bursts with no idle gap between them) to confirm your margin covers the case where the FIFO has not fully drained before the next burst hits.
6. Common Mistakes
Sizing by the AVERAGE rate instead of the worst-case burst. The signature bug and §7's centerpiece. "The reader keeps up on average, so a few slots is plenty" computes the depth from average throughput and produces a tiny FIFO that overflows on the burst — the exact traffic the FIFO exists to absorb. Depth is a worst-case calculation; the average is irrelevant to it.
Forgetting the reader drains DURING the burst — oversizing. The mirror-image error. Sizing to the full BURST (words in) without subtracting the words the reader drains during the burst window gives a FIFO larger than needed — wasted area on every instance. The reader is working the whole time; subtract floor(BURST / RD_EVERY).
Assuming the reader keeps up when it cannot — undersizing. If the reader's sustained rate is slower than the producer's sustained rate (not just during a burst), no finite FIFO is deep enough — the FIFO fills without bound and overflow is inevitable. A FIFO absorbs a transient mismatch, not a permanent one. Check that the average drain rate meets or exceeds the average fill rate before computing a burst depth; if it does not, the problem is flow control (back-pressure), not depth.
Off-by-one on the window — miscounting the drained words. Counting a read-interval that has not completed by the end of the burst as a pop (using ceil or rounding instead of floor for words-out), or counting a write in the idle tail as part of the burst, shifts the depth by one and can under-size. The window is precisely the burst; the drained count is floor of the read-events that complete within it.
Not rounding up, and not going to a power of two. The formula yields a real-valued minimum; a fractional slot is a whole slot, so round up. And for the 7.2 extra-MSB pointer scheme the depth must be a power of two so the pointer wrap and the wrap-bit toggle coincide — a computed minimum of 50 becomes 64. Shipping a non-power-of-two depth into a pointer-based FIFO reintroduces the 7.2 boundary bug.
Ignoring back-to-back bursts. A depth computed for one isolated burst assumes the FIFO drains to empty before the next burst arrives. If bursts can come back-to-back with no idle gap, the second burst starts on a partially-full FIFO and the effective pile-up is larger — that is what design margin is for. Model the real burst-arrival pattern, not a single burst in isolation.
7. DebugLab
The FIFO sized by the average rate — it passed every steady-state test and dropped a word on the burst
The engineering lesson: FIFO depth is a worst-case-burst calculation from the system rates — words in minus words out over the burst window — not an average, and you prove the number with a stress test that overflows at DEPTH-1. The tell for the signature bug is data loss that tracks burst arrival rather than any data value or any single input, and that vanishes the moment you slow the producer or add idle gaps — a FIFO that is correct under steady traffic and drops a word on the burst is under-sized, not broken. Two habits make it impossible, and they are identical across SystemVerilog, Verilog, and VHDL: derive the depth from the worst-case traffic (words_in minus words_out over the burst), round up, add margin, and go power-of-two, and prove it two-sided with a stress test — no overflow at DEPTH, overflow at DEPTH-1, peak occupancy equal to the computed depth. Size by the average and you will pass every test but the one that matters.
8. Interview Q&A
9. Exercises
Design and reasoning exercises — no syntax drills. Each rehearses the worst-case rate-matching calculation and the two-sided proof behind it.
Exercise 1 — Compute and prove a depth
A producer bursts 30 words at 1 word/cycle; the consumer drains 1 word every 5 cycles. State words_in, words_out, and the minimum depth, then the power-of-two depth you would ship. Hand-trace the occupancy to the peak and confirm it equals your minimum. Then state, in one line each, why a FIFO one slot shallower overflows and why your shipped depth does not.
Exercise 2 — Pick the form and size it
For each traffic description, choose the burst-length form or the rate-ratio form, then compute the depth: (a) a source that writes one word per cycle for 40 cycles while the sink takes one word every 4 cycles; (b) a stream at 200 Mwords/s feeding a sink at 150 Mwords/s over a 1 microsecond burst; (c) a producer valid one word every 2 cycles for a 24-cycle window while the reader takes one every 3 cycles. Round each to a power of two and note which one needs the most margin and why.
Exercise 3 — Diagnose the sizing error
An engineer sizes a FIFO to 4 for a system that bursts 16 words at 1/cycle with a reader draining 1 every 4 cycles, reasoning "the reader keeps up on average." Compute the true minimum depth, state exactly how many words are dropped on the first burst and on which write the first drop occurs, and describe the symptom the field would report. Then give the corrected depth and the single stress-test assertion that would have caught the bug before tape-out.
Exercise 4 — When depth cannot save you
A producer sustains an average of one word every 2 cycles indefinitely; the consumer drains one word every 3 cycles indefinitely (no idle gaps for either). Show that no finite depth prevents overflow, and quantify how fast the occupancy grows. State what mechanism — not a deeper FIFO — actually fixes it, and how the full flag participates. Then state the condition on the average rates under which a finite burst depth is sufficient.
10. Related Tutorials
Continue in RTL Design Patterns (sibling and forward links unlock as they ship):
- Synchronous FIFO Architecture — Chapter 7.1; the circular buffer whose
DEPTHthis page computes — the RAM plus wrapping pointers that hold the words the depth calculation sizes. - Full & Empty Logic — Chapter 7.2; the boundary flags that guard the
DEPTHslots, and the reason the computed depth is rounded to a power of two so the extra-MSB pointer scheme wraps cleanly. - FIFO Programmable Flags — Chapter 7.3; almost-full / almost-empty thresholds that give the producer early warning before the hard depth boundary this page sizes.
- First-Word Fall-Through FIFO — Chapter 7.5; the read-timing variant; its zero-latency read changes when the reader drains, which shifts the words-out count in the depth window.
- FIFO Verification — Chapter 7.6; the full self-checking + stress strategy the two-sided depth proof (no overflow at DEPTH, overflow at DEPTH-1) is a core part of.
- Valid/Ready Handshake — Chapter 8.1; the back-pressure protocol that throttles the producer when the FIFO fills — the mechanism for the case where no finite depth suffices.
- Backpressure & Stall Logic — Chapter 8.2; how the
fullflag stalls an upstream pipeline, the complement to depth for guaranteeing long-run balance. - Asynchronous FIFO — Chapter 11.6; the dual-clock FIFO whose depth calculation adds synchronizer latency to the drain side of the same rate-matching sum.
Backward / in-track dependencies:
- Up/Down Counters — Chapter 3.3; the occupancy counter whose peak value the depth must cover — the reference the stress test tracks.
- Comparators — Chapter 1.5; the equality comparators that produce
full, and thus theoverflowstrobe the depth proof watches. - The Register Pattern (D-FF) — Chapter 2.1; the flops the pointers and occupancy counter are built from, and the reset-first clocked-update discipline.
- The RTL Design Mindset — Chapter 0.2; the Verification lens this page applies — the depth is a claim about the system that you must prove two-sided, not assume.
- What Is an RTL Design Pattern? — Chapter 0.1; why depth sizing earns the name "pattern" — a recurring problem, a reusable formula, a synthesis reality, and a signature failure.
Verilog v1 prerequisites (the grammar this pattern transcribes into):
- Arithmetic Operators — the subtraction and integer division (
BURST - BURST/RD_EVERY) that compute the depth in RTL. - Relational Operators — the equality comparisons (
==) that buildfulland theoverflowstrobe. - Blocking and Non-Blocking Assignments — why the pointers and occupancy counter update with non-blocking (
<=) in their clocked process. - Physical Data Types — the vector widths (
AW,AW+1) whose sizing follows from the computed depth.
11. Summary
- Depth is a rate-matching calculation, not a round number. A FIFO exists to absorb the mismatch between a producer and a consumer, so "how deep?" asks how many words can arrive faster than they drain, in the worst-case window. The answer comes from the system rates, never from the FIFO itself.
- The formula is words-in minus words-out over the worst-case burst. In the burst-length form,
min depth = BURST minus floor(BURST / RD_EVERY)— the words written during the burst minus the words the reader drains during that same window. ForBURST = 12,RD_EVERY = 3that is12 minus 4 = 8. The rate-ratio formceil((Wr minus Rd) times T)is the same equation in different units. The reader drains during the burst, so you must subtract its words — forget that and you oversize; use the average instead of the burst and you undersize. - Round up, add margin, go power-of-two. The formula gives a real-valued minimum; a fractional slot is a whole slot, so round up, add margin for back-to-back bursts and reader jitter, and round to a power of two so the 7.2 extra-MSB pointer scheme wraps cleanly. A computed minimum of 50 ships as 64.
- The signature bug is sizing by the average rate. "The reader keeps up on average, so a few slots is plenty" produces a FIFO that overflows on exactly the burst it was installed to absorb — dropping data intermittently, correlated with burst arrival, invisible under steady traffic and green in every lab test. Depth is a worst-case calculation; the average only tells you whether the FIFO can recover between bursts.
- Prove the number two-sided. A correct depth is both sufficient (no overflow at
DEPTH) and minimal (overflow atDEPTH-1), with the reference occupancy peaking at exactly the computed depth. The §4 stress testbench drives the worst-case burst and asserts precisely that, in SystemVerilog, Verilog, and VHDL — turning "a depth that happens to work" into "the right depth," which is exactly what the interview is testing.