面试必杀技:异步FIFO — CDC的那些事(5)

作者:李虹江
原文链接:https://mp.weixin.qq.com/s/ayQjYuXu7jX8_em-Zxm2HA
面试必杀技:异步FIFO(下)– CDC的那些事(6)
本文结合了以上两篇文章,授权转自IC加油站微信号,未经作者授权,严禁二次转载。

面试必杀技:异步FIFO(上)

这一篇老李终于要开始聊异步FIFO(Asynchronous FIFO)了。在知乎上曾经老李见过一个问题:

硕士生找工作的时候把异步fifo写成一个项目经历,是不是显得很low啊?

知乎:https://www.zhihu.com/questio…

下面回答很有意思,老李发现那些回答很low的以在校学生和刚毕业的应届生居多,大家都觉得简历里面一定要写上什么无线接收机,USB控制器等等才显得高大上。而几个来自真正工业界大佬的回答反而不说low,比如下面的这个回答来自海思的架构师说

我如果面试,不会介意。但会很乐意基于这个话题继续问你对异步原理的理解,例如格雷码的原理,两拍同步或者三拍同步的差异,或者FIFO内DATA如何保证绝对稳定等问题来进一步试探,这才是决定结果的。

夏晶晶 https://www.zhihu.com/questio…

老李自己也基本认同这个观点,即异步FIFO里面其实需要了解的东西很多,几乎涵盖了CDC中所有相关的知识点,面试官可以就异步FIFO里面很多的点进行提问。老李当年面试硅谷各大芯片公司,几乎都被问到了异步FIFO。所以说,深刻理解异步FIFO,是一个合格的前端芯片设计工程师必须掌握的基本技能。

在开始讲异步FIFO之前,老李先带大家简单回顾一下同步FIFO。FIFO就是一个存储的管道,有进的口,有出的口。同步FIFO就是说进口(写入端)和出口(读出端)是同一个时钟域。FIFO一般深度多于1,就需要两个指针: write pointer和read pointer。

对于write pointer和read pointer我们一般用2进制,写入操作(Push)使得write pointer + 1,读出操作(Pop)使得read pointer + 1。这就像是两个人在一个环形跑道上赛跑。当write pointer领先了read pointer一圈之后,也就是说FIFO里面所有的存储单元都存了数据,FIFO没有空余的存储单元了,我们就说FIFO满了。反过来,当read pointer追上了write pointer,所有的存储单元都空闲了,我们就说FIFO空了。

对于异步FIFO来说,Push和Pop分别在不同的时钟域,那么最核心的问题就是空满的判断了。在Pop的这一侧,FIFO空不空是关键,因为空的时候不能Pop,满不满反而不重要。在Push的这一侧,反过来,满不满才关键,因为满的时候不能继续往进Push。因此,我们就要在读的这一侧判断FIFO是否空,在写的这一侧来判断FIFO是否满。当然我们还是要有read pointer和write pointer,在pop这一侧更新read pointer,在push这一侧更新write pointer。那么当我们要把pointer同步到另外的时钟域进而去比较的时候,我们就遇到了上一讲讨论的multi-bit 同步的问题,即binary counter不能直接利用double flop来同步。

那么我们上一篇讲到的带反馈的asynchronous load模块可以用来同步pointer吗?可以是可以,但是缺点也很明显,即反馈的话要跨两次时钟域,对于效率很有影响,比如说push这一侧要等到反馈信号回来之后才能继续下一个push,哪怕FIFO里面还有很多空闲的单元。pop的这一侧也是一样。这样对于FIFO的整体性能影响太大。

那有没有更快的办法呢?答案就是老李上一期最后埋的坑 — 用格雷码Gray Code。 

格雷码是以美国学者Frank Gray于1947年提出的一种二进制编码方式,后面这种编码方式就以他的名字命名。这种编码方式的特点老李以两句话概况

  1. 每相邻的两个编码之间有且只有一位不同
  2. 当第N位从0变到1的时候,之后的数的N-1位会关于前半段轴对称,而比N位高的位是相同的。

记住了以上两点,老李保证你可以现场推出来Gray code是什么样的。说实话,老李自己也记不住二进制到Gray code的转换公式,每次都是写出来现场推。(相信老李,面试官问你的时候除非他自己面你之前背了公式,否则他也得现推。)如果你只记得1,你现场可能推不出来,所以老李还是建议你把2也记住。下面这幅图就是用10进制,传统2进制以及Gray code来表示0-15个数。

老李所说的轴对称是什么意思呢?请看Gray code前两个数4’b0000, 4’b0001,它们俩之间可以画一条对称轴,第1-3位都是相同的。再看前4个数,在4‘b0001和4’b0011之间画一条对称轴,第2、3位是相同的,第0位则是轴对称的,从0-1到1-0。之后的规律老李也在图上标出来了,一看就懂。有了这两个规律,更多位数的Gray code老李相信你也可以现场直接写出来。

然后咱们就来推一推关系,你只要大概记住需要用到异或操作,就能推出来


Binary to Gray
g(3) = b(3) ^ 0
g(2) = b(3) ^ b(2)
g(1) = b(2) ^ b(1)
g(0) = b(1) ^ b(0)
g(n) = b(n+1) ^ b(n)
Gray to Binary
b(3) = g(3)
b(2) = g(3) ^ g(2)
b(1) = g(3) ^ g(2) ^ g(1)
b(0) = g(3) ^ g(2) ^ g(1) ^ g(0)

Gray code有什么魔法之处,能够突破muti-bit不能用2flop synchronzier的限制呢?关键就在于它的第一个特点:相邻两个编码之间有且只有1位不同。我们说multi-bit如果在一个时钟沿有多个bit同时翻转,在另外一个时钟域采到的时候由于2flop 稳定需要1个或2个周期,所以可能会出现错误的值。Gray code这种编码,从根本上就没有这个问题,因为以Gray code编码作为计数器,每个时钟沿来的时候只会有1个bit发生了翻转,其余所有bit都是稳定的!这样即使这一个bit在用2flop synchronizer同步到另外一个时钟域时,可能需要1个周期发生变化,或者2个周期,在发生变化前,另一个域的值就是之前的稳定值,变化后就是新的值,而不会出现其他不该出现的值。

用了2flop synchronizer来同步,省去了反馈,把read pointer同步到write domain来判断满,把write pointer 同步到read domain来判断空,只需要跨一次domain,就可以判断,这样可以提高push和pop的效率。

而对于memory的取址还是得用2进制编码,我们需要做的就是在同步pointer的时候把binary pointer 转化为gray code pointer,然后用2flop synchronizer同步到对面时钟域之后,再来判断空满。这里有个问题,我们需不需要把gray code再转化为binary code之后再来比较空满呢?当然可以,我们学习新知识就是不断把问题转换为已经解决的问题,在同步FIFO的时候我们已经知道怎么用read pointer和write pointer判断空满,那么自然而然我们可以这样做。那么有没有更快的办法呢?我们能不能直接利用gray code来判断空满呢?

有!我们再仔细观察gray code。和同步FIFO一样,我们对于2^n个entry的FIFO, 需要N+1个bit来表示address和gray code。以下面的编码为例,假设FIFO有8个entry,我们用4位来表示。

FIFO空比较好判断,write pointer == read pointer,用binary或者gray code都行,要求每位都相同。

满稍微复杂一点,我们举例来说,假设FIFO一开始一直写,不读,写满8个entry后write pointer 的binary变成4’b1000, gray code是4‘b1100, 而read pointer的gray code是4’b0000,可以看到高两位是相反的,之后的低位是相同的。再举个例子,假设write pointer 的gray code到了4’b1011, 而这个时候read pointer如果是4’b0111,那么也是8个entry满了。

所以我们归纳出,利用gray code判断满的条件为:

assign full = (write_ptr_gray[N:N-1] == ~read_ptr_gray[N:N-1])
            &&(write_ptr_gray[N-2:0] == read_ptr_gray[N-2:0]);

最后再说一个面试中的常见问题,这个问题知乎上也有人提

慢时钟域同步快时钟域格雷码时候,在慢时钟域的一个周期中,经历了两次或多次快时钟域的上升沿,那么对应的格雷码就会有两个或多个bits发生变化,这个不会产生多个bits同步的问题吗?

知乎:https://www.zhihu.com/questio…

说实话老李当年面试就被问过好几次这个问题。这个问题很有迷惑性,但是回答起来也很简单,其实老李上面已经回答了,这里再复习一下,继续搬出我们之前看过的图。我们说多个bit发生变化其实是针对source clock的每一个edge来说的,因为不同bit之间发生翻转的时间不能严格对齐,所以会导致destination clock可能看到不同的值,导致最后synchronizer输出会出现错误的值,从而影响FIFO的空满判断。而gray code在每个source clock的沿只会有一个bit发生翻转,其余bit保持稳定,这样每个destination clock edge来的时候最多也只可能碰到1bit在翻转,这个翻转的bit可能会给synchronizer的第一级引入metastable,但是最后synchronizer的输出无非就是保持前值或者是更新后的值,而这两个值都是合理的值,不会出现一个错误的值从而导致FIFO空满判断逻辑错误。虽然慢时钟域同步过来的值可能和之前的值相比有多个bit发生变化,但是这些bit的翻转不是同时发生的,这是回答这道题的关键。

这周老李工作较忙,上周的推送晚了几天,拖到了这周末。下周老李继续带大家了解异步FIFO里的其他细节内容。比如前面讲的判断空满是真满、真空还是假满、假空?如果FIFO的深度不是2^n,还能用gray code吗?

面试必杀技:异步FIFO(下)

上面老李介绍了异步FIFO的基础部分,包括为什么用Gray Code来同步read pointer, write pointer。这一篇咱们从头一起过一遍异步FIFO的具体设计,然后再讨论几个常见的问题。

有的面试官可能上来让你先画异步FIFO的框图,老李建议大家自己手画一下,能够记住。

要注意,wptr和rptr都是gray code,在上一篇我们已经讨论过gray code是可以直接利用2flop synchronizer来同步的。而用来读写实际的memory必须是binary address,在FIFO write control和FIFO read control 里面我们进行binary to gray code的转换。

下面是上图中间fifo memory部分的简单实现

上面的code简化了rdata的逻辑,如果使用SRAM,可能需要加一级flop来存储SRAM读出来的值。

这里插一句,在设计异步FIFO或者使用异步FIFO的时候,需要计算清楚FIFO的深度,(如何FIFO的深度计算老李打算以后单独开一篇文章来讨论)然后要比较使用SRAM和flop array的cost。依据老李的经验,目前较新的7nm/5nm的工艺下,当存储位大于2k bit,使用vendor的compile memory在面积上开始划算起来,低于2k bit,使用flop array划算。这个部分需要大家在实际工作中自己去比较计算。

关于read pointer和write pointer 的同步很简单,用2flop synchronizer即可,老李这里要强调一下,大家在实际工作中不要自作聪明去用verilog的behaivor code去实现2flop syncronzier(上面注释掉的行),而是要直接例化现成的cdc库元件。只要你不是在创立不到一个月的创业公司,这种cdc library一定是你们公司已经有的,轮子已经造出来了,千万别自己再造。

下面我们再看一下write control部分的RTL实现。

这里的满的判断用到了我们上一篇讲的判断逻辑,即高两位相反,低位都相同。下面是read side判断空的逻辑。

下面我们来讨论几个面试中常见的问题。

问题:假设wclk速度比rclk快,那么当raddr+1,再同步到wclk后,如果这期间有了push操作,那会不会使得wptr超过了rptr,造成FIFO overflow呢?

回答:不会,当rptr在传过去之前,如果wptr已经追上了rptr-1,那么wfull已经是1了,FIFO是不允许在FIFO 满的时候进行push操作的(在实际工程中我们通常要利用assertion来check保证在wfull为1的时候push不能为1)。而如果这个时候有了pop操作,raddr+1,这个时候实际上FIFO有了一个free entry,但是push这一侧看到的FIFO依然是满的。这就是我们所说的异步FIFO的假满。相应的,FIFO的empty为1时,也可能FIFO此时有个push操作,导致FIFO为假空。假空和假满并不会影响FIFO的正确性,无非就是早一点告诉push side停止push,或者早一点告诉pop side停止pop,但是FIFO是不会产生overflow和underflow的。如果要说有什么缺点的话,就是在性能上有一些损失,当FIFO的深度很大的时候,这通常不是什么问题。

问题:如何判断FIFO是真空/真满呢?

回答:判断假空假满刚好相反,在push side我们来判断空,在pop side来判断满,为什么要这样留给大家自己思考。

问题:设计一个depth=1的异步FIFO

回答:这个大家就是要活学活用了,不能死板套用。只需要考虑一个问题,只有1个entry,那么需要几位的address 或者pointer呢?当然是1位就够了,那我们真的还需要一个pointer吗?因为只有一个entry,当一次push,FIFO就满了,一次pop,FIFO就空了。1个bit用来表示满和空就足够了。其实这样的FIFO我们已经见过了,老李在多bit信号跨时钟域怎么办?– CDC的那些事(4)里面讲到的带反馈的asynchronous load其实就是depth=1的异步FIFO!

问题:如何设计depth不是2的幂次的异步FIFO?

回答:我们在上一讲里面看到的gray code,只有当depth=2的幂次个数的时候,才能做到wrap around时继续保持gray code的性质:即连续两个码之间只有1位不同。下面这个图是表示depth=8的时候我们利用16个gray code来表示pointer。

比如从4‘d15到4’d0,也只有1位不同。但是如果不是2的幂次,比如DEPTH=7,那我们怎么样来利用Gray code呢?直接从4’b0000到4’b0101肯定是不行的,因为4’b0101变到4’b0000有两个bit发生了变化,这样我们就没法利用2flop synchronizer来同步了。解决这个办法的诀窍其实就是老李上一篇提到的gray code的第二个性质:gray code每一位是有个对称轴的。我们可以这样编码,addr==0的时候gray code不从4’b0000开始,而是从4‘b0001开始,直到4’b1001来wrap around,这样从4’b1001->4’b0001依然只有一个bit翻转。同理,如果是depth=6,那么我们继续往里收缩1位,只利用gray code关于对称轴两侧的部分编码,从4’b0011到4’b1011,我们可以看到,这样的编码依然可以保证相邻两个码之间只会有1位变化。

注意,利用这种编码,FIFO的满判断逻辑就不是简单的高两位取反,低位相同了,比如depth=7, rd_ptr=4’b0001, wr_ptr=4’b1100表示7个entry已经满了,如何得出正确的满判断逻辑就交给大家思考吧,欢迎大家在评论区留言讨论。

下一篇老李会带大家过一下工业界最常用的CDC tool Spyglass CDC的基本介绍,同时会奉上一些工程经验总结,敬请期待。

推荐阅读

常见数电面试题Pulse Synchronizer — CDC的那些事(3)
多bit信号跨时钟域怎么办? — CDC的那些事(4)

更多CDC系列文章请关注数字芯片实验室。

发表评论

邮箱地址不会被公开。 必填项已用*标注