设计应用

一种面向异步FIFO的低开销容错机制研究

侯翔云,黄乐天 2018/6/14 11:01:00

0 引言

    异步FIFO(Fist-In-First-Out)是一种先入先出的数据缓冲器[1]。由于可以很好地解决跨时钟域问题和不同模块之间的速度匹配问题,而被广泛应用于全局异步局部同步[2](Globally Asynchronous Locally Synchronous,GALS)数字系统中。在片上网络(Network-on-Chip,NoC)[3]等复杂的通信系统中,通常会使用异步FIFO处理跨时钟域问题。异步FIFO在这些系统中所占面积比例不低,例如在NI中,异步FIFO的面积超过50%[4]。为提高这类数字系统的整体容错能力,对异步FIFO进行容错设计是很有必要的。

    当前面向FIFO的容错方法主要分为两类:第一类方法通过优化控制逻辑,跳过故障单元进行容错[5]。但文献[5]提出的方法由于无法使用格雷码[1,6]的缘故,不能直接在异步FIFO中使用。第二类方法通过增加硬件冗余,提高单元本身的容错能力,如文献[7]增加备用单元用于替代故障单元,文献[8]采用检错纠错码等方式。比较两类方法,第一类通常面积开销较小,而第二类方法对FIFO性能影响较小。本文提出一种与第一类方法兼容的新方法。该方法可以在降低故障对异步FIFO可靠性影响的同时,只引入少量的面积开销。

1 折叠式容错方案

    由于格雷码自身的特点,通常只能支持2n进制计数器。异步FIFO使用格雷码计数器作为不同时钟域之间的同步指针意味FIFO的深度必须保持为2的幂次方,才能保证格雷码不出现跳码和漏码。本文针对这一问题,通过改进FIFO的控制逻辑进行容错。这就要使FIFO深度保持为2的幂次方,需要在FIFO出现故障以后只选择2的幂次方个无故障存储单元作为工作单元。

    为了便于描述,本文首先定义两个概念:组集和组。组集使用S表示,组使用G表示。在本方案中,组是可可以被操作的最小单位。假设FIFO的初始深度为2n,那么FIFO可以被平均划分为2i(i≤n)组,每组拥有2n-i个存储单元。根据i的取值,可以将FIFO分为不同的组集,每个组集中有2i个组。下面将组集命名为“Si”,组集中的组命名为“Gik”,其中i代表i的值,k代表某一组在组集中的序号。如图1所示,一个深度为8的FIFO,根据i的不同值,被划分为3个不同的组集:S1、S2、S3。图中的G11表示这个组属于组集S1,并且是S1中的第一个组。当i=1时,FIFO被分为了21组,每组有23-1个单元。不同组集的组之间有一定的关系,在组集Si中的组可以由两个属于组集Si+1的组组成。如图1所示,组G11可以由G21和G22组成。在组集和组的概念基础上,需要再定义一个特殊的备选组集合U。该集合包含所有无故障的组。

wdz5-t1.gif

    初始状态时,每个组都将被标记为无故障,因此备选组集合U包含所有的组。发现故障单元以后,包含该单元的所有组都将被标记为故障,并从集合U中移除。此时为了保障FIFO能正常工作,需要从集合U中选择出可以继续工作的组。组之间的优先级遵循两条规则,第一,组集Si中的组优先级高于组集Si+1中的组,这是因为Si中的组包含的单元数大于Si+1中的组。第二,同一组集中,序号越小的组优先级越高。根据这两个原则必然可以得到一个优先级最高的组。图2展示了发生故障以后FIFO的处理方式,其中粗框表示在实际工作中FIFO将会用到的单元。图2(a)中,第3个单元发生了故障,此时将包含此单元的组G11、G22、G33从集合U中排除。根据优先级原则,在集合U中剩余的组里面G12的优先级最高,因此,组G12中的单元被选中,FIFO的深度将会变成4。在图2(b)中,除了第3个单元,第7个单元也出现了故障。G12、G24、G37被标记为故障,从集合U中移除。此时,优先级最高的组是G21,因此G21包含的单元被选中,FIFO的深度变为2。图2(c)和图2(d)包含更多的例子展示容错机制,在此不再赘述。

wdz5-t2.gif

wdz5-gs1-2.gif

    此时FIFO的容错能力达到最大。将这个容错方法被命名为Fold-i,其中i为imax的值。

2 备用单元的引入方法及分析

    虽然Fold-i方法容错能力很强,但是其对FIFO深度影响很大。根据Fold-i方法,当一个深度为16的FIFO出现一个故障存储单元,整个FIFO的深度将会变为8。这会严重影响FIFO的性能。因此,在Fold-i方法的基础上引入备用单元,在提高FIFO容错能力的同时适当减少故障对FIFO深度的影响。

2.1 故障单元替代方法

    引入备用单元的核心是明确替代故障单元的方法。理想的情况是备用单元可以任意替代故障单元,但这会使控制逻辑变得非常复杂。为了简化控制逻辑,可将备用单元的替代方法简化为两条原则:首先,根据数量将备用单元与组集进行绑定,使得组集中每组拥有一个备用单元;其次,在检测到故障单元以后,只用与该组对应的备用单元进行替换。图3展示了在深度为16的FIFO中添加4个备用单元的方法。由于备用单元的数量与组集S2中组的数量一致,因此将备用单元与组集S2绑定。此时组集S2中的每一组拥都有一个备用单元。在图3中,发现组G21中有一个故障单元,根据替代规则,只能使用备用G21单元(图3中粗框)进行替换,而其余的备用单元不能用于替代组G21中的故障。

wdz5-t3.gif

2.2 备用单元引入数量分析

    备用单元的数量对FIFO在故障时的深度有很大影响。如果备用单元太少,那么FIFO在故障数量较少时会浪费大量存储单元。如果备用单元过多,虽然可以保证FIFO深度,但是备用单元本身会引入大量的面积而造成资源的浪费。

    为了确定合理的备份方式,可通过实验确定备用单元的数量。实验对象为一个深度为16,每个存储单元位宽为32的FIFO。该FIFO采用Fold-3容错机制,并在此基础上分别引入0、2、4、8个备用单元。比较在4种不同备用单元数量下,FIFO的面积及在发生故障后FIFO的深度。表1展示了4种不同数量的面积大小,可以看到在备用单元数量为2和4时面积分别增加12%和23%,而在备用单元数量为8时,面积增加了59%,这显然是无法承受的。图4展示了不同备用单元数量下,故障对FIFO深度的影响。图中的纵坐标是平均FIFO深度,横坐标是故障数量。故障的数量和位置都可能影响FIFO实际使用时的深度。令故障的数量一定,随机化故障的发生位置可以得到不同的FIFO深度。多次实验后得到FIFO深度的平均值即为平均FIFO深度,它可以反映在故障数量一定时FIFO深度的期望值,从而反映出故障对FIFO深度的影响大小。可以看到,随着备用单元数量的增加,FIFO的平均深度下降速度变慢。这说明备用单元的引入有效降低了故障数量对FIFO深度的影响。为了评估3种备份方案的优劣,定义面积有效值作为衡量标准。面积有效值以0个备用单元的数据为基准,将增加的FIFO深度除以增加的面积。令R表示单位深度面积,A0和D0分别表示0个备用单元时的面积和平均FIFO深度。A和D表示待评估方案的面积和平均FIFO深度。该参数计算公式如下:

    wdz5-gs3.gif

wdz5-b1.gif

wdz5-t4.gif

    利用式(3)可以计算出故障发生后,3种不同策略增加单位面积可以提高的FIFO深度大小。该值越大,说明单位面积提高的FIFO深度越多,即额外增加的面积更有效率。图5展示了3种策略在故障数量较小时的面积有效值。根据图5所示,添加4个备用单元优于添加2个和8个备份单元的情况。因此,本文选择引入4个备用单元,在面积引入较小的情况下,保持较大的平均FIFO深度。

wdz5-t5.gif

    通过上述方法引入备用单元后,在故障数量较小的情况下,FIFO的深度并不会受到太大的影响,在避免了Fold-i方法缺点的同时FIFO的容错能力也会进一步提高。

3 实验验证与分析

    本节中将对3种不同的容错策略进行对比分析。第一个容错策略是通过增加部分备用单元进行容错,将其命名为SS[7]。第二种是本文提到的,在Fold-2方法的基础上引入备用单元,命名为SF2;第三种与第二种类似,在Fold-3方法基础上引入备用单元,命名为SF3。这里将对比这3种策略的3项指标:容错能力、平均FIFO深度以及总面积。实验对象是一个深度为16的FIFO,增加4个备用单元,每个存储单元拥有32 bits。

    为了容错能力,需要先分别对3种策略进行软件建模。然后,在不同位置引入一定数量的故障,根据FIFO在该故障数量下的存活率判断FIFO是否成功容错。每个故障数量将进行10 000次实验,最后统计FIFO的幸存率,以此衡量FIFO的容错能力。如图6所示,SS在故障数量超过1个以后,FIFO的幸存率已经不能保证100%。随着故障数量的增加,幸存率急剧下降。当故障数量超过4个以后,使用SS策略的FIFO必然失效。而在SS基础上引入Fold-2方法以后,可以看到FIFO的容错能力得到了很大的提升,在故障数量不超过7个的时候可以保证FIFO无故障工作。在故障数量超过7个以后,使用SF2策略的FIFO幸存率逐渐降低。当故障数量到达16个以上时,FIFO必然失效。在SS基础上引入Fold-3方法以后,其容错能力进一步提高,在故障数量不超过11个的情况下FIFO的存活率也可以保持在100%。当超过11个故障以后,FIFO幸存率下降。直到故障数量达到19个时,FIFO的幸存率才降到0。可以看到,Fold-i技术可以大幅提高FIFO的容错能力,并且随着i值的增大,其容错能力增强。

wdz5-t6.gif

    为衡量故障数量对FIFO平均深度的影响,同样将进行10 000次实验,统计不同故障情况下采用3种策略的FIFO可用的平均深度。如图7所示,3种容错方案均可以保证在故障数量只有1个时,FIFO的平均深度不受故障的影响。在使用SS方法进行容错的情况下,其FIFO的平均深度随故障数量下降很快,并且在超过4个故障以后,平均深度变为0,这是由于SS最多能容忍4个故障。对于引入SF2和SF3的情况,可以看到这两种方法其平均FIFO深度都比SS大,当故障数量在4个以内时,两者均可以保证FIFO的平均深度是无故障情况下的50%以上,相对于SF2,SF3的平均深度更大。

wdz5-t7.gif

    用verilog实现3种策略,用synopsys design compiler对代码进行综合得到面积数据。表2展示了3种策略的面积对比情况。SS方法的面积最小,有7 610 μm2,SF2和SF3方法的面积分别为7 718 μm2和7 929 μm2。相较于SS方法,SF2面积增加了1.42%,SF3面积增加了4.19%。两者面积的增幅不大,但可以明显提升FIFO容错能力同时减小故障对性能的影响,是对SS技术的有效改进。 

wdz5-b2.gif

4 结论

    本文提出了一种新的容错方案用于提高NI中FIFO的容错能力。该方案主要思想是结合Fold-i和少量备用单元实现较强的容错能力,同时降低故障对FIFO深度的影响。实验结果表明,对于拥有4个备用单元,深度为16,每个存储单元拥有32 bits的FIFO。相对于只引入备用单元的方法最多只增加了4.19%的面积,同时大幅提高了异步FIFO的容错能力。

参考文献

[1] CUMMINGS C.Simulation and synthesis techniques for asynchronous FIFO design[C].Synopsys Users Group,San Jose,CA,2002.

[2] MUTTERSBACH J,VILLIGER T,KAESLIN H,et al.Glob-ally-asynchronous locally-synchronous architectures to simplify the design of on-chip systems[C].12th Annu.IEEE Int.ASIC/SOC Conf.,1999:317-321.

[3] BENINI L,MICHELI G D.Networks on chips: a new SoC paradigm[J].2002,35(1):70-78.

[4] SAPONARA S,BACCHILLONE T,PETRI E,et al.Design of an NoC interface macrocell with hardware support of advanced networking functionalities[J].IEEE Transactions on Computers,2014,6(3):609-621.

[5] DEORIO A,FICK D,BERTACCO V,et al.A reliable routing architecture and algorithm for NoCs[J].IEEE Trans.Computer-Aided Design of Integrated Circuits and Systems,2012,31(5):726-739.

[6] APPERSON R W,YU I,MEEUWSEN M J,et al.A scalable dual-clock FIFO for data transfers between arbitrary and haltable clock domains[J].IEEE Trans. on Very Large Scale Integration(VLSI) Systems,2007,15(10):1125-1134.

[7] FIORIN L,SAMI M.Fault-tolerant network interfaces for networks-on-chip[J].IEEE Trans. on Dependable and Secure Computing,2014,11(1):16-29.

[8] MURALI S,THEOCHARIDES T,VIJAYKRISHNAN N,et al.Analysis of error recovery schemes for networks on chips[J].In IEEE Design & Test of Computers,2005,22(5):434-442.



作者信息:

侯翔云,黄乐天

(电子科技大学 微电子与固体电子学院,四川 成都610054)

异步FIFO 可靠性