基于片上網絡的容錯通信方法*

歐陽一鳴，郭 凱，梁華國

(合肥工業大學計算機與信息學院 合肥 230009)

1 引言

隨著超大規模集成電路的發展，片上系統（SoC）的集成度越來越高，數以百計的十億級晶體管集成到一個片上，這就要求片上的模塊之間的通信帶寬足夠大，并且具有可重用性以滿足快速投放市場的需求。傳統的片上系統采用的總線結構受到了這兩方面的嚴峻挑戰。參考文獻[1～3]介紹了一種新的片上通信結構——片上網絡（network on chip，NoC），它將互聯網技術移植到片上系統，數以百計的片上資源（IP核）互連起來，并將通信與計算分離。NoC不但具有良好的空間可擴展性，而且采用了全局異步-局部同步GALS（globally asynchronous locally synchronous）通信機制，提供了高效的并行通信能力。

與此同時，隨著電路集成規模的提高，電路在生產和運行過程中非常容易損壞。在NoC中必須存在相應的容錯策略，以便在出現故障時可以繼續有效地工作。對于NoC中的IP核故障，由于NoC中通常存在大量相同的部件，因此在軟件映射時不使用已經損壞的IP核就可以解決；對于NoC中的路由器和鏈路故障，由于在通信過程中可能會用到這些路由器和鏈路，因此可能會導致NoC通信錯誤甚至癱瘓。為了解決該問題，參考文獻[4]將該問題分為以下3個子問題：

·使用適當的內建自測試（BIST）機制探測出故障的路由器和鏈路；

·設計一種容錯的、分布式、可重構的路由算法，并在路由器中執行；

·在NoC中設置配置總線，重構的數據通過配置總線分發到每個路由器中。

本文主要是設計一種能夠容錯的分布式可重構路由算法，使NoC出現路由器和鏈路故障時能夠繼續正確地通信。

[4]提出了一種可重構的容錯路由算法，通過在未出錯區域使用XY路由算法，在出錯區域使用特定的路由路徑，達到容忍單個路由器（或者一個路由器區域）出現故障的目的。該算法將NoC中路由器的損壞狀況分成9種，然后規定了這9種狀況分配的通信路徑，并通過路由器中設置的狀態寄存器標識出該路由器所處的狀態，通信時依據路由器狀態選擇相應的路由路徑。但是該算法沒有解決NoC出現多個不規則路由器故障和鏈路故障的問題。參考文獻[5]和[6]提出的路由算法，通過在節點建立探測機制，探測出沒有故障的傳輸路徑。該算法雖然能夠解決NoC中的路由器和鏈路故障，但是節點中的路由表開銷較大，而且探測數據包會增加數據傳輸時延。參考文獻[7]中采用多路徑傳輸策略，當傳輸數據包時，同時在不同路徑上傳輸多份數據包，通過冗余來防止出錯造成的通信錯誤。該方法容易造成網絡擁塞，同時增大了數據的傳輸時延。

本文提出了新的容錯模型和基于該模型的可重構路由算法。本方法通過容錯模型建立起每個路由器的輸出端口狀態，可重構路由算法通過對每個輸出端口的狀態進行標識，確認與端口相連的路由器和鏈路的損壞狀態，決定數據的轉發方向。這樣可以保證數據傳輸能夠正確地進行，并且沒有額外的數據包進入網絡。與現有方法相比，該方法在能夠容忍路由器和鏈路故障的同時，保障NoC擁有較高的通信性能。

2 容錯模型

NoC是由控制網絡中數據傳輸的路由器和連通片上系統中各IP核之間進行數據傳輸的鏈路構成的網絡結構。NoC 的拓撲多種多樣，有 2D-Mesh、torus、fat-tree等，本文采用的是2D-Mesh拓撲，如圖1所示（R表示路由器，IP表示IP核）。

下面分別給出路由器損毀度（DG）和輸出端口狀態寄存器（SR）的定義。

路由器損毀度：在2D-Mesh結構中，與路由器（x，y）相連的4條鏈路或者路由器的損壞（或者未連接）個數稱為該路由器的損毀度。例如，與非邊沿節點路由器（x，y）相連的一個路由器和一條鏈路損壞，那么該路由器的損毀度為2；邊沿節點（0，1）相連的路由器和鏈路全部完好，那么該路由器的損毀度為1。對于一個路由器，其損毀度的范圍為[0，4]。

輸出端口狀態寄存器：在2D-Mesh結構中，每個路由器存在4個輸出端口，4個輸出端口通過鏈路與下一個路由器相連，因此，在路由器內設置一個8位的端口狀態寄存器用于標識與4個端口相連的鏈路或者路由器的損壞狀態，每個端口對應2位，其格式如圖2所示。

每個路由器的損毀度可以由該路由器的輸出端口狀態寄存器確定，其公式如下。

路由器的每個輸出端口狀態可以由與該輸出端口相連的路由器損毀度確定，其轉換公式如下。

式中，SRi為狀態寄存器中 i對應的方向，DGNei為i對應的輸出端口相連的路由器損毀度，i的取值范圍為[0，3]，0代表 N方向，1代表 E方向，2代表 S方向，3代表W方向。

假設通過適當的BIST測試能夠檢測出NoC中出現故障的路由器或者鏈路的具體位置。若網絡中的某個路由器出現故障或者與路由器相連的3條鏈路出現故障，則在軟件映射時不使用與該路由器相連的IP核，因此，在NoC路由過程中，不存在數據包的目的地是與這些路由器相連的IP核。

3 基于重構的動態容錯路由算法

本文提出的基于重構的動態容錯路由算法是在帶有一定自適應性的維序路由[8]的基礎上，通過對路由器中每個端口的輸出狀態寄存器進行檢查確定路由方向。在路由時還考慮了網絡的擁塞程度，若路由時兩個端口的輸出狀態寄存器的標識相同，那么依據擁塞程度確定路由方向。擁塞程度依據每個端口的轉發率來確定。另外，該路由算法通過虛通道機制可以解決死鎖問題[9]。

轉發率是指該方向上已經轉發出去的數據包數目與該路由器所有轉發出去的數據包總數的比值，即：

路由算法描述如下：設（dx，dy）為數據的目的節點，（cx，cy）為數據傳輸的當前節點。當 dx和 cx、dy和 cy都不相等時保持最短路徑的轉發方向有兩個，根據SR中這兩個方向的標識選擇轉發的端口。若兩個方向標識相等，當標識為11時，數據從余下的非數據進入方向轉發；當不為11時，選擇擁塞程度小的方向轉發。若兩個方向的標識不同，則從標識較小的方向轉發。當dx和cx、dy和cy中有一個相等時，保持最短路由的轉發方向只有一個，如果SR中該方向的標識不為11，則從該方向直接轉發；否則，查看數據的進入端口再做相應處理。若數據是從坐標相等維的端口進入，則比較余下的端口，若這兩個端口的標識相等，則從擁塞程度小的方向轉發，否則從標識較小的方向轉發；若數據是從非坐標相等維的端口進入路由器，檢查非坐標相等維上另一轉發端口的SR中的標識是否為11，不為11則從該方向轉發，否則從剩余的非數據進入方向轉發。路由算法流程如圖3所示。

4 實驗結果

4.1 實驗模型

在基于OPNET編制的一個NoC仿真平臺[10]進行了5×5 2D-Mesh結構的實驗，路由器的每個端口具有3條虛通道。在實驗中，通過評估本文提出的路由算法和參考文獻[4]提出的可重構容錯路由算法的時延，比較算法的優劣。本文采用的是轉置模式的通信，也就是（i，j）節點的數據發送給（5－i－1，5－j－1），這是由于該轉發模式更加接近于NoC的實際通信[11]。

NoC中的節點情況可以分為以下幾種：

·NoC中的邊角節點，如圖4中R1類節點；

·NoC中的邊沿節點，如圖4中R2類節點；

·NoC中靠近中心位置的節點，如圖4中R3類節點；

·NoC中的中心節點，如圖4中R4類節點。

本文分別做了NoC沒有出現故障和故障出現在上述4種位置時的時延比較實驗。邊角節點R1選取（0，0）節點，邊沿節點 R2選取（0，2）節點，靠近中心位置節點 R3選擇（1，1）節點，中心節點 R4 為（2，2）。

本文用平均時延評價網絡的性能，下面對這項指標做具體的說明。

數據包時延：從數據包進入網絡到數據包尾部離開網絡的這段時間的差。在網絡中數據包時延主要由以下3部分組成。

其中，Tdelay表示數據包的傳輸時延，Bdelay表示路由器內部隊列的緩沖時延，Ldelay表示鏈路的傳播時延。由于相對于傳輸時延和緩沖時延，鏈路傳播時延要小得多，因此在仿真中忽略了鏈路傳播時延，即設Ldelay=0。

平均時延：將所得到的各個數據包的時延累加取平均值。

其中pk_num定義為接收到的數據包個數。

4.2 實驗結果

當NoC無故障節點時，本文提出的路由算法和參考文獻[4]提出的路由算法的平均時延比較如圖5所示。

從圖5可以看出，當無故障節點時，在路由時延上本文提出的路由算法略高于參考文獻[4]提出的路由算法。在無故障時，本文提出的路由算法性能略差于參考文獻[4]提出的路由算法性能。

當故障節點出現在NoC中坐標為（0，0）節點處時，本文提出的路由算法和參考文獻[4]提出的路由算法的平均時延比較如圖6所示。

從圖6可以看出，當故障出現在節點（0，0）處時，在路由時延上參考文獻[4]提出的路由算法要小于本文提出的路由算法。這是因為（0，0）節點為NoC中的邊角位置，傳輸數據時使用該節點的頻率不是很高，所以該節點故障對數據時延的影響很小。

圖7和圖 8所示為當故障節點分別位于（0，2）和（1，1）時，本文提出的路由算法和參考文獻[4]提出的路由算法的平均時延比較。

從圖 7 和圖 8 可以看出，節點（0，2）和（1，1）損壞時，在路由時延上本文提出的路由算法小于參考文獻[4]提出的路由算法。這是因為在路由數據時使用該節點的次數增多，不同的容錯路由算法對數據傳輸時延的影響增大，導致時延的差異增大。

當故障節點出現在NoC中坐標為（2，2）處時，本文提出的路由算法和參考文獻[4]提出的路由算法平均時延比較如圖9所示。

從圖9可以看出，當故障節點出現在（2，2）處時，在路由時延上本文提出的路由算法明顯小于參考文獻[4]提出的路由算法。這是由于節點（2，2）處于NoC模型的中心位置，數據傳輸時使用該節點的頻率很高，因此容錯路由算法對數據時延的影響更加明顯。

由上述實驗結果可以得出，與參考文獻[4]提出的路由算法相比，本文提出的路由算法在保障NoC通信的情況下具有更小的傳輸時延，因此本文提出的路由算法具有更高的通信性能，更加適合NoC的容錯通信。

5 結束語

NoC作為一種新的SoC體系結構，已逐漸成為研究的熱點。本文提出了基于NoC的動態容錯路由算法，該算法通過重構NoC中節點每個端口的輸出狀態寄存器，使SR能夠標識出現故障的路由器或者鏈路，在路由過程中不使用這些出現故障的路由器和鏈路，從而保證NoC的通信。

參考文獻

1 Benini L,Micheli G D.Networks on chips:a new SoC paradigm.IEEE Transactions on Computers,2002,35（1）:70～78

2 Daly W J,TowlesB.Route packets,notwires:on-chip interconnection networks.In:the 38rd ACM/IEEE Design Automation Conference,Las Vegas,NV,USA,June 2001

3 高明倫，杜高明.NoC：下一代集成電路主流設計技術.微電子學,2006,36(4):461～466

4 Zhang Z,GreinerA,Taktak S.A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh network-on-chip.In:the 45rd ACM/IEEE Design Automation Conference,Anaheim,California,USA,June 2008

5 Yong-Bin Kim.Faulttolerantsource routing fornetworkon-chip.In:Proceedings of IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems 2007,Rome,Italy,Sept 2007

6 張磊,李華偉,李曉維.用于片上網絡的容錯通信算法.計算機輔助設計與圖形學學報,2007,19(4):508～514

7 Murali S,Atienza D,Benini L,et al.A multi-path routing strategy with guaranteed in-order packet delivery and fault-tolerance for networks on chip.In:the 43rd ACM/IEEE Design Automation Conference,July 2006

8 Li M,Zeng Q A,Jone W B.DyXY-a proximity congestionaware deadlock-free dynamic routing method for network on chip.In:the 43rd ACM/IEEE Design Automation Conference,July 2006

9 Xiang D,Zhang Y,Pan Y.Practical deadlock-free fault-tolerant routing in meshes based on the planar network fault model.IEEE Transactions on Computers,2009,58(5):620～633

10 Wu Ning,Ge Fen,Wang Qi.Simulation and performance analysis of network on chip architectures using OPNET.In:the 7th International Conference on ASIC,Guilin,China,October 2007

11 Daneshtalab M,Sobhani A,Kusha A A,et al.NoC hot spot minimization using AntNetdynamic routing algorithm.In:Proceedings of 17th International Conference on Applicationspecific Systems,Architectures and Processors (ASAP 2006),Colorado,USA,September 2006