由于平时我们工作中,FIFO都是直接调用IP核,对于FIFO深度选择并没有很在意,而在笔试面试过程中,经常被问及的问题之一就是如何计算FIFO深度。
当读数据的速率小于写数据的速率时,我们需要先将数据缓存下来,那么我们需要开多大的空间缓存这些数据呢?缓存开大了会浪费资源,开小了会丢失数据,如何去计算最小FIFO深度是本文的重点。
本文涵盖了FIFO最小深度计算所有情况:
假如模块A不间断的往FIFO中写数据,模块B同样不间断的从FIFO中读数据,不同的是模块A写数据的时钟频率要大于模块B读数据的时钟频率,那么在一段时间内总是有一些数据没来得及被读走,如果系统一直在工作,那么那些没有被读走的数据会越累积越多,那么FIFO的深度需要是无穷大的;
但是若写操作是连续的数据流,那么再大的FIFO都无法保证数据不溢出。因此可以认为这种情况下写数据的传输是“突发Burst”的,即写操作并不连续;
要确定FIFO的深度,关键在于计算出在突发读写这段时间内有多少个数据没有被读走。即FIFO的最小深度就等于没有被读走的数据个数。
Case1 fa>fb with no idle cycles in both write and read
即写时钟快于读时钟,写和读的过程中没有空闲周期;
假设:
写数据时钟频率fa=80MHz
读数据时钟频率fb=50MHz
突发长度= number of data to be transferred = 120
在突发传输过程中,数据都是连续读写的
那么:
写一个数据所需要的时间 = 1/80MHz = 12.5ns
突发传输中,写完所有数据所需要的时间 = 120*12.5ns = 1500ns
读一个数据所需要的时间 = 1/50MHz = 20ns
所以写完所有的突发传输数据需要花费1500ns
在1500ns内能够读走的数据个数 = 1500ns/20ns = 75
所以在1500ns内还没有被读走的数据个数 = 120-75 = 45
因此FIFO的最小深度为45
Case2 fa>fb with two clock cycle delay between two successive read and write
即写时钟频率大于读时钟频率,但在读写的过程中存在空闲周期;
Case2在Case1的基础上增加了一个假设,即读比写慢两拍。这种假设是真正存在的,在异步FIFO设计中,我们需要去判断FIFO的空满来保证逻辑的正确性,判断空满标志需要去比较读写指针,而读指针与写指针处在不同的时钟域中,我们需要采用格雷码和两级同步寄存器去降低亚稳态的概率,而两级同步必然会导致空满标志位的判断至少延迟2个cycle。对于空标志位来说,将写指针同步到读时钟域至少需要花费2个时钟,而在同步这段时间内有可能还会写入新的数据,因此同步后的写指针一定小于或等于(当且仅有同步时间内没有新数据写入的情况下才会等于)当前的写指针,所以此时判断不一定是真空;同理,对于满标志位来说,将读指针同步到读时钟域至少需要花费2个时钟,而在同步这段时间内有可能还会读出新的数据,因此同步后的读指针一定小于或等于当前读指针,所以此时判断并不一定是真满。
通过上述讨论可以知道Case2的FIFO最小深度应该比场景1的FIFO最小深度45略大。
Case3 fa > fb with idle cycles in both write and read
即写时钟频率大于读时钟频率,但在读写的过程中存在空闲周期;
假设:
写数据时钟频率fa=80MHz
读数据时钟频率fb=50MHz
突发长度= number of data to be transferred = 120
连续写入之间的空闲周期为1。
连续读取之间的空闲周期为3。
那么:
两个连续写之间的空闲周期为1个时钟周期。它的意思是,在写入一个数据后,模块A等待一个时钟周期,开始下一个写入。因此,可以理解为每两个时钟周期,一个数据被写入;
两个连续读取之间的空闲周期为3个时钟周期。即读取一个数据后,B模块等待3个时钟周期,开始下一次读取。因此,我们可以理解,每四个时钟周期,读取一个数据;
写一个数据所需要的时间 = 2*1/80MHz = 25ns
突发传输中,写完所有数据所需要的时间 = 120*25ns = 3000ns
读一个数据所需要的时间 = 4*1/50MHz = 80ns
所以写完所有的突发传输数据需要花费3000ns
在3000ns内能够读走的数据个数 = 3000ns/80ns = 37.5
所以在3000ns内还没有被读走的数据个数 = 120-37.5 = 82.5
因此FIFO的最小深度为83
Case4 fa > fb with duty cycles given for wr_enb and rd_enb.
即写时钟频率大于读时钟频率,给定wr_enb和rd_enb的占空比;
假设:
写数据时钟频率fa=80MHz
读数据时钟频率fb=50MHz
突发长度= number of data to be transferred = 120
写使能信号占整个burst时间比重为1/2
读使能信号占整个burst时间比重为1/4
那么:
此场景与前一个场景(场景3)没有任何不同,因为在本例中,一个数据项将在2个时钟周期内写入,而一个数据项将在4个时钟周期内读取。
因此FIFO的最小深度也为83
Case5 fA < fB with no idle cycles in both write and read ( the delay between two consecutive writes and reads is one clock cycle)
即写时钟频率小于读时钟频率,且读写过程中没有空闲周期;
假设:
写数据时钟频率fa=30MHz
读数据时钟频率fb=50MHz
突发长度= number of data to be transferred = 120
在突发传输过程中,数据都是连续读写的
那么:
由于读数据比写数据要快,这种情况下永远也不会发生数据丢失的,因此FIFO只起到过时钟域的作用,FIFO的最小深度为1即可;
Case6 fa < fb with idle cycles in both write and read(duty cycles of wr_enb and rd_enb can also be given in these type of questions).
即写时钟频率小于读时钟频率,给定wr_enb和rd_enb的占空比;
假设:
写数据时钟频率fa=40MHz
读数据时钟频率fb=50MHz
突发长度= number of data to be transferred = 120
连续写入之间的空闲周期为1。
连续读取之间的空闲周期为3。
那么:
两个连续写之间的空闲周期为1个时钟周期。它的意思是,在写入一个数据后,模块A等待一个时钟周期,开始下一个写入。因此,可以理解为每两个时钟周期,一个数据被写入;
两个连续读取之间的空闲周期为3个时钟周期。即读取一个数据后,B模块等待3个时钟周期,开始下一次读取。因此,我们可以理解,每四个时钟周期,读取一个数据;
写一个数据所需要的时间 = 2*1/40MHz = 50ns
突发传输中,写完所有数据所需要的时间 = 120*50ns = 6000ns
读一个数据所需要的时间 = 4*1/50MHz = 80ns
所以写完所有的突发传输数据需要花费6000ns
在6000ns内能够读走的数据个数 = 6000ns/80ns = 75
所以在6000ns内还没有被读走的数据个数 = 120-75 = 45
因此FIFO的最小深度为45
Case7 fA = fB with no idle cycles in both write and read ( the delay between two consecutive writes and reads is one clock cycle).
即写时钟频率等于读时钟频率,且读写过程中没有空闲周期;
假设:
写数据时钟频率fa=50MHz
读数据时钟频率fb=50MHz
突发长度= number of data to be transferred = 120
读和写都没有空闲周期,这意味着突发中的所有项都将以连续的时钟周期写入和读取
那么:
如果clkA和clkB之间没有相位差,则不需要FIFO;
如果clkA和clkB之间存在相位差,深度“1”的FIFO就足够了。
Case8 fA = fB with idle cycles in both write and read (duty cycles of wr_enb and rd_enb can also be given in these type of questions).
即写时钟频率等于读时钟频率,给定wr_enb和rd_enb的占空比;
假设:
写数据时钟频率fa=50MHz
读数据时钟频率fb=50MHz
突发长度= number of data to be transferred = 120
连续写入之间的空闲周期为1。
连续读取之间的空闲周期为3。
那么:
两个连续写之间的空闲周期为1个时钟周期。它的意思是,在写入一个数据后,模块A等待一个时钟周期,开始下一个写入。因此,可以理解为每两个时钟周期,一个数据被写入;
两个连续读取之间的空闲周期为3个时钟周期。即读取一个数据后,B模块等待3个时钟周期,开始下一次读取。因此,我们可以理解,每四个时钟周期,读取一个数据;
写一个数据所需要的时间 = 2*1/50MHz = 40ns
突发传输中,写完所有数据所需要的时间 = 120*40ns = 4800ns
读一个数据所需要的时间 = 4*1/50MHz = 80ns
所以写完所有的突发传输数据需要花费4800ns
在4800ns内能够读走的数据个数 = 4800ns/80ns = 60
所以在4800ns内还没有被读走的数据个数 = 120-60 = 60
因此FIFO的最小深度为60
Case9 如果数据速率如下所示
在前面几种场景中,我们给的条件都是每隔几个时钟读写一次,这种周期性读写在实际中很常见。但是在工程设计中还存在这样一种情形,只给出数据在一段时间内的读写速率,怎么读写完全随机,这种情况我们需要考虑最坏的一种情况避免数据丢失。
对于最坏的情况,读写之间的数据速率差异应该是最大的。因此,对于写操作,应该考虑最大数据速率,对于读操作,应该考虑最小数据速率。
写数据时钟频率fa=读数据时钟频率fb
在写时钟周期内,每100个周期就有80个数据写入FIFO
在读时钟周期内,每10个周期可以有8个数据读出FIFO
以下是一些可能性:
下面是从上图中观察到的情况:
写操作的最大数据速率在上表格中case - 4。(写操作在最小的时间内完成)。因此,考虑case - 4来进行进一步的计算。
首先这里没有给出数据的突发长度,从假设中可以得出每100个周期就有80个数据写入FIFO,这里可能就有人会说突发长度就是80个数据,其实不是这样的,因为数据是随机写入FIFO的,我们需要考虑做坏的情形,即写速率最大的情形,只有如下图背靠背的情形才是写速率最高的情形,burst length为160;
在读时钟周期内,每10个周期可以有8个数据读出FIFO;即一个周期可以写入 8/10 数据
所以160个时钟读了160*8/10 = 128个数据;
考虑背靠背(20个clk不发数据+80clk发数据+80clk发数据+20clk不发数据的共200个clk)
因此FIFO的最小深度=160 - 128 = 32
总结
从上面分析来看,求FIFO的最小深度主要有以下要点:
在求解之前需要验证一下在允许的最大时间长度内写入的数据量是否等于读出的数据量,保证有解;
求FIFO深度需要考虑最坏的情形,读写的速率应该相差最大,也就是说需要找出最大的写速率和最小的读速率;
不管什么场景,要确定FIFO的深度,关键在于计算出在突发读写这段时间内有多少个数据没有被读走;
由于FIFO空满标志位的判断延迟,在实际应用中需要预留一些余量。
下面我们来推导一下FIFO深度的求解公式,假设:
写时钟周期为clkw
读时钟周期为clkr
在读时钟周期内,每x个周期内可以有y个数据读出FIFO,即读数据的读数率
在写时钟周期内,每m个周期内就有n个数据写入FIFO
背靠背“的情形下是FIFO读写的最坏情形,burst长度 B = 2*n
由上得到:FIFO的最小深度为 B - B * (clkr/clkw) * (y/x)
参考文献
https://hardwaregeeksblog.files.wordpress.com/2016/12/fifodepthcalculationmadeeasy2.pdf
欢迎FPGA、嵌入式、信号处理等工程师关注公众号
全国第一大FPGA微信技术群
欢迎大家加入全国FPGA微信技术群,这个群体拥有数万工程师、一群热爱技术的工程师,这里的FPGA工程师相互帮助,相互分享,技术氛围浓厚!赶紧叫上小伙伴一起加入吧!!
用手指按住就可以加入FPGA全国技术群哦
FPGA之家元器件芯城
联系客服