《电子技术应用》
您所在的位置:首页 > 嵌入式技术 > 设计应用 > 一种面向异步FIFO的低开销容错机制研究
一种面向异步FIFO的低开销容错机制研究
2018年电子技术应用第6期
侯翔云,黄乐天
电子科技大学 微电子与固体电子学院,四川 成都610054
摘要: 异步FIFO(First-In-First-Out,先进先出队列)作为数字系统中的一种基本结构,被广泛应用于设计之中。其可靠性影响整个系统能否正常运行。提出一种折叠式的容错方法,用于提高异步FIFO的可靠性。该方法通过控制逻辑绕过故障单元,大大提高异步FIFO能容忍的故障数量。另外,为了减少故障对FIFO深度的影响,在折叠式的方案基础上引入空间冗余技术。实验结果表明,与仅采用空间冗余技术的方案相比,提出的方法可以多容忍12个储存单元故障,而为容错增加的面积开销最多只多了4.19%。
关键词: 异步FIFO 可靠性
中图分类号: TN495
文献标识码: A
DOI:10.16157/j.issn.0258-7998.174781
中文引用格式: 侯翔云,黄乐天. 一种面向异步FIFO的低开销容错机制研究[J].电子技术应用,2018,44(6):23-26.
英文引用格式: Hou Xiangyun,Huang Letian. A low-cost fault-tolerant method for asynchronous FIFO[J]. Application of Electronic Technique,2018,44(6):23-26.
A low-cost fault-tolerant method for asynchronous FIFO
Hou Xiangyun,Huang Letian
School of Microelectronics and Solid State Electronics,University of Electronic Science and Technology of China, Chengdu 610054,China
Abstract: Asynchronous FIFO, a basic structure in digital system, is widely used in digital design. The reliability of asynchronous FIFO can affect the entire system. This paper presents a foldable fault-tolerance approach to improve the reliability of asynchronous FIFO. Asynchronous FIFO can tolerate more failures with this method. In addition, in order to reduce the impact of faults on the depth of the FIFO, spatial redundancy is introduced on the basis of the folding method. Compared with the solution that uses only spatial redundancy, the proposed approach can tolerate 12 more failures, while the area overhead for fault tolerance only increases by 4.19% at most.
Key words : asynchronous FIFO;reliability

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)