基于高層次故障模型的片上網絡交換機的診斷策略

柯敏輝

摘要：該文提出了一種基于高層次故障模型的片上網絡交換機的診斷策略。該文采用了XY和YX相結合的路由算法以覆蓋網格裝片上網絡的每一個交換機。在高層次故障模型的基礎上，通過建立和匹配故障字典可準確定位出發生故障的交換機位置。實驗結果表明該診斷方法在僅需要很少硬件成本你的條件下可達到很高的故障覆蓋率。

關鍵詞：片上網絡交換機；高層次故障模型；故障字典；故障覆蓋率

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）28-0038-04

1 背景

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

將計算機網絡技術引入SoC設計領域，以片上網絡的形式從體系結構上徹底解決上述問題成為該領域的研究熱點。片上網絡的可伸縮性和易擴展性很好地滿足了新設計的要求。片上網絡逐漸發展成為片上總線之外的一種新的通信結構[1]。

NoC（Network on Chips）可以定義為在單一芯片上實現的基于網絡通信的多處理器系統。NoC包括計算和通信兩類節點，計算節點完成廣義的計算任務，它們可以是SoC，也可以是各種單一功能的IP；通信節點負責計算節點之間的數據通信，通信節點及其之間的網絡成為NoC，它借鑒了分布式計算機系統的通信方式，用路由和分組交換技術代替傳統的總線技術完成通信任務。

為了讓片上網絡有效應用于復雜的數字系統，必須要對片上網絡進行有效的測試以判斷片上網絡能否正常工作。對NoC的測試包括對IP核的測試，對網絡中的連接鏈路的測試，以及對交換機的測試[2]。對NoC交換機制測試的重要性能指標有測試功耗、故障覆蓋率及測試時間。

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

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

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

2.1 故障模型

針對2D-MESH結構的片上網絡，[8]建立了一種高層次的功能性故障模型：

在片上網絡交換機中主要包括兩類功能故障：數據故障和控制故障。數據故障指數據包中的負載錯誤，而控制故障指交換機中的路由機制的故障，這是交換機故障在功能方面最主要的表現。

在片上網絡中，從功能角度看，交換機發生控制故障的表現形式是數據包被發送到一個錯誤的輸出接口。一種控制故障類型是固定出口（固定方向）型故障，即交換機收到的所有數據包都會被發送至同一輸出接口。因此，定義以下含有五個固定型方向的故障模型：

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

2.2 洪泛算法

洪泛算法定義如下：源節點將分組發送給所有其相鄰節點。在每個節點處，新到來的分組將會被發送至除了到達接口之外的所有其他出口。除非有終止這種不斷重傳分組的信號，從單個源分組衍生出的分組數量將會是無限的。一種簡單的追蹤這種傳輸方式的方法是在每個分組上設定一塊跳變計數區。這個計數參數起始值設定為一個最大值，例如在網絡中最長的“最短跳變路徑”。每當分組經過了一個交換機，其計數參數就會減一。當此技術參數降為0的時候，改分組就會被丟棄。

2.3 傳統的洪泛算法測試片上網絡交換機的方法

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

此方法的優點在于：

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

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

缺點在于：

1）洪泛算法所需測試包數量過多，有很多測試包最終肯定會被丟棄，因而造成了浪費；

2）測試時間和功耗很高，且無法預計；

3）沒有實現故障交換機的定位。

2.4 優化的基于洪泛算法測試片上網絡交換機的方法

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

然而，此方法依然只能判定片上網絡是否有交換機存在固定方向型故障，卻不能實現故障定位。

3 對片上網絡交換機的故障診斷

3.1 片上網絡拓撲結構：2D MESH結構

2D Mesh結構是目前應用最廣泛的拓撲結構，如圖1。每個節點連接著一個資源和四個相鄰的路由器，每個資源通過一個網絡接口（NI）連接著一個路由器。其中的資源，可以是一個處理器核，內存，一個用戶自定義硬件模塊或者是其他任何可以插入插槽并且可以和網絡接口相配的IP（intellectual property）模塊。路由器與路由器之間，路由器與資源之間是由一對輸入和輸出通道連接。通道是由兩條單向的點對點總線組成。

3.2 測試生成策略

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

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

3.3 故障診斷方法

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

1）根據mesh結構片上網絡的規模建立完整的故障字典，故障字典的建立方法將在下一章說明；

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

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

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

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

4.1 故障字典建立方法

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

因此，建立某交換機發生某固定接口故障對應的二叉樹后，取出每一條從根節點到葉子節點且路徑長度為Manhattan 路徑長度的路徑，該集合即為此交換機發生此固定接口故障的故障字典。

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

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

4.2 故障字典模型

本文建立的故障字典，其每個單元表示片上網路中某一個交換機發生某種固定型方向故障時，在測試出口處所獲得的測試包路徑的集合，如圖4所示。

4.3 故障字典與實際路徑匹配方法

故障字典建立完成之后，從測試入口發送測試包至測試出口，在測試出口獲得路徑集合。將實際在兩個測試出口得到的路徑集合分別與對應的故障字典進行一一匹配，當發現實際路徑集合與故障字典某單元的路徑集合完全一致時，則表示此單元對應的交換機可能發生了此單元對應的故障。按此方式可得到兩個方向的匹配結果。

一般情況下，將兩個方向的結果取交集，則可以得到精確的故障定位結果，即精確定位出哪個交換機發生了哪種故障。

對于如圖5所示的特殊情況，即數據包被傳至MESH邊緣交換機時，不論按XY或YX路由都只能往同一方向發出，而正好故障出現在這個方向。

在此種情況下，有一個方向的匹配結果會無法匹配出故障，而另一個方向的匹配結果能匹配出某一交換機可能發生超過一種故障類型。當出現這種情況時，需要判斷該交換機所在位置以精確定位其發生的故障類型。匹配方法如下：

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 仿真實驗

本文提出的片上網絡交換機的診斷方法通過一種片上網絡交換機模擬器NoCSim來實現。本章通過與其他診斷方法比較故障覆蓋率、硬件成本和測試時間來說明本文的診斷方法的研究意義和可行性。

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

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

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

5.2 診斷時間

通過仿真實驗，獲得了本診斷方法對不同規模片上網絡的交換機進行故障診斷所需要的診斷時間，如表2所示。

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

6 結束語

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

參考文獻：

[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.