原创 重读《异步FIFO结构》

         项目中多处需要用到FIFO，傻瓜式的调用Altera的库即可完成设计。为了深入了解FIFO的结构，上网找了些资料。异步FIFO只能自己写。

     一、关于同步FIFO

      1、在前面的日志里贴出了一个从网上找的同步FIFO的原代码，本人进行了稍微修改，原始的文章为：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/18/30d4e845-8448-42fc-bd8d-ce6543759ac5.rar，文章名字叫“同步FIFO原理剖析”。根据其介绍的同步FIFO原理修改的代码以及测试激励：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/18/575687b3-0cbf-4e1b-b3be-12766daa84f7.rar。

     2、 今天有时间重新拜读了异步FIFO结构（翻译），文章中讲述异步FIFO之前先讲述了同步(单时钟)FIFO。原理虽然和上述的同步FIFO一致,但是有些论述特别是对于"空"和"满"的判断个人觉得讲的非常精辟。特摘录一些重点:

    1)、写指针指向下一个将要写入的位置；读指针指向下一个将要读取的位置。

    2）、"空"和"满"写指针和读指针是相等的。但是"满"或者"空"的决定并不仅仅基于指针的值,而是基于引起指针值相等的操作。如果指针相等的原因是复位或者读操作，FIFO认为是空；如果原因是写操作，那么FIFO认为是满。

    3）、一般情况下(指非临界状况下)读操作和写操作同时都在使其指针增加,但是不改变空标志和满标志的状态。

        在空或满的临界状态同时读操作和写操作都是不允许的。

        由以上几点得出"空"和"满"标志状态变化的条件(未包含复位条件)：

        写操作无条件的清除空标志；

        write_pointer=(read_pointer+1)，读操作置"空"；

        读操作无条件的清除满标志；

        read_pointer=(write_pointer+1)，写操作置"满"(包括read_pointer=0，而write_pointer=depth-1的情况，这里与"同步FIFO原理剖析"中稍有不同)。

        将以上空满判断条件稍加改动：a、临界状态下如果同时有读和写操作，如果FIFO空，那么只允许写，如果满则只允许读；b、对于空和满置位操作，文章中论述的基础是FIFO的深度-depth为2的幂，将深度改为可参数化的任意整数的时候，需要对读和写到depth-1的位置进行判决。

        根据以上改动将文章中提供的FIFO原代码修改如下（文章中提供的原代码本身就有问题）：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/19/266ec7ec-7779-4780-a9ba-8db4b4e46450.rar；FIFO的测试激励：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/19/17819c8c-72d0-4130-a0db-ca01fe42e8b0.rar。

        以下是ModelSim的仿真波形，包含了“写满”，以及“读空”：

      另外，FIFO的almost_empty,almost_full以及usedw（有效字）信号可以参考我修改的《同步fifo原理剖析》源码。

      最后在板子上跑的结果如下：

附上QII工程：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/19/3cd341ed-f5c8-4e41-998d-e064122a7544.rar。

二、关于异步FIFO

      异步FIFO的接口信号包括异步的写时钟（wr_clk）和读时钟（rd_clk）、与写时钟同步的写有效（wren）和写数据（wr_data）、与读时钟同步的读有效（rden）和读数据（rd_data）。为了实现正确的读写和避免FIFO的上溢或下溢，通常还应该给出与读时钟和写时钟同步的FIFO的空标志（empty）和满标志（full）以禁止读写操作。

        下面给出异步FIFO的功能模块图：

        由上图可以看出，写地址产生模块根据写时钟和写有效信号产生递增的写地址，读地址产生模块根据读时钟和读有效信号产生递增的读地址。FIFO的操作如下：在写时钟wr_clk的上升沿，当wren有效时，将wr_data写入双口RAM中写地址对应的位置中；始终将读地址对应的双口RAM中的数据输出到读数据总线上。这样就实现了先进先出的功能。

         写地址产生模块还根据读地址和写地址关系产生FIFO的满标志。当wren有效时，若写地址+2=读地址时，full为1；当wren无效时，若写地址+1=读地址时，full为1。读地址产生模块还根据读地址和写地址的差产生FIFO的空标志。当rden有效时，若写地址-1=读地址时，empty为1；当rden无效时，若写地址=读地址时，empty为1。按照以上方式产生标志信号是为了提前一个时钟周期产生对应的标志信号。

        由于空标志和满标志控制了FIFO的操作，因此标志错误会引起操作的错误。如上所述，标志的产生是通过对读写地址的比较产生的，当读写时钟完全异步时，对读写地址进行比较时，可能得出错误的结果。例如，在读地址变化过程中，由于读地址的各位变化并不同步，计算读写地址的差值，可能产生错误的差值，导致产生错误的满标志信号。若将未满标志置为满标志时，可能降低了应用的性能，降低写数据速率；而将满置标志置为未满时，执行一次写操作，则可能产生溢出错误，这对于实际应用来说是绝对应该避免的。空标志信号的产生也可能产生类似的错误。

        所以使用格雷码来同步异步时钟域的读写指针。

       为了应用的灵活，还可以增加两个标志信号，将满（almosf_full）标志和空（almost_empty）标志。其定义分别如下：当写地址与读地址的距离小于某个预先定义数值时，almost_full为1；当读地址与写地址的距离小于这个预先定义的数值时，almost_empty为1。当然，也可以加入当前有效字输出信号，也即当前FIFO中有效字（或者字节）数，almost_full和almost_empty就是通过比较当前FIFO中有效字与相应阀值来产生的。（Fri Jun 19 200916:40:42 注：以上描述似乎没有考虑读或写地址位于FIFO末端或者FIFO起始的情况，需要仿真确认在这种特例下是否也成立，比如8bit的FIFO，0xff减去0xfe等于1，但是0减去0xff未必等于1）。这是尚未调试的代码：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/19/443dcb7e-90e6-434c-9b72-8b8e969fa2e6.rar；尚未调试的QII工程：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/19/4e5bda68-e82c-45bd-83b1-c30e0e0a1566.rar。

三、SunBurst Design的Asyncronous FIFO思想 

        (一)、Paper介绍了两种异步FIFO Style设计思想,首先讨论第一种设计思想,就叫AfifoNo1Style。

        1、The difficulty associated with doing FIFO design is related to generating the FIFO pointers and finding a reliable way to determine full and empty status on the FIFO.

        2、关于判断满和空的方法（核心思想就是要判断在写指针和读指针相等的时候到底是写操作“追”上读操作还是相反）

       The FIFO is empty when the read and write pointers are both equal. This condition happens when both pointers are reset to zero during a reset operation, or when the read pointer catches up to the write pointer, having read the last word from the FIFO.
        A FIFO is full when the pointers are again equal, that is, when the write pointer has wrapped around and caught up to the read pointer. This is a problem. The FIFO is either empty or full when the pointers are equal, but which?

        One design technique used to distinguish between full and empty is to add an extra bit to each pointer. When the write pointer increments past the final FIFO address, the write pointer will increment the unused MSB while setting the rest of the bits back to zero as shown in Figure 1 (the FIFO has wrapped and toggled the pointer MSB). The same is done with the read pointer. If the MSBs of the two pointers are different, it means that the write pointer has wrapped one more time that the read pointer. If the MSBs of the two pointers are the same, it means that both pointers have wrapped the same number of times.

      3、高手的paper附在这里https://static.assets-stash.eet-china.com/album/old-resources/2009/6/23/0489e30f-905e-46f0-bafc-2cef9ff7db21.rar，其核心思想就是利用n bit格雷码判断n-1 bit深的FIFO的空满状态，保证FIFO不会overflow或者underflow。如下图所示为双n格雷码计数器:

      上图有异于一般异步FIFO的设计思路在于,跨时钟传输的格雷码指针无需再次转换成二进制指针,也即系统中只有二进制到格雷码转换无格雷码到二进制码的转换,判断的时候直接比较双方格雷码(本地指针转换成格雷码与对方时钟域过来的指针进行比较,同时本地转换成格雷码的指针也要跨时钟域传输到对方时钟域).这样减少了逻辑消耗同时提供了系统性能.

       我们知道,格雷码是一种非线性码,虽然它有相邻码只有一位变化的优点,但是它不能直接用来进行各种运算.本例设计的亮点就在于通过巧妙架构使的可以直接拿格雷码来进行"运算".再上一图:

下图是传统异步FIFO设计时候普遍采取的策略:

      4、根据该paper写出的异步FIFO代码为：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/23/0896882f-7970-4879-83d8-f8d85fa65e8a.rar；这是QuartusII工程：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/23/fa4c2f38-d2d8-4102-8d03-2333b9ed621c.rar；ModelSim下仿真文件：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/23/17b24882-43bb-4f1a-a40f-aa2013fa7091.rar。

最后,按照这种风格生成的FIFO框图如下所示:

       (二)、下面再来看第二种设计思想,就叫AfifoNo2Style。

       1、主要思想和AfifoNo1Style一样,一是Gray counter设计,一是FIFO状态判断。

        简单比较两个styles,paper中给出以下观点:AfifoNo1Style中指针同步到对方指针时钟域后生成"空"、"满"标志位;而AfifoNo2Style是通过异步比较两个格雷码指针生成一个异步控制信号去"set"和"reset""空"和"满"触发器。

      2、对于空、满标志的判断，前一种风格采用双n格雷码计数器来完成（One known solution to this problem appends an extra bit to both pointers and then compares the extra bit for equality (for FIFO empty) or inequality (for FIFO full), along with equality of the other read and write pointer bits[1].），而第二种风格将采用将地址分成四个区（象限，其实就是平均分成四块），从而来判断读写地址的“追赶”趋势（Another solution, the one described in this paper, divides the address space into four quadrants and decodes the two MSBs of the two counters to determine whether the FIFO was going full or going empty at the time the two pointers became equal.）。

        下面二图都将读写地址分成了四个区，分别表示了：

         1）、FIFO is going full because the wptr trails the rptr by one quadrant

       如上图所示，如果写指针落后于读指针一个区，则FIFO处于“行将写满”的状态。当这种情况发生时，系统中的方向（direction）标志被置位（set），参考后面的框图。

         2）、FIFO is going empty because the rptr trails the wptr by one quadrant

        如上图所示，如果读指针落后于写指针一个区，则FIFO处于“行将读空”的状态。当这种情况发生时，系统中的方向（direction）标志被清零（clear），参考后面的框图。

(注：当wprt超前rptr一个区时：wprt（N）xor rptr（N-1）都为0；wprt（N-1）xor rptr（N）结果都为1。同样，当rptr超前wptr一个区时：wprt（N）xor rptr（N-1）都为1；wprt（N-1）xor rptr（N）结果都为0。同理当wptr赶上rptr或者rptr赶上wptr一个区以内时同样可以得出上述结果。根据以上分析，在Coding的时候直接可得出direction的逻辑值，实际coding中也没有按照paper所说的细分出dirset_n和dirclr_n或者dirrst等信号，可参考后面附上的async_cmp.vhd代码。)

          下图就是方向（direction）探测电路图：

      3、根据以上分析，第二种思想包含异步指针比较的异步FIFO结构图如下所示：

      根据以上异步FIFO的结构图写出FIFO的RTL代码，同样（AfifoNo1Style有六个模块）主要分五个部分：

      1）、AfifoNo2Style.vhd，FIFO的顶层；

      2）、fifomem.vhd，FIFO存储buffer，可以被读写时钟访问的同步双口RAM；

      3）、async_cmp.vhd，异步指针比较模块，并产生控制标识“空”、“满”状态位的控制信号。本模块均为组合逻辑，无时序逻辑。

      4）、rptr_empty.vhd，这个模块完成读时钟域（rclk）的同步，同时包含读指针和空标志产生逻辑。模块的输入信号aempty_n要被同步到读时钟域，因为aempty_n只能在rptr自增时才能被置有效（assertion），而其被撤销（de-assertion）要在wprt自增时才能发生，而wptr是写时钟域（wclk）的信号，异步于读时钟（rclk）。

       5）、wptr_full.vhd，这个模块完成写时钟域（wclk）的同步，同时包含写指针和满标志产生逻辑。模块的输入信号-afull_n要被同步到写时钟域，因为afull_n只能在wptr自增时才能被置有效（assertion），而其被撤销（de-assertion）要在rprt自增时才能发生，而rptr是读时钟域（rclk）的信号，异步于写时钟（wclk）。

       4、根据分析写出的异步比较模块async_cmp的rtl代码，其结构框图如下所示：

       就象上图显示的那样，aempty_n、afull_n都是异步解码信号，其中aempty_n在rclk上升沿被置有效（asserted），而其被撤销（de-asserted）却是在wclk的上升沿；同样afull_n在wclk上升沿被置有效（asserted），而在rclk上升沿被移除（remove）。

        由此得出，aempty_n的前沿（leading edge）已被正确同步于读时钟rclk，而其后沿（trailing edge）还需要重新同步到rclk，上图右上角利用两级寄存将aempty_n同步到rclk得到rempty信号。相应的wfull信号通过相同的方法得到，如上图的右下角所示。

        5、有必要谈谈FIFO的复位

        显然，FIFO的复位是我们最先应该考虑的问题。当复位发生时，异步比较模块async_cmp以及空、满标志同步器wptr_full和 rptr_empty模块内有四个最重要的事件发生：

        1）、wfull标志被复位信号直接清除，rempty不被复位信号清除；

        2）、复位导致FIFO的两个指针被复位，故此时比较模块使二者相等；

        3）、复位清除direction位；

        4）、随着FIFO的两个指针相等以及direction被清零，则aempty_n被置有效（assert），如此预置（preset）了rempty标志。

        下图是async_cmp, wptr_full 和 rptr_empty模块的连接框图，图中读写分别单独有复位信号，系统中也可只有一个异步复位信号rst_n：

       6、下面谈谈FIFO的写操作和满标志

       (注：aempty_n和afull_n是低有效)

       第一、我们要考虑的是FIFO复位后的FIFO写操作，此时wptr自增，FIFO的两个指针不再一样了，aempty_n被撤销（de-asserted），释放rempty寄存器预置控制信号（如上图所示）。经过rclk两个时钟上升沿后，FIFO撤销（de-asserted）rempty信号。我们知道aempty_n被撤销（de-asserted）发生在wclk上升沿，而rempty位于rclk时钟域，所以图中的两级触发器用来移除有可能在第一个触发器产生的亚稳态。

      第二、当wptr超出rptr一个分区（参考上述指针分区）时，将direction清零（事实上复位信号已经将其清零，这里考虑的是FIFO经过了“多圈”的读写操作情况）。

       第三、当wptr还有不到一个分区的距离即追上rptr时，异步比较器框图中的dirset_n被拉低，由此direction将被拉高。这意味着在FIFO满之前direction将保持为高，从而使afull_n被置为有效（assertion）的时候时序不会太紧张（not timing-critical）。

       第四、当wptr赶上rptr时（同时direction被置位（set））FIFO满了，afull_n预置wfull触发器。afull_n是在FIFO写操作的时候被置有效（assert），并同步于wclk上升沿；那么，满标志的有效（asserting）则同步于wclk。

       第五、FIFO满，当有FIFO读操作且rptr自增的时候，FIFO的指针就又不再相等了，所以afull_n被撤销（de-asserted），由此释放了wfull触发器的预置控制信号。两个wclk上升沿后，FIFO将撤销（de-assert）wfull。同样，由于afull_n是在rclk上升沿被撤销，而wfull是指wclk上升沿被撤销，所以wfull双触发器同步器用来移除系统中产生的亚稳态。

        7、谈谈读操作和空标志

        其实操作步骤可以接着上面所述的写操作后面，故有：

        第六、rptr超出wptr一个分区，direction再次被拉高（set），之前已被拉高。

        第七、rptr距离追上wptr在一个分区以内时，异步比较器框图中的dirrst被置高，由此direction位被清零。这就意味着，在FIFO被读空之前一段时间内direction位一直为零，如此使得aempty_n被置有效（assert）不会变得时序紧张（not timing critical）。

        第八、rptr赶上wptr（当然同时direction为0）时，aempty_n预置rempty触发器。aempty_n的有效（assert）是在读操作的时候，故其同步于rclk上升沿，那么，空标志信号的有效（assert）也同步于rclk。

        第九、最后FIFO又回到空，而写操作来临，wptr自增，FIFO指针不再相等，aempty_n信号被撤销（de-assert），由此释放rempty触发器预置控制信号。两个rclk上升沿后empty标志被撤销（de-assert）。因为aempty_n信号被撤销（de-assert）发生在wclk上升沿，而rempty变化发生在rclk时钟域，故双触发器同步器用来移除系统产生的亚稳态。

        8、谈谈另外一种预置（preset）空、满标志的方法

        这里不详细列出了，可参考paper。给出这种利用自时序电路框图：

        9、谈谈空、满标志信号的关键时序路径

       由于采用了异步比较，所以在产生wfull和rempty信号的时候必然存在关键时序路径。下图是rempty关键时序路径示意图，主要包括以下六条：

       1）、rclk-to-q，rptr自增；

       2）、rptr和wptr比较逻辑；

       3）、比较器输出结合direction锁存输出产生aempty_n信号；

       4）、预置rempty信号；

        5）、任何被rempty驱动的逻辑；

        6）、rclk时钟域触发器下级任何存在建立时间问题的相应信号。

        相应的，上图也显示出了产生wfull时候的关键路径。

        10、最后是附上代码，注意paper是用verilog写的，我已用vhdl改写过，其中paper中FIFO的memory读写地址直接用了gray code指针，这是错误的，另外修改了异步指针比较中direction产生方式：https://static.assets-stash.eet-china.com/album/old-resources/2009/6/26/f328c415-f192-4eca-8e21-140a0d76e332.rar。

      下面是StyleNo2的仿真波形：