文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.174781
中文引用格式: 侯翔云,黃樂天. 一種面向異步FIFO的低開銷容錯機制研究[J].電子技術(shù)應(yīng)用,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)是一種先入先出的數(shù)據(jù)緩沖器[1]。由于可以很好地解決跨時鐘域問題和不同模塊之間的速度匹配問題,而被廣泛應(yīng)用于全局異步局部同步[2](Globally Asynchronous Locally Synchronous,GALS)數(shù)字系統(tǒng)中。在片上網(wǎng)絡(luò)(Network-on-Chip,NoC)[3]等復(fù)雜的通信系統(tǒng)中,通常會使用異步FIFO處理跨時鐘域問題。異步FIFO在這些系統(tǒng)中所占面積比例不低,例如在NI中,異步FIFO的面積超過50%[4]。為提高這類數(shù)字系統(tǒng)的整體容錯能力,對異步FIFO進行容錯設(shè)計是很有必要的。
當(dāng)前面向FIFO的容錯方法主要分為兩類:第一類方法通過優(yōu)化控制邏輯,跳過故障單元進行容錯[5]。但文獻[5]提出的方法由于無法使用格雷碼[1,6]的緣故,不能直接在異步FIFO中使用。第二類方法通過增加硬件冗余,提高單元本身的容錯能力,如文獻[7]增加備用單元用于替代故障單元,文獻[8]采用檢錯糾錯碼等方式。比較兩類方法,第一類通常面積開銷較小,而第二類方法對FIFO性能影響較小。本文提出一種與第一類方法兼容的新方法。該方法可以在降低故障對異步FIFO可靠性影響的同時,只引入少量的面積開銷。
1 折疊式容錯方案
由于格雷碼自身的特點,通常只能支持2n進制計數(shù)器。異步FIFO使用格雷碼計數(shù)器作為不同時鐘域之間的同步指針意味FIFO的深度必須保持為2的冪次方,才能保證格雷碼不出現(xiàn)跳碼和漏碼。本文針對這一問題,通過改進FIFO的控制邏輯進行容錯。這就要使FIFO深度保持為2的冪次方,需要在FIFO出現(xiàn)故障以后只選擇2的冪次方個無故障存儲單元作為工作單元。
為了便于描述,本文首先定義兩個概念:組集和組。組集使用S表示,組使用G表示。在本方案中,組是可可以被操作的最小單位。假設(shè)FIFO的初始深度為2n,那么FIFO可以被平均劃分為2i(i≤n)組,每組擁有2n-i個存儲單元。根據(jù)i的取值,可以將FIFO分為不同的組集,每個組集中有2i個組。下面將組集命名為“Si”,組集中的組命名為“Gik”,其中i代表i的值,k代表某一組在組集中的序號。如圖1所示,一個深度為8的FIFO,根據(jù)i的不同值,被劃分為3個不同的組集:S1、S2、S3。圖中的G11表示這個組屬于組集S1,并且是S1中的第一個組。當(dāng)i=1時,F(xiàn)IFO被分為了21組,每組有23-1個單元。不同組集的組之間有一定的關(guān)系,在組集Si中的組可以由兩個屬于組集Si+1的組組成。如圖1所示,組G11可以由G21和G22組成。在組集和組的概念基礎(chǔ)上,需要再定義一個特殊的備選組集合U。該集合包含所有無故障的組。
初始狀態(tài)時,每個組都將被標記為無故障,因此備選組集合U包含所有的組。發(fā)現(xiàn)故障單元以后,包含該單元的所有組都將被標記為故障,并從集合U中移除。此時為了保障FIFO能正常工作,需要從集合U中選擇出可以繼續(xù)工作的組。組之間的優(yōu)先級遵循兩條規(guī)則,第一,組集Si中的組優(yōu)先級高于組集Si+1中的組,這是因為Si中的組包含的單元數(shù)大于Si+1中的組。第二,同一組集中,序號越小的組優(yōu)先級越高。根據(jù)這兩個原則必然可以得到一個優(yōu)先級最高的組。圖2展示了發(fā)生故障以后FIFO的處理方式,其中粗框表示在實際工作中FIFO將會用到的單元。圖2(a)中,第3個單元發(fā)生了故障,此時將包含此單元的組G11、G22、G33從集合U中排除。根據(jù)優(yōu)先級原則,在集合U中剩余的組里面G12的優(yōu)先級最高,因此,組G12中的單元被選中,F(xiàn)IFO的深度將會變成4。在圖2(b)中,除了第3個單元,第7個單元也出現(xiàn)了故障。G12、G24、G37被標記為故障,從集合U中移除。此時,優(yōu)先級最高的組是G21,因此G21包含的單元被選中,F(xiàn)IFO的深度變?yōu)?。圖2(c)和圖2(d)包含更多的例子展示容錯機制,在此不再贅述。
此時FIFO的容錯能力達到最大。將這個容錯方法被命名為Fold-i,其中i為imax的值。
2 備用單元的引入方法及分析
雖然Fold-i方法容錯能力很強,但是其對FIFO深度影響很大。根據(jù)Fold-i方法,當(dāng)一個深度為16的FIFO出現(xiàn)一個故障存儲單元,整個FIFO的深度將會變?yōu)?。這會嚴重影響FIFO的性能。因此,在Fold-i方法的基礎(chǔ)上引入備用單元,在提高FIFO容錯能力的同時適當(dāng)減少故障對FIFO深度的影響。
2.1 故障單元替代方法
引入備用單元的核心是明確替代故障單元的方法。理想的情況是備用單元可以任意替代故障單元,但這會使控制邏輯變得非常復(fù)雜。為了簡化控制邏輯,可將備用單元的替代方法簡化為兩條原則:首先,根據(jù)數(shù)量將備用單元與組集進行綁定,使得組集中每組擁有一個備用單元;其次,在檢測到故障單元以后,只用與該組對應(yīng)的備用單元進行替換。圖3展示了在深度為16的FIFO中添加4個備用單元的方法。由于備用單元的數(shù)量與組集S2中組的數(shù)量一致,因此將備用單元與組集S2綁定。此時組集S2中的每一組擁都有一個備用單元。在圖3中,發(fā)現(xiàn)組G21中有一個故障單元,根據(jù)替代規(guī)則,只能使用備用G21單元(圖3中粗框)進行替換,而其余的備用單元不能用于替代組G21中的故障。
2.2 備用單元引入數(shù)量分析
備用單元的數(shù)量對FIFO在故障時的深度有很大影響。如果備用單元太少,那么FIFO在故障數(shù)量較少時會浪費大量存儲單元。如果備用單元過多,雖然可以保證FIFO深度,但是備用單元本身會引入大量的面積而造成資源的浪費。
為了確定合理的備份方式,可通過實驗確定備用單元的數(shù)量。實驗對象為一個深度為16,每個存儲單元位寬為32的FIFO。該FIFO采用Fold-3容錯機制,并在此基礎(chǔ)上分別引入0、2、4、8個備用單元。比較在4種不同備用單元數(shù)量下,F(xiàn)IFO的面積及在發(fā)生故障后FIFO的深度。表1展示了4種不同數(shù)量的面積大小,可以看到在備用單元數(shù)量為2和4時面積分別增加12%和23%,而在備用單元數(shù)量為8時,面積增加了59%,這顯然是無法承受的。圖4展示了不同備用單元數(shù)量下,故障對FIFO深度的影響。圖中的縱坐標是平均FIFO深度,橫坐標是故障數(shù)量。故障的數(shù)量和位置都可能影響FIFO實際使用時的深度。令故障的數(shù)量一定,隨機化故障的發(fā)生位置可以得到不同的FIFO深度。多次實驗后得到FIFO深度的平均值即為平均FIFO深度,它可以反映在故障數(shù)量一定時FIFO深度的期望值,從而反映出故障對FIFO深度的影響大小??梢钥吹剑S著備用單元數(shù)量的增加,F(xiàn)IFO的平均深度下降速度變慢。這說明備用單元的引入有效降低了故障數(shù)量對FIFO深度的影響。為了評估3種備份方案的優(yōu)劣,定義面積有效值作為衡量標準。面積有效值以0個備用單元的數(shù)據(jù)為基準,將增加的FIFO深度除以增加的面積。令R表示單位深度面積,A0和D0分別表示0個備用單元時的面積和平均FIFO深度。A和D表示待評估方案的面積和平均FIFO深度。該參數(shù)計算公式如下:
利用式(3)可以計算出故障發(fā)生后,3種不同策略增加單位面積可以提高的FIFO深度大小。該值越大,說明單位面積提高的FIFO深度越多,即額外增加的面積更有效率。圖5展示了3種策略在故障數(shù)量較小時的面積有效值。根據(jù)圖5所示,添加4個備用單元優(yōu)于添加2個和8個備份單元的情況。因此,本文選擇引入4個備用單元,在面積引入較小的情況下,保持較大的平均FIFO深度。
通過上述方法引入備用單元后,在故障數(shù)量較小的情況下,F(xiàn)IFO的深度并不會受到太大的影響,在避免了Fold-i方法缺點的同時FIFO的容錯能力也會進一步提高。
3 實驗驗證與分析
本節(jié)中將對3種不同的容錯策略進行對比分析。第一個容錯策略是通過增加部分備用單元進行容錯,將其命名為SS[7]。第二種是本文提到的,在Fold-2方法的基礎(chǔ)上引入備用單元,命名為SF2;第三種與第二種類似,在Fold-3方法基礎(chǔ)上引入備用單元,命名為SF3。這里將對比這3種策略的3項指標:容錯能力、平均FIFO深度以及總面積。實驗對象是一個深度為16的FIFO,增加4個備用單元,每個存儲單元擁有32 bits。
為了容錯能力,需要先分別對3種策略進行軟件建模。然后,在不同位置引入一定數(shù)量的故障,根據(jù)FIFO在該故障數(shù)量下的存活率判斷FIFO是否成功容錯。每個故障數(shù)量將進行10 000次實驗,最后統(tǒng)計FIFO的幸存率,以此衡量FIFO的容錯能力。如圖6所示,SS在故障數(shù)量超過1個以后,F(xiàn)IFO的幸存率已經(jīng)不能保證100%。隨著故障數(shù)量的增加,幸存率急劇下降。當(dāng)故障數(shù)量超過4個以后,使用SS策略的FIFO必然失效。而在SS基礎(chǔ)上引入Fold-2方法以后,可以看到FIFO的容錯能力得到了很大的提升,在故障數(shù)量不超過7個的時候可以保證FIFO無故障工作。在故障數(shù)量超過7個以后,使用SF2策略的FIFO幸存率逐漸降低。當(dāng)故障數(shù)量到達16個以上時,F(xiàn)IFO必然失效。在SS基礎(chǔ)上引入Fold-3方法以后,其容錯能力進一步提高,在故障數(shù)量不超過11個的情況下FIFO的存活率也可以保持在100%。當(dāng)超過11個故障以后,F(xiàn)IFO幸存率下降。直到故障數(shù)量達到19個時,F(xiàn)IFO的幸存率才降到0??梢钥吹?,F(xiàn)old-i技術(shù)可以大幅提高FIFO的容錯能力,并且隨著i值的增大,其容錯能力增強。
為衡量故障數(shù)量對FIFO平均深度的影響,同樣將進行10 000次實驗,統(tǒng)計不同故障情況下采用3種策略的FIFO可用的平均深度。如圖7所示,3種容錯方案均可以保證在故障數(shù)量只有1個時,F(xiàn)IFO的平均深度不受故障的影響。在使用SS方法進行容錯的情況下,其FIFO的平均深度隨故障數(shù)量下降很快,并且在超過4個故障以后,平均深度變?yōu)?,這是由于SS最多能容忍4個故障。對于引入SF2和SF3的情況,可以看到這兩種方法其平均FIFO深度都比SS大,當(dāng)故障數(shù)量在4個以內(nèi)時,兩者均可以保證FIFO的平均深度是無故障情況下的50%以上,相對于SF2,SF3的平均深度更大。
用verilog實現(xiàn)3種策略,用synopsys design compiler對代碼進行綜合得到面積數(shù)據(jù)。表2展示了3種策略的面積對比情況。SS方法的面積最小,有7 610 μm2,SF2和SF3方法的面積分別為7 718 μm2和7 929 μm2。相較于SS方法,SF2面積增加了1.42%,SF3面積增加了4.19%。兩者面積的增幅不大,但可以明顯提升FIFO容錯能力同時減小故障對性能的影響,是對SS技術(shù)的有效改進。
4 結(jié)論
本文提出了一種新的容錯方案用于提高NI中FIFO的容錯能力。該方案主要思想是結(jié)合Fold-i和少量備用單元實現(xiàn)較強的容錯能力,同時降低故障對FIFO深度的影響。實驗結(jié)果表明,對于擁有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,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.
作者信息:
侯翔云,黃樂天
(電子科技大學(xué) 微電子與固體電子學(xué)院,四川 成都610054)