基于片上網(wǎng)絡(luò)的容錯(cuò)通信方法*

歐陽一鳴，郭 凱，梁華國

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院 合肥 230009)

1 引言

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

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

·使用適當(dāng)?shù)膬?nèi)建自測試（BIST）機(jī)制探測出故障的路由器和鏈路；

·設(shè)計(jì)一種容錯(cuò)的、分布式、可重構(gòu)的路由算法，并在路由器中執(zhí)行；

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

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

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

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

2 容錯(cuò)模型

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

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

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

輸出端口狀態(tài)寄存器：在2D-Mesh結(jié)構(gòu)中，每個(gè)路由器存在4個(gè)輸出端口，4個(gè)輸出端口通過鏈路與下一個(gè)路由器相連，因此，在路由器內(nèi)設(shè)置一個(gè)8位的端口狀態(tài)寄存器用于標(biāo)識(shí)與4個(gè)端口相連的鏈路或者路由器的損壞狀態(tài)，每個(gè)端口對(duì)應(yīng)2位，其格式如圖2所示。

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

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

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

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

3 基于重構(gòu)的動(dòng)態(tài)容錯(cuò)路由算法

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

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

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

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

4.1 實(shí)驗(yàn)?zāi)Ｐ?/h3>

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

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

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

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

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

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

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

本文用平均時(shí)延評(píng)價(jià)網(wǎng)絡(luò)的性能，下面對(duì)這項(xiàng)指標(biāo)做具體的說明。

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

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

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

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

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

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

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

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

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

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

從圖 7 和圖 8 可以看出，節(jié)點(diǎn)（0，2）和（1，1）損壞時(shí)，在路由時(shí)延上本文提出的路由算法小于參考文獻(xiàn)[4]提出的路由算法。這是因?yàn)樵诼酚蓴?shù)據(jù)時(shí)使用該節(jié)點(diǎn)的次數(shù)增多，不同的容錯(cuò)路由算法對(duì)數(shù)據(jù)傳輸時(shí)延的影響增大，導(dǎo)致時(shí)延的差異增大。

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

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

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

5 結(jié)束語

NoC作為一種新的SoC體系結(jié)構(gòu)，已逐漸成為研究的熱點(diǎn)。本文提出了基于NoC的動(dòng)態(tài)容錯(cuò)路由算法，該算法通過重構(gòu)NoC中節(jié)點(diǎn)每個(gè)端口的輸出狀態(tài)寄存器，使SR能夠標(biāo)識(shí)出現(xiàn)故障的路由器或者鏈路，在路由過程中不使用這些出現(xiàn)故障的路由器和鏈路，從而保證NoC的通信。

參考文獻(xiàn)

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：下一代集成電路主流設(shè)計(jì)技術(shù).微電子學(xué),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)絡(luò)的容錯(cuò)通信算法.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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