FIFO Depth Calculation: The Interview Question, Worked
A FIFO must hold whatever the writer puts in faster than the reader takes out during the worst burst. Work out how long the burst lasts at the writer's real rate, how many words the reader removes in that time at its real rate, and subtract: depth = burst − words read during the burst. Real rates include idle cycles, so a writer that writes every other clock at 100 MHz is a 50 million words per second writer. Then check the worst case at the cycle level, because phase alignment can add a word.
What you'll learn
- The formula, and where it comes from
- How idle cycles change the effective rates
- Three worked examples
- The 'X writes in Y clocks' trick question
- What to add for an asynchronous FIFO
The formula
Let the burst be B words, the writer's effective rate W words per second and the reader's R, with R < W. The burst takes B / W seconds, during which the reader removes R × B / W words. So the FIFO must hold B − R × B / W = B (1 − R / W) words. If R ≥ W over the burst, a depth of one or two is enough, and the question is really about the long-term average, which must not exceed the reader's rate.
Example 1: different clocks, no idle cycles
The writer runs at 100 MHz and writes every clock; the reader runs at 50 MHz and reads every clock; the burst is 120 words. The burst lasts 120 / 100 MHz = 1.2 µs, during which the reader takes 1.2 µs × 50 MHz = 60 words. Depth = 120 − 60 = 60.
Example 2: idle cycles
The writer runs at 100 MHz but writes only every second clock, so W = 50 million words per second; the reader runs at 80 MHz and reads every fourth clock, so R = 20 million. For a 100-word burst: 100 / 50 M = 2 µs, the reader takes 2 µs × 20 M = 40 words, and depth = 100 − 40 = 60.
Example 3: 80 writes in any 100 clocks
Same clock for both sides. The writer may write 80 words in any window of 100 clocks, and the reader reads 8 of every 10 clocks. The trap is the window: the writer can put 80 writes at the end of one window and 80 at the start of the next, so the worst burst is 160 back-to-back writes. In 160 clocks the reader takes 160 × 8 / 10 = 128, so the formula gives 160 − 128 = 32.
A cycle-by-cycle simulation of that worst burst, trying all ten alignments of the reader's 8-of-10 pattern, peaks at 33, one more than the formula: when the reader's two idle clocks fall at the start of the burst, the count gets ahead before the average catches up. Say 32 from the formula, then 33 from the worst alignment, and size the FIFO with margin, usually rounding up to a power of two.
The three examples, checked
| Example | Formula | Cycle-level peak |
|---|---|---|
| 1: 100 MHz writer, 50 MHz reader, 120-word burst | 60 | 60 |
| 2: idle cycles on both sides, 100-word burst | 60 | 60 |
| 3: 80 in any 100, reader 8 of 10 | 32 | 33 |
Asynchronous FIFOs
When the two sides have different clocks, the full and empty flags see the other side's pointer through a two-flip-flop synchronizer, so they react a few clocks late. The writer may keep writing for those clocks after the FIFO is in fact full, so add a few words of margin for the synchronizer delay, and in an interview say so.
How to answer in an interview
- Ask for the burst length and both effective rates, including idle cycles. If the question gives none, there is no finite answer.
- Convert both to words per second, or to words per writer clock.
- Compute B (1 − R / W) and say the units.
- Mention the worst-case window and alignment, and the synchronizer margin for an asynchronous FIFO.
Common mistakes
- Using clock frequencies without the idle cycles.
- Missing the back-to-back burst across two windows.
- Forgetting that the reader also reads during the burst.
- Answering with a depth for an average rate that exceeds what the reader can sustain: no depth is enough.
Check your understanding
- Q1. Writer 200 MHz every clock, reader 100 MHz every clock, burst 64. Depth? Answer: 64 × (1 − 100/200) = 32.
- Q2. Same clock; the writer writes 1 in 2, the reader 1 in 3; burst 60 writes. Depth? Answer: the burst lasts 120 clocks, the reader takes 40, so 20.
- Q3. Why add margin to an asynchronous FIFO? Answer: the synchronized pointers make the full flag a few clocks late.
Related
Last verified
The three examples and the burst diagram are checked by a cycle-level FIFO simulation in the site's tests (lib/content2Numbers.test.js) on 17 November 2026.