FIFO 设计笔记

Posted on 2015-10-02 22:13 in IC

FIFO

FIFO 的重要性就不用再重复了，在笔试面试的时候也常常被问到，总结一下设计 FIFO 需要注意的问题。

FIFO 可以分为两类：

  • Sync FIFO: write 和 read 使用同一个时钟

  • Async FIFO: write 和 read 分别使用两个时钟

设计 FIFO 的时候，通常需要考虑的问题有：

  1. FIFO 的大小

  2. FIFO 空满的判断

Sync FIFO

Sync FIFO 的框图如下所示：

sync fifo

因为同步 FIFO 的读写速率是相同的，所以 FIFO 的大小设置不必考虑读写速率差这个因素，要简单很多。

在 FIFO 内部，一般使用 dual port RAM 存储数据。双端口 RAM 有两套独立的读写地址，读地址和写地址分别由读指针和写指针来产生：写指针指向下一个数据被写入的地址，读指针指向下一个被读出的数据的地址，通过判断读写指针的相对大小，就可以得到 FIFO 的状态（full / empty）。

还有另外一种方法来产生 full / empty 信号：FIFO 内部维护一个计数器，每次写入一个数据 cnt++，每次读出一个数据 cnt--。这种方法产生 full / empty 很简单：当 cnt == 0，表示 FIFO empty；当 cnt == max，表示 FIFO full。虽然这种方法产生 full / empty 很简单，但是需要额外的计数器，而且计数器的位宽随着 FIFO 的深度增加，不仅占用的资源更多，而且会降低 FIFO 最终可以达到的速度。

Async FIFO

一般异步 FIFO 的读写速率不同，如果写速度 > 读速度，则当数据量超过一定长度时，会出现溢出的情况，为了防止这种情况，可以采用两种措施：

  1. 预先知道写速率和模式（burst / nonburst），最小的读速率，根据这些条件设置 FIFO 的深度

    通常发送端的数据都是突发的形式，FIFO 的深度至少要大于等于突发数据的最大长度。

  2. 握手机制（full / empty）

    很多情况下，突发数据的长度和分布是预先不知道的，此时则无法确保 FIFO 的深度足够大，因此需要握手机制来告诉发送端已经没有多余的空地址保存数据 or 告诉接收端已经内部已经没有剩余的可以读取的数据。通常使用如下的 FSM 来实现：

    发送端，写数据：

    wr fsm

    接收端，读数据：

    rd fsm

Gray Code

在异步 FIFO 中，因为一些内部的信号要从写 / 读时钟域传递到读 / 写时钟域，所以必须要解决异步信号同步的问题，而且有的信号不止 1 bit，如果使用 “ 同步桥 ”，则因为各个 bit 的同步时延不一定（1~2T），所以不能用同步桥。

这个问题可以使用 gray code 解决：gray code 是循环码，每次只有 1 bit 变化，这样就避免了多 bits 变化的数据同步问题。如下图：

sync

gray code 与 binary code 的相互想换见另外一篇 blog。

wr-ptr / rd-ptr Sync Lag

异步 FIFO 还有个问题是：地址信号跨时钟域时，可能会有 1T 的时延，这个多余的时延并不会导致 full /empty 错误置位，引起错误的 overf：

  • 如果地址信号传递到读时钟域时延时了 1T，此时接收端并不知道数据已经写入了 FIFO，仍然认为 FIFO 是空的，这种情况只会对 FIFO 的吞吐率 throughput 有影响，但是不会导致 underflow；

    如下图，先写满 FIFO，然后开始读：在 t6 时 FIFO 读空，empty = 1，在 t7 时，写入了一个新数据，此时 FIFO 内已经有有效数据了，但是 wr-ptr 同步到读时钟域要花费 2T，所以在 t9 时 empty = 0。有两个时钟周期（t7, t8） rd 被阻塞了，但是并不影响 FIFO 正常工作。

    empty

    时序图：

    empty timing

  • 如果地址信号传递到写时钟域时延是了 1T，此时发送端并不知道 FIFO 已经有空余地址了，仍然认为 FIFO 是满的，这种情况也是只会对 FIFO 的吞吐率 throughput 有影响，但是不会导致 overfl；

    如下图，先写满 FIFO，然后开始读：在 t5 时，full = 1，在 t6 时，读出了一个数据，此时 FIFO 已经有空余地址了，但是 rd-ptr 同步到写时钟域要花费 2T，所以在 t8 时 full = 0。有两个时钟周期（t6, t7） wr 被阻塞了，但是并不影响 FIFO 正常工作。

    full

    时序图：

    full timing

Full / Empty Generation

因为 wr-ptr 和 rd-ptr 相同时，FIFO 既可能是 full，也有可能是 empt，所以需要额外的 1 bit 来区别这两种情况：

假设 FIFO 的深度是 8，则地址为 3 bits，初始时 wr-ptr 和 rd-ptr 都是 0000，FIFO 此时是 empty：

  1. 当连续 8 个数据写入到 FIFO full，wr-ptr = 1000，而 rd-ptr = 0000，MSB 不同，剩余位相同

  2. 当连续 8 次读取数据 FIFO empty，rd-ptr = wr-ptr = 1000，所有 bits 都相等

借助这多余的 1 bit，可以区分出是 wr-ptr 太快，将 rd-ptr 套圈了（wr-ptr = 1000，rd-ptr = 0000， 即 full），还是 rd-ptr 更快，追上了 wr-ptr（rd-ptr = wr-ptr = 1000）。

框图如下：

full empty gen

这种 wr-ptr / rd-ptr 用 gray code 保存，比较 /+1 用 binary 保存的方式，使得 design / debug 变得很简单，但是需要的资源比较多。如果全部使用 gray code，虽然可以降低资源占用，但是需要其他逻辑。

Dual Clock FIFO Design

下图是使用 Dual port RAM 的异步 FIFO 框图，其中 wr-ptr 和 rd-ptr 直接使用 gray code，节省了 gray code 和 binary code 之间的转换逻辑。

dual clock fifo

和前面的逻辑类似，使用多 1 bit 来辅助区分 full / empt，不过因为改成用 gray code 来比较，所以稍有不同，下图显示了 FIFO 从 empty 到 full 再到 empty 的过程：

full empty condition

  1. FIFO empty

    当 wr-ptr = rd-ptr 时 FIFO empty

  2. FIFO full

    如上图，FIFO 初始状态为 empty，然后连续写入 8 个数据，再读出 8 个数据，此时 wr-ptr = rd-ptr = 7，FIFO 又变为 empty。此时如果再写入一个数据，wr-ptr = 8，rd-ptr = 7，如果仍然使用前面介绍的方法（MSB 不同，剩余位相同 )，则会得出 FIFO full 的错误结论，实际上 FIFO 并没有满。

    仔细观察 gray code 的对称性，就可以知道，当 full 时（wr-ptr 将 rd-ptr 套圈时），MSB 不同，wr-ptr 的 2nd MSB 要先翻转，才和 rd-ptr 相同。所以，当下面 3 个条件都满足时，FIFO full：

    1. wr-ptr 和 rd-ptr 的 MSB 不相等

    2. wr-ptr 的 2nd MSB 翻转后和 rd-ptr 的 2nd MSB 相等

    3. 剩余 bits 全部相等

Summary

总结 FIFO 的设计，只要注意 FIFO 通过 wr-ptr 和 rd-ptr 得到 full / empty，而且使用 gray code 来跨时钟域，基本上就没问题了 :-D

Ref

The Art of Hardware Architecture: Design Methods and Techniques for Digital Circuits

Advanced FPGA Design: Architecture, Implementation, and Optimization

Previous Post Next Post