Asynchronous FIFO in FPGA.pdf

techxclusives asynchronous fifo in virtex ii fpgas 1 of 310 28 2006 14 13 techxclusives asynchronous fifo in virtex ii fpgas back to asynchronous fifo in virtex ii fpgas author peter alfkepublication date 08 20 2001 a fifo is a popular memory structure that solves data rate differences in many systems most fifos have independent write and read clocks to move data across clock boundaries this requires some attention to asynchronous design details as described below given a dual ported ram like the block rams available in fpga devices the core fifo design is trivial one port is configured as write port addressed by a write address counter the other port is the read port addressed by the read address counter both counters must count by the same algorithm but they need not be binary counters linear feedback shift register lfsr counters used to be popular but gray counters are best for the general case of asynchronous fifos as described below the only difficult design detail is the proper and reliable handling of the two exceptional cases fifo full and fifo empty full means that the next write if allowed would overwrite the oldest not yet read entry empty means that the next read if allowed would read stale data a second time either of these conditions must raise its own flag telling the system to cope with the potential overflow or underflow designers can cheat on the full flag and raise it early thus sacrificing some fifo depth but there is no alternative to the proper timing of the empty flag since the system needs to read even the very last word stored in the fifo there are two problems with full and empty first both conditions are indicated by the identity of read and write addresses therefore something else has to distinguish between full and empty a simple solution divides the address space into four quadrants and decodes the two msbs of the two counters works in binary or gray but the equations are different together in two 4 input look up tables if the write counter is one quadrant behind the read counter this indicates a possibly going full situation and sets a direction latch if the write counter is one quadrant ahead of the read counter this indicates a possibly going empty situation and resets the direction latch the direction latch eliminates the ambiguity of the address identity decoder techxclusives asynchronous fifo in virtex ii fpgas 2 of 310 28 2006 14 13 the second and more difficult problem stems from the asynchronous nature of the write and read clocks comparing two counters that are clocked asynchronously can lead to unreliable decoding spikes when either or both counters change multiple bits simultaneously the preferred solution is to make both counters count in a gray sequence where only one bit changes from one count to the next any decoder or comparator will then switch only from one valid output to the next one with no danger of spurious decoding glitches virtex logic makes it very easy to design high speed synchronous gray counters taking advantage of the built in binary carry structure a binary counter is implemented by cascading a string of vertical slices using the carry chain the flip flops in the adjacent slice form the gray counter clocked by the same clock and clock enable as the binary counter but its d inputs driven by the xor of the two binary counter d signals one of the same rank and one of the next higher significance dgi dbi xor db i 1 dgmax dbmax where i designates the binary significance and dg and db denote the gray and binary counter s d input respectively the gray counters thus operate in parallel with the binary counters are not pipelined and do not suffer from any decoding glitches there is never a false equal output but there can be an arbitrarily short output glitch when counter a matches b but b increments very soon after the resulting spike either creates a full or empty signal or it does not either case is acceptable generating full and empty these two signals are generated by gating counter equality with the two flavors of direction but some important timing issues exist full is of interest only to the write logic where it must stop further writes full goes active as a result of the last write operation which makes the rising edge of full a synchronous signal although the read clock is asynchronous therefore we only need to synchronize the falling edge of full generated by a read operation to the next rising edge of the write clock a flip flop clocked by the free running write clock and using the decoded full signal as its asynchronous preset as well as its synchronous d input creates a fully synchronous full output the fully synchronous empty signal is generated in the symmetrically equivalent way the most efficient fifos use block rams for data storage virtex or spartan ii devices can implement a 4kx1 2kx2 1kx4 512x8 or 256x16 bit fifo in one block ram virtex ii devices can implement a 16kx1 8kx2 4kx4 2kx9 1kx18 or 512x36 bit fifo in one block ram the overhead for the binary gray counters is two flip flops per counter bit e g from 32 flip flops for a 256 deep fifo to 56 flip flops for a 16k deep fifo the overhead for generating full and empty is 8 to 12 luts for very small fifos up to 32 deep and 16 wide using the distributed ram in clbs xc4000 spartan and virtex devices is more efficient and faster four and five bit gray techxclusives asynchronous fifo in virtex ii fpgas 3 of 310 28 2006 14 13 counters can be implemented directly without the binary assist described above a 16 x 16 fifo uses 256 flip flops for data storage 8 flip flops as address counters plus 6 luts for full empty control as described above remember there are four luts and flip flops in each virtex or spartan ii clb while there are eight luts and flip flops in each virtex ii clb that s why we prefer to