Async FIFO problem...

Yet another async FIFO question... :(

I've inherited an async FIFO that doesn't work. This is, I think, a
fairly standard implementation. On the write port, a clock and a write
enable increment a write pointer, and write the write data into a RAM.

The read pointer is Gray-coded, clocked into a reg on the write clock,
inverse coded, and then compared with the write pointer, to give a
write-side full flag.

The read side is simply the inverse of the write side.

So far, so good. The problem is that this design assumes a
free-running write clock, and my write clock is not free-running; I
simply generate a clock when the (unpredicatable) write data appears.
The write enable is therefore effectively redundant.

The problem arises because the 'fifo full' flag is generated by the
*write* clock. If, on write X, the comparator determines that the FIFO
is full, then the full flag is generated, and I don't create any more
write clocks. The read side might empty the FIFO, but this information
never gets back to the write port, because the register that samples
the Gray-coded read pointer is clocked by the write clock.

Any ideas on how I re-design this to cope with a write clock which
isn't free-running?

TIA -

Paul

Hi - 

What's clocking the logic that's looking at the full flag?  Is it by
any chance an ungated version of the write clock?

Bob Perlman
Cambrian Design Works

On Tue, 08 Mar 2005 19:04:09 +0000, Paul Davis
<rft56@dsl.nospam.pipex.com> wrote:

>Yet another async FIFO question... :(
>
>I've inherited an async FIFO that doesn't work. This is, I think, a
>fairly standard implementation. On the write port, a clock and a write
>enable increment a write pointer, and write the write data into a RAM.
>
>The read pointer is Gray-coded, clocked into a reg on the write clock,
>inverse coded, and then compared with the write pointer, to give a
>write-side full flag.
>
>The read side is simply the inverse of the write side.
>
>So far, so good. The problem is that this design assumes a
>free-running write clock, and my write clock is not free-running; I
>simply generate a clock when the (unpredicatable) write data appears.
>The write enable is therefore effectively redundant.
>
>The problem arises because the 'fifo full' flag is generated by the
>*write* clock. If, on write X, the comparator determines that the FIFO
>is full, then the full flag is generated, and I don't create any more
>write clocks. The read side might empty the FIFO, but this information
>never gets back to the write port, because the register that samples
>the Gray-coded read pointer is clocked by the write clock.
>
>Any ideas on how I re-design this to cope with a write clock which
>isn't free-running?
>
>TIA -
>
>Paul

This might be very tricky. That's why I always demand free-running
clocks.
FULL gets set by the write clock, which is ideal, since only the write
side is interested in FULL.
But FULL gets reset by a write clock, and that is inherently
asynchronous to any write operation. So one has to do some trickery to
move the falling edge of FULL back to the write clock domain. That's
where metastability can bite you.
And the same is also true for EMPTY ( with the clock names reversed).
The extra delay encountered at the trailing edge of FULL ( or EMPTY)
really does not matter, as long as it's just a few clock ticks. It just
means the FIFO pretends to be FULL (or EMPTY) a few cycles longer than
necessary. No big deal.

Maybe this helps to get your creative juices flowing. Your challenge is
non-trivial.
Peter Alfke, Xilinx Applications ("FIFO is my middle name")

On Tue, 08 Mar 2005 20:47:29 GMT, Bob Perlman
<bobsrefusebin@hotmail.com> wrote:

>Hi - 
>
>What's clocking the logic that's looking at the full flag?  Is it by
>any chance an ungated version of the write clock?

No - it's just the write clock that gets supplied to the FIFO. I do
create the clock myself, though - it's a combination of various
signals from two other clock domains. There isn't a free-running
precursor to this signal in one of the two domains (presumably that's
what you meant?)

- Paul

Paul Davis wrote:
> Yet another async FIFO question... :(
> 
> I've inherited an async FIFO that doesn't work. This is, I think, a
> fairly standard implementation. On the write port, a clock and a write
> enable increment a write pointer, and write the write data into a RAM.
> 
> The read pointer is Gray-coded, clocked into a reg on the write clock,
> inverse coded, and then compared with the write pointer, to give a
> write-side full flag.
> 
> The read side is simply the inverse of the write side.
> 
> So far, so good. The problem is that this design assumes a
> free-running write clock, and my write clock is not free-running; I
> simply generate a clock when the (unpredicatable) write data appears.
> The write enable is therefore effectively redundant.
> 
> The problem arises because the 'fifo full' flag is generated by the
> *write* clock. If, on write X, the comparator determines that the FIFO
> is full, then the full flag is generated, and I don't create any more
> write clocks. The read side might empty the FIFO, but this information
> never gets back to the write port, because the register that samples
> the Gray-coded read pointer is clocked by the write clock.
> 
> Any ideas on how I re-design this to cope with a write clock which
> isn't free-running?
> 
> TIA -
> 
> Paul
I think it was common back in the day to have FIFOs without free-running 
clocks but these have mostly disappeared.  What you really want to do, 
if at all possible, is to make the write clock free-running and gate it 
with the write enable.  If you have a gated write clock, you introduce a 
lot of timing issues, and the whole point of the asynchronous FIFO is to 
encapsulate the domain-crossings and abstract those problems away from 
you.  You can change the full flag so that it is clocked by the read 
domain, but then, again, you are reading it in a different domain and 
have domain-crossing issues.  You want all of the domain crossings to be 
between the gray-coded pointers inside the FIFO.
-Kevin

On 8 Mar 2005 13:36:30 -0800, "Peter Alfke" <peter@xilinx.com> wrote:

>Maybe this helps to get your creative juices flowing. Your challenge is
>non-trivial.

No kidding... :)
Luckily, I'm on an hourly rate. Just checking that there weren't any
simple answers.

I recall using small discrete FIFOs about 10 or 15 years ago that
bubbled through read and write ops, and that only required a single
write strobe. I may try to look it up (a 7400 device?), but I remember
being surprised that they worked at all.

- Paul

First I apologize for a typo: FULL gets reset by the read clock (of
course,not the write clock!)

The fall-through FIFO that you mention was my Fairchild 3341 design (or
 copy thereof).
It was a real self-clocking asynchronous shift register. AMD later
second-sourced it, but further FIFOs were all dual-ported-RAM based.
I have fiddled with FIFOs for 35 years. And the best one (and the most
thoroughly tested one) is the FIFO controller in every Virtex-4
BlockRAM. 500 MHz asynchronous operation, tested with 10e14
"asynchronously-going-empty" cycles, and no glitch!

Peter Alfke, Xilinx Applications

Peter Alfke wrote:

(snip)

> I have fiddled with FIFOs for 35 years. And the best one (and the most
> thoroughly tested one) is the FIFO controller in every Virtex-4
> BlockRAM. 500 MHz asynchronous operation, tested with 10e14
> "asynchronously-going-empty" cycles, and no glitch!

Asynchronous, meaning to phase relationship between the two 
clocks?   (And hope they don't phase lock by themselves.)

How about a PLL to lock onto exactly the worst part of the cycle 
to make the transition?   I am not so sure what to put into the 
phase comparator, but it would seem that it might be possible.

-- glen

Why?
The two clocks can have any frequency or phase relationship, or
non-relationship. That's what I mean by asynchronous. But both should
be a reasonably steady stream of clocks. Need not be of a fixed
frequency. And all that only to resolve FULL and EMPTY. Otherwise you
can use any clocks or strobes you want.
Peter Alfke

"Peter Alfke" <peter@xilinx.com> writes:
> FULL gets set by the write clock, which is ideal, since only the write
> side is interested in FULL.
> But FULL gets reset by a write clock, and that is inherently
> asynchronous to any write operation.

Unless I'm very confused, you must have meant to write that FULL gets
reset by a read clock.