Asynchronous FIFO with depth that is not a power of 2

[googler]

I am trying to design an asynchronous FIFO that works with two clock
domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads
happen on clk_B. clk_A is faster than clk_B. I thought about using
gray-coded write and read pointers that is usually recommended for
designing async fifos, but the problem is that in this case the depth
of the FIFO is 688, which is not a power of 2. So it seems I cannot
use the Gray pointer technique. Is that right?

Can this be done using binary pointers instead of using Gray pointers?
Maybe we can use handshaking technique, exchanging 'ready' and
'acknowledge' between the two sides whenever the write/read pointer is
to be sent across clock domain. So suppose we want to send the write
pointer from clk_A domain to clk_B domain. When write pointer in clk_A
domain changes, it generates a 'ready' that goes to clk_B domain. This
'ready' is synchronized in clk_B domain and then clk_B reads the value
of the write pointer. Then clk_B domain sends 'acknowledge' back to
clk_A domain (where it is synchronized). Only after clk_A domain gets
this 'acknowledge' back, it can change the write pointer value. Is
this concept correct? If yes, then I guess there is still a problem.
In the above example, the write side is on faster clock. If the write
pointer cannot change until write side gets back 'acknowledge', then
we probabaly need to stall writes to the FIFO, correct?

Please advise how this can be done. Thanks.

 

[John_H]

googler wrote:

I am trying to design an asynchronous FIFO that works with two clock
domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads
happen on clk_B. clk_A is faster than clk_B. I thought about using
gray-coded write and read pointers that is usually recommended for
designing async fifos, but the problem is that in this case the depth
of the FIFO is 688, which is not a power of 2. So it seems I cannot
use the Gray pointer technique. Is that right?
snip

You can use a Gray pointer but with one slight change. Increment from
Gray 343 to Gray -344. There is still only one bit (the MSbit)
change.

Gray counters are often easier to design as binary counters with a
binary-to-gray conversion such that you make the increment from binary
343 to binary -344 and let the Gray conversion do its stuff.

If your depth was an odd number of elements, it wouldn't work with
this Gray adjustment. Since you're even, you're set.

- John_H

 

[Kevin Neilson]

googler wrote:

I am trying to design an asynchronous FIFO that works with two clock
domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads
happen on clk_B. clk_A is faster than clk_B. I thought about using
gray-coded write and read pointers that is usually recommended for
designing async fifos, but the problem is that in this case the depth
of the FIFO is 688, which is not a power of 2. So it seems I cannot
use the Gray pointer technique. Is that right?


Please advise how this can be done. Thanks.

You can make any even-numbered Graycoded sequence. Instead of counting
from Gray(0) to Gray(2^N-1), where Gray(x) is the Gray version of the
sequential number x and N = ceil(log2(FIFO_DEPTH)), count from:

Gray(2^N/2 - FIFO_DEPTH/2) to Gray(2^N/2 + FIFO_DEPTH/2 - 1)

So in your case, FIFO_DEPTH=688 and N=10, so you would count from

Gray(168) to Gray(855)

and then roll over back to Gray(168).

Gray(168)=0011111100 and Gray(855)=1011111100

which you can see differ only in bit 9, so there is a smooth Gray-like
transition when you roll over.

In case you don't know the Gray conversion,
Gray(x[y]) = x[y]^x[y+1]
where [y] is bit y and ^ is an XOR.
-Kevin

 

[John_H]

googler wrote:

Thank you Kevin and John_H for your replies. I will try your ideas and
I hope it will solve my problem (it is a little more complicated than
I described but that was the main problem I was facing).

Since we are discussing this particular topic, I will take this
opportunity to get some concepts clear. Basically I am not totally
clear on why gray pointers are being used instead of just using binary
pointers and synchronizing them in the other clock domain. I have done
some reading on this and they say that if multiple bits in a pointer
change at the same time on a clock edge, then the data obtained after
synchronization may not be correct. My first question is, why will the
synchronized data not be correct? Is it because of the fact that there
is always a chance (however small) that the output of a synchronizer
may not be stable, which means it can be any value 0 or 1?
-------------

The problem isn't whether it's a one or zero, the problem is catching
them all on the same side of the transition. Imagine a bunch of people
lined up in the hallway against the walls. When a whistle blows, one or
more of those against each wall must race to the other side and wait
until the next whistle just like bits changing state in a counter.
Pictures are taken at regular intervals with no knowledge of when the
whistle blows. Most of the pictures show people lined up on both sides
of the hallway. Occasionally you see the motion of someone still racing
from one side to the other. You can decide pretty quickly if someone is
considered on the right or the left side of the hallway but the players
don't all have the same reflexes so a photo may show one person on the
other side of the hallway while another hasn't yet gotten very far.
They *should* all be pre-journey or post-journey but sometimes you get a
mixed set.

It's because bits don't change at the same attosecond (or get sampled at
the same point for that matter) that the occasional sample has some bits
that have transitioned and some that haven't yet though they were all
supposed to run on the same whistle.

The Gray counter (thanks, Frank Gray of Bell Labs) gives you just one
person running from one side of the hall to the other for any one
whistle blow. Since only one bit changes, the photo can always say
right or left side even if it rarely takes a moment longer to figure out
which side.

-------------

If the above is true, then even in case of gray pointer the
synchronizer output may be erroneous. True, the error will be only in
one bit, but it is still an error and may cause things to fail, right?
For example, if the write pointer increments and causes the FIFO to
become full, and at the same time the value of the write pointer is
read incorrectly on the other side as the old value, then the read
side will not know that the FIFO has become full, which is wrong.
(Well, people may argue that read side usually does not need the
'full' flag, but there might be some logic there that needs it.. or
the read side may need to calculate the number of current entries,
etc.)

The read side doesn't need to know that the FIFO is full, just that
there's data available since it's the write side that needs to avoid
overfilling the FIFO. Having the read side be a cycle late in knowing
that there's more data is not a problem in any system I've ever seen or
imagined. The write side of the FIFO similarly doesn't need nanosecond
accurate empty (or fill level) information but needs to know when it
should stop providing data. If you want a burst scheme of a certain
size and want to make sure two bursts butt up against each other to
avoid any possibility of read gaps, it's not an issue of providing the
flags faster, it's an issue of sizing your FIFO so the delays inherent
in an asynchronous system are part of your latency/bandwidth budget.

Asynchronous crossings are where green engineers often demonstrate the
greatest trouble. Getting to understand and work around those
asynchronous boundaries makes life in this digital world much easier.

Happy coding,
- John_H

 

[googler]

On May 14, 5:35 pm, Kevin Neilson
<kevin_neil...@removethiscomcast.net> wrote:

googler wrote:
I am trying to design an asynchronous FIFO that works with two clock
domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads
happen on clk_B. clk_A is faster than clk_B. I thought about using
gray-coded write and read pointers that is usually recommended for
designing async fifos, but the problem is that in this case the depth
of the FIFO is 688, which is not a power of 2. So it seems I cannot
use the Gray pointer technique. Is that right?

Please advise how this can be done. Thanks.

You can make any even-numbered Graycoded sequence.  Instead of counting
from Gray(0) to Gray(2^N-1), where Gray(x) is the Gray version of the
sequential number x and N = ceil(log2(FIFO_DEPTH)), count from:

Gray(2^N/2 - FIFO_DEPTH/2) to Gray(2^N/2 + FIFO_DEPTH/2 - 1)

[snip]

Thank you Kevin and John_H for your replies. I will try your ideas and
I hope it will solve my problem (it is a little more complicated than
I described but that was the main problem I was facing).

Since we are discussing this particular topic, I will take this
opportunity to get some concepts clear. Basically I am not totally
clear on why gray pointers are being used instead of just using binary
pointers and synchronizing them in the other clock domain. I have done
some reading on this and they say that if multiple bits in a pointer
change at the same time on a clock edge, then the data obtained after
synchronization may not be correct. My first question is, why will the
synchronized data not be correct? Is it because of the fact that there
is always a chance (however small) that the output of a synchronizer
may not be stable, which means it can be any value 0 or 1?

If the above is true, then even in case of gray pointer the
synchronizer output may be erroneous. True, the error will be only in
one bit, but it is still an error and may cause things to fail, right?
For example, if the write pointer increments and causes the FIFO to
become full, and at the same time the value of the write pointer is
read incorrectly on the other side as the old value, then the read
side will not know that the FIFO has become full, which is wrong.
(Well, people may argue that read side usually does not need the
'full' flag, but there might be some logic there that needs it.. or
the read side may need to calculate the number of current entries,
etc.)

 

On Thursday, 15 May 2008 04:05:03 UTC+5:30, Kevin Neilson wrote:

googler wrote:
I am trying to design an asynchronous FIFO that works with two clock
domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads
happen on clk_B. clk_A is faster than clk_B. I thought about using
gray-coded write and read pointers that is usually recommended for
designing async fifos, but the problem is that in this case the depth
of the FIFO is 688, which is not a power of 2. So it seems I cannot
use the Gray pointer technique. Is that right?


Please advise how this can be done. Thanks.

You can make any even-numbered Graycoded sequence. Instead of counting
from Gray(0) to Gray(2^N-1), where Gray(x) is the Gray version of the
sequential number x and N = ceil(log2(FIFO_DEPTH)), count from:

Gray(2^N/2 - FIFO_DEPTH/2) to Gray(2^N/2 + FIFO_DEPTH/2 - 1)

So in your case, FIFO_DEPTH=688 and N=10, so you would count from

Gray(168) to Gray(855)

and then roll over back to Gray(168).

Gray(168)=0011111100 and Gray(855)=1011111100

which you can see differ only in bit 9, so there is a smooth Gray-like
transition when you roll over.

In case you don't know the Gray conversion,
Gray(x[y]) = x[y]^x[y+1]
where [y] is bit y and ^ is an XOR.
-Kevin

Hi Kevin,
In your method How can we generated Full and Empty signals?

Thanks in advance

Regards,
Ketan

 

[Kevin Neilson]

Hi Kevin,
In your method How can we generated Full and Empty signals?

Thanks in advance

Regards,
Ketan

Ketan,
First, let me say, if you can get a FIFO from somewhere else, do so. I know it's not always easy to find one, but there are a lot of little things that can go wrong when you make your own. Also, I would just round the depth up to a power of 2, especially if you are using FPGA blockRAM.

From my recollection the empty logic would be something like below. Note that you don't have to do Gray-to-binary conversion, which can use many levels of logic. Only binary-to-Gray is used.

always@(posedge rd_clk) begin
// Update pointers on FIFO read
if (rd_en) begin
// next_next_rd_ptr is the pointer 2 ahead of rd_ptr
if (next_next_rd_ptr==855) next_next_rd_ptr <= 168; // ptr rolls from 855 to 168
else next_next_rd_ptr <= next_next_rd_ptr + 1;

// You can use rd_ptr as the read address to the RAM.
// You use rd_ptr_gray for empty and full flag logic.
next_rd_ptr <= next_next_rd_ptr;
rd_ptr <= next_rd_ptr;

next_rd_ptr_gray <= Gray(next_next_rd_ptr); // Gray() is the fcn described previously
rd_ptr_gray <= Gray(next_rd_ptr);
end

// The empty flag is asserted if the pointers match or if you are reading
// the FIFO and the pointers will match after the read.
// Please note that you may re-register wr_ptr_gray in this clock
// domain to be extra-safe. That would add a little latency.
empty <= rd_ptr_gray==wr_ptr_gray || rd_en && next_rd_ptr_gray==wr_ptr_gray;

// The almost-empty flag would require an extra pointer:
almost_empty <= next_rd_ptr_gray==wr_ptr_gray || rd_en && next_next_rd_ptr_gray==wr_ptr_gray;
end