TDEB Top Bar

Trending
Semiconductor Industry News — The Digital Electronics Blog
Follow Us

TDEB Masthead

The Semiconductor Hub

Semiconductors.  Chips and Systems.  Innovation.

Indexed by leading Search Engines, AI and referenced by Engineers worldwide 500+ Articles 10M+ Pageviews 30+ Reports 50+ Citations

Asynchronous FIFO Design: Gray Pointers, Synchronizers and Safe Flags (FIFO Series, Part 2)

The Semiconductor Hub
by
0
Share Facebook X LinkedIn WhatsApp Email
Hand-drawn cover card for FIFO Series Part 2, Asynchronous FIFO, with a sketch of entries moving from push to pop.

Part 1 built a FIFO where the writer and the reader share one clock. Real chips are rarely that tidy. A PCIe controller runs on a clock recovered from its link, a DMA engine on the fabric clock, a sensor interface on whatever the sensor provides. Wherever two clock domains exchange a stream of data, there is almost always an asynchronous FIFO between them, and it is one of the few places where a small design mistake can pass every simulation and still fail in silicon.

This is Part 2 of the FIFO Series. We keep the ring buffer and the two pointers from Part 1, put each pointer in its own clock domain, and work out how each side can learn where the other pointer is without ever seeing a wrong value.

Key takeaways

  • An asynchronous FIFO has a write side on one clock and a read side on another. Each side owns its own pointer and only sees a delayed, synchronized copy of the other one.
  • Pointers cross the clock boundary in Gray code, so only one bit changes per step. A synchronizer that samples during a change then returns either the old value or the new one, never a third value.
  • Full is computed in the write domain and empty in the read domain. Both are pessimistic: a flag may stay asserted a few cycles longer than needed, but it is never cleared too early.
  • The data itself never goes through a synchronizer. It sits in the memory, and the synchronized pointer is what makes it safe to read.
  • Most failures come from the surroundings: a binary pointer that crosses, logic between the Gray register and the synchronizer, missing constraints, or one side reset while the other keeps running.

In this part

What problem it solves

A single flip-flop can carry one slow control bit across a clock boundary: two flops in series give a metastable first stage most of a cycle to settle. That does not work for a bus. If a 32-bit value changes while the destination clock samples it, each bit settles on its own, and the receiver can capture a mix of old and new bits that was never sent.

The asynchronous FIFO solves this for a stream of words. The words are written into a memory by the write clock and read out by the read clock. Only the pointers cross the boundary, and they are encoded so that a mixed sample cannot happen.

The interface

Hand-drawn block diagram of an asynchronous FIFO: a write domain with push, wdata, the write pointers and full logic, a read domain with pop, rdata, the read pointers and empty logic, a dual-port memory between them, and two-flop synchronizers carrying each Gray pointer across the clock boundary.

The ports look like Part 1, split in two. The write side has wclk, wrst_n, push, wdata and full. The read side has rclk, rrst_n, pop, rdata and empty. Every signal belongs to exactly one domain.

Some designs also export a write-side count and a read-side count. Each mixes a local pointer with a synchronized remote one, so each is a conservative estimate: the write side can only overstate how full the FIFO is, and the read side can only understate how much data is waiting.

Why the pointers cross in Gray code

Hand-drawn table of 4-bit pointer values 0 to 15 in binary and Gray code, with the empty and full rules for a depth-8 FIFO and a worked example where read pointer 3 and write pointer 11 give full.

A binary counter can flip many bits in one step: 0111 to 1000 flips all four. If the read domain samples during that step, each bit can land either way, and it might capture 1111 or 0000. A write pointer that appears to jump ahead lets the reader pop entries that were never written.

A Gray counter changes exactly one bit per step, including the wrap from the last value back to zero. When the synchronizer samples during a change, only that one bit is uncertain, so the result is either the old pointer or the new pointer. The receiving side may be one step behind, and that is safe.

The usual implementation keeps two registers per pointer: a binary counter for incrementing and addressing the memory, and a Gray copy computed as (bin >> 1) ^ bin from the next binary value and registered. The Gray register is the only thing that crosses. It must come straight from a flop with no logic in between, because combinational logic can glitch and turn a clean one-bit change into several transient ones.

Full and empty in their own domains

Empty is a read-side question, so it is computed in the read domain: the read pointer in Gray code is compared with the write pointer after two synchronizer flops. If they match, there is nothing the reader can safely take.

Full is a write-side question, computed in the write domain against the synchronized read pointer. Part 1 used one extra wrap bit: full means equal index bits and a different top bit. In Gray code the same condition becomes "the top two bits inverted and the rest equal", because the second bit of a Gray value is the XOR of the two top binary bits. The table above works it through for a depth of 8 with 4-bit pointers: read pointer 3 is 0010 in Gray, write pointer 11 is 1110, and flipping the top two bits of 0010 gives 1110, so the FIFO is full.

Hand-drawn timing diagram: a push in the write clock domain changes the Gray write pointer, which passes through two read-clock synchronizer flops before empty falls, after which the reader pops the entry and empty rises again.

The timing diagram shows the price. A push changes wgray, the first synchronizer flop catches it on the next read edge, the second one a cycle later, and the registered empty flag falls one edge after that. The reader sees the new entry a few read cycles after it was written. Full behaves the same way from the other side. Both flags are pessimistic, and that is exactly the guarantee we want: a late flag costs a little latency, while an early flag loses data.

RTL sketch

A power-of-two depth of 4 or more, binary and Gray pointers in each domain, two-flop synchronizers, and registered flags computed from the next pointer values:

module async_fifo #(
  parameter int W     = 32,
  parameter int DEPTH = 16,               // power of two, at least 4
  localparam int AW   = $clog2(DEPTH)
) (
  input  logic         wclk, wrst_n,
  input  logic         push,
  input  logic [W-1:0] wdata,
  output logic         full,
  input  logic         rclk, rrst_n,
  input  logic         pop,
  output logic [W-1:0] rdata,
  output logic         empty
);
  logic [W-1:0] mem [DEPTH];
  logic [AW:0]  wbin, wgray, rbin, rgray;
  logic [AW:0]  rgray_w1, rgray_w2;       // read pointer seen by wclk
  logic [AW:0]  wgray_r1, wgray_r2;       // write pointer seen by rclk

  // write domain
  wire        do_push  = push && !full;
  wire [AW:0] wbin_nx  = wbin + do_push;
  wire [AW:0] wgray_nx = (wbin_nx >> 1) ^ wbin_nx;

  always_ff @(posedge wclk or negedge wrst_n)
    if (!wrst_n) begin
      wbin <= '0; wgray <= '0; full <= 1'b0;
      rgray_w1 <= '0; rgray_w2 <= '0;
    end else begin
      wbin <= wbin_nx; wgray <= wgray_nx;
      rgray_w1 <= rgray; rgray_w2 <= rgray_w1;
      full <= (wgray_nx == {~rgray_w2[AW:AW-1], rgray_w2[AW-2:0]});
    end

  always_ff @(posedge wclk)
    if (do_push) mem[wbin[AW-1:0]] <= wdata;

  // read domain
  wire        do_pop   = pop && !empty;
  wire [AW:0] rbin_nx  = rbin + do_pop;
  wire [AW:0] rgray_nx = (rbin_nx >> 1) ^ rbin_nx;

  always_ff @(posedge rclk or negedge rrst_n)
    if (!rrst_n) begin
      rbin <= '0; rgray <= '0; empty <= 1'b1;
      wgray_r1 <= '0; wgray_r2 <= '0;
    end else begin
      rbin <= rbin_nx; rgray <= rgray_nx;
      wgray_r1 <= wgray; wgray_r2 <= wgray_r1;
      empty <= (rgray_nx == wgray_r2);
    end

  always_ff @(posedge rclk)
    if (do_pop) rdata <= mem[rbin[AW-1:0]];
endmodule

The flags compare the next local pointer with the current synchronized remote pointer, so they are registered and still take the current push or pop into account. The memory write is in the write domain and the read is in the read domain. A slot is read only after its write pointer has passed through two read flops, so its data has been stable for at least two read cycles before the read.

Corner cases

  • Very different clock rates. If the write clock is several times faster, the read side may skip several pointer values between samples. That is fine with Gray code as long as each sample is a value the pointer really held, which the registered Gray output guarantees. What the receiver must never do is assume the pointer moved by exactly one.
  • Depth and round-trip latency. A full FIFO only reopens after a pop has travelled back through the write synchronizers. If the depth is smaller than the round trip in cycles, a streaming source stalls even when the long-term rates match. Size the depth to cover the burst and the flag latency together.
  • Non-power-of-two depth. A plain Gray sequence only wraps cleanly at a power of two. Part 8 covers the options when the depth cannot be one.
  • Reset. The two resets must both be applied while traffic is stopped, or a domain that comes out of reset early may see the other pointer at an old value. Reset sequencing when only one side resets gets its own part later in the series.

Timing, area and power

  • Constraints. The two clocks are asynchronous to each other, so the pointer paths are not timed as normal paths. Use a maximum-delay or skew constraint on the Gray pointer bus so that all bits arrive at the synchronizer within about one destination clock period. Without it, routing can spread the bits enough that a "one-bit change" arrives as two changes.
  • Synchronizer cells. Many libraries have dedicated synchronizer flops with better metastability resolution. Use them for the first and second stage and keep the two flops close together. Faster clocks or harsher reliability targets may need three stages.
  • Area. Each pointer costs a binary counter, a Gray register and a two-stage synchronizer on the far side. For a deep FIFO the memory dominates; for a four-entry FIFO the pointer logic is a large share.

Verification checklist

  • A scoreboard queue written on the write clock and checked on the read clock, run with many clock ratios: equal, close, 2 to 1, 1 to 7, and drifting phase.
  • Assertions in each domain:
    a_gray_w: assert property (@(posedge wclk) disable iff (!wrst_n)
                $onehot0(wgray ^ $past(wgray)));
    a_gray_r: assert property (@(posedge rclk) disable iff (!rrst_n)
                $onehot0(rgray ^ $past(rgray)));
    a_no_ovf: assert property (@(posedge wclk) disable iff (!wrst_n)
                !(push && full));
    a_no_udf: assert property (@(posedge rclk) disable iff (!rrst_n)
                !(pop && empty));
  • A metastability model in simulation: on the first synchronizer flop, when the input changed close to the sampling edge, randomly keep the old value of each changed bit. Plain RTL simulation never shows the mixed values that break binary pointers.
  • A structural CDC check that confirms only the Gray registers cross, nothing combinational sits between them and the synchronizers, and no other signal crosses unsynchronized.
  • Coverage of fill to full, drain to empty, pointer wrap in both domains, and reset of each side with the other side idle.

Interview questions

1. Why not synchronize a binary pointer with two flops?

A strong answer explains that several bits can change at once, so a sample during the change can produce a value the pointer never held, and then shows that Gray code limits the change to one bit so the sample is always the old or the new value.

2. Why is empty computed in the read domain and full in the write domain?

A strong answer says each flag is used by the side that owns it, so it must be in that clock, and that computing it from a synchronized remote pointer makes it pessimistic, which is safe.

3. Write the full condition for Gray pointers.

A strong answer gives "top two bits inverted, the rest equal" and explains it from the binary wrap-bit rule of a synchronous FIFO, using a short example.

4. The read clock is ten times slower than the write clock. Does the design still work?

A strong answer says yes, because every sample is a real pointer value even if many steps are skipped, and then discusses the effect on full latency and the depth needed to keep the writer streaming.

5. What would you check in the constraints and the CDC report?

A strong answer mentions the maximum-delay or skew constraint on the Gray bus, synchronizer cell choice, no logic before the synchronizer, the memory read path, and reset domain crossing.

Where it is used in real chips

Asynchronous FIFOs sit wherever streams cross clocks: between a PCIe or Ethernet physical layer and the controller logic, between a network-on-chip and the IP blocks attached to it at their own clocks, between a DMA engine and a memory controller, in AXI clock-domain bridges, and at the edge of accelerators that run on their own clock.

The rest of the series

Part 1 covered the synchronous FIFO: pointers, the extra wrap bit, and the same-cycle push and pop.

Part 3 is the first-word fall-through FIFO, where the oldest entry is already waiting on the output before anyone asks for it.

Share Facebook X LinkedIn WhatsApp Email

Post a Comment

0 Comments

Your comments will be moderated before it appears here.

Post a Comment (0)

#buttons=(Ok, Go it!) #days=(20)

Our website uses cookies to enhance your experience. Learn more
Ok, Go it!