基于高層次故障模型的片上網(wǎng)絡(luò)交換機(jī)的診斷策略

柯敏輝

摘要：該文提出了一種基于高層次故障模型的片上網(wǎng)絡(luò)交換機(jī)的診斷策略。該文采用了XY和YX相結(jié)合的路由算法以覆蓋網(wǎng)格裝片上網(wǎng)絡(luò)的每一個(gè)交換機(jī)。在高層次故障模型的基礎(chǔ)上，通過建立和匹配故障字典可準(zhǔn)確定位出發(fā)生故障的交換機(jī)位置。實(shí)驗(yàn)結(jié)果表明該診斷方法在僅需要很少硬件成本你的條件下可達(dá)到很高的故障覆蓋率。

關(guān)鍵詞：片上網(wǎng)絡(luò)交換機(jī)；高層次故障模型；故障字典；故障覆蓋率

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）28-0038-04

1 背景

隨著半導(dǎo)體技術(shù)以及集成電路技術(shù)的飛速發(fā)展，單個(gè)芯片中IP（Intellectual Property）核數(shù)量越來越多。當(dāng)單個(gè)芯片上集成的IP核數(shù)目達(dá)到成百上千的時(shí)候，基于片上總線的SoC（System-on-chip）在設(shè)計(jì)上遇到了全局時(shí)鐘難以同步、地址空間有限、無法支持多節(jié)點(diǎn)并行通訊與系統(tǒng)拓展不夠靈活等問題，嚴(yán)重制約了集成在單一芯片上的IP核規(guī)模及系統(tǒng)性能。

將計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)引入SoC設(shè)計(jì)領(lǐng)域，以片上網(wǎng)絡(luò)的形式從體系結(jié)構(gòu)上徹底解決上述問題成為該領(lǐng)域的研究熱點(diǎn)。片上網(wǎng)絡(luò)的可伸縮性和易擴(kuò)展性很好地滿足了新設(shè)計(jì)的要求。片上網(wǎng)絡(luò)逐漸發(fā)展成為片上總線之外的一種新的通信結(jié)構(gòu)[1]。

NoC（Network on Chips）可以定義為在單一芯片上實(shí)現(xiàn)的基于網(wǎng)絡(luò)通信的多處理器系統(tǒng)。NoC包括計(jì)算和通信兩類節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)完成廣義的計(jì)算任務(wù)，它們可以是SoC，也可以是各種單一功能的IP；通信節(jié)點(diǎn)負(fù)責(zé)計(jì)算節(jié)點(diǎn)之間的數(shù)據(jù)通信，通信節(jié)點(diǎn)及其之間的網(wǎng)絡(luò)成為NoC，它借鑒了分布式計(jì)算機(jī)系統(tǒng)的通信方式，用路由和分組交換技術(shù)代替?zhèn)鹘y(tǒng)的總線技術(shù)完成通信任務(wù)。

為了讓片上網(wǎng)絡(luò)有效應(yīng)用于復(fù)雜的數(shù)字系統(tǒng)，必須要對(duì)片上網(wǎng)絡(luò)進(jìn)行有效的測(cè)試以判斷片上網(wǎng)絡(luò)能否正常工作。對(duì)NoC的測(cè)試包括對(duì)IP核的測(cè)試，對(duì)網(wǎng)絡(luò)中的連接鏈路的測(cè)試，以及對(duì)交換機(jī)的測(cè)試[2]。對(duì)NoC交換機(jī)制測(cè)試的重要性能指標(biāo)有測(cè)試功耗、故障覆蓋率及測(cè)試時(shí)間。

對(duì)片上網(wǎng)絡(luò)交換機(jī)的測(cè)試和診斷一直是NoC研究的熱點(diǎn)。文獻(xiàn)[3]提出了一種對(duì)片上網(wǎng)絡(luò)交換機(jī)制的可拓展的外部測(cè)試方法。此方法采用支持確定性路由的偏向交換機(jī)。實(shí)驗(yàn)表明此方法相比于基于測(cè)試設(shè)計(jì)方法，具有更高的故障覆蓋率。并且此方法還具有更少的測(cè)試數(shù)據(jù)量。文獻(xiàn)[4]提出了一種對(duì)片上網(wǎng)絡(luò)交換機(jī)的并行測(cè)試的方法。它重用了芯片上的網(wǎng)絡(luò)作為測(cè)試訪問機(jī)制（TAM），并通過片上網(wǎng)絡(luò)來廣播測(cè)試矢量到被測(cè)交換機(jī)，通過比較各交換機(jī)的輸出反饋來檢測(cè)故障。文獻(xiàn)[5]提出了一種片上網(wǎng)絡(luò)交換機(jī)的無掃描的測(cè)試方法。其提出了一種對(duì)片上網(wǎng)絡(luò)交換機(jī)的高等級(jí)故障模型。相比于基于掃描的測(cè)試方法，此測(cè)試方法還具有更少的硬件開銷。文獻(xiàn)[6]提出了一種對(duì)片上網(wǎng)絡(luò)交換機(jī)的可拓展的測(cè)試方法。此方法基于部分掃描鏈，并利用了一種IEEE 1500兼容的封裝器，充分利用片上網(wǎng)絡(luò)的常規(guī)設(shè)計(jì)來減少測(cè)試的面積成本和測(cè)試時(shí)間。文獻(xiàn)[7]提出了一種對(duì)片上網(wǎng)絡(luò)交換機(jī)的在線測(cè)試的有效方法。實(shí)驗(yàn)證明該測(cè)試方法具有很高的故障覆蓋率和較小的硬件開銷。

相比于其他的片上網(wǎng)絡(luò)交換機(jī)的測(cè)試方法，基于洪泛算法的片上網(wǎng)絡(luò)交換機(jī)測(cè)試方法[6]是一種故障覆蓋率高、硬件成本低、簡(jiǎn)單易行、具有高延展性的測(cè)試交換機(jī)的算法，然而現(xiàn)有的基于洪泛算法的片上網(wǎng)絡(luò)交換機(jī)測(cè)試方法只給出了判定片上網(wǎng)絡(luò)是否有交換機(jī)存在故障，并沒有給出明確的故障診斷的方法，即沒有精確定位故障交換機(jī)。本文基于傳統(tǒng)的利用洪泛算法測(cè)試片上網(wǎng)絡(luò)交換機(jī)的方法，應(yīng)用了一種高層次的功能性故障模型，給出了故障診斷的方法，以定位發(fā)生故障的片上網(wǎng)絡(luò)交換機(jī)。

2 故障模型和基于洪泛算法的測(cè)試方法

2.1 故障模型

針對(duì)2D-MESH結(jié)構(gòu)的片上網(wǎng)絡(luò)，[8]建立了一種高層次的功能性故障模型：

在片上網(wǎng)絡(luò)交換機(jī)中主要包括兩類功能故障：數(shù)據(jù)故障和控制故障。數(shù)據(jù)故障指數(shù)據(jù)包中的負(fù)載錯(cuò)誤，而控制故障指交換機(jī)中的路由機(jī)制的故障，這是交換機(jī)故障在功能方面最主要的表現(xiàn)。

在片上網(wǎng)絡(luò)中，從功能角度看，交換機(jī)發(fā)生控制故障的表現(xiàn)形式是數(shù)據(jù)包被發(fā)送到一個(gè)錯(cuò)誤的輸出接口。一種控制故障類型是固定出口（固定方向）型故障，即交換機(jī)收到的所有數(shù)據(jù)包都會(huì)被發(fā)送至同一輸出接口。因此，定義以下含有五個(gè)固定型方向的故障模型：

Stuck-at East，Stuck-at West，Stuck-at South，Stuck-at North， Stuck-at Processor。

2.2 洪泛算法

洪泛算法定義如下：源節(jié)點(diǎn)將分組發(fā)送給所有其相鄰節(jié)點(diǎn)。在每個(gè)節(jié)點(diǎn)處，新到來的分組將會(huì)被發(fā)送至除了到達(dá)接口之外的所有其他出口。除非有終止這種不斷重傳分組的信號(hào)，從單個(gè)源分組衍生出的分組數(shù)量將會(huì)是無限的。一種簡(jiǎn)單的追蹤這種傳輸方式的方法是在每個(gè)分組上設(shè)定一塊跳變計(jì)數(shù)區(qū)。這個(gè)計(jì)數(shù)參數(shù)起始值設(shè)定為一個(gè)最大值，例如在網(wǎng)絡(luò)中最長(zhǎng)的“最短跳變路徑”。每當(dāng)分組經(jīng)過了一個(gè)交換機(jī)，其計(jì)數(shù)參數(shù)就會(huì)減一。當(dāng)此技術(shù)參數(shù)降為0的時(shí)候，改分組就會(huì)被丟棄。

2.3 傳統(tǒng)的洪泛算法測(cè)試片上網(wǎng)絡(luò)交換機(jī)的方法

首先設(shè)定網(wǎng)格狀NoC的測(cè)試入口和出口分別在網(wǎng)格的左下和右上角。規(guī)定Manhattan 路徑：使起點(diǎn)（x1， y1）到終點(diǎn)（x2， y2） 跳變距離最短的路徑，路徑長(zhǎng)度為： |x1 - x2| + |y1 - y2|。一個(gè)3×3網(wǎng)格狀NoC的Manhattan路徑有六種。一個(gè)m * n的片上網(wǎng)絡(luò)的Manhattan路徑有條。在測(cè)試入口的信息包中插入一個(gè)跳變總數(shù)值（value），其值等于Manhattan 路徑的長(zhǎng)度。信息包到達(dá)某個(gè)路由后，此值減一，并且向除了反方向之外的另外三個(gè)方向發(fā)送。信息包以此種方式在NoC中傳輸。當(dāng)value值等于0時(shí)，信息包被丟棄。其中，所需的信息包的數(shù)量為存在的路徑總數(shù)。這樣，如果最終到達(dá)出口的路徑條數(shù)等于K（m，n），則轉(zhuǎn)換機(jī)制沒有問題。否則轉(zhuǎn)換機(jī)制有問題。

此方法的優(yōu)點(diǎn)在于：

1）相比于基于掃描鏈硬件或BIST測(cè)試方法，本方法所需硬件成本低；

2）故障覆蓋率很高（接近100%）。

缺點(diǎn)在于：

1）洪泛算法所需測(cè)試包數(shù)量過多，有很多測(cè)試包最終肯定會(huì)被丟棄，因而造成了浪費(fèi)；

2）測(cè)試時(shí)間和功耗很高，且無法預(yù)計(jì)；

3）沒有實(shí)現(xiàn)故障交換機(jī)的定位。

2.4 優(yōu)化的基于洪泛算法測(cè)試片上網(wǎng)絡(luò)交換機(jī)的方法

基于上述的洪泛算法測(cè)試故障交換機(jī)的方法，Mahshid Sedghi等人提出了一種改進(jìn)的測(cè)試方法[9]。此方法將測(cè)試包的路由算法由完全的洪泛算法改為采用XY和YX相結(jié)合的路由算法，每個(gè)收到測(cè)試包的交換機(jī)都會(huì)按XY和YX路由算法發(fā)送測(cè)試包，這樣既保證了100%的故障覆蓋率，又能夠有效避免測(cè)試包的浪費(fèi)，使測(cè)試包數(shù)量、測(cè)試時(shí)間和功耗可預(yù)測(cè)。

然而，此方法依然只能判定片上網(wǎng)絡(luò)是否有交換機(jī)存在固定方向型故障，卻不能實(shí)現(xiàn)故障定位。

3 對(duì)片上網(wǎng)絡(luò)交換機(jī)的故障診斷

3.1 片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：2D MESH結(jié)構(gòu)

2D Mesh結(jié)構(gòu)是目前應(yīng)用最廣泛的拓?fù)浣Y(jié)構(gòu)，如圖1。每個(gè)節(jié)點(diǎn)連接著一個(gè)資源和四個(gè)相鄰的路由器，每個(gè)資源通過一個(gè)網(wǎng)絡(luò)接口（NI）連接著一個(gè)路由器。其中的資源，可以是一個(gè)處理器核，內(nèi)存，一個(gè)用戶自定義硬件模塊或者是其他任何可以插入插槽并且可以和網(wǎng)絡(luò)接口相配的IP（intellectual property）模塊。路由器與路由器之間，路由器與資源之間是由一對(duì)輸入和輸出通道連接。通道是由兩條單向的點(diǎn)對(duì)點(diǎn)總線組成。

3.2 測(cè)試生成策略

本文采用[9]中使用的測(cè)試生成策略。將片上網(wǎng)絡(luò)的左下角和右上角處的交換機(jī)（記為TAS1和TAS2）同時(shí)作為測(cè)試輸入接口和輸出接口。測(cè)試包分別從TAS1和TAS2輸入，從TAS2和TAS1獲得測(cè)試結(jié)果。測(cè)試包在片上網(wǎng)絡(luò)中采用的路由算法是XY和YX算法相結(jié)合的算法，即每個(gè)收到測(cè)試包的交換機(jī)都將該測(cè)試包復(fù)制一份，并根據(jù)目的交換機(jī)的位置分別按XY和YX路由算法發(fā)出。如圖2所示。

采用XY和YX路由算法相結(jié)合的路由算法，并從兩個(gè)方向相互發(fā)送測(cè)試包，可以在保證故障覆蓋率100%的情況下有效減少由洪泛算法造成的測(cè)試包的浪費(fèi)。

3.3 故障診斷方法

為了診斷出片上網(wǎng)絡(luò)中發(fā)生固定型方向的交換機(jī)的位置和故障類型，本文采用故障字典匹配的方式診斷片上網(wǎng)絡(luò)交換機(jī)。其診斷流程如下：

1）根據(jù)mesh結(jié)構(gòu)片上網(wǎng)絡(luò)的規(guī)模建立完整的故障字典，故障字典的建立方法將在下一章說明；

2）測(cè)試入口TAS1（TAS2）分別按XY和YX路由算法發(fā)出兩個(gè)測(cè)試包，記錄下路由方向，分別用1、2、3、4表示方向E、N、W、S；

3）每個(gè)收到測(cè)試包的交換機(jī)都將該分組復(fù)制一份，并按XY和YX路由算法發(fā)出，記錄下路由方向；

4）在TAS2（TAS1）收集到所有能到達(dá)出口的測(cè)試包，按故障字典匹配測(cè)試包的數(shù)據(jù)，最終確定故障交換機(jī)，故障字典的匹配方法將在下一章說明。

4 故障字典的建立和匹配方法

4.1 故障字典建立方法

如第三章所述，TAS1（TAS2）分別按XY和YX路由算法發(fā)出兩個(gè)測(cè)試包，記錄下路由方向； 每個(gè)收到測(cè)試包的交換機(jī)都將該測(cè)試包復(fù)制一份，并按XY和YX路由算法發(fā)出，記錄下路由方向。按此方式記錄下所有到達(dá)測(cè)試出口的測(cè)試包的路徑信息應(yīng)是一個(gè)類似于二叉樹的結(jié)構(gòu)。圖3表示3*3NoC交換機(jī)（1，1）發(fā)生stuck-at-S故障時(shí)，從TAS1至TAS2發(fā)送測(cè)試包時(shí)，在測(cè)試出口出獲得的類樹形結(jié)構(gòu)的路徑集合。

因此，建立某交換機(jī)發(fā)生某固定接口故障對(duì)應(yīng)的二叉樹后，取出每一條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)且路徑長(zhǎng)度為Manhattan 路徑長(zhǎng)度的路徑，該集合即為此交換機(jī)發(fā)生此固定接口故障的故障字典。

按上述方式，取出所有交換機(jī)發(fā)生所有固定接口故障的路徑集合，則建立了完整的故障字典。

由分析可知，單個(gè)方向（TAS1至TAS2）的故障字典并不能精確表示故障路徑集合（如圖中故障交換機(jī)發(fā)生stuck-at-S和stuck-at-W故障字典相同）。因此需建立兩個(gè)方向（TAS1至TAS2和TAS2至TAS1）的故障字典。

4.2 故障字典模型

本文建立的故障字典，其每個(gè)單元表示片上網(wǎng)路中某一個(gè)交換機(jī)發(fā)生某種固定型方向故障時(shí)，在測(cè)試出口處所獲得的測(cè)試包路徑的集合，如圖4所示。

4.3 故障字典與實(shí)際路徑匹配方法

故障字典建立完成之后，從測(cè)試入口發(fā)送測(cè)試包至測(cè)試出口，在測(cè)試出口獲得路徑集合。將實(shí)際在兩個(gè)測(cè)試出口得到的路徑集合分別與對(duì)應(yīng)的故障字典進(jìn)行一一匹配，當(dāng)發(fā)現(xiàn)實(shí)際路徑集合與故障字典某單元的路徑集合完全一致時(shí)，則表示此單元對(duì)應(yīng)的交換機(jī)可能發(fā)生了此單元對(duì)應(yīng)的故障。按此方式可得到兩個(gè)方向的匹配結(jié)果。

一般情況下，將兩個(gè)方向的結(jié)果取交集，則可以得到精確的故障定位結(jié)果，即精確定位出哪個(gè)交換機(jī)發(fā)生了哪種故障。

對(duì)于如圖5所示的特殊情況，即數(shù)據(jù)包被傳至MESH邊緣交換機(jī)時(shí)，不論按XY或YX路由都只能往同一方向發(fā)出，而正好故障出現(xiàn)在這個(gè)方向。

在此種情況下，有一個(gè)方向的匹配結(jié)果會(huì)無法匹配出故障，而另一個(gè)方向的匹配結(jié)果能匹配出某一交換機(jī)可能發(fā)生超過一種故障類型。當(dāng)出現(xiàn)這種情況時(shí)，需要判斷該交換機(jī)所在位置以精確定位其發(fā)生的故障類型。匹配方法如下：

IF “result1 and 2 are not empty” THEN -- “Calculate intersection”

Else

IF “result 1 and 2 are both empty” THEN -- “Not fault”

ELSIF “result 2 is empty”

IF ”fault switch is at the right edge ” THEN -- “stuck-at N fault”

ELSIF ”fault switch is at the top edge ” THEN -- “stuck-at E fault”

ESLE

“return error”

END IF

ELSE

IF ”fault switch is at the leftt edge ” THEN -- “stuck-at S fault”

ELSIF ”fault switch is at the bottom edge ” THEN -- “stuck-at W fault”

ESLE

“return error”

END IF

END IF

END IF

5 仿真實(shí)驗(yàn)

本文提出的片上網(wǎng)絡(luò)交換機(jī)的診斷方法通過一種片上網(wǎng)絡(luò)交換機(jī)模擬器NoCSim來實(shí)現(xiàn)。本章通過與其他診斷方法比較故障覆蓋率、硬件成本和測(cè)試時(shí)間來說明本文的診斷方法的研究意義和可行性。

5.1 故障覆蓋率和硬件成本比較

本文將所提出的診斷方法與兩種同樣使用高層次故障模型的片上網(wǎng)絡(luò)交換機(jī)模擬器的診斷方法“Slow train and fast train”方法[6]和“自測(cè)試交換機(jī)”方法[7]以及基于掃描鏈[5]和基于自建內(nèi)測(cè)試[10]的方法相比較。這些方法所能獲得的故障覆蓋率和所需硬件成本如表1所示。

由上表可以看出，相比于其它診斷方法，本文所提出的方法僅需要很少的硬件成本就可以達(dá)到極高的故障覆蓋率（100%）。

5.2 診斷時(shí)間

通過仿真實(shí)驗(yàn)，獲得了本診斷方法對(duì)不同規(guī)模片上網(wǎng)絡(luò)的交換機(jī)進(jìn)行故障診斷所需要的診斷時(shí)間，如表2所示。

由上表可以看出，在可以達(dá)到100%故障覆蓋率且硬件成本需求較少的情況下，所需診斷時(shí)間可以接受。

6 結(jié)束語(yǔ)

本文提出了一種基于高層次故障模型的片上網(wǎng)絡(luò)交換機(jī)的診斷方法。此方法使用XY和YX相結(jié)合的路由算法來實(shí)現(xiàn)對(duì)片上網(wǎng)絡(luò)所有交換機(jī)的完全覆蓋。通過記錄測(cè)試包在片上網(wǎng)絡(luò)中的跳變方向來獲取測(cè)試包的路徑信息，通過建立故障字典并將實(shí)際路徑信息與故障字典匹配的方式定位故障交換機(jī)。仿真實(shí)驗(yàn)表明本方法在僅需要很少硬件成本的條件下能獲得極高的故障覆蓋率，且診斷時(shí)間合理。

參考文獻(xiàn)：

[1] ?rika Cota， Fernanda Lima Kastensmidt，Maico Cassel.A High-Fault-Coverage Approach for the Test of Data， Control， and Handshake Interconnects in Mesh Networks-on-Chip[J]. IEEE Transactions on Computers，2006，57（9）：1202-1215.

[2] Yan Zheng， Hong Wang， Shiyuan Yang， et al. Accelerating strategy for functional test of NoC communication fabric[C]. Proceeding of 19th IEEE Asian Test Symposium， 2010， 224-227.

[3] Jaan Raik， Vineeth Govind， Raimund Ubar. External test approach for network-on-a-chip switches[C]. Proceeding of 15th Asian Test Symposium， 2006： 437-442.

[4] Mohammad Hosseinabady， Abbas Banaiyan， Mahdi Nazm Bojnordi， Zainalabedin Navabi. A concurrent testing method for NoC switches[C]. Proceedings of the Design Automation & Test in Europe Conference， 2006： 414-420.

[5] Mahshid Sedghi， Armin Alaghi， Elnaz Koopahi， et al. An HDL-based platform for high level NoC switch testing[C]. Proceeding of 16th Asian Test Symposium， 2007： 453-458.

[6] Alexandre M Amory， Eduardo Bri?o， ?rika Cota， et al. A scalable test strategy for network-on-chip routers[C]. Proceeding of IEEE International Conference on Test， 2005： 591-599.

[7] Armin Alaghi， Naghmeh Karimi， Mahshid Sedghi， et al. Online NoC switch fault detection and diagnosis using a high level fault model[C]. Proceeding of 22nd IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems， 2007： 21-29.

[8] Mahshid Sedghi， Elnaz Koopahi， Armin Alaghi，et al.An Exhaustive Test Strategy Based on Flooding routing for NoC Switch Testing[C]// Proceeding of IEEE East-West Design and Test Symposium （EWDTS）， Yerevan， Armenia， September 2007： 262-267.

[9] Mahshid Sedghi， Elnaz Koopahi， Armin Alaghi， et al. An NoC test strategy based on flooding with power， test time and coverage considerations[C]// Proceeding of 21st International Conference on VLSI Design， 2008： 409-414.

[10] Hsiang-Ning Liu，Yu-Jen Huang，Jin-Fu Li. Memory built-in self test in multicore chips with mesh-base networks. IEEE Computer Society， 2009，50（9）：46-55.