【好设计论文】一种面向异步FIFO的低开销容错机制研究

摘要：异步FIFO(First-In-First-Out，先进先出队列)作为数字系统中的一种基本结构，被广泛应用于设计之中。其可靠性影响整个系统能否正常运行。提出一种折叠式的容错方法，用于提高异步FIFO的可靠性。该方法通过控制逻辑绕过故障单元，大大提高异步FIFO能容忍的故障数量。另外，为了减少故障对FIFO深度的影响，在折叠式的方案基础上引入空间冗余技术。实验结果表明，与仅采用空间冗余技术的方案相比，提出的方法可以多容忍12个储存单元故障，而为容错增加的面积开销最多只多了4.19%。

中文引用格式： 侯翔云，黄乐天. 一种面向异步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.

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的初始深度为2ⁿ，那么FIFO可以被平均划分为2ⁱ(i≤n)组，每组拥有2^n-i个存储单元。根据i的取值，可以将FIFO分为不同的组集，每个组集中有2ⁱ个组。下面将组集命名为“S_i”，组集中的组命名为“G_ik”,其中i代表i的值，k代表某一组在组集中的序号。如图1所示，一个深度为8的FIFO，根据i的不同值，被划分为3个不同的组集：S₁、S₂、S₃。图中的G₁₁表示这个组属于组集S₁，并且是S₁中的第一个组。当i=1时，FIFO被分为了2¹组，每组有2^3-1个单元。不同组集的组之间有一定的关系，在组集S_i中的组可以由两个属于组集S_i+1的组组成。如图1所示，组G₁₁可以由G₂₁和G₂₂组成。在组集和组的概念基础上，需要再定义一个特殊的备选组集合U。该集合包含所有无故障的组。

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

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

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

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

2.1 故障单元替代方法

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

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表示单位深度面积，A₀和D₀分别表示0个备用单元时的面积和平均FIFO深度。A和D表示待评估方案的面积和平均FIFO深度。该参数计算公式如下：

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

通过上述方法引入备用单元后，在故障数量较小的情况下，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值的增大，其容错能力增强。

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

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

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）