一種高吞吐低延時(shí)NoC容錯(cuò)路由算法

韋良芬，張佑生，王勇

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

一種高吞吐低延時(shí)NoC容錯(cuò)路由算法

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

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

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

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

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

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

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

1 T-XY路由算法

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

1.1 算法原理

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

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

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

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

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

圖1 路由方向標(biāo)示Fig.1 Route direction flag

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

1.2 算法描述

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

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

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

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

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

算法如下：

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

2）進(jìn)行XY維序路由;

3）if(TTL＜=0)

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

4）路由開(kāi)始

(1)if(△X=0&&△Y=0)到達(dá)目的節(jié)點(diǎn)，發(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）類(lèi)似，但拐彎一個(gè)節(jié)點(diǎn)后使用YX算法向目標(biāo)節(jié)點(diǎn)路由。

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

if(check(X+)==good)

{channel=X+；進(jìn)行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）類(lèi)似。

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

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

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

2 T-XY算法性能仿真

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

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

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

圖4 時(shí)延比較曲線Fig.4 Latency com parison curves

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

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

3 結(jié)語(yǔ)

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

[1]葛芬.專(zhuān)用片上網(wǎng)絡(luò)設(shè)計(jì)關(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ù)和時(shí)鐘比率對(duì)片上網(wǎng)絡(luò)的影響[J].清華大學(xué)學(xué)報(bào)：自然科學(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]姚磊,蔡覺(jué)平,李贊,等.基于內(nèi)建自測(cè)技術(shù)的Mesh結(jié)構(gòu)NoC無(wú)虛通道容錯(cuò)路由算法[J].電子學(xué)報(bào),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

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

韋良芬（1975-），女，安徽舒城人，講師，研究方向?yàn)槠暇W(wǎng)絡(luò)、容錯(cuò)技術(shù)。