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

崔艷 王劉濤

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

關鍵詞： 故障檢測； 片上網(wǎng)絡； 二進制退避算法； 互連線串擾； 監(jiān)控模塊； 優(yōu)先級仲裁機制

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

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

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

1 NoC故障模型

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

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

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

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

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

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

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

2.1 信道擁堵檢測器

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

2.2 流量傳感器模塊

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

當信道處于無故障狀態(tài)時，常規(guī)應用程序能隨時通過無故障信道傳輸數(shù)據(jù)，因此常規(guī)應用程序（[pregular]）的優(yōu)先級高于故障檢測應用程序（[ptest]）優(yōu)先級，即[pregular>ptest。]常規(guī)應用程序完成數(shù)據(jù)傳輸后，信道變?yōu)榭臻e狀態(tài)時，則[pregular

如果信道發(fā)生故障，故障檢測應用程序?qū)⒅貜蜋z測信道且限制常規(guī)應用程序傳輸數(shù)據(jù)，即[pregular

如果信道處于診斷狀態(tài)，傳統(tǒng)檢測周期被定義為診斷周期。此時，信道限制常規(guī)應用程序流量傳輸數(shù)據(jù)，所以故障檢測優(yōu)先級高于常規(guī)應用程序優(yōu)先級，即[pregularptest]。如果信道在診斷階段通過所有檢測，則設定信道無故障且信道的狀態(tài)變?yōu)闊o故障狀態(tài)。

2.3 信道檢測器

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

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

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

3 實驗結(jié)果與分析

3.1 實驗平臺

構(gòu)建測試平臺，使用VHDL實現(xiàn)NoC路由器和信道中的監(jiān)控模塊，路由器的吞吐量可用來分析故障檢測應用程序?qū)ΤＲ?guī)應用程序產(chǎn)生的影響。本文開發(fā)了基于SystemC的數(shù)據(jù)包生成器和計數(shù)器平臺[10]來測量常規(guī)應用程序的吞吐量。數(shù)據(jù)包生成器根據(jù)圖3描述的常規(guī)數(shù)據(jù)包結(jié)構(gòu)生成數(shù)據(jù)，數(shù)據(jù)包計數(shù)器測量輸出數(shù)據(jù)包率，用來推導路由器吞吐量和未成功發(fā)送的數(shù)據(jù)包數(shù)量。

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

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

3.2 實驗結(jié)果

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

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

圖10 發(fā)生故障時的信道吞吐量

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

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

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

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

4 結(jié) 語

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

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

參考文獻

[1] 王諦，趙天磊，唐遇星，等.一種面向通信特征的3D NoC體系結(jié)構(gòu)設計[J].計算機研究與發(fā)展，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] 胡婧瑾.基于環(huán)形拓撲的片上網(wǎng)絡架構(gòu)設計與性能評估研究[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].計算機研究與發(fā)展，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.