DescriptionQ335
Q335DesignDVAppleASIC interview problem
Size an asynchronous FIFO from exact event times
TechniquesDesignDVArchAsync FIFORate mismatch
DifficultyMedium
TopicClock Domain Crossing
LanguageSystemVerilog
Requirements4 checkpoints
01
Problem
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?
Example input and output
Use this case to check your interpretationInput
126 scheduled writes; 101 scheduled read attempts including the empty attempt at t=0Output
126 accepted writes, 100 accepted reads, maximum occupancy 26, minimum depth 26Explanation
The endpoint convention adds both t=1000 events. The failed read at zero makes accepted reads one fewer than scheduled attempts.
02
Requirements (4)
- Include writes at 0,8,...,1000 ns and read attempts at 0,10,...,1000 ns.
- The read at t=0 fails because the FIFO is empty before the simultaneous event is evaluated.
- Treat an accepted read and write at the same nonempty timestamp as zero net occupancy change.
- Evaluate every event time and report maximum occupancy, not only an average-rate estimate.