FPGA Central - World's 1st FPGA / CPLD Portal

FPGA Central

World's 1st FPGA Portal

 

Go Back   FPGA Groups > NewsGroup > FPGA

FPGA comp.arch.fpga newsgroup (usenet)

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 12-13-2006, 05:14 AM
bijoy
Guest
 
Posts: n/a
Default FPGA : Async FIFO, Programmable full

Hi In designing asynchronous FIFOs we have to use Gray code read/write pointers.

And while using gray code I know how to generate full and empty flags.

But i would like to get ideas from experienced designers how to generate Programmable full or programmable empty flags

Thanks in advance

rgds bijoy
Reply With Quote
  #2 (permalink)  
Old 12-13-2006, 10:25 AM
Symon
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

"bijoy" <[email protected]> wrote in message
news:[email protected]
> Hi In designing asynchronous FIFOs we have to use Gray code read/write
> pointers.
>

Well, no, you don't _HAVE_ to. You can use ordinary binary counters just
fine, as long as you design the clock domain crossing bit properly.
>
> And while using gray code I know how to generate full and empty flags.
>

Perhaps you could share this with the V4 FIFO designers! :-) Sorry Peter!
>
> But i would like to get ideas from experienced designers how to generate
> Programmable full or programmable empty flags
>
> Thanks in advance
>
> rgds bijoy
>

I use binary counters for my FIFOs. A Google search shows that arithmetic is
difficult on gray coded numbers.
e.g. http://www.altera.com/literature/an/an083_01.pdf

There may well be a trick other than converting to binary, let us know if
you find it!
HTH, Syms.


Reply With Quote
  #3 (permalink)  
Old 12-13-2006, 01:55 PM
Kim Enkovaara
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

Symon wrote:

> "bijoy" <[email protected]> wrote in message
>
>>Hi In designing asynchronous FIFOs we have to use Gray code read/write
>>pointers.

>
> Well, no, you don't _HAVE_ to. You can use ordinary binary counters just
> fine, as long as you design the clock domain crossing bit properly.


But crossing the clock domain with binary counter is hard to do correctly,
it needs some kind of handshake protocol. It's not enough to just put
dual flops to each counter bit like with gray coding.

--Kim
Reply With Quote
  #4 (permalink)  
Old 12-13-2006, 03:31 PM
Ben Jones
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full


"Kim Enkovaara" <[email protected]> wrote in message
news:[email protected] ..
> Symon wrote:
>
>> "bijoy" <[email protected]> wrote in message
>>>Hi In designing asynchronous FIFOs we have to use Gray code read/write
>>>pointers.

>>
>> Well, no, you don't _HAVE_ to. You can use ordinary binary counters just
>> fine, as long as you design the clock domain crossing bit properly.

>
> But crossing the clock domain with binary counter is hard to do correctly,
> it needs some kind of handshake protocol. It's not enough to just put
> dual flops to each counter bit like with gray coding.


A useful compromise is to have counters in binary, so you can have fast
arithmetic, and then convert from binary to Gray-code, cross the clock
domain, and then convert back again to do the pointer comparison. While
there is some latency, it is usually easier than a bi-directional handshake.

Cheers,

-Ben-


Reply With Quote
  #5 (permalink)  
Old 12-13-2006, 05:30 PM
JuanC
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

You can read these papers by Cliff Cummings on aSynchronous FIFO
design:

http://www.sunburst-design.com/paper...02SJ_FIFO1.pdf
http://www.sunburst-design.com/paper...02SJ_FIFO2.pdf

Reply With Quote
  #6 (permalink)  
Old 12-14-2006, 12:50 AM
Peter Alfke
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

There is a wrong way and a right way to convert binary to Gray count
values:
The wrong way hangs the (simple!) combinatorial conversion logic (XORs)
on the binary outputs. That does you no good, since the Gray code will
just reflect the binary transient errors.
The right way takes the D inputs of the binary counter (, converts them
independently to Gray and registers them in their own flip-flops. Now
you have two parallel rgisters, both counting in step, the first in
binary, the other in Gray, and there are no funny decoding spikes.
BTW, only Gray counter outputs have the feature that you can compare
two asynchronous counters for identity, without transient errors.
If the Gray code does not come from a counter, it might change multiple
bits per transition...
Fast asynchronous FIFOs with configurable flag values are definitely
not a trivial design exercise. We got it right in Virtex-5, after a
silly oversight in Virtex-4.
Peter Alfke


On Dec 13, 6:31 am, "Ben Jones" <[email protected]> wrote:
> "Kim Enkovaara" <[email protected]> wrote in messagenews:[email protected] hti.fi...
>
> > Symon wrote:

>
> >> "bijoy" <[email protected]> wrote in message
> >>>Hi In designing asynchronous FIFOs we have to use Gray code read/write
> >>>pointers.

>
> >> Well, no, you don't _HAVE_ to. You can use ordinary binary counters just
> >> fine, as long as you design the clock domain crossing bit properly.

>
> > But crossing the clock domain with binary counter is hard to do correctly,
> > it needs some kind of handshake protocol. It's not enough to just put
> > dual flops to each counter bit like with gray coding.A useful compromise is to have counters in binary, so you can have fast

> arithmetic, and then convert from binary to Gray-code, cross the clock
> domain, and then convert back again to do the pointer comparison. While
> there is some latency, it is usually easier than a bi-directional handshake.
>
> Cheers,
>
> -Ben-


Reply With Quote
  #7 (permalink)  
Old 12-14-2006, 04:56 AM
KJ
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

"bijoy" <[email protected]> wrote in message
news:[email protected]
> Hi In designing asynchronous FIFOs we have to use Gray code read/write
> pointers.
>
> And while using gray code I know how to generate full and empty flags.
>
> But i would like to get ideas from experienced designers how to generate
> Programmable full or programmable empty flags
>
> Thanks in advance
>

Not to put a damper on the thread but I've found that there are probably
very few applications for true programmable fifo flags inside a programmable
chip that can be in-system updated like an FPGA. By 'programmable flag' I'm
assuming that we're talking about having some register that can be written
to with some arbitrary number that will cause some associated fifo status
flag to trigger when it reaches that level. This arbitrary number is in
some fashion controlled by software and is not and can not be known a
priori.

There are applications where I'd like a flag to go off at 'almost full' or
'almost empty' but those 'almost' conditions have always been able to be
determined as hard fixed constants. Maybe those levels are things like 7/8
or 321/456 or .01 (just making up numbers here) but the point is that the
point where I want a fifo flag to trigger has (for me at least) always been
traceable back to known system parameters. It could be that the trigger
level is some bizzarro function of those system parameters but the end
result is a known fixed number so generally what I will do is code the
bizzarro function into the VHDL that instantiates the fifo to produce the
constant that will be input as a generic input to the fifo that uses it to
determine the flag status trigger levels.

True programmable flags where some outside software comes in and actually
tells the fifo what specific level to trigger at came about back when fifos
were mostly implemented as discrete parts and the suppliers of these little
gens of course would have virtually no market for parts that trigger at
levels like 7/8 or 321/456 or .01 so instead they came up with a mechanism
to allow the user to program in an arbitrary level...which they did....and
always (in my experience) did so with some constant that was determined from
system parameters.

For those applications that fit the cases I've described and really can have
fixed constants to determine possibly bizzaro trigger levels there is no
need for any convoluted math or moving gray code to binary to do math. Your
gray code counter that keeps track of the depth is a finite state machine,
there is exactly one state that needs to be matched to see if it corresponds
to the equivalent of being 321/456 full.

If someone does have an application that really requires true programmable
flags I'd be interested to hear about it. The environment though is
- Fifo is inside a programmable part.
- That programmable part can be updated in system.

Presumably this would have to mean that the trigger levels can not be
determined either empirically at design/design verification time or as a
function of known system parameters but would (presumably) have to be a
dynamic function of what is going on in a particular system at a particular
time (i.e. something unique to the particular system at that point causes
the software to go 'Woooah, I need to change that fifo trigger level from
321/456 to 7/8 (or some such)'.

KJ


Reply With Quote
  #8 (permalink)  
Old 12-14-2006, 01:52 PM
Kim Enkovaara
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

KJ wrote:
>
> If someone does have an application that really requires true programmable
> flags I'd be interested to hear about it. The environment though is
> - Fifo is inside a programmable part.
> - That programmable part can be updated in system.


I have many examples from telecom side. For example if you have some universal
interface card, that has each port configurable to different protocol (for
example STM1/4/16). That kind of big change in speed usually needs some changes
in fifo limits to get maximum efficiency. If you have for example 8 ports that
would need quite many different FPGA images to cover static settings. Also
partial reconfiguration in my opinion is little too dififficult way to handle
this problem.

Of course you can code the static values for each protocol and use mux to select
one of them to the fifo comparison logic. But it's easier just to add
one register and let the software to handle the values. Also usually maximum
efficiency needs some lab testing to find the optimal fifo values. And waiting
hours for new fpga after each change in the limits is not fun.

I have used programmable flags so many times in lab while debugging different
problems in the design, and while trying to understand the dynamics how different
limits affect interconnected fifo fystems between chips etc.


--Kim
Reply With Quote
  #9 (permalink)  
Old 12-14-2006, 06:00 PM
RCIngham
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

>There is a wrong way and a right way to convert binary to Gray count
>values:
>The wrong way hangs the (simple!) combinatorial conversion logic (XORs)
>on the binary outputs. That does you no good, since the Gray code will
>just reflect the binary transient errors.
>The right way takes the D inputs of the binary counter (, converts them
>independently to Gray and registers them in their own flip-flops. Now
>you have two parallel rgisters, both counting in step, the first in
>binary, the other in Gray, and there are no funny decoding spikes.
>BTW, only Gray counter outputs have the feature that you can compare
>two asynchronous counters for identity, without transient errors.
>If the Gray code does not come from a counter, it might change multiple
>bits per transition...


<snip />
Whether that is the right answer rather depends on WHY the OP "has" to us
Gray Code, which is still not fully established.

BTW, there is a quite interesting article on Gray Code just posted at:
http://www.pldesignline.com/showArti...leID=196604078

Reply With Quote
  #10 (permalink)  
Old 12-14-2006, 06:50 PM
Peter Alfke
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

In an asynchronous FIFO, reading and writing is controlled by two
counters with independent clocks.
If you need to detect FULL or EMPTY, you compare the two counters for
identity.
If you do that with binary counters, you are vulnerable to strange
decoding glitches, while multiple binary bits change (almost, but not
quite, simultaneously). You never have that problem with Gray counters,
where only one bit changes, from one state to the next.
Peter Alfke
=============
RCIngham wrote:
> >There is a wrong way and a right way to convert binary to Gray count
> >values:
> >The wrong way hangs the (simple!) combinatorial conversion logic (XORs)
> >on the binary outputs. That does you no good, since the Gray code will
> >just reflect the binary transient errors.
> >The right way takes the D inputs of the binary counter (, converts them
> >independently to Gray and registers them in their own flip-flops. Now
> >you have two parallel rgisters, both counting in step, the first in
> >binary, the other in Gray, and there are no funny decoding spikes.
> >BTW, only Gray counter outputs have the feature that you can compare
> >two asynchronous counters for identity, without transient errors.
> >If the Gray code does not come from a counter, it might change multiple
> >bits per transition...

>
> <snip />
> Whether that is the right answer rather depends on WHY the OP "has" to use
> Gray Code, which is still not fully established.
>
> BTW, there is a quite interesting article on Gray Code just posted at:
> http://www.pldesignline.com/showArti...leID=196604078


Reply With Quote
  #11 (permalink)  
Old 12-14-2006, 07:26 PM
KJ
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full


Kim Enkovaara wrote:
> KJ wrote:
> >
> > If someone does have an application that really requires true programmable
> > flags I'd be interested to hear about it. The environment though is
> > - Fifo is inside a programmable part.
> > - That programmable part can be updated in system.

>
> I have many examples from telecom side. For example if you have some universal
> interface card, that has each port configurable to different protocol (for
> example STM1/4/16). That kind of big change in speed usually needs some changes
> in fifo limits to get maximum efficiency. If you have for example 8 ports that
> would need quite many different FPGA images to cover static settings. Also
> partial reconfiguration in my opinion is little too dififficult way to handle
> this problem.
>
> Of course you can code the static values for each protocol and use mux to select
> one of them to the fifo comparison logic. But it's easier just to add
> one register and let the software to handle the values. Also usually maximum
> efficiency needs some lab testing to find the optimal fifo values. And waiting
> hours for new fpga after each change in the limits is not fun.
>
> I have used programmable flags so many times in lab while debugging different
> problems in the design, and while trying to understand the dynamics how different
> limits affect interconnected fifo fystems between chips etc.
>


Having a single fifo with (in your case) 8 different flags come out at
those 8 different fill levels would accomplish the same thing. The
only thing that needing muxing would be the 8 different flags not 8
entire fifos. Software would write to a register which would select
one of the 8 pre-defined constants.

At some point though the logic required to generate an arbitrary number
of flags that are comparisons of the fill level to a set of fixed
constants becomes greater than the cost to compare the fill level to a
programmable register. At what point that you cross that threshold
depends on the number of bits in the counter, but in the cases where
I've run across it was cheaper (in logic) and faster in performance to
do the multiple comparisons and select but that was with 4 sets of fill
levels....8 choices might just push you over.

I agree that lab testing to empirically find those optimal values can
be a pain when it means an FPGA rebuild but once beyond that and the
optimal values determined they usually tend to stay set in concrete.
Hard coding them in at that point would tend to give you less logic and
better performance (again, how much depends on the counter size).

Good example.

KJ

Reply With Quote
  #12 (permalink)  
Old 12-14-2006, 07:43 PM
Tommy Thorn
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

Peter Alfke wrote:
> In an asynchronous FIFO, reading and writing is controlled by two
> counters with independent clocks.
> If you need to detect FULL or EMPTY, you compare the two counters for
> identity.
> If you do that with binary counters, you are vulnerable to strange
> decoding glitches, while multiple binary bits change (almost, but not
> quite, simultaneously). You never have that problem with Gray counters,
> where only one bit changes, from one state to the next.


How about a different way? Couldn't one simply maintain two views (one
for each clock) of the state of the FIFO, always a conservative
approximation to the "true" state, and use standard handshake
techniques to communicate to the writer "since our last handshake, I've
dequeued X words", and visa versa.

The advantage of this (besides simplicity) is that one can pipeline the
handshake arbitrarily much, only at the expense of added latency
between full->non-full and empty->non-empty transitions.

Isn't this a standard technique?

Tommy

Reply With Quote
  #13 (permalink)  
Old 12-15-2006, 07:45 AM
Peter Alfke
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

When you understand the details of a particular application, you can
use all sorts of trickery and compromises, etc. I have always been
forced to design a universal FIFO at the highest possible speed, with
the greatest versatility, without unnecessary limitations.
That limits the freedom to explore special and limited design styles.
The fate of an IC applications engineer...But I am not complaining.
Peter Alfke

On Dec 14, 10:43 am, "Tommy Thorn" <[email protected]> wrote:
> Peter Alfke wrote:
> > In an asynchronous FIFO, reading and writing is controlled by two
> > counters with independent clocks.
> > If you need to detect FULL or EMPTY, you compare the two counters for
> > identity.
> > If you do that with binary counters, you are vulnerable to strange
> > decoding glitches, while multiple binary bits change (almost, but not
> > quite, simultaneously). You never have that problem with Gray counters,
> > where only one bit changes, from one state to the next.How about a different way? Couldn't one simply maintain two views (one

> for each clock) of the state of the FIFO, always a conservative
> approximation to the "true" state, and use standard handshake
> techniques to communicate to the writer "since our last handshake, I've
> dequeued X words", and visa versa.
>
> The advantage of this (besides simplicity) is that one can pipeline the
> handshake arbitrarily much, only at the expense of added latency
> between full->non-full and empty->non-empty transitions.
>
> Isn't this a standard technique?
>
> Tommy


Reply With Quote
  #14 (permalink)  
Old 12-15-2006, 06:37 PM
Ray Andraka
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

Tommy Thorn wrote:
> Peter Alfke wrote:
>
>>In an asynchronous FIFO, reading and writing is controlled by two
>>counters with independent clocks.
>>If you need to detect FULL or EMPTY, you compare the two counters for
>>identity.
>>If you do that with binary counters, you are vulnerable to strange
>>decoding glitches, while multiple binary bits change (almost, but not
>>quite, simultaneously). You never have that problem with Gray counters,
>>where only one bit changes, from one state to the next.

>
>
> How about a different way? Couldn't one simply maintain two views (one
> for each clock) of the state of the FIFO, always a conservative
> approximation to the "true" state, and use standard handshake
> techniques to communicate to the writer "since our last handshake, I've
> dequeued X words", and visa versa.
>
> The advantage of this (besides simplicity) is that one can pipeline the
> handshake arbitrarily much, only at the expense of added latency
> between full->non-full and empty->non-empty transitions.
>
> Isn't this a standard technique?
>
> Tommy
>


I've used similar techniques. Basically, an alternative to using gray
code is to maintain population counts that are separate from the read
and write pointers, and then resynchronizing the write event for a read
side population count and/or resynchronizing the read event for a write
side population count. The things to watch are 1: you need to make sure
that read or write events can't overrun the flag in your system. This
can happen if, for example, you write twice between successive read
clock edges. So, yes, this is a viable alternative, it will sometimes
save some logic, can result in higher speeds, but it also carries with
it a responsibility for the user to make sure the event flags don't overrun.
Reply With Quote
  #15 (permalink)  
Old 12-15-2006, 07:51 PM
Tommy Thorn
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

First to Peter, my comment was definitely not intended as a critism of
the Async FIFO in Virtex, but as an alternative to consider for the OP.

Ray Andraka wrote:
> I've used similar techniques. Basically, an alternative to using gray
> code is to maintain population counts that are separate from the read
> and write pointers, and then resynchronizing the write event for a read
> side population count and/or resynchronizing the read event for a write
> side population count.


That was the idea. I admit I have never done it so I was looking for
the potential pitfalls.

> The things to watch are 1: you need to make sure
> that read or write events can't overrun the flag in your system. This
> can happen if, for example, you write twice between successive read
> clock edges.


I'm afraid I don't follow. As writing (resp. reading) follow a local,
synchronous, conservative approximation how could it overrun? The
"flag" as I understand it is direct function of the local counter so it
would be updated for each write.

Thanks,
Tommy


> So, yes, this is a viable alternative, it will sometimes
> save some logic, can result in higher speeds, but it also carries with
> it a responsibility for the user to make sure the event flags don't overrun.


Reply With Quote
  #16 (permalink)  
Old 12-15-2006, 07:54 PM
Tommy Thorn
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

First to Peter, my comment was definitely not intended as a critism of
the Async FIFO in Virtex, but as an alternative to consider for the OP.

Ray Andraka wrote:
> I've used similar techniques. Basically, an alternative to using gray
> code is to maintain population counts that are separate from the read
> and write pointers, and then resynchronizing the write event for a read
> side population count and/or resynchronizing the read event for a write
> side population count.


That was the idea, although I'm suggesting communicating deltas rather
than absolute values (ie, how many elements read / written
respectively). It may be the same, but it seems more intuitive.

I admit I have never done it so I was looking for the potential
pitfalls.

> The things to watch are 1: you need to make sure
> that read or write events can't overrun the flag in your system. This
> can happen if, for example, you write twice between successive read
> clock edges.


I'm not sure I follow. As writing (like reading) follow a local,
synchronous, conservative approximation that would be updated for each
write, what would stop me from adding logic to drop the write if I deem
the FIFO full?

BTW, what were the other things to look out for? :-)

> So, yes, this is a viable alternative, it will sometimes
> save some logic, can result in higher speeds, but it also carries with
> it a responsibility for the user to make sure the event flags don't overrun.


Thanks,
Tommy

Reply With Quote
  #17 (permalink)  
Old 12-15-2006, 08:52 PM
Tommy Thorn
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

First to Peter, my comment was definitely not intended as a critism of
the Async FIFO in Virtex, but as an alternative to consider for the OP.

Ray Andraka wrote:
> I've used similar techniques. Basically, an alternative to using gray
> code is to maintain population counts that are separate from the read
> and write pointers, and then resynchronizing the write event for a read
> side population count and/or resynchronizing the read event for a write
> side population count.


That was the idea. I admit I have never done it so I was looking for
the potential pitfalls.

> The things to watch are 1: you need to make sure
> that read or write events can't overrun the flag in your system. This
> can happen if, for example, you write twice between successive read
> clock edges.


I'm afraid I don't follow. As writing (resp. reading) follow a local,
synchronous, conservative approximation how could it overrun? The
"flag" as I understand it is direct function of the local counter so it
would be updated for each write.

BTW, what were the other things to look out for? :-)

> So, yes, this is a viable alternative, it will sometimes
> save some logic, can result in higher speeds, but it also carries with
> it a responsibility for the user to make sure the event flags don't overrun.


Thanks,
Tommy

Reply With Quote
  #18 (permalink)  
Old 12-15-2006, 10:26 PM
Ray Andraka
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

Tommy Thorn wrote:

> First to Peter, my comment was definitely not intended as a critism of
> the Async FIFO in Virtex, but as an alternative to consider for the OP.
>
> Ray Andraka wrote:
>
>>I've used similar techniques. Basically, an alternative to using gray
>>code is to maintain population counts that are separate from the read
>>and write pointers, and then resynchronizing the write event for a read
>>side population count and/or resynchronizing the read event for a write
>>side population count.

>
>
> That was the idea. I admit I have never done it so I was looking for
> the potential pitfalls.
>
>
>>The things to watch are 1: you need to make sure
>>that read or write events can't overrun the flag in your system. This
>>can happen if, for example, you write twice between successive read
>>clock edges.

>
>
> I'm afraid I don't follow. As writing (resp. reading) follow a local,
> synchronous, conservative approximation how could it overrun? The
> "flag" as I understand it is direct function of the local counter so it
> would be updated for each write.
>
> BTW, what were the other things to look out for? :-)
>
>
>>So, yes, this is a viable alternative, it will sometimes
>>save some logic, can result in higher speeds, but it also carries with
>>it a responsibility for the user to make sure the event flags don't overrun.

>
>
> Thanks,
> Tommy
>



OK, for example, if the write clock is at 10 MHz and the read clock is
at 5 MHz, if you wrote on 2 consecutive write clocks, then synchronizing
them to the read clock domain, you'd lose one or both of the write
events. In order for this set-up to work, you need to guarantee that
whatever signal you send across the clock domain boundary to indicate a
write event or events is infrequent enough to be reliably sensed in the
other domain for every single event. If there is a possibility of
writing too frequently, then you need some sort of signaling scheme that
can indicate a certain number of writes occurred and update the
population count accordingly. If the clocks for both sides are similar
frequencies, you need at least one clock between events to get a clean
crossing. This extra care to make sure you don't have events happen too
quickly for reliable operation is the reason the shrink wrapped FIFO
components use the gray code schemes.
Reply With Quote
  #19 (permalink)  
Old 12-15-2006, 10:56 PM
Tommy Thorn
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

Ray Andraka wrote:
> OK, for example, if the write clock is at 10 MHz and the read clock is
> at 5 MHz, if you wrote on 2 consecutive write clocks, then synchronizing
> them to the read clock domain, you'd lose one or both of the write
> events.


Thanks Ray. I'm sorry to persist, but I still can't agree.

When the writer writes the first item we can have one of several
situations, including:

- The reader has yet to acknowledge some messages prior to this write.
No update will be sent until it does. The writes writes another item
and updates its local count. Once the reader finally acknowledges the
original message, the writer sends a "2 written" message.

- The writer wasn't waiting and goes ahead with a "1 written" message.
The reader updates it's local count and acknowledges that it saw "1
written" message. The writer writes again etc.

- The writer wasn't waiting and goes ahead with a "1 written" message.
The reader doesn't pick up the message in time before the writer writes
to the FIFO again. No worries. Once the reader finally acknowledges the
"1 written", the writer can issue a new message to the reader with the
delta between the writers current count and the writers count at the
time of the last message, thus including the write that just happend.



> In order for this set-up to work, you need to guarantee that
> whatever signal you send across the clock domain boundary to indicate a
> write event or events is infrequent enough to be reliably sensed in the
> other domain for every single event.


IMHO, any scheme depending on such an assumption is broken (it's too
easy to forget this assumption when the design is revised a year
later). I make no assumption on the relative speed of writers and
readers. I do assume that no messages will be dropped/missed, but that
assumption can also be removed with more work.


> If there is a possibility of
> writing too frequently, then you need some sort of signaling scheme that
> can indicate a certain number of writes occurred and update the
> population count accordingly.


I beleive that's what I suggested.


Thanks
Tommy


> If the clocks for both sides are similar
> frequencies, you need at least one clock between events to get a clean
> crossing. This extra care to make sure you don't have events happen too
> quickly for reliable operation is the reason the shrink wrapped FIFO
> components use the gray code schemes.


Reply With Quote
  #20 (permalink)  
Old 12-17-2006, 04:30 PM
Daniel S.
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

There is a simple way of avoiding "mysterious glitches" when using
binary counters: freeze the counter in a second register in the first
clock domain and do a one bit handshake across the two domains. Since
the counter (copy) is frozen during the handshaking, the other clock
domain's FFs will have ample setup time until the strobe propagates
through the resync.

With a fully resync'd handshake, this approach does introduce up to 3x
clock1 + 1.5x clock2 cycles delay between update, which is certainly not
suitable for low-latency and small high-speed FIFOs, especially if there
is a large difference in clock speeds. It works well as long as one can
live with long status delays for the first (read) and last (write) few
FIFO words.

The design is nice as long as clocks are of similar frequencies but the
delay may become an issue for large read:write (and vice-versa) clock
ratios. At 10:1, the status update may have a latency exceeding 40 fast
clock cycles.

So, binary counters can be safely used by using frozen copies and
handshaking. The caveat is higher latency than gray counters due to
handshaking and register copies that add extra dependencies upon the
other clock domain.

As always, designers are free to pick their poison.

Peter Alfke wrote:
> In an asynchronous FIFO, reading and writing is controlled by two
> counters with independent clocks.
> If you need to detect FULL or EMPTY, you compare the two counters for
> identity.
> If you do that with binary counters, you are vulnerable to strange
> decoding glitches, while multiple binary bits change (almost, but not
> quite, simultaneously). You never have that problem with Gray counters,
> where only one bit changes, from one state to the next.
> Peter Alfke
> =============
> RCIngham wrote:
>>> There is a wrong way and a right way to convert binary to Gray count
>>> values:
>>> The wrong way hangs the (simple!) combinatorial conversion logic (XORs)
>>> on the binary outputs. That does you no good, since the Gray code will
>>> just reflect the binary transient errors.
>>> The right way takes the D inputs of the binary counter (, converts them
>>> independently to Gray and registers them in their own flip-flops. Now
>>> you have two parallel rgisters, both counting in step, the first in
>>> binary, the other in Gray, and there are no funny decoding spikes.
>>> BTW, only Gray counter outputs have the feature that you can compare
>>> two asynchronous counters for identity, without transient errors.
>>> If the Gray code does not come from a counter, it might change multiple
>>> bits per transition...

>> <snip />
>> Whether that is the right answer rather depends on WHY the OP "has" to use
>> Gray Code, which is still not fully established.
>>
>> BTW, there is a quite interesting article on Gray Code just posted at:
>> http://www.pldesignline.com/showArti...leID=196604078

>

Reply With Quote
  #21 (permalink)  
Old 12-17-2006, 05:49 PM
Peter Alfke
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

Daniel, why do you want to avoid the Gray register? Your design is at
least as complicated and expensive, and incurs all this latency. Why do
it, when there are simpler ways to avoid it?
Peter Alfke

On Dec 17, 7:30 am, "Daniel S." <[email protected]>
wrote:
> There is a simple way of avoiding "mysterious glitches" when using
> binary counters: freeze the counter in a second register in the first
> clock domain and do a one bit handshake across the two domains. Since
> the counter (copy) is frozen during the handshaking, the other clock
> domain's FFs will have ample setup time until the strobe propagates
> through the resync.
>
> With a fully resync'd handshake, this approach does introduce up to 3x
> clock1 + 1.5x clock2 cycles delay between update, which is certainly not
> suitable for low-latency and small high-speed FIFOs, especially if there
> is a large difference in clock speeds. It works well as long as one can
> live with long status delays for the first (read) and last (write) few
> FIFO words.
>
> The design is nice as long as clocks are of similar frequencies but the
> delay may become an issue for large read:write (and vice-versa) clock
> ratios. At 10:1, the status update may have a latency exceeding 40 fast
> clock cycles.
>
> So, binary counters can be safely used by using frozen copies and
> handshaking. The caveat is higher latency than gray counters due to
> handshaking and register copies that add extra dependencies upon the
> other clock domain.
>
> As always, designers are free to pick their poison.
>
> Peter Alfke wrote:
> > In an asynchronous FIFO, reading and writing is controlled by two
> > counters with independent clocks.
> > If you need to detect FULL or EMPTY, you compare the two counters for
> > identity.
> > If you do that with binary counters, you are vulnerable to strange
> > decoding glitches, while multiple binary bits change (almost, but not
> > quite, simultaneously). You never have that problem with Gray counters,
> > where only one bit changes, from one state to the next.
> > Peter Alfke
> > =============
> > RCIngham wrote:
> >>> There is a wrong way and a right way to convert binary to Gray count
> >>> values:
> >>> The wrong way hangs the (simple!) combinatorial conversion logic (XORs)
> >>> on the binary outputs. That does you no good, since the Gray code will
> >>> just reflect the binary transient errors.
> >>> The right way takes the D inputs of the binary counter (, converts them
> >>> independently to Gray and registers them in their own flip-flops. Now
> >>> you have two parallel rgisters, both counting in step, the first in
> >>> binary, the other in Gray, and there are no funny decoding spikes.
> >>> BTW, only Gray counter outputs have the feature that you can compare
> >>> two asynchronous counters for identity, without transient errors.
> >>> If the Gray code does not come from a counter, it might change multiple
> >>> bits per transition...
> >> <snip />
> >> Whether that is the right answer rather depends on WHY the OP "has" to use
> >> Gray Code, which is still not fully established.

>
> >> BTW, there is a quite interesting article on Gray Code just posted at:
> >>http://www.pldesignline.com/showArti...leID=196604078


Reply With Quote
  #22 (permalink)  
Old 12-17-2006, 10:06 PM
Daniel S.
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

What I want to avoid is the gray-to-binary conversion necessary to
calculate population counts and flags afterwards.

The design only introduces a simple handshake and replaces the gray
resync registers by copy (hold) registers to create a safe false path
for data between clock domains. IMO, this is simpler than having to
decode gray counters before computing differences.

Yes, that approach does sacrifice five extra FFs and some in-to-out
latency for the handshaking in each direction (that could be reduced by
using some async SR FFs) but it is a straight register-to-register
design that enables direct pointer arithmetic on both sides. With gray
counters, you end up needing a decoder for both local and remote
counters on each side before doing arithmetic in each clock domain.

As I said, designers are free to pick their poison.

For most applications I have in mind (mostly DMA-like), I can afford to
trade some latency and a few FFs for the ability to stick with a simple,
plain binary register-to-register and decoder-less design.

BTW, unless the gray decoders are fully absorbed by the arithmetic at no
performance cost (doesn't gray code kill the carry chains?), my
implementation should use fewer LUTs and be able to clock higher.

Peter Alfke wrote:
> Daniel, why do you want to avoid the Gray register? Your design is at
> least as complicated and expensive, and incurs all this latency. Why do
> it, when there are simpler ways to avoid it?
> Peter Alfke
>
>> So, binary counters can be safely used by using frozen copies and
>> handshaking. The caveat is higher latency than gray counters due to
>> handshaking and register copies that add extra dependencies upon the
>> other clock domain.
>>
>> As always, designers are free to pick their poison.

Reply With Quote
  #23 (permalink)  
Old 12-17-2006, 11:55 PM
Peter Alfke
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

Maybe this is getting too long in the tooth.
For B-to-G conversion use the D input of the binary counter, so it adds
only one LUT delay, irrespective of length.
There is no G-to-B conversion, because I derived the Gray code from the
binary.
Maybe this is getting too complex for just a short e-mail.
My idea is: Do all the math in binary, convert to Gray in a synchronous
transfer that does NOT add any latency, do the identity comparison
between clock domains in Gray, then add some ciruitry to combat
metastability.
But, as I mentioned before, I never had the luxury of designing for a
single-point solution.
BTW, if you want to check existing patents, now you can use:
www.google.com/patents. Very nice!
Peter Alfke

On Dec 17, 1:06 pm, "Daniel S." <[email protected]>
wrote:
> What I want to avoid is the gray-to-binary conversion necessary to
> calculate population counts and flags afterwards.
>
> The design only introduces a simple handshake and replaces the gray
> resync registers by copy (hold) registers to create a safe false path
> for data between clock domains. IMO, this is simpler than having to
> decode gray counters before computing differences.
>
> Yes, that approach does sacrifice five extra FFs and some in-to-out
> latency for the handshaking in each direction (that could be reduced by
> using some async SR FFs) but it is a straight register-to-register
> design that enables direct pointer arithmetic on both sides. With gray
> counters, you end up needing a decoder for both local and remote
> counters on each side before doing arithmetic in each clock domain.
>
> As I said, designers are free to pick their poison.
>
> For most applications I have in mind (mostly DMA-like), I can afford to
> trade some latency and a few FFs for the ability to stick with a simple,
> plain binary register-to-register and decoder-less design.
>
> BTW, unless the gray decoders are fully absorbed by the arithmetic at no
> performance cost (doesn't gray code kill the carry chains?), my
> implementation should use fewer LUTs and be able to clock higher.
>
> Peter Alfke wrote:
> > Daniel, why do you want to avoid the Gray register? Your design is at
> > least as complicated and expensive, and incurs all this latency. Why do
> > it, when there are simpler ways to avoid it?
> > Peter Alfke

>
> >> So, binary counters can be safely used by using frozen copies and
> >> handshaking. The caveat is higher latency than gray counters due to
> >> handshaking and register copies that add extra dependencies upon the
> >> other clock domain.

>
> >> As always, designers are free to pick their poison.


Reply With Quote
  #24 (permalink)  
Old 12-18-2006, 03:02 AM
Daniel S.
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

Yes, one can do "ptrA == ptrB" directly in gray... but if I want to do
"ptrA - ptrB" to know how much headroom I have, it does not work quite
as nicely, this does require G2B conversion.

For a gray implementation, it is probably preferable to generate a
straight gray counter and convert that to linear binary for local use to
avoid combinational paths and routing between the counter's registers
and the other domain's resync registers since it increases the risk
transcoding glitches (path delays + non-existing phase relation + ...)
getting through. With a binary counter, the gray conversion must be
registered on the local clock before resyncing to the other clock.

In any case, the most important point of any design always is: it has to
work.

Peter Alfke wrote:
> Maybe this is getting too long in the tooth.
> For B-to-G conversion use the D input of the binary counter, so it adds
> only one LUT delay, irrespective of length.
> There is no G-to-B conversion, because I derived the Gray code from the
> binary.
> Maybe this is getting too complex for just a short e-mail.
> My idea is: Do all the math in binary, convert to Gray in a synchronous
> transfer that does NOT add any latency, do the identity comparison
> between clock domains in Gray, then add some ciruitry to combat
> metastability.
> But, as I mentioned before, I never had the luxury of designing for a
> single-point solution.
> BTW, if you want to check existing patents, now you can use:
> www.google.com/patents. Very nice!
> Peter Alfke
>
> On Dec 17, 1:06 pm, "Daniel S." <[email protected]>
> wrote:
>> What I want to avoid is the gray-to-binary conversion necessary to
>> calculate population counts and flags afterwards.
>>
>> The design only introduces a simple handshake and replaces the gray
>> resync registers by copy (hold) registers to create a safe false path
>> for data between clock domains. IMO, this is simpler than having to
>> decode gray counters before computing differences.
>>
>> Yes, that approach does sacrifice five extra FFs and some in-to-out
>> latency for the handshaking in each direction (that could be reduced by
>> using some async SR FFs) but it is a straight register-to-register
>> design that enables direct pointer arithmetic on both sides. With gray
>> counters, you end up needing a decoder for both local and remote
>> counters on each side before doing arithmetic in each clock domain.

Reply With Quote
  #25 (permalink)  
Old 12-18-2006, 05:53 AM
Peter Alfke
Guest
 
Posts: n/a
Default Re: FPGA : Async FIFO, Programmable full

Let's leave it at that. We won't agree, but then: we do not have to...
Peter Alfke
BTW, Google lists over 1000 patents on FIFOs.
A few of them are mine, but I could not believe the total number...

On Dec 17, 6:02 pm, "Daniel S." <[email protected]>
wrote:
> Yes, one can do "ptrA == ptrB" directly in gray... but if I want to do
> "ptrA - ptrB" to know how much headroom I have, it does not work quite
> as nicely, this does require G2B conversion.
>
> For a gray implementation, it is probably preferable to generate a
> straight gray counter and convert that to linear binary for local use to
> avoid combinational paths and routing between the counter's registers
> and the other domain's resync registers since it increases the risk
> transcoding glitches (path delays + non-existing phase relation + ...)
> getting through. With a binary counter, the gray conversion must be
> registered on the local clock before resyncing to the other clock.
>
> In any case, the most important point of any design always is: it has to
> work.
>
> Peter Alfke wrote:
> > Maybe this is getting too long in the tooth.
> > For B-to-G conversion use the D input of the binary counter, so it adds
> > only one LUT delay, irrespective of length.
> > There is no G-to-B conversion, because I derived the Gray code from the
> > binary.
> > Maybe this is getting too complex for just a short e-mail.
> > My idea is: Do all the math in binary, convert to Gray in a synchronous
> > transfer that does NOT add any latency, do the identity comparison
> > between clock domains in Gray, then add some ciruitry to combat
> > metastability.
> > But, as I mentioned before, I never had the luxury of designing for a
> > single-point solution.
> > BTW, if you want to check existing patents, now you can use:
> >www.google.com/patents. Very nice!
> > Peter Alfke

>
> > On Dec 17, 1:06 pm, "Daniel S." <[email protected]>
> > wrote:
> >> What I want to avoid is the gray-to-binary conversion necessary to
> >> calculate population counts and flags afterwards.

>
> >> The design only introduces a simple handshake and replaces the gray
> >> resync registers by copy (hold) registers to create a safe false path
> >> for data between clock domains. IMO, this is simpler than having to
> >> decode gray counters before computing differences.

>
> >> Yes, that approach does sacrifice five extra FFs and some in-to-out
> >> latency for the handshaking in each direction (that could be reduced by
> >> using some async SR FFs) but it is a straight register-to-register
> >> design that enables direct pointer arithmetic on both sides. With gray
> >> counters, you end up needing a decoder for both local and remote
> >> counters on each side before doing arithmetic in each clock domain.


Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Questions about Async. FIFO [email protected] Verilog 0 01-17-2006 11:42 AM
async fifo design Michael Dreschmann FPGA 9 12-03-2005 11:36 AM
Best Async FIFO Implementation Davy FPGA 34 11-11-2005 01:18 AM
Best Async FIFO Implementation Davy Verilog 10 11-11-2005 01:18 AM
Async FIFO problem... Paul Davis FPGA 13 03-10-2005 09:40 AM


All times are GMT +1. The time now is 08:43 PM.


Powered by vBulletin® Version 3.8.0
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.2.0
Copyright 2008 @ FPGA Central. All rights reserved