文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2017.03.008
中文引用格式： 杭彥希，徐金甫，陳松濤，等. 面向片上網(wǎng)絡(luò)路由器FIFO故障的實時容錯設(shè)計[J].電子技術(shù)應(yīng)用，2017，43(3)：36-39.
英文引用格式： Hang Yanxi，Xu Jinfu，Chen Songtao，et al. Design of fault-tolerant router for online FIFO fault detection on network-on-chip[J].Application of Electronic Technique，2017，43(3)：36-39.
0 引言
目前對路由器故障的檢測與容忍研究是片上網(wǎng)絡(luò)相關(guān)研究的一個重要方面。其解決辦法主要有以下兩類：(1)通過容錯路由算法繞開故障節(jié)點，如文獻[1]和文獻[2]。但是這些方法容錯粒度較大，一旦發(fā)現(xiàn)故障節(jié)點就選擇繞開或者丟棄，極大地浪費了片上緩存等資源；(2)通過修改路由器微結(jié)構(gòu)進行容錯，如文獻[3]和文獻[5]，但是根據(jù)文獻[4]，在FIFO深度為32的路由器中，F(xiàn)IFO占用了94%以上的面積，發(fā)生故障的概率也最大，文獻[3]未對FIFO提出容錯方案，這顯然對于設(shè)計容錯路由器是不夠的。文獻[5]的檢錯粒度大，且其采用的故障通道隔離技術(shù)浪費了片上一些仍然可用的資源。文獻[4]提出了一種可靠的容錯路由器架構(gòu)Vicis，但是文中提出的故障診斷是線下的，降低了路由器的工作效率。文獻[6]提出了一種在線的FIFO硬故障檢查方法，能夠在線對FIFO故障進行檢測，但是故障覆蓋率不高，也未對最關(guān)鍵的FIFO控制部分進行故障檢測，而且在對故障檢測后也未提出合適的容錯方案。
綜合以上研究，本文針對于片上網(wǎng)絡(luò)FIFO提出了一種故障實時容忍設(shè)計方案，首先針對于片上網(wǎng)絡(luò)FIFO中易發(fā)生的故障建立故障模型；然后提出一種針對于片上網(wǎng)絡(luò)路由器FIFO的實時故障檢測算法，最后提出了有效的容錯機制容忍FIFO故障。
1 FIFO功能模型及故障模型
本文選用的路由器是基本的蟲孔路由器，采用蟲孔交換機制，輸入通道中利用FIFO作為數(shù)據(jù)包緩存。
1.1 FIFO功能模型
本文討論的是異步雙端口RAM型FIFO，其功能模型如圖1所示。
FIFO相關(guān)控制信號作用如下：
FF：FIFO滿信號，為1表示滿，為0表示不滿；
EF：FIFO空信號，為1表示空，為0表示不空；
RS：復(fù)位信號，將讀寫地址恢復(fù)到初始地址（Initial Address,IA），即（RAR）:=IA||（WAR）:=IA||FF:=0||EF:=1，||代表操作同時獨立發(fā)生；
WE：寫使能，WE=1時允許寫操作；
RE：讀使能，RE=1時允許讀操作；
WClk：寫時鐘；
RClk：讀時鐘。
1.2 FIFO故障模型
本文結(jié)合RAM型FIFO中尋址故障和功能故障發(fā)生相似性，將片上網(wǎng)絡(luò)FIFO故障分為存儲單元陣列故障和FIFO控制邏輯故障兩大類。存儲單元陣列故障模型包括：固定型故障(Stuck-At Fault，SAF)、開路故障(Stuck-Open Fault，SOF)、地址譯碼器故障(Address Decoder Fault，ADF)、跳變故障(Transition Fault，TF)、耦合故障（Coupling Fault，CF)(包括倒置耦合故障CFin，固化耦合故障CFid，狀態(tài)耦合故障CFst)、數(shù)據(jù)延時故障(Data Retention Fault，DRF)和多端口故障(Multi-Port Fault，MPF)。FIFO控制邏輯故障模型主要有以下5種：
FF=0,while(WAR)=(RAR) and (LO)=WO；
FF=1,while(WAR)≠(RAR) or (LO)≠WO；
EF=0,while(WAR=RAR) and (LO=RO)；
EF=1,while(WAR)≠(RAR) or (LO)≠RO；
RS:(WAR)≠IA or (RAR)≠IA or (LO)≠RO。
2 容錯設(shè)計
2.1 實時故障檢測算法描述
i=test_address；//FIFO地址指針
j=0；//j代表單地址測試周期
while(j≤2) do
if(j == 1||j == 2)
delay；//發(fā)現(xiàn)DRF故障
temp1=read(i)；
if(j == 0)
if(0 < i < n-1) check(FF == 0&EF == 0);
if(i = n-1) check(FF == 0&EF == 1);
original = temp1;
write(i,!temp1) & temp2 = read(i);
result = compare(temp1,temp2);
else if(j == 1)
result = compare(temp1,original);
write(i,!temp1) & temp2 = read(i);
result = compare(temp1,temp2);
if(0 < i < n-1) check(FF == 0&EF == 0);
if(i = n-1) check(FF == 1&EF == 0);
else
result = compare(temp1,original);
end if
j = j+1;
endwhile
算法中i代表FIFO的測試地址，每次測試分為3個階段，由j來控制，當j為0時執(zhí)行算法的第一個階段，讀出測試地址test_address的值，保存在一個臨時寄存器temp1中，并通過判斷是否是FIFO最后一個地址來檢查空標志EF的狀態(tài)，隨后將temp1的值保存在一個寄存器original中，然后對temp1取反，將取反值寫到測試地址上，與此同時，讀出測試地址上的值與temp1做比較；當j為1時，進入第二個測試階段，先經(jīng)過一段時間的延遲，然后讀出測試地址上的值存在temp1中，與original值作比較，并將temp1值取反寫回到測試地址上，與此同時，讀出測試地址上的值，與temp1值作比較，并通過判斷是否是FIFO最后一個地址來檢查滿標志FF的狀態(tài)；當j為2時，同樣經(jīng)過一段延時，然后讀出測試地址上的值，最后一個階段的讀操作保證了對前兩個階段未發(fā)現(xiàn)的故障再次進行檢測，有效增強了故障檢測能力。
2.2 故障覆蓋率分析
針對前文描述的不同故障類型，本文對提出的測試算法能達到的故障覆蓋率分析如下。
耦合故障(CF)： 算法對FIFO每個地址的值都采取了翻轉(zhuǎn)和讀寫交替操作，但是地址只遞增遍歷一次，對于侵略單元地址大于受害單元地址的故障不能檢出，因此只能覆蓋50%的耦合故障。
數(shù)據(jù)延時故障(DRF)：算法描述中的Del代表了一定的延時操作，可覆蓋DRF。
控制邏輯故障：可對空滿信號FF/EF故障進行檢測，但是因為算法強調(diào)實時性和無損性，所以對復(fù)位信號RS故障無法檢測。
2.3 FIFO重定向機制
本文引入FIFO讀寫指針重定向表（Redirection Table），提出一種FIFO故障檢測與重定向機制。讀寫地址生成器生成的讀寫指針輸入到重定向表中，產(chǎn)生輸入到FIFO緩存的讀寫指針，其原理圖如圖3所示，深色方塊代表故障槽。在未檢測到故障時，重定向表與FIFO中地址一一順序?qū)?yīng)；當檢測到故障后，測試電路產(chǎn)生地址更新信號address_update對重定向表進行更新，有效避開了故障并充分節(jié)省了片上資源。
3 功能比較及實驗結(jié)果
3.1 功能比較
本文提出的路由器FIFO檢錯容錯方法與文獻[4]、文獻[6]提出的方法在故障覆蓋率、測試在線性和是否有容錯機制分析比較如表1所示?？梢园l(fā)現(xiàn)本文方案故障覆蓋率較高，具有實時測試性，且包含容錯機制。
3.2 仿真實驗
本文采用修改的開源片上網(wǎng)絡(luò)仿真器作為仿真實驗平臺，使用systemC作為硬件描述語言，搭建的拓撲結(jié)構(gòu)為4×4的mesh結(jié)構(gòu)，F(xiàn)IFO深度為6個微片，路由算法采用XY維序路由方式。根據(jù)提出的算法設(shè)計相應(yīng)的FIFO故障測試電路，并通過設(shè)置故障測試電路不同的時鐘周期觀察網(wǎng)絡(luò)的延時和吞吐率。
圖4所示的是在不同的測試周期下網(wǎng)絡(luò)的吞吐率變化圖。隨著測試周期的不斷增加，吞吐率增長越來越緩慢，逐漸接近一個固定值，這是因為當測試周期增加，對FIFO測試的頻率減少，測試過程對片上網(wǎng)絡(luò)正常工作模式的影響越來越小。
圖5所示為不同測試周期下的網(wǎng)絡(luò)延時變化圖，隨著測試周期的不斷增加，平均網(wǎng)絡(luò)延時逐漸接近一個固定值。
為測試本文容錯機制對故障容忍的效果，在FIFO注入相同故障的情況下，比較基準蟲孔路由器和本文提出的路由器在不同數(shù)據(jù)包注入率下的吞吐率和延時。圖6所示為吞吐率對比圖，隨著注入率增大，采用基準路由器和本文路由器的網(wǎng)絡(luò)的吞吐率都逐漸接近飽和值，但是因為本文路由器采取了容錯措施，吞吐率改善約為17.89%。
圖7所示為延時對比圖，可以看出本文的路由器隨數(shù)據(jù)包注入率增加，延時均小于基準路由器，這是因為基準路由器未設(shè)計合適的容錯機制，隨注入率增加，基準路由器的堵塞和丟包現(xiàn)象越來越嚴重。與基準蟲孔路由器相比，本文路由器延時改善約25.67%。
4 結(jié)論
本文根據(jù)FIFO讀寫特性，提出了一種可對片上網(wǎng)絡(luò)路由器FIFO故障實時檢測并對故障容忍的方法。實驗結(jié)果表明，在故障條件下，能有效提高片上網(wǎng)絡(luò)吞吐率，并且降低了網(wǎng)絡(luò)延時。
參考文獻
[1] 姚磊，蔡覺平，李贊，等.基于內(nèi)建自測技術(shù)的Mesh結(jié)構(gòu)NoC無虛通道容錯路由算法[J].電子學報，2012，40(5)：983-989.
[2] Liu Junxiu，Jim Harkin，Li Yuhua，et al.Fault-tolerant networks-on-chip routing with coarse and fine-grained look-ahead[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems，2016，35(2)：260-273.
[3] Pavan Poluri，Ahmed Louri.Shield：a reliable network-on-chip router architecture for chip multiprocessors[J].IEEE Transactions on Parallel and Distributed Systems，2016.
[4] Andrew DeOrio，David Fick，Valeria Bertacco，et al.A reli-able routing architecture and algorithm for NoCs[J].IEEE Transactions on Computer-aided design of Integrated Circuits and Systems.2012，31(5)：726-739.
[5] 歐陽一鳴，陳義軍，梁華國，等.一種故障通道隔離的低開銷容錯路由器設(shè)計[J].電子學報，2014，42(11)：2142-2149.
[6] Bibhas Ghoshal，Kanchan Manna，Santanu Chattopadhyay et al.In-field test for permanent faults in FIFO buffers of NoC routers[J].IEEE Transactions on Very Large Scale Integration Systems.2016，24(1)：393-397.
[7] SEBASTIAN W，JAVIER N，MIKEL L.A survey on design approaches to circumvent permanent faults in networks-on-chip[J].ACM Computing Surveys.2016，48(4)：5920-5936.
作者信息:
杭彥希，徐金甫，陳松濤，郭朋飛
（解放軍信息工程大學，河南 鄭州450001）