Why Every Design Has a FIFO in It

Section 7.3 ended with a pipeline that could be stalled. Section 7.4 is about the other way of dealing with a consumer that is not ready: put a buffer in between.

A UART receives one byte roughly every 100 microseconds. The processor that reads those bytes might be busy for 200 microseconds at a stretch before it checks. With nothing between the UART and the processor, the second byte is gone by the time anyone looks, overwritten by the third or dropped outright. That is the whole problem a FIFO solves: two sides of an interface producing and consuming at rates that do not match moment to moment, even if their averages over time are fine. A FIFO, first in first out, is a buffer that absorbs the mismatch, so a slow consumer does not force a fast producer to stop and a producer’s bursts do not overwhelm a consumer that is merely a little behind.

The minimal FIFO interface

Every FIFO, whatever is inside it, exposes roughly the same four-signal contract on each side:

FIFO interface: write side, read side, full and empty — Figure 1: The minimal FIFO interface

wdata and wr_en: the producer presents data and asserts wr_en to push it in.
full: the FIFO tells the producer not to push anything else right now. A well-behaved producer checks full before asserting wr_en.
rdata and rd_en: the consumer asserts rd_en to pop the oldest entry, which appears on rdata.
empty: the FIFO tells the consumer there is nothing to read. A well-behaved consumer checks empty before asserting rd_en.

This is the ready/valid backpressure idea from Section 7.3 in FIFO vocabulary. full is backpressure flowing back to the producer; empty is the same thing flowing to the consumer. A FIFO is a buffer with backpressure logic built into both ends.

Two problems, one structure

The rate-mismatch problem is a producer and consumer whose long-run rates match but whose instantaneous rates do not, the UART case above. The FIFO only needs to be deep enough to smooth the jitter between the two sides, and on average it sits about half full.

The burst problem is a producer that occasionally delivers a burst much faster than the consumer’s steady rate, followed by an idle period that lets the consumer catch up. A network receiver getting a whole Ethernet frame back to back, handed to a processor that services the buffer once per frame, is the usual example. Here the depth has to hold the whole burst, not just average out jitter. Get it wrong and the FIFO fills mid-burst, and the producer either stalls (which the protocol may not allow) or drops data.

Depth is a calculation, not a guess

For the rate-mismatch case, depth is a function of how much timing variance you expect between the sides. For the burst case it comes directly from the largest burst you have to absorb before the consumer is guaranteed to start draining:

$$\text{Required Depth} \geq \text{Burst Size} - (\text{Consumer Rate} \times \text{Burst Duration})$$

If a burst delivers 64 bytes over 10 cycles and the consumer drains 1 byte every 2 cycles during that window (5 bytes while the burst arrives), the FIFO needs to hold at least $64 - 5 = 59$ bytes. Undersize it and the design does not just get slower; it drops data or forces a stall the producer may not honour. Nearly every peripheral on a real SoC has a FIFO in it (UART, USB endpoints, Ethernet MAC, DMA staging) and the depth of each one is a spec parameter in the datasheet, because getting it wrong means data loss in the field.

What is coming in this section

We build a synchronous FIFO first, where both sides share one clock. That sidesteps the hardest part entirely and lets us get full/empty detection and pointer arithmetic right. Then we meet Gray code, which is the one piece of number theory standing between a synchronous FIFO and a correct asynchronous one, where the read and write sides run on unrelated clocks. That case is by far the more common one in real chips and connects directly into Section 7.5.

Practice Exercise

A sensor produces a burst of 32 readings over 16 clock cycles, followed by a long idle period. A downstream filter consumes one reading every 3 cycles, continuously, including during the burst. Find the minimum FIFO depth that avoids dropping data.

Solution

During the 16-cycle burst the consumer drains one reading per 3 cycles, so $\lfloor 16 / 3 \rfloor = 5$ readings (floor, since a partial 3-cycle period at the end has not completed a read). The FIFO must hold the remainder: $32 - 5 = 27$ readings. In practice you would round up to 32 for clean power-of-two pointer arithmetic, which the next article explains, and for a little margin.

A FIFO is the hardware answer to producers and consumers whose rates do not line up moment to moment, and its depth is a number you calculate from the traffic the design has to survive. In the next article we build the synchronous version and get the full/empty pointer arithmetic exactly right, which is more subtle than it looks.