查看完整版本: 关于fifo深度问题

关于fifo深度问题

前几天发了没有人回，在：别的论坛上看到的这个贴子，觉得有点问题，大家来讨论一下：

写时钟周期w_clk,
读时钟周期r_clk,
写时钟周期里，每B个时钟周期会有A个数据写入FIFO
读时钟周期里，每Y个时钟周期会有X个数据读出FIFO
则，FIFO的最小深度是？

首先，这道题不一定有解
有解的必要条件是在一定时间内（足够长），写入的数据数量一定要等于读出的数据数量
因此有：A/B * w_clk = X/Y * r_clk

其次，算出写数据的最大burst_length。考虑最坏情况
比如，如果条件给出，每100个写时钟，写入80个数据，那么在背靠背的情况下，burst_length = 2*80=160

最后，fifo_depth = burst_length - burst_length * X/Y * r_clk/w_clk

BTW：通常，为了安全起见，都会多留一些depth的余度

个人觉得，公式应该是这样：
A/(B * w_clk) = X/(Y * r_clk)

fifo_depth = burst_length - burst_length * X/Y * w_clk /r_clk


举例说明：
如果100个写时钟周期可以写入80个数据，10个读时钟可以读出8个数据
其中w_ck=5ns,r_ck=10ns

如果按照之前的公式，得出的深度为：fifo_depth = burst_length - burst_length * X/Y * r_ck/w_clk=160-160*8/10*2=-94,显然是不对的

实际上，考虑背靠背（20个clk不发数据＋80clk发数据＋80clk发数据＋20个clk不发数据的200个clk）

这样在中间160个写时钟周期连续写的情况下，只能读出160*5/(10*10)*8=64个数据，所以FIFO的深度应该为160-64=96
也就是fifo_depth = burst_length - burst_length * X/Y * w_clk /r_clk=160-160*8/10*5/10=96

大家可以讨论一下，加深对这个问题的认识。

[quote]原帖由 [i]windzjy[/i] 于 2007-1-14 17:18 发表
个人觉得，公式应该是这样：
A/(B * w_clk) = X/(Y * r_clk)

fifo_depth = burst_length - burst_length * X/Y * w_clk /r_clk


举例说明：
如果100个写时钟周期可以写入80个数据，10个读时钟可以读出 ... [/quote]

我以前看到过这个公式，是用来计算同步fifo的。

你所举的那个例子， 如果呼入fifo的数据宽度和呼出相同的话，都设为w bit。那么呼如fifo的带宽就是200wbps，呼出fifo的带宽是100wbps。考虑链路利用率都是80％。那么呼入fifo的有效带宽是160wbps。呼出fifo的带宽是80wbps。现在看到矛盾了，由于输入输出带宽不相等，进来永远比出去多，那么FIFO总是处于不断积累数据的状态。所以lz所举的这个例子并不合适。
应该提高读时钟的速率，使fifo两端的带宽匹配，在这个前提下才能计算出有解的fifo深度。

如果令wclk＝rclk （以下内容中的clk表示时钟的频率，不是周期）。可使得读写带宽匹配。那么这个例子的答案是32
原因如下： 考虑背靠背的情况，160个wclk连续都写入了160个数据。而这160个wclk时间内，由于wclk＝rclk，那么读出了（16/10 ）×8＝128个数据。有32个数据会被留在fifo里。那么fifo的最小深度就是32。

如果令wclk＝200mhz，改为100个wclk里写入40个，rclk＝100mhz，10个rclk里读出8个。那么fifo深度为48

[[i] 本帖最后由 wice3 于 2007-1-15 14:52 编辑 [/i]]

续上：
讲数据带入公式 fifo_depth = burst_length - burst_length * X/Y * r_clk/w_clk
正好也是也是这个结果。所以我觉得公式是对的。
其实 A/B * w_clk = X/Y * r_clk 即 (A/B)*W_CLK=(X/Y)*R_CLK
所表达的含义就是 fifo的输入和输出带宽要匹配，其中A/B表示链路利用率，w_clk×width表示带宽，这里大概是默认输入输出的数据宽度相同，所以以wclk来代替带宽。 X/Y 和 r_clk 的含义也是这样：） 。在带宽匹配的前提下数据不会无限积累。

fifo_depth = burst_length - burst_length * (X/Y) * (r_clk/w_clk)公式是对的。

[[i] 本帖最后由 wice3 于 2007-1-15 14:32 编辑 [/i]]

续上：
fifo_depth = burst_length - burst_length * (X/Y) * (r_clk/w_clk) 作个变形，
得到 fifo_depth = burst_length - （burst_length /w_clk)*[r_clk*(x/y)]
其中（burst_length /w_clk) 表示这个burst的持续时间，r_clk*(x/y)表示读的实际速度。
两者的乘积自然就是这段时间读出的数据量。显然burst_length表示这段时间写入的数据量，两者的差为fifo中残留的数据，这个也就是理论上的fifo的最小深度。
实际应用中往往是以半空半满信号来指示fifo的空满状态的，所以实际设计fifo的时候会至少留下一个数据空间的深度裕量。

以上是我的一点粗浅的理解，欢迎各路高手批评指正。

[[i] 本帖最后由 wice3 于 2007-1-15 15:07 编辑 [/i]]

仔细看了一下发现自己的问题：
1，贴子中写时钟周期w_clk和读时钟周期r_clk并不是指的周期，而是指的频率
2，我举例不当，因该是wice3所说的那样，100个CLOCK写40个数据，这样在100个周期内
     写入的数据数量和读出的数据数量就一致了，不会造成溢出。

总结：
1，原公式还是对的，只是w_clk和r_clk意义描述的容易让人误解
2，又加深了对fifo的理解

有什么问题大家可以继续讨论。

同意楼上的意见

回复 #3 wice3 的帖子

如果令wclk＝200mhz，改为100个wclk里写入40个，rclk＝100mhz，10个rclk里读出8个。那么fifo深度为48???
怎么算的?我算得怎么是0.
谢谢

[quote]原帖由 [i]deangreen[/i] 于 2007-1-16 18:00 发表
如果令wclk＝200mhz，改为100个wclk里写入40个，rclk＝100mhz，10个rclk里读出8个。那么fifo深度为48???
怎么算的?我算得怎么是0.
谢谢 [/quote]
考虑最糟糕的情况，背靠背写fifo，80个wclk里写进了80个数据，
80个wclk的时间等于40个rclk时间，在40个rclk时间里读出了4×8＝32个
那末fifo中残留48个 ：）

长见识了，我做过的fifo都是比较简单的，还没用过这么复杂的公式去弄，没太多考虑最小深度问题

[quote]原帖由 [i]wice3[/i] 于 2007-1-16 22:03 发表

考虑最糟糕的情况，背靠背写fifo，80个wclk里写进了80个数据，
80个wclk的时间等于40个rclk时间，在40个rclk时间里读出了4×8＝32个
那末fifo中残留48个 ：） [/quote]
按照您的意识就是：
60+40写 +40写+60
在2个40写的时间段中读，读出32个
80-32=48？

回复 #10 wice3 的帖子

再问一个有关深度的问题。
数据流水线技术，是不是就是利用fifo来实现的？那末一般的数据流水线都是4-5级。那么fifo一般的深度是4-5？
这两个有什么联系？
谢谢

[quote]原帖由 [i]deangreen[/i] 于 2007-1-17 14:06 发表

按照您的意识就是：
60+40写 +40写+60
在2个40写的时间段中读，读出32个
80-32=48？ [/quote]
嗯，是这样.
代公式算也可以，结果也是48.

[quote]原帖由 [i]deangreen[/i] 于 2007-1-17 16:13 发表
再问一个有关深度的问题。
数据流水线技术，是不是就是利用fifo来实现的？那末一般的数据流水线都是4-5级。那么fifo一般的深度是4-5？
这两个有什么联系？
谢谢 [/quote]

版主可以回答我的这个问题？
谢谢

斑竹解答得非常清楚，理解了。

在追问一下，
1.算出深度以后，在设计时如何考虑，影响那些参数阿，谢谢？

[quote]原帖由 [i]deangreen[/i] 于 2007-1-18 13:36 发表


版主可以回答我的这个问题？
谢谢 [/quote]
你的意思是不是这样，数据到来后，需要等待处理器在一定的逻辑控制之下对它进行几个步骤的处理。由于到来的数据需要等待上流水线，在它上流水线之前，需要在fifo中排个队。你想要问的流水线处理级数和fifo的深度关系，也就是级数为4～5的流水线会造成数据排多长的队，是这样吧？如果我没理解错的话，下面你就可以继续看了 ：）。

   说实在的，看到你这个问题我怔了好一会儿，我好像从来没有见过别人把流水线处理级数问题和fifo的深度计算问题直接挂钩的，后来突然明白了，你好像是没有很好地把问题分解开。
  
   这样分析，我想要计算fifo深度(在这里我想把它叫成数据队长)，首先我需要知道fifo的读写频率、数据宽度、读写链路利用率、写数据burst的长度，在数据宽度相等的情况下，不考虑数据宽度。其实也就是想办法找到前边提到的公式里的各个参数。
  
接下来分析流水线是怎么影响数据（指令）队长的，显然，流水线影响的是fifo的读链路利用率。要弄清楚有多大影响，其实需要结合实际情况，某个指令集，某种组织结构等。在这里我只能很笼统的说，需要找到流水线对指令的处理效率最低的时候，假设流水长n级，由于前边指令的处理结果可能会影响下一个指令的取指时间，假设最糟糕的情况是需要等到前一个指令完全处理完了，才能做下一个（这个需要结合具体应用来具体分析，也许情况比这个好得多，也许更糟糕）。 这时候下一个指令在队列里的等待时间就是流水线各步骤单独执行一遍的时间和。假设每个步骤一个系统时钟周期，那么读链路的利用率大约是1/n，对应到前边讨论过的内容，其实也就是n个读时钟时间，读出了1个。
下面你就可以根据前边的公式，结合你的实际应用来计算fifo的深度了。

水平有限，不知道自己表达清楚了没，另外我不是设计交流版的斑竹 ：p 。

[quote]原帖由 [i]deangreen[/i] 于 2007-1-17 16:13 发表
再问一个有关深度的问题。
数据流水线技术，是不是就是利用fifo来实现的？那末一般的数据流水线都是4-5级。那么fifo一般的深度是4-5？
这两个有什么联系？
谢谢 [/quote]
第2个问题回答：如果这是个经验数据，那我不能说什么。如果不是的话，这样说多少有点武断。不仅仅是数据流水线的级数问题，还需要参考这个流水线相关的指令集，处理器的组织结构等.
第一个问题回答：当指令进流水线之前需要排队的时候，确实可以用个fifo来缓存下。
第3个问题回答，参见上边的帖子。

[[i] 本帖最后由 wice3 于 2007-1-18 19:42 编辑 [/i]]

[quote]原帖由 [i]stanleyfan[/i] 于 2007-1-18 19:20 发表
斑竹解答得非常清楚，理解了。

在追问一下，
1.算出深度以后，在设计时如何考虑，影响那些参数阿，谢谢？ [/quote]
计算出fifo的深度后，可以选择fifo的实现方式。其他的需要结合具体的应用才能讨论吧。

学习了！！！！！！！！！！！！！！