韋良芬，張佑生，王勇

(1.安徽三聯(lián)學(xué)院計算機科學(xué)與技術(shù)系，安徽合肥230601；2.合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽合肥230092；3.安徽工程大學(xué)計算機與信息學(xué)院，安徽蕪湖241000)

一種高吞吐低延時NoC容錯路由算法

韋良芬1,2，張佑生2，王勇3

(1.安徽三聯(lián)學(xué)院計算機科學(xué)與技術(shù)系，安徽合肥230601；2.合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽合肥230092；3.安徽工程大學(xué)計算機與信息學(xué)院，安徽蕪湖241000)

為了提高片上網(wǎng)絡(luò)（Network-on-Chip，NoC）系統(tǒng)的可靠性及故障情況下的網(wǎng)絡(luò)性能，基于轉(zhuǎn)彎模型（Turn Model）的思想對現(xiàn)有的XY路由算法進行了改進,提出了一種容錯路徑短，且在故障情況下具有信息均衡能力的無虛通道容錯路由算法（T-XY路由算法）。OPNET仿真結(jié)果表明，該算法與同類算法相比具有較好的吞吐及時延性能。

片上網(wǎng)絡(luò)；容錯路由；2Dmesh

隨著芯片制造技術(shù)的不斷發(fā)展，芯片系統(tǒng)制造工藝不斷升級，如元器件設(shè)計的精簡、電路集成方式密集度增加、電路工作頻率的提高以及電路工作電壓的降低等，導(dǎo)致芯片故障的因素亦隨之增多[1]；另外，芯片規(guī)模不斷擴大，特征尺寸減小、IP核的增多等也將增加片上網(wǎng)絡(luò)（Network-on-Chip，NoC）系統(tǒng)出現(xiàn)故障的概率[2]。因此，增加系統(tǒng)的容錯能力，提高系統(tǒng)的可靠性成為片上網(wǎng)絡(luò)系統(tǒng)的重點研究內(nèi)容之一?，F(xiàn)有的容錯方案中，通常存在容錯開銷較大、網(wǎng)絡(luò)流量不均衡等問題。

NoC容錯路由算法分為有虛通道技術(shù)和無虛通道技術(shù)2種類型。增加了虛通道技術(shù)的路由節(jié)點比無虛通道的路由節(jié)點需要多增加1至2個邏輯門，建立時延將近增加了1倍[3]。而NoC對功耗、面積及成本要求均非常嚴格，所以無虛通道技術(shù)更適合NoC要求。文獻[4]提出了一種無虛通道容錯路由算法，該算法可以用于解決單故障節(jié)點時的容錯問題，但卻存在繞行規(guī)律不強，網(wǎng)絡(luò)負載不均等問題；文獻[5]中無虛通道單故障節(jié)點的容錯路由算法復(fù)雜度較低，繞行規(guī)律性較強，但繞行環(huán)路上網(wǎng)絡(luò)負載較重；文獻[6]提出利用內(nèi)建自測機制（Built-in Self Test,BIST）獲取故障位置信息的一種適用于多故障節(jié)點的無虛通道容錯路由算法，但BIST所需的電路增加了NoC的面積，同時建立測試也需要時間。

本文利用XY路由算法在中低網(wǎng)絡(luò)流量情況下的高效性特點以及轉(zhuǎn)彎模型（Turn Model）的自適應(yīng)能力，在不增加額外硬件的情況下，提出了一種無虛通道容錯路由算法（T-XY路由算法）。

1 T-XY路由算法

本文T-XY路由算法是適用于2D_Mesh拓撲結(jié)構(gòu)的一種容錯路由算法。在網(wǎng)絡(luò)沒有故障的情況下采用傳統(tǒng)的XY路由算法進行路由，一旦遇到故障，則向離目標節(jié)點近的垂直方向轉(zhuǎn)彎路由，若相對于目標節(jié)點有2個相同距離的垂直節(jié)點，則根據(jù)不同方向優(yōu)先選擇指定的垂直節(jié)點進行路由。

1.1 算法原理

T-XY路由方向標示見圖1。路由算法中每個節(jié)點擁有一張實時記錄鄰居節(jié)點故障狀態(tài)的路由表。數(shù)據(jù)包的傳輸在路由過程中，若某個路由表記錄了下一個節(jié)點存在故障，則根據(jù)源節(jié)點和目的節(jié)點的位置關(guān)系，分為以下幾種情況避開故障。

1)源目的節(jié)點Y維坐標相等時，若向東或向西路由時遇到故障，則向其垂直方向拐彎路由一個節(jié)點（具有兩個垂直節(jié)點的情況下，向東路由時優(yōu)先判斷Y+，向西路由時優(yōu)先判斷Y-），再應(yīng)用XY路由算法路由到目標節(jié)點。

2)源目的節(jié)點X維坐標相等時，故障情況下，若具有兩個垂直節(jié)點，向北路由時優(yōu)先判斷X+，向南路由時優(yōu)先判斷X-，再使用先Y后X的路由方式（即YX路由）路由到目標節(jié)點。

3)目的節(jié)點位于源節(jié)點的東北方向時，若X維東向路由時遇到故障，則轉(zhuǎn)為YX路由；Y維北向再次遇到故障，則有轉(zhuǎn)為XY路由；路由到X維坐標相同時遇到故障，則轉(zhuǎn)向2；路由到Y(jié)維坐標相同遇到故障，則轉(zhuǎn)向1。

當目的節(jié)點位于源節(jié)點的東南、西北、西南等方向時，故障的處理情況與3原理基本相同。若(XS,YS)表示源節(jié)點的坐標，(XD,YD)表示目的節(jié)點的坐標，ΔX=XD-XS表示目的節(jié)點和源節(jié)點X軸方向相對偏移量，ΔY=YD-YS表示目的節(jié)點和源節(jié)點Y軸方向相對偏移量。則T-XY路由算法故障時的拐彎方法可用表1所示。

圖1 路由方向標示Fig.1 Route direction flag

表1 T-XY算法故障避讓方法Tab.1 Faultavoidancemethodsof T-XY algorithm

1.2 算法描述

算法描述中的相關(guān)參數(shù)說明：

1）布爾值good、bad表示鄰居狀態(tài)。good表示鄰居節(jié)點及鏈路狀態(tài)正常。bad表示鄰居節(jié)點及鏈路出現(xiàn)故障。

2）check（）函數(shù)用于判斷鄰居故障狀態(tài)，返回值為good或bad。

3）channel為所選擇的通道方向，其值的集合為{X+，X-，Y+,Y-}。具體方向設(shè)置如圖1所示。

4）TTL表示一個數(shù)據(jù)包的生命周期。當TTL遞減為0時，表示數(shù)據(jù)包傳送失敗。

算法如下：

1）收集相關(guān)狀態(tài)信息，填寫路由表;

2）進行XY維序路由;

3）if(TTL＜=0)

{維序路由失敗，銷毀數(shù)據(jù)包，釋放鏈路和緩存資源}

4）路由開始

(1)if(△X=0&&△Y=0)到達目的節(jié)點，發(fā)送數(shù)據(jù)包到本地處理器，路由結(jié)束;

(2)if（△X!=0&&△Y=0），算法偽代碼為：

①if（△X＞0&&△Y==0）

if(check(X+)==good)XY路由；

else if(check(Y+)==good)

{channel=Y+;△Y++;XY路由；} else if(check(Y-)==good)

{channel=Y-;△Y--;XY路由；}

else路由失敗，轉(zhuǎn)向3；

②if(△X＜0&&△Y==0)

if(check(X-)==good)XY路由；

else if(check(Y-)==good) {channel=Y-;△Y-;XY路由；}

else if(check(Y+)==good)

{channel=Y+;△Y++;XY路由；}

else路由失敗，轉(zhuǎn)向3；

(3)if（△X==0&&△Y!=0），與（2）類似，但拐彎一個節(jié)點后使用YX算法向目標節(jié)點路由。

(4)if（△X＞0&&△Y＞0），算法偽代碼為：

if(check(X+)==good)

{channel=X+；進行XY路由；

if(check(Y+)==bad）轉(zhuǎn)向（3）}

else{channel=Y+；YX路由；

if（check(Y+)==bad）

{channel=X+；轉(zhuǎn)向（4）；}

else if（check(X+)==bad）轉(zhuǎn)向（2）；}

△X＞0&&△Y＜0;△X＜0&&△Y＞0;△X＜0&&△Y＜0等幾種情況的偽代碼與（4）類似。

T-XY路由算法中無故障時采用XY路由算法進行路由，遇到故障時，采用容錯方案將數(shù)據(jù)包正確傳送到目的節(jié)點。因此，無故障時不會影響網(wǎng)絡(luò)的性能。而在故障的情況下，除了源目的節(jié)點在一條直線上會略微增加數(shù)據(jù)的傳輸路徑之外，其他情況的容錯路徑仍然是兩節(jié)點間的最短路徑。另外，該算法不需要增加額外的硬件開銷。

圖2所示為T-XY路由算法源節(jié)點和目的節(jié)點在不同位置關(guān)系情況下避讓故障節(jié)點的示例。當源節(jié)點S（3,2）向其東北方向的目的節(jié)點D1（1,4）發(fā)送數(shù)據(jù)時，意向節(jié)點（3,3）為故障節(jié)點，則路由意向立即轉(zhuǎn)為其垂直且朝向目標的北向節(jié)點（2,2）路由，接著應(yīng)該向節(jié)點（1,2）路由，但節(jié)點（1,2）也為故障節(jié)點，固又轉(zhuǎn)向其垂直且朝向目標的節(jié)點（2,3），并沿著東向繼續(xù)路由，直到與目標節(jié)點Y維坐標相同再轉(zhuǎn)為北向路由。所以源節(jié)點（3,2）向其東北方向的目的節(jié)點（1,4）發(fā)送數(shù)據(jù)，并遇到（3,3）和（1, 2）兩個故障節(jié)點的情況下，T-XY路由算法的路由路徑為：（3,2）→（2,2）→（2,3）→（2,4）→（1,4）。此路徑仍然為源目的節(jié)點間的最短路徑。從圖3可以看出，當源節(jié)點和目標節(jié)點不在同一直線上時，即使遇到多處故障，T-XY容錯路徑仍然是最短路徑，但當源節(jié)點和目標節(jié)點在同一直線上時遇到一個故障將會增加2個節(jié)點的路徑長度。

圖2 T-XY路由算法實例Fig.2 T-XY routing algorithm instance

2 T-XY算法性能仿真

延時和吞吐量是衡量片上網(wǎng)絡(luò)性能的兩個重要參數(shù)[7]。本文利用OPNET仿真平臺對T-XY容錯路由算法進行仿真，并與文獻[8]提出的容錯算法分別進行仿真比較，從而驗證T-XY算法故障情況下的吞吐率和延時性能。文獻[8]提出的算法是針對2D_Mesh結(jié)構(gòu)中單故障節(jié)點的容錯路由算法，在無故障區(qū)域，該算法也使用XY算法進行路由，但在故障區(qū)域，繞行環(huán)路上的負載較重。

仿真中搭建了一個包含6×6個節(jié)點的2D_Mesh結(jié)構(gòu)的網(wǎng)絡(luò)。為了驗證算法在故障情況下的網(wǎng)絡(luò)性能，人為設(shè)置了多處故障節(jié)點。網(wǎng)絡(luò)仿真在蟲孔交換機制和均勻流量模式下進行測試；如圖3為文獻[8]容錯路由算法和T-XY容錯路由算法在相同環(huán)境下的吞吐量對比曲線，圖4為它們相同環(huán)境下的時延性能對比曲線。

圖3 吞吐量比較曲線Fig.3 Throughput com parison curves

圖4 時延比較曲線Fig.4 Latency com parison curves

從圖3吞吐量曲線中可以看出在相同的網(wǎng)絡(luò)環(huán)境下，T-XY容錯路由算法故障的情況下具有較好吞吐性能，從輸入率為0.1開始，T-XY算法相對于文獻[8]算法來說，能實現(xiàn)更多的數(shù)據(jù)傳輸，因為T-XY算法在容錯的時候不僅不會增加網(wǎng)絡(luò)的擁塞程度，而且對網(wǎng)絡(luò)的擁塞狀況還具有一定的調(diào)節(jié)作用；從圖4的時延曲線中可以看出，T-XY相對于文獻[8]的算法來說具有更好的時延特性，因為T-XY算法除了源目的節(jié)點同在一條直線時容錯具有繞道現(xiàn)象外，其他容錯路徑仍然為兩節(jié)點間的最短路徑。

T-XY容錯路由算法不僅彌補了XY路由缺乏容錯能力的不足，而且容錯時根據(jù)源目的節(jié)點的相對位置采用不同的拐彎方式，對網(wǎng)絡(luò)的擁塞狀況也具有一定調(diào)節(jié)作用。同時容錯帶來的能耗和開銷也相對較低。

3 結(jié)語

本文結(jié)合XY路由算法及轉(zhuǎn)彎模型的思想，基于2D_Mesh拓撲結(jié)構(gòu)，提出了一種新的容錯路由算法——T-XY路由算法。該算法設(shè)計簡單，基本沒有額外的硬件開銷。通過OPNET的仿真結(jié)果表明該算法具有高吞吐、低時延的特點，完全適合NoC的設(shè)計需求。

[1]葛芬.專用片上網(wǎng)絡(luò)設(shè)計關(guān)鍵技術(shù)研究[D].南京：南京航空航天大學(xué),2010.

[2]SeyrafiM,Asad A,ZonouzA E,etal.A new low cost fault tolerantsolution formesh based NoCs[C]//2010 InternationalConference on Electronicsand Information Engineering.Piscataway:IEEE,2010:207-213.

[3]林世俊,蘇厲,金德鵬,等.虛通道數(shù)和時鐘比率對片上網(wǎng)絡(luò)的影響[J].清華大學(xué)學(xué)報：自然科學(xué)版,2009,49(1):86-89.

[4]Duan X M,Sun X M.Fault-tolerant routing in A PRDT(2,1)-based NoC[C]//2010 2nd International Conference on Computer Engineering and Technology.Piscataway:IEEE,2010：506-510.

[5]Zhang Z,GreinerA,Taktak S.A reconfigurable routing algorithm fora fault-tolerant2D-mesh network-on-chip[C]//45th ACM/IEEE Design Automation Conference.Piscataway:IEEE,2008:441-446.

[6]姚磊,蔡覺平,李贊,等.基于內(nèi)建自測技術(shù)的Mesh結(jié)構(gòu)NoC無虛通道容錯路由算法[J].電子學(xué)報,2012,40(5):983-989.

[7]Cai JP,Huang G,Wang S,etal.OPNEC-sim:an efficientsimulation tool fornetwork-on-chip communication and energy performance analysis[J]//InternationalConference on Solid-State and Integrated CircuitTechnology 2010.Piscataway:IEEE,2010:1892-1894.

[8]Yusuke F,Masaru F.A fault-tolerant routing algorithm for network on chip withoutvirtual channels[C]//2009 IEEE International Symposium on Defectand FaultTolerance in VLSISystems.Piscataway:IEEE,2009:313-321.

責(zé)任編輯：丁吉海

AHigh-Throughputand Low-Latency TolerantRouting Algorithm for NoC

WEILiangfen1,2,ZHANG Yousheng2,WANG Yong3
(1.Departmentof Computer Science and Technology,Anhui Sanlian University,Hefei230601,China;2.School of Computer and Information,Hefei University of Technology,Hefei 230092,China;3.School of Computer and Information,AnhuiPolytechnic University,Wuhu 241000,China)

To improve reliability and network performance under fault conditions for the Network-on-Chip (Network-on-Chip,NoC)system,the idea based on Turn Modelmakes improvement of the current XY routing algorithm and puts forward a no virtual channel fault-tolerant routing algorithm(T-XY Routing A lgorithm).The algorithm has the short fault-tolerantpath and theability to balance the information.TheOPNET simulation results show that thisalgorithm hasbetterperformanceof throughputand latency compared with the sim ilaralgorithms.

network-on-chip;fault-tolerant routing;2Dmesh

TP302

A

10.3969/j.issn.1671-7872.2014.02.019

1671-7872(2014)02-0195-04

2013-06-13

國家自然科學(xué)基金項目(61106037)；安徽高校自然科學(xué)重點項目（KJ2013A040）；安徽省質(zhì)量工程項目（2012jyxm589）

韋良芬（1975-），女，安徽舒城人，講師，研究方向為片上網(wǎng)絡(luò)、容錯技術(shù)。