文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2017.03.008
中文引用格式： 杭彥希，徐金甫，陳松濤，等. 面向片上網絡路由器FIFO故障的實時容錯設計[J].電子技術應用，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 引言
目前對路由器故障的檢測與容忍研究是片上網絡相關研究的一個重要方面。其解決辦法主要有以下兩類：(1)通過容錯路由算法繞開故障節點，如文獻[1]和文獻[2]。但是這些方法容錯粒度較大，一旦發現故障節點就選擇繞開或者丟棄，極大地浪費了片上緩存等資源；(2)通過修改路由器微結構進行容錯，如文獻[3]和文獻[5]，但是根據文獻[4]，在FIFO深度為32的路由器中，FIFO占用了94%以上的面積，發生故障的概率也最大，文獻[3]未對FIFO提出容錯方案，這顯然對于設計容錯路由器是不夠的。文獻[5]的檢錯粒度大，且其采用的故障通道隔離技術浪費了片上一些仍然可用的資源。文獻[4]提出了一種可靠的容錯路由器架構Vicis，但是文中提出的故障診斷是線下的，降低了路由器的工作效率。文獻[6]提出了一種在線的FIFO硬故障檢查方法，能夠在線對FIFO故障進行檢測，但是故障覆蓋率不高，也未對最關鍵的FIFO控制部分進行故障檢測，而且在對故障檢測后也未提出合適的容錯方案。
綜合以上研究，本文針對于片上網絡FIFO提出了一種故障實時容忍設計方案，首先針對于片上網絡FIFO中易發生的故障建立故障模型；然后提出一種針對于片上網絡路由器FIFO的實時故障檢測算法，最后提出了有效的容錯機制容忍FIFO故障。
1 FIFO功能模型及故障模型
本文選用的路由器是基本的蟲孔路由器，采用蟲孔交換機制，輸入通道中利用FIFO作為數據包緩存。
1.1 FIFO功能模型
本文討論的是異步雙端口RAM型FIFO，其功能模型如圖1所示。
FIFO相關控制信號作用如下：
FF：FIFO滿信號，為1表示滿，為0表示不滿；
EF：FIFO空信號，為1表示空，為0表示不空；
RS：復位信號，將讀寫地址恢復到初始地址（Initial Address,IA），即（RAR）:=IA||（WAR）:=IA||FF:=0||EF:=1，||代表操作同時獨立發生；
WE：寫使能，WE=1時允許寫操作；
RE：讀使能，RE=1時允許讀操作；
WClk：寫時鐘；
RClk：讀時鐘。
1.2 FIFO故障模型
本文結合RAM型FIFO中尋址故障和功能故障發生相似性，將片上網絡FIFO故障分為存儲單元陣列故障和FIFO控制邏輯故障兩大類。存儲單元陣列故障模型包括：固定型故障(Stuck-At Fault，SAF)、開路故障(Stuck-Open Fault，SOF)、地址譯碼器故障(Address Decoder Fault，ADF)、跳變故障(Transition Fault，TF)、耦合故障（Coupling Fault，CF)(包括倒置耦合故障CFin，固化耦合故障CFid，狀態耦合故障CFst)、數據延時故障(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 容錯設計
2.1 實時故障檢測算法描述
i=test_address；//FIFO地址指針
j=0；//j代表單地址測試周期
while(j≤2) do
if(j == 1||j == 2)
delay；//發現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時執行算法的第一個階段，讀出測試地址test_address的值，保存在一個臨時寄存器temp1中，并通過判斷是否是FIFO最后一個地址來檢查空標志EF的狀態，隨后將temp1的值保存在一個寄存器original中，然后對temp1取反，將取反值寫到測試地址上，與此同時，讀出測試地址上的值與temp1做比較；當j為1時，進入第二個測試階段，先經過一段時間的延遲，然后讀出測試地址上的值存在temp1中，與original值作比較，并將temp1值取反寫回到測試地址上，與此同時，讀出測試地址上的值，與temp1值作比較，并通過判斷是否是FIFO最后一個地址來檢查滿標志FF的狀態；當j為2時，同樣經過一段延時，然后讀出測試地址上的值，最后一個階段的讀操作保證了對前兩個階段未發現的故障再次進行檢測，有效增強了故障檢測能力。
2.2 故障覆蓋率分析
針對前文描述的不同故障類型，本文對提出的測試算法能達到的故障覆蓋率分析如下。
耦合故障(CF)： 算法對FIFO每個地址的值都采取了翻轉和讀寫交替操作，但是地址只遞增遍歷一次，對于侵略單元地址大于受害單元地址的故障不能檢出，因此只能覆蓋50%的耦合故障。
數據延時故障(DRF)：算法描述中的Del代表了一定的延時操作，可覆蓋DRF。
控制邏輯故障：可對空滿信號FF/EF故障進行檢測，但是因為算法強調實時性和無損性，所以對復位信號RS故障無法檢測。
2.3 FIFO重定向機制
本文引入FIFO讀寫指針重定向表（Redirection Table），提出一種FIFO故障檢測與重定向機制。讀寫地址生成器生成的讀寫指針輸入到重定向表中，產生輸入到FIFO緩存的讀寫指針，其原理圖如圖3所示，深色方塊代表故障槽。在未檢測到故障時，重定向表與FIFO中地址一一順序對應；當檢測到故障后，測試電路產生地址更新信號address_update對重定向表進行更新，有效避開了故障并充分節省了片上資源。
3 功能比較及實驗結果
3.1 功能比較
本文提出的路由器FIFO檢錯容錯方法與文獻[4]、文獻[6]提出的方法在故障覆蓋率、測試在線性和是否有容錯機制分析比較如表1所示。可以發現本文方案故障覆蓋率較高，具有實時測試性，且包含容錯機制。
3.2 仿真實驗
本文采用修改的開源片上網絡仿真器作為仿真實驗平臺，使用systemC作為硬件描述語言，搭建的拓撲結構為4×4的mesh結構，FIFO深度為6個微片，路由算法采用XY維序路由方式。根據提出的算法設計相應的FIFO故障測試電路，并通過設置故障測試電路不同的時鐘周期觀察網絡的延時和吞吐率。
圖4所示的是在不同的測試周期下網絡的吞吐率變化圖。隨著測試周期的不斷增加，吞吐率增長越來越緩慢，逐漸接近一個固定值，這是因為當測試周期增加，對FIFO測試的頻率減少，測試過程對片上網絡正常工作模式的影響越來越小。
圖5所示為不同測試周期下的網絡延時變化圖，隨著測試周期的不斷增加，平均網絡延時逐漸接近一個固定值。
為測試本文容錯機制對故障容忍的效果，在FIFO注入相同故障的情況下，比較基準蟲孔路由器和本文提出的路由器在不同數據包注入率下的吞吐率和延時。圖6所示為吞吐率對比圖，隨著注入率增大，采用基準路由器和本文路由器的網絡的吞吐率都逐漸接近飽和值，但是因為本文路由器采取了容錯措施，吞吐率改善約為17.89%。
圖7所示為延時對比圖，可以看出本文的路由器隨數據包注入率增加，延時均小于基準路由器，這是因為基準路由器未設計合適的容錯機制，隨注入率增加，基準路由器的堵塞和丟包現象越來越嚴重。與基準蟲孔路由器相比，本文路由器延時改善約25.67%。
4 結論
本文根據FIFO讀寫特性，提出了一種可對片上網絡路由器FIFO故障實時檢測并對故障容忍的方法。實驗結果表明，在故障條件下，能有效提高片上網絡吞吐率，并且降低了網絡延時。
參考文獻
[1] 姚磊，蔡覺平，李贊，等.基于內建自測技術的Mesh結構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] 歐陽一鳴，陳義軍，梁華國，等.一種故障通道隔離的低開銷容錯路由器設計[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）