Syncronous FIFO - flag generation

[shaiko]

While designing a synchronous FIFO, I'm evaluating the pros and cons of 2 methods for generating the full and empty flags:

1. First method - use read and write pointers that are one bit larger than the address. For example:

signal full , empty : std_logic ;
signal write_address , read_addres : unsigned ( 2 downto 0 ) ;
signal write_pointer , read_pointer : unsigned ( 3 downto 0 ) ;

write_address <= write_pointer ( 2 downto 0 ) ;
read_address <= read_pointer ( 2 downto 0 ) ;

if write_pointer ( 2 downto 0 ) = read_pointer ( 2 downto 0 ) then
   if ( write_pointer ( 3 ) = read_pointer ( 3 ) ) then 
      full <= '0' ; 
      empty <= '1' ;
   else
      full < = '1' ; 
      empty < = '0' ;
   end if ;
end if ;

2. Second method - I call it: "remember who got you there". for example:

-- The red equations are evaluated only under the read or write operations. 
-- The logic "knows" the state it was at prior to the read or write operation - therefore it can assert the correct flag afterwards...
if rising_edge ( clock ) then
   if read_operation = '1' and empty = '0' then
      read_address <= read_address + 1 ;
      full <= '0' ;
      if [COLOR="#FF0000"]write_address - read_address = 1[/COLOR] then        
        empty <= '1' ;
      end if ;
   end if ;
   if write_operation = '1' and full = '0' then
      write_address <= write_address + 1 ; 
      empty <= '1' ;
      if [COLOR="#FF0000"]read_address - write_address = 1[/COLOR] then 
         full <= '1' ;
      end if ;
   end if ;
end if ;

Which method would you suggest? And why?

 

[TrickyDicky]

1. This option flags the fifo as full when only half the addresses are used.
2. There is a bug, empty goes high on every write that is not full.

Neither of these codes seem to take into account what happens when you get simultaneous read and write.

Assuming the same clock, you can easily mark full or empty by taking the difference between read address and write address.

diff <= write_addr - read_addr;

if diff = 0 and empty and write then
  empty <= '0';
elsif diff = 1 and read = 1 and write = 0 then 
  empty <= '1';
end if;

if diff = 0 and full and read then
  full <= '0';
elsif diff = -1 and read = 0 and write = 1 then 
  full <= '1';
end if;

 

[shaiko]

1. This option flags the fifo as full when only half the addresses are used.

Why?? the leftmost bit doesn't "participate" in actual addressing...
With this approach I view the FIFO as a circular buffer with the read address always chasing the write address. The lefmost bit is used only as "racetrack encirclement indication" (either even or odd).

 

[std_match]

I'm not sure which method I prefer, but I see some problems in your code examples.

First method: the example should be clocked. You want to update the empty/full flags at the same time you update the pointer(s). This means that you can not test for equality in the lower bits of the pointers. You must increment the pointers in parallel and use those values together with the current values to decide if the full or empty flags should be set.

Both methods: the read and write functionality is normally separated. This means that it should be possible to read and write at the same time. This must be considered when creating the logic for the empty/full flags.
Doing this in one clock domain is simple. Having the read and write in different clock domains is much more complicated.

It is common to waste one word, so the pointers are only equal when the FIFO is empty.

Both methods will work.
I am not sure, but I think the second method will use less resources and can use a slightly higher clock frequency.

 

[shaiko]

std_match,

You must increment the pointers in parallel and use those values together with the current values to decide if the full or empty flags should be set.

Please post an example in code...

It is common to waste one word, so the pointers are only equal when the FIFO is empty.

What do you mean by "waste one word" ?
The only "waste" I see is the extra leftmost bit of both pointer...

 

[ads-ee]

What do you mean by "waste one word" ?
The only "waste" I see is the extra leftmost bit of both pointer...

By waste std_match means when the FIFO is empty:
1) the read and write pointers are both pointing to the same location.
2) the read pointer will be pointing to the next address to read, which is currently empty
3) the write pointer points to the next address to write, which is the same as the empty read location

So the read and write operations update the pointers after the read and write.
do_a_write => update_wr_ptr
do_a_read => update_rd_ptr

Regards

 

[shaiko]

TrickyDicky,
Please explain what you meant in post #2:

This option flags the fifo as full when only half the addresses are used.

Do you agree with my reply (post #3)?

std_match,
regarding what you wrote in post #4

You must increment the pointers in parallel and use those values together with the current values to decide if the full or empty flags should be set.

Please show an example in code.

 

[ads-ee]

I think TrickyDicky didn't realize you meant having an extra bit beyond the required number of bits for the address pointer. Then you wouldn't be able to address more than half the FIFO.

e.g.
10-bit FIFO addresses = 1024 locations
11-bit pointer = 10-bit FIFO address and an extra "overflow" bit to allow using all locations as now FULL and EMPTY will have different results when subtracted or compared.

4-location FIFO (2-bit address pointers)
wptr rptr
000 000 - empty
... write 4 times
100 000 - full

 

[shaiko]

Thanks,
ads-ee

I'll try to post a finished code soon based on the first method of flag generation. Your input is very welcome.

 

[shaiko]

TrickyDicky,

diff <= write_addr - read_addr;

if diff = 0 and empty and write then
  empty <= '0';
elsif diff = 1 and read = 1 and write = 0 then 
  empty <= '1';
end if;

if diff = 0 and full and read then
  full <= '0';
elsif [COLOR="#FF0000"]diff = -1[/COLOR] and read = 0 and write = 1 then 
  full <= '1';
end if;

Do you suggest defining "diff" as type signed?

 

[std_match]

What do you mean by "waste one word" ?

It is an alternative to an extra address bit in the pointers.
If the full flag is set when there is still one unused word in the FIFO, the read and write pointers can only be equal when the FIFO is empty. The trick with the extra address bit is not needed in that case.

I think you should start from the beginning with you FIFO code. You want to allow read and write in the same clock cycle.
Use one process for read and another for write. The write process will update the write pointer and the full flag.
The read process will update the read pointer and the empty flag.
At reset, set both pointers to zero (and set the empty flag).
Don't forget to test for simultaneous read and write!
The empty/full flags will never be set by a simultaneous read and write operation.

Your code will now be quite different, and useful in a real project.

Edit: "procedure" was a mistake, I meant "process". Now changed.

 

[shaiko]

It is an alternative to an extra address bit in the pointers.
If the full flag is set when there is still one unused word in the FIFO, the read and write pointers can only be equal when the FIFO is empty. The trick with the extra address bit is not needed in that case.

Very clear now.










Regarding what you wrote in post #4:

You want to update the empty/full flags at the same time you update the pointer(s). This means that you can not test for equality in the lower bits of the pointers.

Please explain why not?

You must increment the pointers in parallel and use those values together with the current values to decide if the full or empty flags should be set.

I don't quite understand what you mean. Please post a code example...it will help a lot!

 

[shaiko]

This is what I wrote for the first method - using pointers with one bit larger then the address range:

write_flags_and_queue : process ( clock , reset ) is
begin
   if reset = '1' then -- Asynchronous reset. 
      full <= '0' ;
      write_pointer <= ( others => '0' ) ;	
   elsif rising_edge ( clock ) then
      if write_request = '1' and full = '0' then
         write_pointer <= write_pointer + 1 ;
      end if ;
      if 
      ( write_pointer ( write_pointer ' high - 1 downto 0 ) = 
      read_pointer ( read_pointer ' high - 1 downto 0 ) ) and 
      ( write_pointer ' high /= read_pointer ' high ) then
         full < = '1' ;
      else
         full < = '0' ;
      end if ;	
   end if ;
end process write_flags_and_queue ;	



read_flags_and_queue : process ( clock , reset ) is
begin
   if reset = '1' then
      empty <= '1' ;
      read_pointer <= ( others => '0' ) ;	
   elsif rising_edge ( clock ) then
      if read_request = '1' and empty = '0' then 
         read_pointer <= read_pointer + 1 ;
      end if ;
      if write_pointer = read_pointer then 
         empty <= '1' ;
      else 
         empty <= '0' ; 
      end if ;	
   end if ;
end process read_flags_and_queue ;

 

[TrickyDicky]

There are several bugs with your code. Consider this:

1.
Write pointer = 110
Read pointer = 011
write request = 1 (constant)
read request = 0

assuming write requests are made constantly, and no reads, you get the write pointer over flowing to 000 and the full flag will be marked when the write pointer goes to 000, at which point it flips back to 0 again:

clk  write p   full
0    110         0
1    111         0   --fifo not currently full, so write pointer can increment
2    000         1   
3    000         0   --full flips here as full condition no longer met

- - - Updated - - -

you have the oposite problem with the read side, you get underflow when there are no writes but constant reads.

 

[std_match]

The following code should work without an extra address bit:

---

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signal write_pointer, read_pointer, write_request, read_request;
variable new_write_pointer;
 
-- write process
if reset = '1' then
  full <= '0' ;
  write_pointer <= ( others => '0' ) ;  
elsif rising_edge(clock) then
  new_write_pointer := write_pointer + 1;
  if write_request = '1' and full = '0' then
    write_pointer <= new_write_pointer;
    if new_write_pointer = read_pointer then
      full <= '1';
    end if;
  end if;
  if read_request = '1' then
    full <= '0';
  end if;
end if;

---

The read process will be similar.

The code is written so the synthesis tool should use only one adder.
One problem with "method 2" in the first posting is that it needs an adder for the pointer increment and a subtractor for the pointer compare.

 

[shaiko]

TrickyDicky -I disagree.
If the read pointer is 011, I don't see why the write pointer should rise when it wraps from "111" to "000". It doesn't satisfy the condition:

if 
( write_pointer ( write_pointer ' high - 1 downto 0 ) = 
read_pointer ( read_pointer ' high - 1 downto 0 ) ) and 
( write_pointer ' high /= read_pointer ' high ) then
full < = '1' ;
else
full < = '0' ;

- - - Updated - - -

std_match,

I don't understand the need for "new_write_pointer".
Can you point to a condition where the code I wrote in post #13 will fail?

 

[TrickyDicky]

Look at your code. The full flag comes from the registered version of the write pointer. So assuming you get consecutive writes, the write pointer is incremented when it reaches 011.

Your full check needs to be on the next value of the adder, and set when the counter is incremented to this value, not one clock later. Simulate it yourself and you'll see the error occur.

 

[shaiko]

Is this 100% correct?

write_pointer_next <= write_pointer + 1 ;

write_flags_and_queue : process ( clock , reset ) is
begin
   if reset = '1' then -- Asynchronous reset. 
      full <= '0' ;
      write_pointer <= ( others => '0' ) ;	
   elsif rising_edge ( clock ) then
      if write_request = '1' and full = '0' then
         write_pointer <= write_pointer + 1 ;
      end if ;
      if 
      ( write_pointer_next ( write_pointer_next ' high - 1 downto 0 ) = 
      read_pointer ( read_pointer ' high - 1 downto 0 ) ) and 
      ( write_pointer_next ' high /= read_pointer ' high ) then
         full < = '1' ;
      else
         full < = '0' ;
   end if ;
end process write_flags_and_queue ;	





read_pointer_next <= read_pointer + 1 ;

read_flags_and_queue : process ( clock , reset ) is
begin
   if reset = '1' then -- Asynchronous reset. 
      empty < = '0' ;
      read_pointer <= ( others => '0' ) ;	
   elsif rising_edge ( clock ) then
      if read_request = '1' and empty = '0' then
         read_pointer <= read_pointer + 1 ;
      end if ;
      if read_pointer_next = write_pointer then
         empty < = '1' ;
      else
         empty < = '0' ;
      end if ;
   end if ;
end process read_flags_and_queue ;

 

[std_match]

It is not correct for simultaneous read and write.

To help the synthesis tool, you should use the incremented signal write_pointer_next when you assign the incremented value to the pointer. Maybe a good synthesis tool can merge the identical additions, but why take any risk when it is so easy to write "safer" code.

 

[shaiko]

To help the synthesis tool, you should use the incremented signal write_pointer_next when you assign the incremented value to the pointer. Maybe a good synthesis tool can merge the identical additions, but why take any risk when it is so easy to write "safer" code.

I assume you mean that I wrote:

write_pointer <= write_pointer + 1 ;

instead of simply writing:

write_pointer <= write_pointer_next ;

If so, I see how it can decrease Fmax (if the adders are far appart on the silicon) but I don't see how it can be "unsafe"...