Difficulty: Easy · Puzzle 1 of 6 · Topic: FIFO, Arbitration and Credit Puzzles
A producer writes a burst of 64 words, one word every 10 ns (100 MHz). The consumer reads one word every 20 ns (50 MHz) whenever the FIFO is non-empty, starting 10 ns after the first write. No other traffic. Ideal model: no synchronizer latency, and when a read and a write fall at the same instant the read frees its slot first. What is the minimum depth so nothing is lost?
// producer clock: 100 MHz, 1 word per clock for 64 clocks
// consumer clock: 50 MHz, 1 word per clock whenever not empty
// question: minimum FIFO depth (words) with no overflowCount the words written and read at the end of the burst; the peak occupancy is at the last write.
1) The burst takes 64 x 10 ns = 640 ns.
2) In that time the consumer reads about 640 / 20 = 32 words.
3) Peak occupancy = written - read = 64 - 32 = 32 words (reached around the last write).
4) The formula is depth = burst x (1 - fr/fw) = 64 x (1 - 0.5) = 32. The Python model steps the time line in 1 ns and finds the same peak.Answer: 32 words in the ideal model.
Checked by running a model of the rule in a Python model. A time-stepped Python model (reader starts 10 ns after the first write) reproduces the closed-form depth of 32.
Using the full burst length (64) forgets that the reader drains during the burst; using the formula with the ratio inverted gives 64 x (1 - 2) = negative. And the ideal number is a minimum: an asynchronous FIFO's write side sees the read pointer several write clocks late, so real designs add margin for the synchronizer delay and round up (Gray-coded FIFOs also need a power-of-two depth).
How would the required depth change if the consumer could not start until the whole burst had arrived? Model answer: It becomes the full burst, 64 words, because nothing is drained during the burst. The formula assumes the reader runs concurrently.