0 引言

    異步FIFO（Fist-In-First-Out）是一種先入先出的數(shù)據(jù)緩沖器^[1],。由于可以很好地解決跨時(shí)鐘域問(wèn)題和不同模塊之間的速度匹配問(wèn)題，而被廣泛應(yīng)用于全局異步局部同步^[2](Globally Asynchronous Locally Synchronous,，GALS)數(shù)字系統(tǒng)中,。在片上網(wǎng)絡(luò)(Network-on-Chip，NoC)^[3]等復(fù)雜的通信系統(tǒng)中,，通常會(huì)使用異步FIFO處理跨時(shí)鐘域問(wèn)題,。異步FIFO在這些系統(tǒng)中所占面積比例不低，例如在NI中,，異步FIFO的面積超過(guò)50%^[4],。為提高這類數(shù)字系統(tǒng)的整體容錯(cuò)能力，對(duì)異步FIFO進(jìn)行容錯(cuò)設(shè)計(jì)是很有必要的,。

    當(dāng)前面向FIFO的容錯(cuò)方法主要分為兩類：第一類方法通過(guò)優(yōu)化控制邏輯,，跳過(guò)故障單元進(jìn)行容錯(cuò)^[5]。但文獻(xiàn)[5]提出的方法由于無(wú)法使用格雷碼^[1,，6]的緣故,，不能直接在異步FIFO中使用,。第二類方法通過(guò)增加硬件冗余，提高單元本身的容錯(cuò)能力,，如文獻(xiàn)[7]增加備用單元用于替代故障單元,，文獻(xiàn)[8]采用檢錯(cuò)糾錯(cuò)碼等方式。比較兩類方法,，第一類通常面積開(kāi)銷較小,，而第二類方法對(duì)FIFO性能影響較小。本文提出一種與第一類方法兼容的新方法,。該方法可以在降低故障對(duì)異步FIFO可靠性影響的同時(shí),，只引入少量的面積開(kāi)銷。

1 折疊式容錯(cuò)方案

    由于格雷碼自身的特點(diǎn),通常只能支持2n進(jìn)制計(jì)數(shù)器,。異步FIFO使用格雷碼計(jì)數(shù)器作為不同時(shí)鐘域之間的同步指針意味FIFO的深度必須保持為2的冪次方,，才能保證格雷碼不出現(xiàn)跳碼和漏碼。本文針對(duì)這一問(wèn)題,，通過(guò)改進(jìn)FIFO的控制邏輯進(jìn)行容錯(cuò),。這就要使FIFO深度保持為2的冪次方，需要在FIFO出現(xiàn)故障以后只選擇2的冪次方個(gè)無(wú)故障存儲(chǔ)單元作為工作單元,。

    為了便于描述,，本文首先定義兩個(gè)概念：組集和組。組集使用S表示,，組使用G表示,。在本方案中，組是可可以被操作的最小單位,。假設(shè)FIFO的初始深度為2ⁿ,，那么FIFO可以被平均劃分為2ⁱ(i≤n)組，每組擁有2^n-i個(gè)存儲(chǔ)單元,。根據(jù)i的取值,，可以將FIFO分為不同的組集，每個(gè)組集中有2ⁱ個(gè)組,。下面將組集命名為“S_i”,，組集中的組命名為“G_ik”,其中i代表i的值，k代表某一組在組集中的序號(hào),。如圖1所示,，一個(gè)深度為8的FIFO，根據(jù)i的不同值,，被劃分為3個(gè)不同的組集：S₁,、S₂、S₃。圖中的G₁₁表示這個(gè)組屬于組集S₁,，并且是S₁中的第一個(gè)組,。當(dāng)i=1時(shí)，F(xiàn)IFO被分為了2¹組,，每組有2^3-1個(gè)單元,。不同組集的組之間有一定的關(guān)系，在組集S_i中的組可以由兩個(gè)屬于組集S_i+1的組組成,。如圖1所示，組G₁₁可以由G₂₁和G₂₂組成,。在組集和組的概念基礎(chǔ)上,，需要再定義一個(gè)特殊的備選組集合U。該集合包含所有無(wú)故障的組,。

    初始狀態(tài)時(shí),，每個(gè)組都將被標(biāo)記為無(wú)故障，因此備選組集合U包含所有的組,。發(fā)現(xiàn)故障單元以后,，包含該單元的所有組都將被標(biāo)記為故障，并從集合U中移除,。此時(shí)為了保障FIFO能正常工作,，需要從集合U中選擇出可以繼續(xù)工作的組。組之間的優(yōu)先級(jí)遵循兩條規(guī)則,，第一,，組集S_i中的組優(yōu)先級(jí)高于組集S_i+1中的組，這是因?yàn)镾_i中的組包含的單元數(shù)大于S_i+1中的組,。第二,，同一組集中，序號(hào)越小的組優(yōu)先級(jí)越高,。根據(jù)這兩個(gè)原則必然可以得到一個(gè)優(yōu)先級(jí)最高的組,。圖2展示了發(fā)生故障以后FIFO的處理方式，其中粗框表示在實(shí)際工作中FIFO將會(huì)用到的單元,。圖2(a)中,，第3個(gè)單元發(fā)生了故障，此時(shí)將包含此單元的組G₁₁,、G₂₂,、G₃₃從集合U中排除。根據(jù)優(yōu)先級(jí)原則,，在集合U中剩余的組里面G12的優(yōu)先級(jí)最高,，因此，組G₁₂中的單元被選中，F(xiàn)IFO的深度將會(huì)變成4,。在圖2(b)中,，除了第3個(gè)單元，第7個(gè)單元也出現(xiàn)了故障,。G₁₂,、G₂₄、G₃₇被標(biāo)記為故障,，從集合U中移除,。此時(shí)，優(yōu)先級(jí)最高的組是G₂₁,，因此G₂₁包含的單元被選中,，F(xiàn)IFO的深度變?yōu)?。圖2(c)和圖2(d)包含更多的例子展示容錯(cuò)機(jī)制,，在此不再贅述,。

    此時(shí)FIFO的容錯(cuò)能力達(dá)到最大。將這個(gè)容錯(cuò)方法被命名為Fold-i,，其中i為i_max的值,。

2 備用單元的引入方法及分析

    雖然Fold-i方法容錯(cuò)能力很強(qiáng)，但是其對(duì)FIFO深度影響很大,。根據(jù)Fold-i方法,，當(dāng)一個(gè)深度為16的FIFO出現(xiàn)一個(gè)故障存儲(chǔ)單元，整個(gè)FIFO的深度將會(huì)變?yōu)?,。這會(huì)嚴(yán)重影響FIFO的性能,。因此，在Fold-i方法的基礎(chǔ)上引入備用單元,，在提高FIFO容錯(cuò)能力的同時(shí)適當(dāng)減少故障對(duì)FIFO深度的影響,。

2.1 故障單元替代方法

    引入備用單元的核心是明確替代故障單元的方法。理想的情況是備用單元可以任意替代故障單元,，但這會(huì)使控制邏輯變得非常復(fù)雜,。為了簡(jiǎn)化控制邏輯，可將備用單元的替代方法簡(jiǎn)化為兩條原則：首先,，根據(jù)數(shù)量將備用單元與組集進(jìn)行綁定,，使得組集中每組擁有一個(gè)備用單元；其次,，在檢測(cè)到故障單元以后,，只用與該組對(duì)應(yīng)的備用單元進(jìn)行替換。圖3展示了在深度為16的FIFO中添加4個(gè)備用單元的方法,。由于備用單元的數(shù)量與組集S₂中組的數(shù)量一致,，因此將備用單元與組集S₂綁定,。此時(shí)組集S₂中的每一組擁都有一個(gè)備用單元。在圖3中,，發(fā)現(xiàn)組G₂₁中有一個(gè)故障單元,，根據(jù)替代規(guī)則，只能使用備用G₂₁單元(圖3中粗框)進(jìn)行替換,，而其余的備用單元不能用于替代組G₂₁中的故障,。

2.2 備用單元引入數(shù)量分析

    備用單元的數(shù)量對(duì)FIFO在故障時(shí)的深度有很大影響。如果備用單元太少,，那么FIFO在故障數(shù)量較少時(shí)會(huì)浪費(fèi)大量存儲(chǔ)單元,。如果備用單元過(guò)多，雖然可以保證FIFO深度,，但是備用單元本身會(huì)引入大量的面積而造成資源的浪費(fèi),。

    為了確定合理的備份方式，可通過(guò)實(shí)驗(yàn)確定備用單元的數(shù)量,。實(shí)驗(yàn)對(duì)象為一個(gè)深度為16，每個(gè)存儲(chǔ)單元位寬為32的FIFO,。該FIFO采用Fold-3容錯(cuò)機(jī)制,，并在此基礎(chǔ)上分別引入0、2,、4,、8個(gè)備用單元。比較在4種不同備用單元數(shù)量下,，F(xiàn)IFO的面積及在發(fā)生故障后FIFO的深度,。表1展示了4種不同數(shù)量的面積大小，可以看到在備用單元數(shù)量為2和4時(shí)面積分別增加12%和23%,，而在備用單元數(shù)量為8時(shí),，面積增加了59%，這顯然是無(wú)法承受的,。圖4展示了不同備用單元數(shù)量下,，故障對(duì)FIFO深度的影響。圖中的縱坐標(biāo)是平均FIFO深度,，橫坐標(biāo)是故障數(shù)量,。故障的數(shù)量和位置都可能影響FIFO實(shí)際使用時(shí)的深度。令故障的數(shù)量一定,，隨機(jī)化故障的發(fā)生位置可以得到不同的FIFO深度,。多次實(shí)驗(yàn)后得到FIFO深度的平均值即為平均FIFO深度，它可以反映在故障數(shù)量一定時(shí)FIFO深度的期望值,，從而反映出故障對(duì)FIFO深度的影響大小,。可以看到，隨著備用單元數(shù)量的增加,，F(xiàn)IFO的平均深度下降速度變慢,。這說(shuō)明備用單元的引入有效降低了故障數(shù)量對(duì)FIFO深度的影響。為了評(píng)估3種備份方案的優(yōu)劣,，定義面積有效值作為衡量標(biāo)準(zhǔn),。面積有效值以0個(gè)備用單元的數(shù)據(jù)為基準(zhǔn)，將增加的FIFO深度除以增加的面積,。令R表示單位深度面積,，A₀和D₀分別表示0個(gè)備用單元時(shí)的面積和平均FIFO深度。A和D表示待評(píng)估方案的面積和平均FIFO深度,。該參數(shù)計(jì)算公式如下：

    利用式(3)可以計(jì)算出故障發(fā)生后,，3種不同策略增加單位面積可以提高的FIFO深度大小。該值越大,，說(shuō)明單位面積提高的FIFO深度越多,，即額外增加的面積更有效率。圖5展示了3種策略在故障數(shù)量較小時(shí)的面積有效值,。根據(jù)圖5所示,，添加4個(gè)備用單元優(yōu)于添加2個(gè)和8個(gè)備份單元的情況。因此,，本文選擇引入4個(gè)備用單元,，在面積引入較小的情況下，保持較大的平均FIFO深度,。

    通過(guò)上述方法引入備用單元后,，在故障數(shù)量較小的情況下，F(xiàn)IFO的深度并不會(huì)受到太大的影響,，在避免了Fold-i方法缺點(diǎn)的同時(shí)FIFO的容錯(cuò)能力也會(huì)進(jìn)一步提高,。

3 實(shí)驗(yàn)驗(yàn)證與分析

    本節(jié)中將對(duì)3種不同的容錯(cuò)策略進(jìn)行對(duì)比分析。第一個(gè)容錯(cuò)策略是通過(guò)增加部分備用單元進(jìn)行容錯(cuò),，將其命名為SS^[7],。第二種是本文提到的，在Fold-2方法的基礎(chǔ)上引入備用單元,，命名為SF2,；第三種與第二種類似，在Fold-3方法基礎(chǔ)上引入備用單元,命名為SF3,。這里將對(duì)比這3種策略的3項(xiàng)指標(biāo)：容錯(cuò)能力,、平均FIFO深度以及總面積。實(shí)驗(yàn)對(duì)象是一個(gè)深度為16的FIFO,，增加4個(gè)備用單元,，每個(gè)存儲(chǔ)單元擁有32 bits,。

    為了容錯(cuò)能力，需要先分別對(duì)3種策略進(jìn)行軟件建模,。然后,，在不同位置引入一定數(shù)量的故障，根據(jù)FIFO在該故障數(shù)量下的存活率判斷FIFO是否成功容錯(cuò),。每個(gè)故障數(shù)量將進(jìn)行10 000次實(shí)驗(yàn),，最后統(tǒng)計(jì)FIFO的幸存率，以此衡量FIFO的容錯(cuò)能力,。如圖6所示,，SS在故障數(shù)量超過(guò)1個(gè)以后，F(xiàn)IFO的幸存率已經(jīng)不能保證100%,。隨著故障數(shù)量的增加,，幸存率急劇下降。當(dāng)故障數(shù)量超過(guò)4個(gè)以后,，使用SS策略的FIFO必然失效。而在SS基礎(chǔ)上引入Fold-2方法以后,，可以看到FIFO的容錯(cuò)能力得到了很大的提升，在故障數(shù)量不超過(guò)7個(gè)的時(shí)候可以保證FIFO無(wú)故障工作,。在故障數(shù)量超過(guò)7個(gè)以后,，使用SF2策略的FIFO幸存率逐漸降低,。當(dāng)故障數(shù)量到達(dá)16個(gè)以上時(shí)，F(xiàn)IFO必然失效,。在SS基礎(chǔ)上引入Fold-3方法以后,，其容錯(cuò)能力進(jìn)一步提高，在故障數(shù)量不超過(guò)11個(gè)的情況下FIFO的存活率也可以保持在100%,。當(dāng)超過(guò)11個(gè)故障以后,，F(xiàn)IFO幸存率下降,。直到故障數(shù)量達(dá)到19個(gè)時(shí)，F(xiàn)IFO的幸存率才降到0,。可以看到,，F(xiàn)old-i技術(shù)可以大幅提高FIFO的容錯(cuò)能力，并且隨著i值的增大,，其容錯(cuò)能力增強(qiáng),。

    為衡量故障數(shù)量對(duì)FIFO平均深度的影響,，同樣將進(jìn)行10 000次實(shí)驗(yàn),，統(tǒng)計(jì)不同故障情況下采用3種策略的FIFO可用的平均深度,。如圖7所示，3種容錯(cuò)方案均可以保證在故障數(shù)量只有1個(gè)時(shí),，F(xiàn)IFO的平均深度不受故障的影響,。在使用SS方法進(jìn)行容錯(cuò)的情況下，其FIFO的平均深度隨故障數(shù)量下降很快,，并且在超過(guò)4個(gè)故障以后,，平均深度變?yōu)?，這是由于SS最多能容忍4個(gè)故障,。對(duì)于引入SF2和SF3的情況，可以看到這兩種方法其平均FIFO深度都比SS大,，當(dāng)故障數(shù)量在4個(gè)以內(nèi)時(shí)，兩者均可以保證FIFO的平均深度是無(wú)故障情況下的50%以上,，相對(duì)于SF2，SF3的平均深度更大,。

    用verilog實(shí)現(xiàn)3種策略，用synopsys design compiler對(duì)代碼進(jìn)行綜合得到面積數(shù)據(jù),。表2展示了3種策略的面積對(duì)比情況,。SS方法的面積最小,，有7 610 μm²,，SF2和SF3方法的面積分別為7 718 μm²和7 929 μm²。相較于SS方法,，SF2面積增加了1.42%,，SF3面積增加了4.19%,。兩者面積的增幅不大，但可以明顯提升FIFO容錯(cuò)能力同時(shí)減小故障對(duì)性能的影響,，是對(duì)SS技術(shù)的有效改進(jìn),。 

4 結(jié)論

    本文提出了一種新的容錯(cuò)方案用于提高NI中FIFO的容錯(cuò)能力。該方案主要思想是結(jié)合Fold-i和少量備用單元實(shí)現(xiàn)較強(qiáng)的容錯(cuò)能力,，同時(shí)降低故障對(duì)FIFO深度的影響,。實(shí)驗(yàn)結(jié)果表明,，對(duì)于擁有4個(gè)備用單元,，深度為16，每個(gè)存儲(chǔ)單元擁有32 bits的FIFO,。相對(duì)于只引入備用單元的方法最多只增加了4.19%的面積，同時(shí)大幅提高了異步FIFO的容錯(cuò)能力,。

參考文獻(xiàn)

[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,，F(xiàn)ICK 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.

作者信息:

侯翔云,，黃樂(lè)天

（電子科技大學(xué) 微電子與固體電子學(xué)院，四川 成都610054）