Asynchronous FIFO Depth

Problem

A write side pushes data at w_rate MHz, a read side pops it at r_rate MHz, and the two sit in different clock domains. The writer sends a burst of burst back to back items, then idles. The reader needs idle_cycles of its own clock between pops because of downstream backpressure.

Work out the minimum FIFO depth that guarantees no overflow, then write the function that computes it for arbitrary numbers.

Examples

Example 1, w_rate = 100, r_rate = 100, burst = 120, idle_cycles = 1 The reader consumes one item every 2 read clocks, so in the time the writer pushes 120 items the reader has drained 60. Depth = 120 - 60 = 60.

Example 2, w_rate = 200, r_rate = 100, burst = 100, idle_cycles = 0 Burst duration is 100 / 200 MHz = 500 ns. In 500 ns the reader pops 0.5 us * 100 MHz = 50. Depth = 100 - 50 = 50.

Example 3, w_rate = 100, r_rate = 250, burst = 40, idle_cycles = 0 The reader is faster than the writer, so one entry is enough for the rate mismatch. Depth = 1.

Constraints

• Rates are positive, not necessarily integers.
• Round the depth up, never down.
• Then tell me the depth you would actually implement and why it is not the number you just computed.

What they look for

The arithmetic is the easy half. The second half is the design conversation that always follows:

• Why the pointers are gray coded before they cross, and why binary pointers break even with two flop synchronisers.
• Why full and empty are generated on different sides of the FIFO, and why each side is conservative in its own direction.
• Where the synchroniser latency goes into your depth number, so that full asserts late and you overflow a FIFO that your spreadsheet said was fine.
• What you do when the depth comes out at 4096 and nobody will give you that much memory.