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）