文獻標(biāo)識碼： 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來控制,，當(dāng)j為0時執(zhí)行算法的第一個階段,，讀出測試地址test_address的值，保存在一個臨時寄存器temp1中,，并通過判斷是否是FIFO最后一個地址來檢查空標(biāo)志EF的狀態(tài),，隨后將temp1的值保存在一個寄存器original中,，然后對temp1取反，將取反值寫到測試地址上,，與此同時,，讀出測試地址上的值與temp1做比較；當(dāng)j為1時,，進入第二個測試階段,，先經(jīng)過一段時間的延遲，然后讀出測試地址上的值存在temp1中,，與original值作比較,，并將temp1值取反寫回到測試地址上，與此同時,，讀出測試地址上的值,，與temp1值作比較，并通過判斷是否是FIFO最后一個地址來檢查滿標(biāo)志FF的狀態(tài),；當(dāng)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),；當(dāng)檢測到故障后,，測試電路產(chǎn)生地址更新信號address_update對重定向表進行更新，有效避開了故障并充分節(jié)省了片上資源,。
3 功能比較及實驗結(jié)果
3.1 功能比較
本文提出的路由器FIFO檢錯容錯方法與文獻[4],、文獻[6]提出的方法在故障覆蓋率、測試在線性和是否有容錯機制分析比較如表1所示,?？梢园l(fā)現(xiàn)本文方案故障覆蓋率較高，具有實時測試性,，且包含容錯機制,。
3.2 仿真實驗
本文采用修改的開源片上網(wǎng)絡(luò)仿真器作為仿真實驗平臺，使用systemC作為硬件描述語言,，搭建的拓?fù)浣Y(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ò)的吞吐率變化圖,。隨著測試周期的不斷增加,，吞吐率增長越來越緩慢，逐漸接近一個固定值,，這是因為當(dāng)測試周期增加,，對FIFO測試的頻率減少，測試過程對片上網(wǎng)絡(luò)正常工作模式的影響越來越小,。
圖5所示為不同測試周期下的網(wǎng)絡(luò)延時變化圖,，隨著測試周期的不斷增加，平均網(wǎng)絡(luò)延時逐漸接近一個固定值,。
為測試本文容錯機制對故障容忍的效果,，在FIFO注入相同故障的情況下，比較基準(zhǔn)蟲孔路由器和本文提出的路由器在不同數(shù)據(jù)包注入率下的吞吐率和延時,。圖6所示為吞吐率對比圖,，隨著注入率增大，采用基準(zhǔn)路由器和本文路由器的網(wǎng)絡(luò)的吞吐率都逐漸接近飽和值,，但是因為本文路由器采取了容錯措施,，吞吐率改善約為17.89%。
圖7所示為延時對比圖,，可以看出本文的路由器隨數(shù)據(jù)包注入率增加,，延時均小于基準(zhǔn)路由器，這是因為基準(zhǔn)路由器未設(shè)計合適的容錯機制，隨注入率增加,，基準(zhǔn)路由器的堵塞和丟包現(xiàn)象越來越嚴(yán)重,。與基準(zhǔ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].電子學(xué)報,，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].電子學(xué)報，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.
作者信息:
杭彥希,，徐金甫，陳松濤，郭朋飛
（解放軍信息工程大學(xué),，河南 鄭州450001）