崔艷 王劉濤

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

關(guān)鍵詞： 故障檢測(cè)； 片上網(wǎng)絡(luò)； 二進(jìn)制退避算法； 互連線串?dāng)_； 監(jiān)控模塊； 優(yōu)先級(jí)仲裁機(jī)制

中圖分類號(hào)： TN711?34； TP399 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）05?0014?05

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

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

1 NoC故障模型

NoC中常見的故障為邏輯層的門級(jí)故障、橋接故障和串?dāng)_故障[4]，本文主要針對(duì)串?dāng)_故障進(jìn)行研究。

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

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

2 提出的串?dāng)_故障檢測(cè)方案

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

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

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

2.1 信道擁堵檢測(cè)器

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

2.2 流量傳感器模塊

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

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

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

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

2.3 信道檢測(cè)器

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)平臺(tái)

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

從表1可以看出，本文方案的故障情況對(duì)網(wǎng)絡(luò)吞吐量的影響最小。因?yàn)楸疚姆桨赣行У貦z測(cè)故障，快速回復(fù)暫時(shí)故障的吞吐量，另外，檢測(cè)模塊所需的流量較小，并采用仲裁機(jī)制避免沖突，大大提高了檢測(cè)和數(shù)據(jù)傳輸?shù)男省?/p>

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

4 結(jié) 語

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

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

參考文獻(xiàn)

[1] 王諦，趙天磊，唐遇星，等.一種面向通信特征的3D NoC體系結(jié)構(gòu)設(shè)計(jì)[J].計(jì)算機(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)形拓?fù)涞钠暇W(wǎng)絡(luò)架構(gòu)設(shè)計(jì)與性能評(píng)估研究[D].杭州：浙江大學(xué)，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容錯(cuò)路由算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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 容錯(cuò)路由器設(shè)計(jì)[J].計(jì)算機(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.