歐陽一鳴，郭 凱，梁華國

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

1 引言

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

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

·使用適當?shù)膬冉ㄗ詼y試（BIST）機制探測出故障的路由器和鏈路；

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

·在NoC中設置配置總線，重構的數(shù)據(jù)通過配置總線分發(fā)到每個路由器中。

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

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

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

2 容錯模型

NoC是由控制網(wǎng)絡中數(shù)據(jù)傳輸?shù)穆酚善骱瓦B通片上系統(tǒng)中各IP核之間進行數(shù)據(jù)傳輸?shù)逆溌窐嫵傻木W(wǎng)絡結構。NoC 的拓撲多種多樣，有 2D-Mesh、torus、fat-tree等，本文采用的是2D-Mesh拓撲，如圖1所示（R表示路由器，IP表示IP核）。

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

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

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

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

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

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

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

3 基于重構的動態(tài)容錯路由算法

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

轉發(fā)率是指該方向上已經(jīng)轉發(fā)出去的數(shù)據(jù)包數(shù)目與該路由器所有轉發(fā)出去的數(shù)據(jù)包總數(shù)的比值，即：

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

4 實驗結果

4.1 實驗模型

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

NoC中的節(jié)點情況可以分為以下幾種：

·NoC中的邊角節(jié)點，如圖4中R1類節(jié)點；

·NoC中的邊沿節(jié)點，如圖4中R2類節(jié)點；

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

·NoC中的中心節(jié)點，如圖4中R4類節(jié)點。

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

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

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

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

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

其中pk_num定義為接收到的數(shù)據(jù)包個數(shù)。

4.2 實驗結果

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

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

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

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

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

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

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

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

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

5 結束語

NoC作為一種新的SoC體系結構，已逐漸成為研究的熱點。本文提出了基于NoC的動態(tài)容錯路由算法，該算法通過重構NoC中節(jié)點每個端口的輸出狀態(tài)寄存器，使SR能夠標識出現(xiàn)故障的路由器或者鏈路，在路由過程中不使用這些出現(xiàn)故障的路由器和鏈路，從而保證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 張磊,李華偉,李曉維.用于片上網(wǎng)絡的容錯通信算法.計算機輔助設計與圖形學學報,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