Asynchronous FIFO with depth that is not a power of 2
googler
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
> 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?
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
> 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?
>
>
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
googler
<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)
>
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.)
John_H
> [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?
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
John Penton
> 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>
> binary-to-gray conversion such that you make the increment from binary
> 343 to binary -344 and let the Gray conversion do its stuff.
But make sure that the Gray value comes directly out of a flop before it
crosses into the other clock domain. Don't put the conversion logic
in-between the clock domains.
John
--
John Penton, posting as an individual unless specifically indicated
otherwise.
John Penton
Others have commented that a Gray scheme can be made to work. Your scheme
above is also reasonable (if rather high latency). Of course you need a
ready and ack for both the pointers. FIFOs almost always need a method to
stall the input side - unless you can guarentee (by analysis) that it can
never fill up. However, to avoid the excessive delay that you envisage you
could have two sets of registers for each pointer. A current state -
recording how many items have been written or read, and then a state for
transmission - which captures the current state and holds it stable while
the handshake is ongoing.
A final thought I have is that 688 entries is pretty big. In particular, I
think it requires a 688 input mux (or muxes) to read out the data. I
suppose that is only 11 gates deep, but if the FIFO is particularly wide, it
will also involve a lot of routing (and of course, it is possible to break
timing across an asynchronous interface). I would be thinking about a
two-stage system, with a large synchronous FIFO on the front (possibly built
with a RAM if the data is wide) and a small asynchronous FIFO on the back.
I guess it all depends on the data characteristics and the design
requirements.
shethke...@gmail.com
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
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