基于二進制退避算法和流量感知的片上網絡在線故障檢測

崔艷 王劉濤

摘 要： 針對片上網絡（NoC）中互連線容易發生串擾故障問題，提出了一種基于二進制退避算法（BEBOA）結合流量感知的NoC串擾在線診斷故障方案。當NoC信道空閑時，使用信道檢測器檢測信道以最小化NoC入侵吞吐量；當臨時故障恢復時，使用基于BEBOA的檢測間隔時間參數動態設定檢測時間，使網絡快速恢復。此外，構建一種優先級仲裁機制，避免應用程序和檢測程序發生信道訪問沖突。實驗結果表明，提出的方案能夠準確檢測和診斷故障，并能夠迅速恢復吞吐量，同時具有最小的額外芯片面積開銷需求。

關鍵詞： 故障檢測； 片上網絡； 二進制退避算法； 互連線串擾； 監控模塊； 優先級仲裁機制

中圖分類號： TN711?34； TP399 文獻標識碼： A 文章編號： 1004?373X（2016）05?0014?05

片上網絡（Networks?on?Chip，NoC）[1]是一種用于復雜片上系統（System?on?Chip，SoC）的可擴充且有效的通信架構，片上網絡越來越高的復雜性導致出現多種互連問題[2]。為了保證現代NoC能適應故障且正常運行，需要開發一種能在互連結構中進行自我檢測和自我維修的容錯策略[3]。

由于NoC網絡中存在大量互連結構，傳統測試機制不能有效診斷和定位故障。因此，本文提出一種利用監控模塊（Monitoring Module，MM）在線檢測和診斷NoC互連線串擾故障，并以并行方法運行，最小化NoC入侵吞吐量。

1 NoC故障模型

NoC中常見的故障為邏輯層的門級故障、橋接故障和串擾故障[4]，本文主要針對串擾故障進行研究。

在NoC互連中，串擾故障通常由空間相近的兩條邏輯信道線路的信號相互影響而形成。本文使用最大激勵串擾故障（Maximal Aggressor Fault，MAF）[5]模型描述導致串擾故障的所有原因。在MAF模型中，線路受相鄰線路傳輸數據信號的干擾而形成串擾故障，如圖1所示MAF模型形成的6種串擾方式，分別為正/負脈沖、上升/下降延遲、上升/下降加速。

圖1表明檢測器需給每條線路發送2個測試向量來形成各種可能干擾，因此需要12種測試向量來檢測6種可能干擾。MAF模型對于一種[N]位信道，設定第4 b作為受干擾線路，測試向量[（v1，v2，…，v8）]依次發送特定測試向量，用于檢測6種可能串擾故障，如圖2所示。

2 提出的串擾故障檢測方案

本文利用CCD組件[6]的監控模塊來增強路由器檢測故障的能力，監控模塊通過隔離測試過程的流量和執行常規應用程序流量來管理NoC測試過程的入侵流量，使用基于二進制退避算法（Binary Exponential Back?off Algorithm，BEBOA）[7]的檢測間隔時間參數動態設定檢測時間，使網絡快速恢復。

圖3所示為監控模塊與路由器中其他組件的連接結構。對一種n b數據包，最重要的4 b定義為頭，目標地址占16 b，其余bit為有效負荷。以“（002025A5A）16”為例，則頭字段為（0）16，目標地址為（0202）16，有效負荷為（5A5A）16。僅使用1 b的MSB表示數據包類型，若頭字段的MSB為1，則該數據包為測試數據包，否則為常規應用程序數據包。

圖4為兩個路由器通過East端口和West端口相互連接的例子。監控模塊（MM）有4個子組件，信道擁堵檢測器（CDD）、信道檢測器（CT）、流量傳感器模塊（TSM）和測試間隔時間決策模塊（TID），下面詳細介紹這些模塊。

2.1 信道擁堵檢測器

本文使用信道擁堵檢測器（Channel Congestion Detector，CCD）[8]檢測信道的當前流量狀態，為流量傳感器模塊提供信道擁堵信息。流量狀態分類為：信道不擁堵、信道繁忙和信道擁堵。該方法能有效地做出路由決策，選擇輕擁堵路由，提高信道吞吐量。

2.2 流量傳感器模塊

由于故障檢測應用程序和常規應用程序共享使用信道，所以流量傳感器模塊（TSM）定義了一種優先級仲裁方案，以避免沖突。TSM通過每個信道局部CCD提供的繁忙/擁堵/故障信號來獲得端口狀態，以此做出仲裁。共享信道的優先級定義如圖5所示。

當信道處于無故障狀態時，常規應用程序能隨時通過無故障信道傳輸數據，因此常規應用程序（[pregular]）的優先級高于故障檢測應用程序（[ptest]）優先級，即[pregular>ptest。]常規應用程序完成數據傳輸后，信道變為空閑狀態時，則[pregular

如果信道發生故障，故障檢測應用程序將重復檢測信道且限制常規應用程序傳輸數據，即[pregular

如果信道處于診斷狀態，傳統檢測周期被定義為診斷周期。此時，信道限制常規應用程序流量傳輸數據，所以故障檢測優先級高于常規應用程序優先級，即[pregularptest]。如果信道在診斷階段通過所有檢測，則設定信道無故障且信道的狀態變為無故障狀態。

2.3 信道檢測器

信道檢測器（Channel Detector，CT）[9]負責檢測信道，若信道出現故障，CT將給其他模塊發出警告標志。根據警告標志，自適應仲裁機制隨后做出路由決策。CT由兩個主要子模塊組成：檢測向量生成器和檢測響應分析器。

若故障檢測的優先級高于常規應用程序優先級且檢測時間間隔等于0，則只進行信道故障檢測過程。CT能檢測每個信道中多種類型的故障，如果線路#1發生故障，CT單元將檢測線路#2到線路n，直到檢測到故障線路。對一個n b信道，受干擾線路的范圍為從1～n-1。對每個受干擾線路，測試向量生成器順序發送測試向量[（v1，v2，…，v8）]來診斷線路是否為6種串擾故障[{sf，sr，gn，…，gp}]中的一種。接收端的檢測響應分析器生成標準檢測向量，用于與接收到的檢測向量作比較。如果它們不匹配，則該線路存在串擾故障且生成故障標簽。檢測向量生成器需要9個時鐘周期檢測一條線路，其中1個時鐘周期用于發送初始數據包（表明需檢測線路位置），8個時鐘周期用于發送檢測向量。因此，它需要總共9[×]（n-1）個時鐘周期檢測完n b信道。

信道檢測器模塊中生成檢測向量的流程圖，如圖6所示。在每次檢測的開始，CT讀取來自TID的檢測間隔時間并啟動計數器。當計數器值等于檢測間隔時間值時，CT初始化一個新的檢測過程，且順序發送檢測向量[（v1，v2，…，v8）]。CT完成檢測后，TID模塊增加間隔時間，這是因為如果信道已經成功通過先前檢測，則沒有必要持續檢測信道。間隔時間參數可以控制故障檢測過程占有信道的平均時間。

3 實驗結果與分析

3.1 實驗平臺

構建測試平臺，使用VHDL實現NoC路由器和信道中的監控模塊，路由器的吞吐量可用來分析故障檢測應用程序對常規應用程序產生的影響。本文開發了基于SystemC的數據包生成器和計數器平臺[10]來測量常規應用程序的吞吐量。數據包生成器根據圖3描述的常規數據包結構生成數據，數據包計數器測量輸出數據包率，用來推導路由器吞吐量和未成功發送的數據包數量。

圖8為實現監控模塊各種功能的3×3的NoC路由器平臺。監控模塊能處理NoC在實際中遇到的不同場景情況。基于XY路由選擇算法，路由器[2，3]的Western輸入信道在特定時間周期內是空閑的，但是Eastern信道總是擁堵的，如圖9所示。根據這些信道的實時吞吐量來分析常規應用程序的入侵流量。

仿真實驗中，設置數據包大小為36 b，系統頻率為100 MHz。不同數據包發送率能產生不同流量，這些不同流量可以用來分析監控模塊性能（特別是入侵流量分析）。通過故障分發器給一些信道分配串擾故障，引起一些永久故障（PF）或暫時故障（TF）。另外，本文使用基于SADE 90 nm CMOS的集成電路設計編譯工具獲取監控模塊的面積開銷（檢測單元占路由器整體面積的百分比）。

3.2 實驗結果

圖10為不同故障情況（永久性故障、暫時故障）和不同[β]值的TID模型下的信道吞吐量，分析監控模塊行為對平均常規應用程序吞吐量產生的影響。

如果信道無故障，則對常規應用程序吞吐量而言，故障檢測流量不為入侵流量。圖10（a）和圖10（b）中，檢測周期0～3之間，信道無故障且常規應用程序能在任何時間傳輸數據，因此[pregular>ptest，]信道吞吐量保持最大值（即3.6 Gb/s）。另一方面，當給信道引入故障時，第4個檢測周期檢測到了故障，故障檢測過程將繼續檢測該信道。因此，常規應用程序不能通過該信道傳輸數據，其吞吐量為0。對于暫時故障，故障從第7個周期開始恢復，如圖10（a）所示，在此診斷期間，常規應用程序在檢測間隔時間內仍能傳輸數據。在監控模塊診斷信道為無故障后，隨著檢測間隔時間呈指數增長，常規應用程序占有信道時間加長，信道吞吐量逐漸恢復。對永久性故障，故障檢測過程總能檢測到故障，因此常規應用程序吞吐量總是為0。

圖10 發生故障時的信道吞吐量

另外，從圖10（a）能清楚地看到，TID模型中檢測過程的恢復速度依賴于[β]值（后退程度）。例如，如果[β=2，]則第一次檢測過程的[Ncount（1）=2]。如果沒有檢測到故障，則第二次檢測過程的[Ncount（2）=4]。[Ncount（n）]的變化趨勢依賴于[β。][β]值越大，檢測間隔時間[Ncount（n）-Ncount（n-1）]越大。在診斷階段，常規應用程序在兩次檢測之間可以傳輸數據，因此[β]值越大，則吞吐量恢復速度越快。但如果[β]值太大，在故障檢測階段又出現故障時，模型的反應能力會下降。

在兩種常見的通信模式下（均勻隨機、位補碼）評估各種算法隨著網絡中故障鏈路數目的增加對網絡吞吐率的影響。故障條件設為無故障，5%鏈路故障和15%鏈路故障三種情況，另外，故障鏈路中設置一半為永久故障，一半為暫時故障。網絡吞吐率為網絡的最大通信量，單位為packet·（cycle·node）-1。4種算法的吞吐量比較，如表1所示。

從表1可以看出，本文方案的故障情況對網絡吞吐量的影響最小。因為本文方案有效地檢測故障，快速回復暫時故障的吞吐量，另外，檢測模塊所需的流量較小，并采用仲裁機制避免沖突，大大提高了檢測和數據傳輸的效率。

以使用4個監控模塊的路由器為例，每個信道有1個監控模塊。路由器擁有32 928個邏輯門，假設其中11.56%（3 808個）的邏輯門有4個監控模塊。各個算法的硬件面積開銷如表2所示，可以看出，本文方案的硬件面積開銷最小，約為12%，具有良好的可擴展性。

4 結 語

本文提出了一種針對NoC互連的流量感知串擾故障自適應在線檢測和診斷方案，使用TSM組件監控信道流量，使用后退算法和優先級定義構建一種信道訪問仲裁機制，避免了應用程序和檢測程序發生訪問沖突。此外，還提出了快速故障恢復策略，故障消除后，能夠使常規應用程序吞吐量快速恢復到最大值。在不同信道故障情況下評估本文方案性能，實驗結果表明，本文方案能夠在線準確診斷故障，在故障情況下能獲得最大吞吐量，且需要的額外面積開銷也較小。

檢測時間間隔參數[β]的值影響著檢測效率和吞吐量恢復速度，如何確定合適的[β]值非常重要。因此，在未來工作中，將進一步研究故障優化恢復決策。

參考文獻

[1] 王諦，趙天磊，唐遇星，等.一種面向通信特征的3D NoC體系結構設計[J].計算機研究與發展，2014，51（9）：1971?1979.

[2] DALL′OSSO M， BICCARI G， GIOVANNINI L， et al. A latency insensitive parameterized network?on?chip architecture for multi?processor SoCs [C]// Proceedings of 2012 30th IEEE International Conference on Computer Design. [S.l.]： IEEE， 2012： 45?48.

[3] 胡婧瑾.基于環形拓撲的片上網絡架構設計與性能評估研究[D].杭州：浙江大學，2013.

[4] CARRILLO S， HARKIN J， MCDAID L， et al. Advancing interconnect density for spiking neural network hardware implementations using traffic?aware adaptive network?on?chip routers [J]. Neural networks， 2012， 33（4）： 42?57.

[5] LIU J， HARKIN J， LI Y， et al. Online fault detection for networks?on?chip interconnect [C]// Proceedings of 2014 NASA/ESA Conference on Adaptive Hardware and Systems. [S.l.]： IEEE， 2014： 31?38.

[6] 張士鑒，韓國棟，沈劍良，等.基于故障鏈路緩存再利用的NoC容錯路由算法[J].計算機輔助設計與圖形學學報，2014，26（1）：131?137.

[7] TAMRAKAR D， BHATTACHARYA S， JAIN S. A scheme to eliminate redundant rebroadcast and reduce transmission delay using binary exponential algorithm in Ad?Hoc wireless networks [J]. International journal of scientific research in network security and communication， 2014， 31（2）： 1?5.

[8] 歐陽一鳴，張一棟，梁華國，等.基于虛通道故障粒度劃分的 3D NoC 容錯路由器設計[J].計算機研究與發展，2014，51（9）：1993?2002.

[9] GRECU C， IVANOV A， SALEH R， et al. Testing network?on?chip communication fabrics [J]. IEEE transactions on compute?raided design of integrated circuits and systems， 2007， 26（12）： 2201?2214.

[10] HERVE M， ALMEIDA P， KASTENSMIDT F L， et al. Concurrent test of network?on?chip interconnects and routers [C]// 2010 11th Latin American of Test Workshop. Pule del Este： IEEE， 2010： 1?6.