synchronous FIFO design

Hello,

I've seen many synchronous FIFO implementations that evaluate the "read_address = write_address" condition combinatoricly to determine full and empty flags.
This method is somewhat ambiguous as the expression is true for both full and empy conditions. That leads to the need of another variable to evalute the number of times that address warpage occurred.

My question. why not do it in the following way:

----------------------------------------------------------------
-- a full condition can be generated ONLY by a write action
if write_request = '1' and write_en = '1' then
if read_address = (write_addr + 1) mod depth then -- depth is an entity generic
full <= '1';

-- an empty condition can be generated ONLY by a read action
if read_request = '1' and read_en = '1' then
if write_address = (read_addr + 1) mod depth then
empty <= '1';
----------------------------------------------------------------

The above logic takes into consideration the reason to why now read_address = write_address.
This eliminates the ambiguity associated with a combinatorial comparation of read_address = write_address.

What do you think?
Any reason not to use this method instead?

Your example is not complete. You must also have code to clear the full/empty flags.
You must also handle that a read and a write can happen at the same time.

There is a very interesting solution in this paper, it will also work for an asynchronous FIFO:

http://www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIFO2.pdf

The examples are in Verilog, but there are good explanations.

This is the full process for the flag generation:

flags_and_queue_management: process (clk,rst) is
begin
if rst = '1' then
WRITE_ADDRESS <= 0;
READ_ADDRESS <= 0;
WRITE_GRANTED <= '0';
READ_GRANTED <= '0';
WRITE_DENIED <= '0';
READ_DENIED <= '0';
ALMOST_FULL <= '0';
ALMOST_EMPTY <= '0';
FULL <= '0';
EMPTY <= '1';
elsif rising_edge(clk) then
WRITE_GRANTED <= '0';
READ_GRANTED <= '0';
WRITE_DENIED <= '0';
READ_DENIED <= '0';
------------------------------------------------------------
if write_request = '1' then
if FULL = '1' then
WRITE_DENIED <= '1';
else
WRITE_GRANTED <= '1';
fifo_memory_array(WRITE_ADDRESS) <= DATA_TO_FIFO_I;
EMPTY <= '0';
if READ_ADDRESS = (WRITE_ADDRESS + 1) mod depth then
FULL <= '1';
end if;
if WRITE_ADDRESS = depth - 1 then
WRITE_ADDRESS <= 0;
else
WRITE_ADDRESS <= WRITE_ADDRESS + 1;
end if;
end if;
end if;
--------------------
if read_request = '1' then
if EMPTY = '1' then
READ_DENIED <= '1';
else
READ_GRANTED <= '1';
FULL <= '0';
if WRITE_ADDRESS = (READ_ADDRESS + 1) mod depth then
EMPTY <= '1';
end if;
if READ_ADDRESS = depth - 1 then
READ_ADDRESS <= 0;
else
READ_ADDRESS <= READ_ADDRESS + 1;
end if;
end if;
end if;
--------------------
if READ_ADDRESS /= WRITE_ADDRESS then
if (READ_ADDRESS - WRITE_ADDRESS) mod depth <= almost_full_threshold then
ALMOST_FULL <= '1';
else
ALMOST_FULL <= '0';
end if;
if (WRITE_ADDRESS - READ_ADDRESS) mod depth <= almost_empty_threshold then
ALMOST_EMPTY <= '1';
else
ALMOST_EMPTY <= '0';
end if;
end if;
--------------------
end if;
end process flags_and_queue_management;

I would stay clear from the mod function. you will see logic dissapear. you can also subtract the read address from the write address to determine the size, saving an extra counter. use an extra control bit to say if there is data, and the read = write means empty when false, or full when true. doing something like this you can easily read at 300mhz

TrickyDicky,

Please read my first post.
This is exactly what I want to avoid.
Also, what's wrong with using integers and "mod" ?

"you will see logic dissapear"
Are you saying that the synthesis tool doesn't implement integer counters well?
A wrapping integer counter should use the same logic as a vector counter...

---------- Post added at 16:55 ---------- Previous post was at 16:09 ----------

std_match,

I read know **broken link removed**
The author mentions (page 4):

"Trying to synchronize a binary count value from one clock domain to another is problematic because every bit of an
n-bit counter can change simultaneously (example 7->8 in binary numbers is 0111->1000, all bits changed)."

How is that a problem?
Why registering a single bit is OK but a [3:0] vector isn't ?

the mod function basically contains a divider, that will eat your resources (and not have a v good fmax performance in a single clock cycle)

as integer type doesn't allow overflow, you cant deduce the depth from them. you need to use unsigned types, then you can simply work out the number of words in the fifo from the differences in addresses.

std_match's comment is valid for a dual clock fifo, due to potentially not having all bits changing at the same time across the domain. hence some implementations use grey codes to cross the domain. but I have used non grey codes across a 300mhz boundary previously without problems.

So, you're saying that the synthesis tool isn't smart enough to translate:
(15 + 1) mod 15
to
"1111" + '1'
?

that's only 1 case. it has to account for all the possible values of the addresses. hence the need for a divider.

what does it need to divide?

---------- Post added at 18:22 ---------- Previous post was at 18:03 ----------

As long as "depth" is 2^n there's no need to divide

shaiko said:

"Trying to synchronize a binary count value from one clock domain to another is problematic because every bit of an
n-bit counter can change simultaneously (example 7->8 in binary numbers is 0111->1000, all bits changed)."

How is that a problem?
Why registering a single bit is OK but a [3:0] vector isn't ?

Click to expand...

If you have a multi-bit comparator and more than one bit changes at a time on either side, you can get glitches that says "A = B" even if the
two vectors were not equal. You can not assume that all bits change at exactly the same time. The problem is that the "A = B" glitch can appear at any time, so it can happen when the comparator output is sampled.

With Gray-coding, the comparator can only say "A = B" if the vectors are identical.

You don't have to worry about this if the input and output of the FIFO are in the same clock domain, because the comparator output will then be sampled when it is "safe".


Regarding the read/write pointers, integer and mod stuff, if you only intend to use "depth" that is a power of 2,
why don't you use "unsigned" and delete all the "mod" stuff.
You have much better control over the design with "unsigned".

If the integer pointers are properly constrained, and "depth" is a constant set to a power of 2, it is possible that you get the optimal end result, but you can't be sure.
If you make a small mistake, the design can work but consume a lot of logic.

If you use "unsigned", you can easily predict what logic you will get. It is easy to see how many bits will be used for the pointers,
no "mod" is needed, no risk for division, and the pointers will wrap back to zero automatically.

std_match,

I had the code written using unsigned...but changed it to integers.
Please read my older post - see FvM's response.
https://www.edaboard.com/threads/232742/
Sure - as someone mentioned to me, integers in VHDL must be used with care...but in my opinion, they are good for counters and literals.

BTW:

Can you help me write a generic gray to binary conversion function ?

Integers are good for counters, but for situations where you want something to wrap, unsigned is much more appropriate and requires less code (and possibly less logic)

eg:


You would like to think that both bits of code synthesise to the same thing, but with the integer version you run the risk of the synthesisor adding the extra comparitor and mux that the first one does not need (and neither does the second one really). So while you may feel integer is the "best way" from a code pov, its always best to think about synthesis too.


As for binary -> grey code,

Can you please give me an example of how to write it genericly in a function?

Ignore : I missread something

---------- Post added at 22:37 ---------- Previous post was at 22:29 ----------

Ignore me - Grey code is just the number divided by 2 and XOR'd with itself. Not exactluy hard to implement
I read ^ in the C above as a power function :shock:

I don't have a lot of expirience writing generic functions in VHDL.
correct me if I'm wrong - but first we to get the vector length...using the 'length attribute.
Right?

depends what the inputs to the function are, and what the purpose of the function is.

This is a bit OT for this thread. For function discussion, I suggest you start a new thread (unless its related to the FIFO)

My thought exactly...
Thanks

notes:
I think most synthesizers will pick up "x <= (x + 1) mod 255;" as the correct operation. the type might not be inferred from that, but from the "signal x : integer range 0 to 255;" line.

gray code doesn't make too much sense unless you have async clock domains.

FPGA's have built in fifos that have this logic built in. a handwritten fifo is more likely to be a small fifo using distributed RAM in a single clock domain.

as for types, i think integers will always init to 0, instead of 'x'. There may be some sim differences as a result. I'd expect int's to be faster for sim overall. as always, I don't really see why VHDL requires unsigned separate from std_logic_vector -- in this case "unsigned" has been used in the examples, but there isn't any strong reason to use unsigned vs signed. I don't see how calling it "unsigned" is any more descriptive than calling it "std_logic_vector".

also, async logic can break designs at any frequency (including sub-Hz). If a design ran at high clock rates without issues, then the logic probably didn't ever come into play, or the clock domain crossing was safely handled even though it hadn't been specifically designed for it.

permute said:

as for types, i think integers will always init to 0, instead of 'x'. There may be some sim differences as a result. I'd expect int's to be faster for sim overall. as always, I don't really see why VHDL requires unsigned separate from std_logic_vector -- in this case "unsigned" has been used in the examples, but there isn't any strong reason to use unsigned vs signed. I don't see how calling it "unsigned" is any more descriptive than calling it "std_logic_vector".

Click to expand...

Integers (and all types) init to type'left. So if you declare an integer as:

signal my_int : integer 6 to 20;

In Simulation it will init to 6. BUT I wouldnt trust a synthesisor to power this up to 6, it will probably power it up to 0 unless you put a specific init = 6)

And the reason std_logic inits to 'U' is because it is the left most value in the type declaration.

As for unsigned vs std_logic_vector - remember VHDL is strongly typed - so this type of separation is encouraged. Origionally VHDL defined std_logic_vector and integer types. Because people wanted counters and many synthesisors only worked with std_logic_vector, Synopsys (note - not IEEE) created the std_logic_signed/unsigned and arith packages. THey have never been adopted as a VHDL standard. Because SLV was never intended as an integer (and why would you, when its used for busses that are NOT integers as well) IEEE created types similar to SLV with the express purpose of making them behave like integers and put them in the numeric_std package (which is a VHDL standard). With SLV you can never do signed and unsigned math in the same file. With numeric_std you can.

So basically, you cannot do arithmatic in VHDL 87, 93 or 2002 with SLV (they added packages for them in 2008).

permute said:

I think most synthesizers will pick up "x <= (x + 1) mod 255;" as the correct operation

Click to expand...

it should be "mod 256" - Precision and Synplify get it right