Digital Design / Module 10: Clock domain crossing
58. Asynchronous FIFO
Design the standard solution for bulk crossing.
See it move
The idea
An asynchronous lets streams of data pass between two unrelated clocks. The memory is dual-port and holds data steady. The only signals crossing domains are the read and write pointers, in .
The structure
- The write side keeps a binary write pointer, and a registered Gray copy.
- The read side does the same, with its read pointer.
- Each Gray pointer goes through a two-flop into the other domain.
- Full is computed in the write domain, and empty in the read domain.
// Write domain
assign wbin_next = wbin + (wr && !full);
assign wgray_next = (wbin_next >> 1) ^ wbin_next;
assign full_next = (wgray_next ==
{~rgray_sync[AW:AW-1], rgray_sync[AW-2:0]});
always_ff @(posedge wclk or negedge wrst_n)
if (!wrst_n) {wbin, wgray, full} <= '0;
else {wbin, wgray, full} <= {wbin_next, wgray_next, full_next};
// Read domain
assign rbin_next = rbin + (rd && !empty);
assign rgray_next = (rbin_next >> 1) ^ rbin_next;
assign empty_next = (rgray_next == wgray_sync);The full condition
With Gray pointers having one extra bit, the FIFO is empty when the pointers match. It's full when the top two bits differ and the rest match, rather than when just the MSB differs. That's a consequence of how Gray code mirrors its sequence.
Why the flags are safe
Each side sees the other's pointer a few cycles late.
- The writer sees an old read pointer, so it thinks the FIFO has less space than it does. It may declare full early, but it can't overflow.
- The reader sees an old write pointer, so it thinks the FIFO holds less data than it does. It may declare empty early, but it can't underflow.
Flags can be pessimistic, and they can never be dangerously wrong. The result is a small loss of usable , in exchange for complete safety.
Sizing
Extra depth covers the pointer synchronizer delay. The animation above uses a real two-clock simulation model: change the clock ratio and watch the contents move without losing a word.
Common mistake
Combining reset poorly. Each domain needs its own synchronized reset, and the pointers must not change during the release. Also, the depth must be a power of two for this Gray scheme to work without special handling.
Key ideas
- Gray pointers cross domains through synchronizers.
- Full is computed in the write domain and empty in the read domain.
- Stale pointers make flags conservative, which is safe.
Lab: Clock crossing lab
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
assign full = (wgray == {~rgray[3:2], rgray[1:0]});Why it failed
With binary pointers, full means only the MSB differs. Gray code mirrors its sequence, so the second-highest bit is also inverted, one depth apart. The correct test inverts the top two bits and compares. Copying the binary rule into Gray code is the classic async FIFO bug.
Interview questions
coreWhat is the full condition with Gray pointers?
The top two bits differ and the remaining bits match.
basicIn an asynchronous FIFO, why is full computed in the write domain and empty in the read domain?
Each flag has to stop one side, so it must be a clean, registered signal in that side's clock domain. Full stops the writer, so it is computed from the writer's own pointer and a synchronized copy of the read pointer. Empty stops the reader, so it uses the reader's own pointer and a synchronized copy of the write pointer. Computing a flag in the other domain would mean the flag itself has to cross, adding latency and another crossing to get right.
basicWhy do the pointers of a depth-16 async FIFO have 5 bits, and why does the depth need to be a power of two?
Four bits address the 16 entries, and the extra bit counts laps, so equal pointers mean empty while the same address one lap apart means full. The Gray scheme needs the count to wrap with a single bit change, which only happens at a power of two. For example, a 3-bit count from 0 to 5 would wrap from Gray 111 to 000, changing three bits at once. A depth that is not a power of two needs special handling.
coreA depth-8 async FIFO uses 4-bit Gray pointers. The synchronized read pointer is binary 2. What write pointer, in binary and in Gray, makes the FIFO full?
Full means the writer is exactly one lap, 8 entries, ahead: binary 2 + 8 = 10. Binary 2 is Gray 0011, and binary 10 is 1010 ^ 0101 = Gray 1111. The rule says full when the write Gray pointer equals the read Gray pointer with its top two bits inverted, and 0011 with the top two bits inverted is 1111, which matches. The lower bits agree, and the top two differ.
coreEach side of an async FIFO only sees a delayed copy of the other side's pointer. Why can that never cause an overflow or an underflow?
Pointers only move forward, so a delayed copy is always behind the real value. The writer, seeing an old read pointer, thinks less has been read than really has, so it sees less free space and may say full early, but never late. The reader, seeing an old write pointer, sees less data and may say empty early, but never late. The flags are pessimistic, which costs some throughput but never loses or repeats a word.
coreThis full flag was written by copying the binary rule (invert only the MSB) into the Gray version. What happens?
assign full_next = (wgray_next == {~rgray_sync[AW], rgray_sync[AW-1:0]});In Gray code, two pointers one lap apart differ in their top two bits, not just the top bit. With the read pointer at 0000, this rule waits for the write pointer to reach Gray 1000, which is binary 15, so the writer fills 15 entries of an 8-entry memory before stopping and overwrites unread data. Checking all 256 pointer pairs of a depth-8 FIFO, this rule misses all 16 true full cases. The correct comparison inverts rgray_sync[AW:AW-1] and keeps the rest.
coreWhy is full computed from wgray_next and registered, rather than computed combinationally from the current wgray?
Using the next pointer means full rises on the same clock edge as the write that fills the last entry. If it were computed from the current pointer, full would appear one cycle late, and a write in that cycle would overflow. Registering it also gives the writer a clean flop output with no glitches from the comparison logic. The same reasoning applies to empty on the read side.
advancedA burst of 64 words is written at 200 MHz into an async FIFO, one word per cycle. The reader takes one word per cycle at 100 MHz. What depth would you choose?
The burst lasts 64 x 5 ns = 320 ns, and in that time the reader takes 320 / 10 = 32 words, so 32 words pile up. On top of that, the reader only starts after the write pointer has crossed into its domain, and the writer only sees freed space after the read pointer has crossed back, each taking a few cycles. So 32 is too tight, and the depth needs a few more entries of margin. Because the Gray scheme wants a power of two, you would choose 64, or accept that the writer may stall briefly at the end of a burst with depth 32.
advancedHow would you add an almost-full flag to an async FIFO, and why is it still safe?
In the write domain, convert the synchronized read Gray pointer back to binary and compute occupancy as wbin minus that value, modulo the pointer width. Raise almost-full when the occupancy reaches a threshold, and register the result. Because the read pointer copy is old, the computed occupancy is never lower than the truth, so almost-full can only come early, never late. The Gray-to-binary conversion is safe here because it acts on a value that has already been synchronized into the write domain.