Digital Design & Verification (Verilog, SystemVerilog, VLSI) Module 5 – Pipelines, handshakes, FIFOs and on-chip buses
Synchronous FIFOs and FIFO depth sizing
Build a synchronous FIFO with full, empty and almost-full flags, choose its read style, and size its depth from a burst and two rates, checked by simulation.
What you will learn
- Build a synchronous FIFO whose pointers tell full from empty, with full, empty and almost-full flags
- Choose between registered-output, first-word-fall-through and block-RAM FIFOs for a design
- Size a FIFO from the burst length and the producer and consumer rates, and check the size by simulation
- Verify a FIFO against a queue model with random traffic and assertions
Before you start
What you’ll learn · Before you start
What you will learn
- Build a synchronous FIFO whose pointers tell full from empty, with full, empty and almost-full flags
- Choose between registered-output, first-word-fall-through and block-RAM FIFOs for a design
- Size a FIFO from the burst length and the producer and consumer rates, and check the size by simulation
- Verify a FIFO against a queue model with random traffic and assertions
Before you start
On this page
A producer writes a burst of 64 words, one per clock cycle, into a FIFO whose consumer can take a word on only 4 cycles in 5. When the burst ends, 12.8 words, so at least 13, are still waiting, yet a FIFO whose full flag is read before each edge needs 14 entries: with 13 it lost a word in the simulation on this page.
You will build the pointers and flags of synchronous FIFOs, meet their three styles and size a FIFO from a burst and two rates, with a simulation that runs in your browser. Verilator 5.052, Icarus Verilog 13.0 and Yosys 0.69 ran and mapped the FIFOs.
A FIFO is a memory, two pointers and two flags
A synchronous FIFO: A first-in, first-out buffer whose write side and read side use the same clock: words leave in the order they came, and full and empty flags tell each side when to stop. keeps words in a small memory and gives them back in the order they came, first in, first out, with one clock for both sides. A write pointer says where the next word goes, a read pointer where the oldest one waits, and both wrap round to slot 0 after the last slot. Step through a ring of 4 slots filling up, refusing a word, wrapping round and draining:
- being moved or written
Pseudo-code
-
enqueue(x): if count = capacity: error "full" -
a[rear] ← x; rear ← (rear + 1) mod capacity; count ← count + 1 -
dequeue(): if count = 0: error "empty" -
x ← a[front]; front ← (front + 1) mod capacity; count ← count − 1; return x
A circular queue with 4 slots. front is where the next item leaves, rear where the next one goes; both wrap around to slot 0 after slot 3.
When it finishes: 0 items queued.
Try your own input
When the ring is full and when it is empty the two pointers point at the same slot, so a pointer alone cannot tell the two apart. The figure keeps a count. Synchronous FIFOs in RTL often give each pointer one bit more than an address needs instead. The low bits pick the slot and the top bit flips at every lap, so equal pointers mean empty, and equal slots on different laps mean full. For 8 entries the pointers have 4 bits:
| Moment | Write pointer | Read pointer | Slots | Laps | Flag |
|---|---|---|---|---|---|
| After reset | 0000 | 0000 | equal | equal | empty |
| 3 words written | 0011 | 0000 | differ | equal | none |
| 8 words written | 1000 | 0000 | equal | differ | full |
| All 8 read too | 1000 | 1000 | equal | equal | empty |
An almost-full flag: A FIFO flag that rises while a set number of entries is still free, so that a producer that reacts a few cycles late can stop before the FIFO overflows. flag rises a few words before full, so a producer that reacts late still has room. FIFOs also differ in how they give words out: a registered-output FIFO shows a word one cycle after the read request, a first-word-fall-through FIFO shows the oldest word before any request, and a block-RAM FIFO keeps its memory in the FPGA’s RAM blocks, whose reads are clocked. Whatever the style, a FIFO is tested against a queue model that holds the same words.
Checkpoint
Check: Pointers, lap bits and flags
FIFO depth sizing counts the words that must wait
FIFO depth sizing starts from the busiest moment: during a burst the FIFO must hold every word written that the consumer could not yet read. For the burst of 64 words, one per cycle, read on 4 cycles in 5, that is 64 − 64 × 4/5 = 12.8 words, so at least 13 entries. fifo_depth.py works the formula out, then runs the burst cycle by cycle into FIFOs of growing depth, with full and empty read before each edge as the RTL reads them. Press Run, then Edit:
"""How deep must a FIFO be for one burst? A producer writes BURST words, one at every cycle; the consumer can take a
word on READ_ON of every READ_OF cycles, whenever the FIFO holds one. The formula counts the words written during the
burst that the consumer could not read yet. The simulation runs the burst edge by edge into FIFOs of growing depth,
with full and empty read before each edge as the RTL reads them, and reports the first depth that loses nothing."""
import math
BURST = 64 # words in the burst, one written per cycle
READ_ON = 4 # the consumer reads on 4 ...
READ_OF = 5 # ... of every 5 cycles
def reads_on(cycle):
"""Whether the consumer can read at this cycle: the first READ_ON cycles of every READ_OF."""
return cycle % READ_OF < READ_ON
def simulate(depth):
"""Runs the burst into a FIFO of this depth. A word written at one edge can be read at the next one at the
earliest, and a write at an edge where the FIFO was full is refused. Returns (words lost, most words held)."""
stored = most = lost = written = cycle = 0
while written < BURST or stored:
full, empty = stored == depth, stored == 0
if reads_on(cycle) and not empty: # the read side takes the oldest word
stored -= 1
if written < BURST: # the write side writes its next word, unless the FIFO was full
if full:
lost += 1
else:
stored += 1
written += 1
most = max(most, stored)
cycle += 1
return lost, most
waiting = BURST - BURST * READ_ON / READ_OF
print(f"burst of {BURST} words, one written per cycle, read on {READ_ON} of every {READ_OF} cycles")
print(f"formula: {BURST} - {BURST} x {READ_ON}/{READ_OF} = {waiting:g} words still waiting, so at least {math.ceil(waiting)} entries")
depth = 1
while True:
lost, most = simulate(depth)
if depth >= math.ceil(waiting) - 1:
print(f"simulation: {depth} entries lose {lost} word{'' if lost == 1 else 's'}, at most {most} held")
if lost == 0:
break
depth += 1
print(f"smallest depth that loses nothing: {depth}")Output
burst of 64 words, one written per cycle, read on 4 of every 5 cycles formula: 64 - 64 x 4/5 = 12.8 words still waiting, so at least 13 entries simulation: 12 entries lose 2 words, at most 12 held simulation: 13 entries lose 1 word, at most 13 held simulation: 14 entries lose 0 words, at most 13 held smallest depth that loses nothing: 14
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 fifo_depth.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The simulation agrees that 13 words are the most ever waiting, yet the FIFO of 13 entries lost a word, and 14 was the smallest that lost none. At the edge where 13 words fill it, a read and a write come together: the read frees a slot, but the full flag was read before the edge, so the write is refused. A FIFO whose full flag lets a write through when a read happens at the same edge would manage with 13. That is why FIFO depth sizing ends with a simulation of the real flag timing, not with the formula alone.
Change the traffic
Press Edit and set READ_ON to 3: the formula rises to 25.6 words, and the simulation gives the depth to build.
Key idea
A FIFO must hold every word written that the consumer could not read yet; the formula gives that number, and a simulation with the real flag timing gives the depth, here 14 for 13 words in waiting.
Checkpoint
Check: Sizing the depth for a burst
A FIFO in RTL, checked against a queue model Pro: opens with a Pro, Premium or Ultimate pass
sync_fifo.sv builds the pointers and flags of the table above. This part reads its RTL, runs it for 10,000 cycles against a queue model, and runs a copy whose pointers lost their lap bit.
In this part:
- Pointers with a lap bit, and flags worked out from them
- 10,000 random cycles against a queue model
- Pointers without the lap bit cannot tell full from empty
1 runnable example (Commands, sync_fifo.sv, sync_fifo_bug.sv, tb_fifo.sv) · about 4 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Sizing with numbers: idle cycles, a late consumer and almost-full Pro: opens with a Pro, Premium or Ultimate pass
fifo_depth.py sized one burst. This part sizes three harder cases with numbers, each by the formula and by a simulation with the RTL’s flag timing, and finds the almost-full level that a producer who sees the flag late needs.
In this part:
- Idle cycles on both sides: count the burst in cycles
- A consumer that starts late: the depth its delay adds
- Almost-full must leave room for the latency of backpressure
- Your turn: the smallest depth that loses no word
- Find the smallest FIFO depth that loses no word
- Results of the sample tests
1 runnable example (Python) · 1 exercise with sample tests · about 5 minutes
Opening this part with your pass…Pro part. It opens with the same pass as the part above.
Registered output, first-word fall-through and block RAM Pro: opens with a Pro, Premium or Ultimate pass
A FIFO’s read side comes in two timings, and only one of them is a block RAM’s clocked read as it stands. This part runs both side by side and shows what Yosys did to put the other in a block RAM all the same.
In this part:
- A registered output gives the word one cycle after the read
- A fall-through FIFO shows the head before the read
- What block RAM cost each style on the iCE40
1 runnable example (Commands, fwft_fifo.sv, ram_table.py, tb_styles.sv) · about 4 minutes
Opening this part with your pass…Pro part. It opens with the same pass as the part above.
Practise: pointers, flags and depth
Pointer flags and depth arithmetic come next, and the session leads with whichever of the two your past answers here found harder.
Practice that adapts to you
Practise this lesson
9 questions about 5 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Interview questions
Warm-up (fresher): how does a FIFO tell full from empty?
Full and empty both leave the write and read pointers on the same slot, so the slot alone cannot say which. Either keep a count of the words stored, full at the depth and empty at zero, or give each pointer one bit more than the address needs: that bit flips at every lap, so equal pointers mean empty and equal slots with different lap bits mean full. For 8 entries, write pointer 1000 against read pointer 0000 is full.
Three harder questions follow, on sizing a FIFO for a burst, on a FIFO that loses data once it fills, and on a fall-through FIFO in block RAM:
-
Fresher to mid
A block writes bursts of 96 words into a FIFO, one per cycle. The consumer reads on 3 cycles of every 4 and sees the first word 4 cycles after it is written; the producer stops on almost_full 2 cycles after the flag rises. What depth and almost-full level do you choose, and how do you check them?
-
Fresher to mid
A 32-entry FIFO passes its block-level tests, which run at even read and write rates. In the system it corrupts data under heavy traffic, and a waveform shows empty rising while the FIFO should be full. What is the likely bug, and how do you fix both the FIFO and its tests?
-
Mid to senior
A consumer is a valid/ready sink, so the FIFO in front of it must be first-word fall-through, yet the FIFO is 4,096 words deep and must use block RAM, whose read is clocked. How do you build it, and what does it cost?
Flashcards · 6 cards
Recall it, then check
Say the answer to yourself before you look: recalling it is what makes it stick.
-
Why can't a FIFO's read and write pointers alone tell full from empty?
In both cases they point at the same slot. Keep a count, or give each pointer one extra bit that flips at every lap: equal pointers mean empty, equal slots on different laps mean full.
-
With 4-bit pointers on an 8-entry FIFO, what do write pointer 1000 and read pointer 0000 mean?
Full: the low three bits name the same slot and the lap bits differ.
-
What is an almost-full flag for?
It rises a few words before full, so a producer that reacts late still has room.
-
How do registered-output, first-word-fall-through and block-RAM FIFOs give words out?
A registered-output FIFO shows a word one cycle after the read request; a first-word-fall-through FIFO shows the oldest word before any request; a block-RAM FIFO keeps its words in RAM blocks whose reads are clocked.
-
How many words wait when a 64-word burst, one word per cycle, meets a consumer that can read only 4 cycles out of 5?
64 - 64 x 4/5 = 12.8, so the formula asks for at least 13 entries.
-
Why did a FIFO of 13 entries still lose a word on that burst?
At the edge where 13 words filled it a read and a write came together, but the full flag was read before the edge, so the write was refused. With that flag timing 14 entries were needed, which only the simulation showed.
Key takeaways
- A FIFO is a memory with two pointers; with a lap bit on each, equal pointers mean empty and equal slots on different laps mean full.
- An almost-full flag rises before full, so a producer that reacts late still has room.
- The depth must hold every word the consumer could not read yet, and a simulation with the real flag timing gives it: 14 entries for the 13 words that waited here.
Terms in this lesson
- almost-full flag
- A FIFO flag that rises while a set number of entries is still free, so that a producer that reacts a few cycles late can stop before the FIFO overflows.
- synchronous FIFO
- A first-in, first-out buffer whose write side and read side use the same clock: words leave in the order they came, and full and empty flags tell each side when to stop.
References
- IEEE 1800-2023: IEEE Standard for SystemVerilog, Unified Hardware Design, Specification, and Verification Language (IEEE Standards Association)
- Verilator documentation: simulating (the --binary flow, assertions) (Verilator)
- Icarus Verilog documentation (Icarus Verilog)
- Yosys command reference: synth_ice40 and the other iCE40 commands (YosysHQ)
- Yosys command reference: memory commands (memory_dff merges registers into memory read ports) (YosysHQ)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress