Skip to question
asic.fyi

Hardware interview practice

Size an asynchronous FIFO from exact event times

MediumClock Domain CrossingSystemVerilog

A producer writes one item every 8 ns from t=0 through t=1000 ns. A consumer attempts one read every 10 ns from t=0 through t=1000 ns. The FIFO starts empty, and events at the same timestamp are simultaneous. What minimum capacity is required?

Reviewed example

Work through one case

Input
126 scheduled writes; 101 scheduled read attempts including the empty attempt at t=0
Expected output
126 accepted writes, 100 accepted reads, maximum occupancy 26, minimum depth 26

The endpoint convention adds both t=1000 events. The failed read at zero makes accepted reads one fewer than scheduled attempts.

What to cover

Requirements

  1. Include writes at 0,8,...,1000 ns and read attempts at 0,10,...,1000 ns.
  2. The read at t=0 fails because the FIFO is empty before the simultaneous event is evaluated.
  3. Treat an accepted read and write at the same nonempty timestamp as zero net occupancy change.
  4. Evaluate every event time and report maximum occupancy, not only an average-rate estimate.
Continue practicing
Clock Domain CrossingBinary-to-Gray converterClock Domain CrossingWhy synchronized async-FIFO pointers are conservativeClock Domain CrossingEight-entry asynchronous FIFO