針對瞬時故障和間歇性故障的NoC鏈路容錯方法

歐陽一鳴 孫成龍 李建華 梁華國 黃正峰 杜高明

1(合肥工業大學計算機與信息學院 合肥 230009)2 (合肥工業大學電子科學與應用物理學院 合肥 230009) (oyymbox@163.com)

針對瞬時故障和間歇性故障的NoC鏈路容錯方法

歐陽一鳴1孫成龍1李建華1梁華國2黃正峰2杜高明2

1(合肥工業大學計算機與信息學院 合肥 230009)2(合肥工業大學電子科學與應用物理學院 合肥 230009) (oyymbox@163.com)

片上網絡中鏈路是路由器之間連接的關鍵通路，其發生故障將嚴重影響網絡性能.針對這一問題，提出了一種針對瞬時和間歇性故障的高可靠鏈路容錯方法,該方法可以在網絡中實時檢測數據是否發生錯誤，并以此定義瞬時故障和間歇性故障，從而進行容錯.在減輕網絡擁塞和延時的同時，保證了數據的正確傳輸，有效保障了系統的高可靠性.當鏈路中發生瞬時故障導致數據出錯且不能正確糾正時，通過設置的重傳緩沖區內備份的數據重新進行傳輸.當鏈路中發生間歇性故障導致數據出錯且不能正確糾正時，數據包傳輸被截斷，對被截斷的數據重新添加頭微片或尾微片，從而進行重新路由或資源釋放.實驗結果表明:該容錯方法在不同故障情況下較對比對象，均較大地降低了延時，提高了吞吐率，該方法能有效地提高網絡的可靠性，保證了系統性能.

片上網絡；瞬時故障；間歇性故障；容錯；重傳；可靠性

隨著半導體技術的發展，單個芯片上集成的核數目越來越多，傳統的基于總線(bus)架構的片上系統(system-on-chip， SoC)由于可擴展性差、通信效率低等問題已不能高效地實現處理器之間快速的數據資源交換.片上網絡(network-on-chip， NoC)作為一種新的片上多核系統(multiprocessor system-on-chip， MPSoC)互連通信架構的解決方案，由于其可擴展性高、低延時和高帶寬的優點被提出[1-4].

NoC系統的主要功能是通過路由器保證數據包能夠正確無損地從源節點傳輸到目的節點.鏈路作為路由器之間連接的關鍵數據通路，起著至關重要的作用.而由于軟錯誤、線間串擾、溫度和老化等問題，鏈路傳輸可靠性受到了極大的挑戰.當鏈路故障發生時，即使路由器無故障，也不能發揮其正常的路由功能，大大降低了整體網絡性能.因此針對鏈路的容錯設計顯得尤為重要[5-7].

面對鏈路容錯問題很多研究學者紛紛展開了深入研究.在鏈路上發生的故障可分為永久性故障、瞬時故障和間歇性故障.

1) 鏈路永久性故障是高能粒子擊穿硅氧界面，導致鏈路功能損害[8].永久性故障一旦發生就會一直存在不會消失，故永久性故障可控性好，容錯一般采用重路由[9]或硬件冗余[10]來解決.

2) 瞬時故障的發生隨機且沒有規律，一般發生是瞬時性的且可恢復.文獻[11]中指出大約有80%的通信故障為瞬時故障.對于瞬時故障容錯，一般可以分為兩大類：①基于隨機通信的容錯機制，如文獻[12]提出的洪泛算法，通過廣播和擴散，目的節點會收到很多冗余的數據包備份，即使有數據被損壞，仍然能收到正確的數據，但同時也帶來了很大的功耗開銷;②基于檢錯碼和糾錯碼的請求重傳機制，主要有端到端(end-to-end, e2e)的重傳[13]和跳到跳(switch-to-switch, s2s)的重傳[14-15]，文獻[13]中使用e2e重傳機制，在發送端和接收端的網絡接口中進行差錯校驗編碼(error correcting code, ECC)編解碼，若接收端檢測到數據包出現錯誤，則向發送端請求重傳數據包，但是該方法僅在目的節點進行錯誤檢測，發生重傳時會導致延時翻倍，且傳統ECC僅能糾正一位數據出錯，檢測效率低下，在多位數據出錯時，重傳會大幅增大傳輸延時.文獻[15]使用s2s重傳機制，通過在每個路由器內部設置重傳緩沖區(buffer)暫存傳輸的數據，當下游ECC檢測到數據出錯，則重新傳輸，但是ECC只能覆蓋一位數據錯誤，多位數據出錯時會觸發重傳機制，也會增大網絡延時.

3) 間歇性故障是指由于溫度、電壓等因素的影響導致故障間歇性發生，且持續多個時鐘周期，其可控性差.既不能通過重傳機制來解決，也不能定義為永久性故障進行解決，間歇性故障發生時，數據包的傳輸路徑被故障鏈路截斷[16].已通過故障鏈路的數據由于缺少尾微片(flit)對其所占用資源的釋放，長時間的資源占用會造成網絡擁塞，從而導致網絡延時增加、吞吐量下降，降低了網絡性能.同樣地，由于間歇性故障鏈路的存在，未通過故障鏈路的數據缺少頭flit的路由引導，長時間占用Buffer資源會造成網絡擁塞，甚至有可能導致死鎖.文獻[17]提出一種混合路由機制，設置North-last和South-last兩個子網,使用不同路由算法復制數據進行傳輸，增加了數據傳輸的成功率，但2個子網的復制傳輸明顯造成了資源的浪費.

結合以上內容，本文提出了一種針對瞬時和間歇性故障的高可靠鏈路容錯方法.主要有2點創新之處：

1) 設計一種分離式ECC編碼策略，可同時容忍4個連續錯誤，并在此基礎上提出一種瞬時故障鏈路重傳容錯方法，最大化提高容錯的能力.在路由器中添加重傳Buffer，當鏈路發生瞬時故障時，重傳Buffer結合分離式ECC編碼最大化容忍瞬時故障.

2) 提出一種間歇性故障鏈路截斷重傳容錯方法.在路由器的虛通道中備份頭flit，當鏈路發生間歇性故障時，已通過故障鏈路的數據添加偽尾flit，進行資源釋放.未通過故障鏈路的數據添加偽頭flit，重傳路由，減輕故障對系統性能的影響.

1 NoC中路由器架構

1.1 基準虛通道路由器結構

基準的P端口的虛通道路由器結構如圖1所示，包含5個基本單元：輸入緩沖區Buffer、路由計算單元(routing computation, RC)、虛通道分配單元(virtual channel allocator, VA)、交叉開關Crossbar和交叉開關分配單元(switch allocator, SA).每個端口對應一條物理鏈路，每條物理鏈路對應著多個虛通道(virtual channel, VC)進行數據傳輸.

在路由器發送數據包時，本地處理單元將數據包劃分為格式統一的flit，以方便路由數據包.典型地，數據包被劃分為3種類型的flit：頭flit(head flit， HF)、數據flit(data flit， DF)、尾flit(tail flit， TF).其中HF攜帶了源節點和目的節點的地址信息等，數據包在每一跳的數據傳輸的過程中，都需要HF中的目的節點的地址信息進行路由選擇，因此HF對于整個數據包的傳輸至關重要；DF攜帶了數據包的數據信息；TF用來釋放數據包所占用的資源.

Fig. 2 Transient and intermittent fault model analysis圖2 瞬時和間歇性故障模型分析

1.2 鏈路故障分析

路由器之間通過2條單向鏈路進行連接通信，由于溫度、電壓和串擾等因素的影響，鏈路會發生瞬時故障或間歇性故障.由于高能粒子轟擊晶體管、串擾等因素的影響就有可能發生瞬時故障，引發數據出錯，這些錯誤是瞬態且可恢復的[8,18].如圖2(a)所示，瞬時故障導致的數據錯誤表現為一段時間內單脈沖的活躍時間，其故障持續時間即為活躍時間.文獻[15]中指出瞬時故障的持續時間一般為一個時鐘周期.如圖2(b)所示,間歇性故障表現為一段時間內數據頻繁無規律的錯誤跳變，且持續多個脈沖周期[16,19].從時間角度分析，間歇性故障將突然發生并持續一段時間，而瞬時故障一般只會持續一個時鐘周期.瞬時故障和間歇性故障的發生均不會導致鏈路的永久性失效，本文考慮的故障類型為瞬時故障和間歇性故障.

2 高可靠鏈路容錯路由器結構

本文綜合考慮NoC中鏈路發生瞬時故障和間歇性故障情況，提出了高可靠鏈路容錯路由器結構.在傳統ECC編碼的基礎上設計一種分離式ECC編碼，從而提高路由器的容忍錯誤能力.通過在路由器內部設置重傳Buffer，結合分離式ECC編碼策略，實現對鏈路瞬時故障容錯.當鏈路中發生間歇性故障時，鏈路表現為多個時鐘周期的數據出錯.通過在VC上備份的頭flit，對被截斷數據包添加偽頭flit或偽尾flit，實現對間歇性故障容錯，并且在一定程度上減輕了網絡擁塞.

2.1 容錯路由器整體設計

本文提出的高可靠鏈路容錯路由器設計，其整體結構如圖3所示.容錯路由器基本部分包括東(E)、西(W)、南(S)、北(N)、本地(L)五個端口，還有虛通道、交叉開關以及相應的控制邏輯部分.圖3灰度部分所示為本文添加的容錯部分，主要由ECC單元、一組三態門、多路選擇器(multiplexer, MUX)、截斷恢復單元(truncate recovery unit, TRU)和重傳恢復單元(retransmission recovery unit, RRU)組成.

Fig. 3 The proposed fault-tolerant router architecture圖3 本文提出的容錯路由器結構

Fig. 4 Separated ECC data encoding format圖4 分離式ECC數據編碼格式

當數據包到達輸入端口時，首先根據其虛通道標識(virtual channel identifier,VC_ID)存儲到對應的VC當中，然后依次經過RC,VA,SA,交叉開關傳輸(switch transmission， ST)和鏈路傳輸(link transmission， LT)階段，經過鏈路路由至下游路由器.相較于傳統路由器的流水而言，本文無故障時路由流水沒有增加額外的流水周期.

2.2 容錯路由器詳細設計

2.2.1 分離式ECC檢測單元

ECC是通過在原本的數據位上添加校驗位來實現的.ECC能夠糾正1 b錯誤發現2 b錯誤，可以用來對數據包進行編碼[20].由圖3可以看出，ECC編碼模塊設置在交叉開關之前，數據經過交叉開關傳輸之前都要通過ECC編碼模塊對數據編碼.ECC解碼檢錯模塊設置在輸入端口，每當數據到達輸入端口都要經過ECC檢錯模塊進行分析，用于檢測數據是否發生錯誤.

傳統ECC編碼對于flit的128 b數據而言，需要8 b的冗余校驗.然而8 b僅能糾正128 b數據中的1 b數據錯誤和發現2 b數據錯誤，當數據位中發生多位錯誤時，則需要源節點重新發送數據包，增加了整體傳輸的時間和功耗開銷，檢測效率低下.

如圖4所示為本文提出的分離式ECC數據編碼格式，采用交叉編碼的方式，同一顏色深度的為同一編碼分組.數據出錯在不同分組中，具有同時容忍4 b連續數據出錯并糾正的能力.本文把128 b數據交叉劃分為4組32 b的數據，每組32 b的數據需要6 b冗余校驗，每組可糾正1 b錯誤，則可同時糾正4 b不同分組的數據錯誤，有更強的容錯能力.

2.2.2 RRU

RRU設置在輸入端口和交叉開關之間，其內部結構及數據重傳容錯邏輯如圖5所示.RRU內部包括2個flit大小的重傳Buffer、一個多路選擇器MUX、計數器counter、RRU控制器(RRU controller)和一張VC追蹤表(VC_IDtracker table).其中，RRU Controller用于控制MUX的選通輸出以及控制信號的發送，Counter1用于計數RRU Controller連續收到NACK信號的次數，VC追蹤表保存重傳Buffer內數據原始所在的VC_ID，在TRU數據容錯時用到.下游路由器中Counter2用于計數ECC Controller連續檢測數據出錯且不能正確糾正的次數.

Fig. 5 RRU internal structure and data retransmission recovery logic圖5 RRU內部結構及數據重傳恢復邏輯

Fig. 6 Data retransmission flow schematic diagram圖6 數據重傳流水示意圖

當下游輸入端口ECC模塊檢測到上游傳輸的數據發生錯誤且不能正確糾正時，Counter2+1，并反饋NACK信號給上游，否則反饋ACK信號，告知上游數據傳輸正確.RRU Controller接收到下游反饋的NACK信號時，Counter1+1，通過控制MUX選通重傳Buffer內數據進行傳輸.

由于RRU設置在輸入端口和交叉開關之間，重傳機制的數據傳輸流水如圖6所示.數據flit1經過LT傳輸至下游路由器時，ECC檢測數據出錯且不能正確糾正，存儲上游重傳Buffer中的flit1重新經過ST，LT階段傳輸.注意到重傳的flit1進行ST階段時，flit2進行LT階段，即下游路由器在收到重傳的flit1之前會收到flit2，為了保證數據包的順序性，在檢測到flit1出錯且不能正確糾正后，需要丟棄錯誤數據flit1和flit2，且無論flit2錯誤與否均需重傳flit2.ECC會依次對flit1，flit2、重傳的flit1進行檢測.

ECC檢測flit2和重傳的flit1的4種結果如表1所示，1表示數據出錯，0表示數據正確，根據檢測結果定義故障類型并進行相應操作.表1中1表示檢測到數據出錯且不能糾正，0表示數據沒有出錯或可正確糾正.當出現1或2個flit錯誤如表中行①～③，可通過重傳Buffer重傳數據保證數據的正常傳輸，RRU Controller通過Delete_Retransmission_flit信號刪除重傳Buffer內正確傳輸的數據，并將Counter1和Counter2清0.當連續3個flit傳輸錯誤且不能正確糾正時，即為表1中行④認為該條鏈路存在間歇性故障，Counter2閾值達到3，ECC Controller向本地TRU發送Tx_Fault_Detected信號.RRU Controller通過Counter1計數器計數連續收到NACK信號的次數，當達到閾值3時，RRU Controller向TRU發送Rx_Fault_Detected信號.

Table 1 Fault Type Definitions and Corresponding Operation表1 故障類型定義及相應操作

Fig. 8 Fault-tolerant method analysis diagram圖8 容錯方法分析示意圖

2.2.3 TRU

TRU設置在每個VC上，其內部結構及邏輯示意圖如圖7所示.內部的1-flit Buffer用來存儲每個到來數據包的HF，TRU有2條數據通路：偽頭flit修改通路Head和偽尾flit修改通路Tail.控制器TRU Controller用來控制數據流的輸出.

Fig. 7 TRU internal structure and logic圖7 TRU內部結構和邏輯

當來自ECC Controller的Tx_Fault_Detected信號有效時，TRU Controller控制選通Tail通路，將存儲的頭flit經過Tail flit modify修改為偽TF進行傳輸，釋放數據包所占用資源，偽TF傳輸后TRU Controller通過Delete_Head_Flit信號刪除1-flit Buffer內存儲的頭flit；當來自RRU Controller的Rx_Fault_Detected信號有效時，則選通Head通路，將存儲的頭flit經過Head flit modify修改為偽HF，將其重新進行路由計算，選擇其他可用輸出端口進行輸出，由于RRU重傳Buffer內VC_IDtracker table保存數據的原VC_ID，重傳Buffer內數據跟隨偽HF進行傳輸，并根據偽HF修改其VC_ID，故障數據正常傳輸，實現容錯的目的，在一定程度上減輕網絡擁塞.

2.2.4 容錯方法分析

HF在鏈路傳輸時可能會發生錯誤，當下游路由器檢測到HF發生錯誤且在可糾正范圍內，則糾正出錯數據位完成正常傳輸；當HF出錯且不能正確糾正，由于上游路由器中重傳Buffer中保存有HF，則進行重傳，若下游連續3次接收到數據出錯，則認為該鏈路中存在間歇性故障，上游TRU中備份的HF則重新路由.

圖8中針對鏈路中出現的故障情況，對瞬時故障和間歇性故障容錯方法進行了分析說明.在4×4mesh網絡中，如圖8(a)所示，黑色實線為其路由路徑，源節點9向目的節點4發送數據包.當數據到達節點11并檢測到數據出錯，則該鏈路存在瞬時故障，即存在表1的①情況，在節點10中通過RRU的重傳Buffer重新傳輸，檢測重傳數據無故障則恢復了正常傳輸.如圖8(b)所示，當在節點11連續檢測到數據出錯達到3次，則節點10通往節點11的鏈路存在間歇性故障，此時數據傳輸被截斷.此時進行表1中的④操作，在節點11中TRU把HF修改為偽TF進行資源的釋放，在節點10中TRU將HF修改為偽HF重新路由，未傳輸的數據跟隨偽HF重新路由的路徑進行傳輸,如圖8(b)中被截斷的數據路由如圖所示，2部分數據包在目的節點重新組合成一個數據包.

Fig. 9 Average latency of different packet injection rate under transient faults圖9 瞬時故障下不同數據包注入率的平均延時比較

3 實 驗

本文實驗在網絡性能、面積開銷和功耗3個方面進行展開，其基本參數設定為路由器有E，W，S，N，L這5個端口，每個端口有4個VC，VC的深度為8個flit大小，具體實驗結果及分析如下.

3.1 網絡性能

NoC中網絡性能主要有兩大類：延時和吞吐率.實驗的仿真工具使用的是Booksim[21]擴展的仿真器，在4×4的2D-Mesh拓撲下對網絡的延時和吞吐率做出實驗分析，本文假定數據包由本地輸入端口進入路由器時不會出錯，本文的故障分布僅針對片上網絡中路由器間的數據傳輸鏈路，不針對本地傳輸鏈路.通信模式采用標準模式(uniform)和位補模式(bit complement)，采樣周期為1 000.瞬時故障對比對象為文獻[13]使用的基于ECC的端到端請求重傳機制e2e和文獻[15]使用的傳統基于ECC的跳到跳請求重傳機制s2s.間歇性故障對比對象為文獻[17]提出的NS-FTR，其劃分North-last和South-last這2個子網算法復制數據進行傳輸，數據包在2個子網內分別進行傳輸.本文分別對瞬時故障、間歇性故障以及混合故障類型分布下，比較不同容錯方案的性能.

圖9為在瞬時故障的2種不同模式下不同數據包注入率的平均延時比較.圖9(a)(b)為在標準模式的5%和30%故障率下平均延時的比較.可以看出鏈路發生5%低故障率時，在注入率比較低的時候，本文方案較對比對象優勢不明顯；隨著注入率的增加，e2e和s2s容錯能力低的弊端逐漸凸顯，本文方案較對比對象優勢逐漸凸顯.鏈路發生30%高故障率時，在注入率比較低時，本文方案的延時已明顯小于對比對象.在發生故障時，e2e延時會明顯高于s2s和本文方法，由于本文采用的分離式ECC編碼具有高容錯能力，本文方法延時會低于s2s.當注入率為0.2flit/(node·cycle)時，本文方案在5%故障率下，較s2s方案延時降低9.9%，較e2e方案延時降低30.6%；在30%故障率下，較s2s方案延時降低18.6%，較e2e方案延時降低54.4%.圖9(c)(d)是在位補模式的5%和30%故障率下平均延時的比較.當注入率為0.125flit/(node·cycle)時，本文方案在5%故障率下較s2s方案延時降低13.0%，較e2e方案延時降低34.3%；在30%故障率下較s2s方案延時降低24.8%，較e2e方案延時降低55.81%.

圖10為在瞬時故障的2種不同模式下不同數據包注入率的吞吐率比較.由圖10可看出隨著注入率的增加，本文方案吞吐率會大于e2e和s2s方案.e2e的重傳路徑長，占用資源引發擁塞，吞吐率會明顯低于本文和s2s，高故障率時尤為明顯.本文較s2s提出的分離式ECC編碼具有高容錯能力，減少了重傳，在一定程度上減輕了整體網絡擁塞，因此本文吞吐率最高.圖10(a)(b)是在均勻模式的5%和30%故障率下吞吐率的比較，當注入率為0.2flit/(node·cycle)時，本文方案在5%故障率下吞吐率較s2s方案吞吐率提高7.6%，較e2e方案吞吐率提高30.7%.在30%故障率下較s2s方案吞吐率提高12.5%，較e2e方案吞吐率提高63.6%.圖10(c)(d)是在位補模式的5%和30%故障率下吞吐率的比較，當注入率為0.125flit/(node·cycle)時，本文方案在5%故障率下較s2s方案吞吐率提高11.5%，較e2e方案吞吐率提高33.8%.在30%故障率下較s2s方案吞吐率提高13.9%，較e2e方案吞吐率提高57.9%.

Fig. 10 Throughput of different packet injection rate under transient faults圖10 瞬時故障下不同數據包注入率的吞吐率比較

圖11為在間歇性故障的2種不同模式下不同數據包注入率的延時比較.圖11(a)(b)為在均勻模式的5%和30%故障率下平均延時的比較.鏈路發生5%低故障率時，在注入率比較低的時候，本文方案延時會稍微高于文獻[17]的NS-FTR方法，這是因為在低注入率低故障率下，NS-FTR方法采用的2個子網復制傳輸數據，傳輸成功率高.隨著注入率的增加，NS-FTR的容錯能力趨近飽和，本文方案較對比對象優勢逐漸明顯.鏈路發生30%高故障率時，在注入率比較低時，本文方案的延時小于對比對象.主要原因在于：NS-FTR在高故障率的情況下，2個子網的復制傳輸會占用很大資源，且不能容忍高故障率下的數據出錯，整體平均延時會高于本文.當注入率為0.15flit/(node·cycle)時，本文方案在5%故障率下較NS-FTR延時降低2.9%,在30%故障率下較NS-FTR延時降低21.2%.圖11(c)(d)是在位補模式的5%和30%故障率下平均延時的比較，當注入率為0.125flit/(node·cycle)時，本文方案在5%故障率下較文獻延時降低7.36%，在30%故障率下較文獻延時降低50.1%.

圖12為在間歇性故障的2種不同模式下不同數據包注入率的吞吐率比較.隨著注入率的增加，本文方案吞吐率會大于NS-FTR.NS-FTR采用的2個子網算法復制傳輸數據，在低注入率低故障率時可以達到不錯的效果，隨著注入率的增加，子網復制傳輸的弊端逐漸凸顯，2個子網各占用一半的資源，且在高故障率下容錯能力很有限，造成網絡吞吐率不高.圖12(a)(b)是在均勻模式的5%和30%故障率下吞吐率的比較，當注入率為0.2flit/(node·cycle)時，本文方案在5%故障率下吞吐率較NS-FTR吞吐率提高6.9%；在30%故障率下吞吐率提高12.5%.圖12(c)(d)是位補模式下在5%和30%故障率下吞吐率的比較，當注入率為0.125flit/(node·cycle)時，本文方案在5%故障率下較NS-FTR吞吐率提高14.1%，在30%故障率下吞吐率提高28.6%.

Fig. 11 Average latency of different packet injection rate under intermittent faults圖11 間歇性故障下不同數據包注入率的平均延時比較

Fig. 12 Throughput of different packet injection rate under intermittent faults圖12 間歇性故障下不同數據包注入率的吞吐率比較

圖13為在混合故障率的均勻模式下不同數據包注入率的延時比較.由于本文采用的分離式ECC編碼的高容錯能力，結合重傳Buffer和備份的頭HF能有效容忍瞬時故障和間歇性故障的發生.e2e，s2s在混合故障下，不能有效容忍間歇性故障的發生，其性能低下；NS-FTR方法的2個子網的傳輸在故障率較低時可以容忍瞬時故障和間歇性故障的同時發生，但當故障率增大時，其弊端逐漸凸顯.當注入率為0.15flit/(node·cycle)時，本文方案在5%混合故障率下較s2s方案延時降低33.3%，較e2e方案延時降低37.1%，較NS-FTR延時降低18.2%；在30%故障率下較s2s方案延時降低38.6%，較e2e方案延時降低50.0%，較NS-FTR延時降低25%.

Fig. 13 Average latency of different packet injection rate under mixed faults圖13 混合故障下不同數據包注入率的平均延時比較

圖14為在混合故障率的均勻模式下不同數據包注入率的吞吐率比較.隨著注入率的增加，本文方案吞吐率大于e2e，s2s，NS-FTR.圖14(a)中，當注入率為0.15flit/(node·cycle)時，本文方案在5%故障率下較s2s方案吞吐率提高21.4%，較e2e方案提高36.2%，較NS-FTR提高6.8%.圖14(b)中，在30%故障率下較s2s方案吞吐率提高38.9%，較e2e方案提高56.3%，較NS-FTR提高25%.

Fig. 14 Throughput of different packet injection rate under mixed faults圖14 混合故障下不同數據包注入率的吞吐率比較

3.2 面積開銷及功耗

本文使用Synopsis Design Compiler在45nm工藝下，對比本文設計路由器與基準路由器、e2e路由器、s2s路由器的面積和功耗進行了仿真，其中設置對比路由器中重傳Buffer數目一致.實驗結果如表2所示:

Table 2 The Router Area Overhead and Power Consumption表2 路由器面積和功耗開銷

數據表明，本文方案路由器面積較基準路由器約增加9.9%，較e2e路由器約增加8.0%，較s2s路由器約增加5.6%.本文結合參考文獻瞬時故障容錯和間歇性故障容錯的優勢，并在此基礎上加以改進，容錯部分增加的ECC，TRU，RRU會使面積有所增加.本文方案較基準路由器功耗約增加10.3%，較e2e路由器功耗約增加7.8%，較s2s路由器功耗約增加5.8%.這是因為本文方案路由器在基準路由器基礎上增加了容錯模塊，會使功耗有所增加.在發生故障時，考慮本文方案在延時和吞吐率上的良好表現，增加的面積開銷和功耗也是可以接受的.

4 結束語

本文針對路由器鏈路瞬時故障和間歇性故障，設計了一種高容錯能力的分離式ECC編碼，并在此基礎上提出了一種針對瞬時故障和間歇性故障的高可靠鏈路容錯方法.該方法根據鏈路瞬時故障和間歇性故障發生持續時間的特性，依情況進行容錯.重傳Buffer結合分離式ECC編碼能有效地容忍瞬時故障，對于間歇性故障，保存頭flit修改成頭flit或尾flit，減輕網絡擁塞，平衡網絡負載，能有效地減輕故障對網絡性能的影響.實驗結果表明：本文在僅增加可接受的面積開銷和功耗的前提下，在發生故障時，能有效地減輕故障對網絡性能的影響，具有很好的容錯效果，保障了系統可靠性.

[1]Dally W J, Towles B. Route packets, not wires: On-chip interconnection networks[C] //Proc of the 38th Int Conf on Design Automation. Piscataway, NJ: IEEE, 2001: 684-689

[2]Ouyang Yiming, Zhang Yidong, Liang Huaguo, et al. Design of fault-tolerant router for 3D NoC based on virtual channel fault granularity partition[J]. Journal of Computer Research and Development, 2014, 51(9): 1993-2002 (in Chinese)(歐陽一鳴, 張一棟, 梁華國, 等. 基于虛通道故障粒度劃分的3D NoC容錯路由器設計[J]. 計算機研究與發展, 2014, 51(9): 1993-2002)

[3]Ouyang Yiming, Chen Yijun, Liang Huaguo, et al. Design of a low-overhead fault channel isolated fault-tolerant router[J]. Acta Electronica Sinca, 2014, 42(11): 2142-2149 (in Chinese)(歐陽一鳴, 陳義軍, 梁華國, 等. 一種故障通道隔離的低開銷容錯路由器設計[J]. 電子學報, 2014, 42(11): 2142-2149)

[4]Wang Xinyu, Xiang Dong, Yu Zhigang. TM: A new topology for networks-on-chip[J]. Chinese Journal of Computers, 2014, 37(11): 2327-2341 (in Chinese)(王新玉, 向東, 虞志剛. TM: 一種新的片上網絡拓撲結構[J]. 計算機學報, 2014, 37(11): 2327-2341)

[5]Ganguly A, Pande P P, Belzer B. Crosstalk-aware channel coding schemes for energy efficient and reliable NOC interconnects[J]. IEEE Trans on Very Large Scale Integration Systems, 2009, 17(11): 1626-1639

[6]Feng Chaochao, Zhang Minxuan, Li Jinwen, et al. A fault-tolerant deflection router with reconfigurable bidirectional link for NoC[J]. Journal of Computer Research and Development, 2015, 52(2): 454-463 (in Chinese)(馮超超, 張民選, 李晉文, 等. 一種可配置雙向鏈路的片上網絡容錯偏轉路由器[J]. 計算機研究與發展, 2015, 52(2): 454-463)

[7]Dimopoulos M, Gang Y, Anghel L, et al. Fault-tolerant adaptive routing under an unconstrained set of node and link failures for many-core systems-on-chip[J]. Microprocessors and Microsystems, 2014, 38(6): 620-635

[8]Constantinescu C. Trends and challenges in VLSI circuit reliability[J]. IEEE Micro, 2003 (4): 14-19

[9]Fu Binzhang, Han Yinhe, Li Huawei, et al. Building resilient NoC with a reconfigurable routing algorithm[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(3): 448-455 (in Chinese)(付斌章, 韓銀和, 李華偉, 等. 面向高可靠片上網絡通信的可重構路由算法[J]. 計算機輔助設計與圖形學學報, 2011, 23(3): 448-455)

[10]Ouyang Yiming, Wang Qiao, Liang Huaguo, et al. A link adaptive fault-tolerant method based on fault granularity partition in NoC[J]. Journal of Electronic Measurement and Instrumentation, 2015, 29(8): 1102-1113 (in Chinese)(歐陽一鳴, 王悄, 梁華國, 等. 基于故障粒度劃分的 NoC 鏈路自適應容錯方法[J]. 電子測量與儀器學報, 2015, 29(8): 1102-1113)

[11]Benini L, De Micheli G. Networks on chips: A new SoC paradigm[J]. Computer, 2002, 35(1): 70-78

[12]Pirretti M, Link G M, Brooks R R, et al. Fault tolerant algorithms for network-on-chip interconnect[C] //Proc of the 2014 IEEE Computer Society Annual Symp on VLSI. Piscataway, NJ: IEEE, 2004: 46-51

[13]Schley G, Batzolis N, Radetzki M. Fault Localizing end-to-end flow control protocol for networks-on-chip[C] //Proc of the 21st Euromicro Int Conf on Parallel, Distributed and Network-Based Processing. Piscataway, NJ: IEEE, 2013: 454-461

[14]Murali S, Theocharides T, Vijaykrishnan N, et al. Analysis of error recovery schemes for networks on chips[J]. IEEE Design & Test of Computers, 2005, 22(5): 434-442

[15]Feng Chaochao, Lu Zhonghai, Axel J, et al. Addressing transient and permanent faults in NoC with efficient fault-tolerant deflection router[J]. IEEE Trans on Very Large Scale Integration Systems, 2013, 21(6): 1053-1066

[16]Gil-Tomás D, Gracia-Moran J, Baraza-Calvo J C, et al. Analyzing the impact of intermittent faults on microprocessors applying fault injection[J]. IEEE Design & Test of Computers, 2012, 29(6): 66-73

[17]Pasricha S, Zou Y. NS-FTR: A fault tolerant routing scheme for networks on chip with permanent and runtime intermittent faults[C] //Proc of the 16th Asia and South Pacific Conf on Design Automation. Piscataway, NJ: IEEE, 2011: 443-448

[18]Zhang Ying, Li Huawei, Li Xiaowei. Selected crosstalk avoidance code for reliable network-on-chip[J]. Journal of Computer Science and Technology, 2009, 24(6): 1074-1085

[19]Behrouz R J, Modarressi M. A reconfigurable fault-tolerant routing algorithm to optimize the network-on-chip performance and latency in presence of intermittent and permanent faults[C] //Proc of the 29th Int Conf on Computer Design. Piscataway, NJ: IEEE, 2011: 433-434

[20]Zimmer H, Jantsch A. A fault model notation and error-control scheme for switch-to-switch buses in a network-on-chip[C] //Proc of the 1st IEEE/ACM/IFIP Int Conf on Hardware/Software Codesign and System Synthesis. New York: ACM, 2003: 188-193

[21]Jiang N, Michelogiannakis G, Becker D, et al. Booksim interconnection network simulator[OL]. (2010-09-11)[2012-06-05]. https://nocs.stanford.edu/cgibin/trac.cgi/wiki/Resources/BookSim

Addressing Transient and Intermittent Link Faults in NoC with Fault-Tolerant Method

Ouyang Yiming1, Sun Chenglong1, Li Jianhua1, Liang Huaguo2, Huang Zhengfeng2, and Du Gaoming2

1(School of Computer and Information, Hefei University of Technology, Hefei 230009)2(School of Electronic Science and Applied Physics, Hefei University of Technology, Hefei 230009)

As the link is the critical path between routers in NoC，it will seriously affect the network performance when faults occur in the link. For this reason, we propose a high reliable fault-tolerant method addressing transient and intermittent link faults. The method can detect real-time data error occurring in the network, and then define that whether the fault is transient fault or intermittent fault, thereby realizing fault-tolerance. As a result, it not only alleviates the network congestion and decreases the data delay, but also ensures the correct transmission of data, effectively guaranteeing the high reliability of the system. It is well known that when a transient fault occurs in the link, the fault link will result in a data error, which cannot be corrected properly. Therefore, the proposed method set up the retransmission buffer and then the backup data will be retransmitted. If an intermittent fault occurs, the packet transmission is truncated. To solve this problem, the proposed method adds a pseudo head flit and a pseudo tail flit to the truncated data, then re-routing begins and the occupied resource is released. Experimental results show that, in different fault conditions, this method outperforms the comparison objects with significant reduction in average packet latency and obvious improvement in throughput. In a word, this scheme can effectively improve network reliability in addition to ensuring network performance.

network-on-chip (NoC); transient fault; intermittent fault; fault-tolerant; retransmission; reliable

Ouyang Yiming, born in 1963. PhD and professor. Senior member of CCF. His main research interests include the network on chip (NoC) and system on chip (SoC), embedded systems integrated and testing, digital system design automation.

Sun Chenglong, born in 1993. Master candidate. His main research interests include the methods of fault-tolerant network on chip.

Li Jianhua, born in 1985. Lecturer. His main research interests include computer system architecture, non-volatile memory, network on chip and near data computation.

Liang Huaguo, born in 1961. Professor and PhD supervisor. Senior member of CCF. His main research interests include embedded system integration and testing, digital system design automation, ATPG algorithms and distributed control.

Huang Zhengfeng, born in 1978. Associate professor. His main research interests include embedded system integration and testing, hardware fault tolerance of digital integrated circuits and anti radiation hardening of spaceborne SoC chip.

Du Gaoming, born in 1977. PhD and associate professor. His main research interests include multi-core architecture, performance evaluation and fault-tolerant design for 2D/3D network-on-chip.

2015-12-01；

2016-10-20

國家自然科學基金項目(61474036,61274036,61371025,61574052)；國家自然科學基金青年科學基金項目(61402145);安徽省自然科學基金青年基金項目(1508085QF138);安徽省自然科學基金項目(1508085MF117) This work was supported by the National Natural Science Foundation of China (61474036, 61274036, 61371025, 61574052), the National Natural Science Foundation for Young Scholars of China (61402145), the Natural Science Foundation for Young Scholars of Anhui Province of China (1508085QF138), and the Natural Science Foundation of Anhui Province of China (1508085MF117).

孫成龍(18256910706@163. com)

TP302