asynchronous fifo design flags

[shaiko]

I'm designing an asynchronous fifo.
My read and write pointers are generated in one clock domain, encoded to gray and transffered to the other clcok domain, decoded and compared.

Now, to generate the control flags (almost_full , full , almost_empty , empty) I use the actual read and write requests double synchronized to the appropriate clock domains (marked in red). I think this is a bad approach because these might not synchronize well and get missed.
Please propose a solution to the problem.

--------------------------------------------
-----------WRITE CLOCK DOMAIN---------------
--------------------------------------------
registering_read_request_to_write_clock_domain : process ( write_clock , reset ) is
begin
	if reset = '1' then  
		temp_write_request_synchronized_to_read_domain <= '0' ;
		write_request_synchronized_to_read_domain <= '0' ;
	elsif rising_edge ( write_clock ) then   
		temp_write_request_synchronized_to_read_domain <= write_request ;
		[COLOR="#FF0000"]write_request_synchronized_to_read_domain[/COLOR] <= temp_write_request_synchronized_to_read_domain ;	
	end if ; 
end process registering_read_request_to_write_clock_domain ; 
				
completely_and_almost_empty_flags : process ( write_clock , reset ) is
begin
	if reset = '1' then  
		completely_empty <= '1' ;
		almost_empty <= '0' ;
	elsif rising_edge ( write_clock ) then  
		if read_pointer /= write_pointer_synchronized_to_read_domain then 
			if write_pointer_synchronized_to_read_domain - read_pointer <= almost_empty_threshold then 
				almost_empty <= '1' ;
			else
				almost_empty <= '0' ; 
			end if ;
		end if;
		if [COLOR="#FF0000"]write_request_synchronized_to_read_domain[/COLOR] = '1' then -- questinable synchronization success
			completely_empty <= '0' ;							
		end if ;
	end if ;
end process completely_and_almost_empty_flags ;


--------------------------------------------
-----------READ CLOCK DOMAIN----------------
--------------------------------------------
registering_write_request_to_read_clock_domain : process ( read_clock , reset ) is
begin
	if reset = '1' then  
		temp_read_request_synchronized_to_write_domain <= '0' ;		
		read_request_synchronized_to_write_domain <= '0' ;
	elsif rising_edge ( write_clock ) then   
		temp_read_request_synchronized_to_write_domain <= read_request ;		
		[COLOR="#FF0000"]read_request_synchronized_to_write_domain[/COLOR] <= temp_read_request_synchronized_to_write_domain ;	
	end if ; 
end process registering_write_request_to_read_clock_domain ; 

completely_and_almost_full_flags : process ( read_clock , reset ) is
begin
	if reset = '1' then  
		completely_full <= '1' ;
		almost_full <= '0' ;
	elsif rising_edge ( read_clock ) then  
		if write_pointer /= read_pointer_synchronized_to_write_domain then 
			if read_pointer_synchronized_to_write_domain - write_pointer <= almost_full_threshold then 
				almost_full <= '1' ;
			else
				almost_full <= '0' ;
			end if ;
		end if;
		if [COLOR="#FF0000"]read_request_synchronized_to_write_domain[/COLOR] = '1' then -- questinable synchronization success
			completely_full <= '0' ;							   	
		end if ;	
	end if ;
end process completely_and_almost_full_flags ;

 

[permute]

try synchronizing the encoded sizes/pointers instead of the control inputs.

for example, assume you are looking for the read side logic. you know your read pointer is 0000. you synchronize the write pointer to your clock domain and get 0000 -- you are empty. at some later time, a single write occurs, you measure either 0000, or 0001 depending on how close the writes are to the read clock edge. Either way, on the next cycle you will see 0001 and declare not empty.

likewise, if your read pointer is 0001, and the write pointer estimate is 0010, then you aren't empty. if a write and read occur, you will either get a 0010 or a 0011 for the write pointer, and a 0010 for the read pointer -- you will either declare the fifo as empty for one cycle, then correctly declare it is not empty on the next, or you will catch the change to the write pointer and declare "not empty".

This ends up giving a situation where the fifo can declare empty when the fifo is not empty (and then correct 1 cycle later). However, you never declare the fifo not empty when the fifo is empty.

The gray coding is used to ensure you see either write pointer, or write pointer -1, but never any other value due to multiple bits changing. (assuming you still constrain the paths for skew)

The above arguments can be made for the full flag as well.

edit -- and the above also allows for massive differences in clock frequency, eg if the write clock were 8x faster than the read clock.

 

[shaiko]

You suggest using the MSB of the read/write pointers to help setting the full and empy flags ?

 

[permute]

no, I suggest using the entire values of the read/write pointers. eg, the read pointer and the double-registered write pointer will be used to determine "empty". the values can simply be compared to see if they are equal. If they are equal, then the fifo may be empty. If they are not equal then the fifo is definately not empty. In this manner you will never declare "not empty" when the fifo is empty, though you may declare "empty" for one/two extra cycles when the fifo is not empty.

when the pointers are converted back into two's complement, you can also determine a fifo size estimate of each of the clock domains. again, the read side will give you an estimate that is less than or equal to the actual fifo size, while the write side will give an estimate that is greater than of equal to the actual size. if reads/writes stop, both estimates will reach the same value, equal to the actual size of the data in the fifo.

for this method to work, all bits from the read pointer must route to the write-clock domain registers within one write-clock cycle. setup/hold doesn't matter, but skew does. The gray coding means the value will either be equal to, or one less than the actual pointer value (determined by the exact time of the clock edge). But if there is more than one clock cycle of skew between the bits, the value could be corrupt.

 

[shaiko]

I'm sure that your proposal will yield a working asynchronous FIFO - but it seems a little ambiguous when generating the control flags.
Nonetheless, if you can post the code of such a FIFO it'll help me understand better.

Also, what do you think about a design that uses the MSB of the pointers for control signal generation ?

 

[permute]

that doesn't really work too well -- eg. after reset the pointers are 0. after a write, you have 001 and 000. the fifo is not empty, but until there are more writes this will not be seen. If the input data is finite -- eg, only the length of a file -- then the fifo may end up declaring empty when it is not, and then would never see more input and just never declare "not empty".

Fifo's have ambiguity in the control flag generation. It is ok for a fifo to declare empty when it is not empty as long as the condition doesn't persist. keep in mind that this will happen in any scheme simply because you are re-registering some of the control signals -- information about the read side is not immediately seen on the write side, but takes some time.

 

[shaiko]

Thanks permute.
I'd appreciate very much if you post a VHDL process for generating the flag for the asynchronous FIFO you proposed.
This will make the explanation much clearer!

Thanks

 

[std_match]

Not VHDL but good anyway:

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

 

[shaiko]

std_match,
I think the author of the article tries to promote the same design approach that permute discourages of using.