趙巍，才華，吳劍飛

（長(zhǎng)春理工大學(xué)，長(zhǎng)春　130022）

一種片上網(wǎng)絡(luò)容錯(cuò)路由算法

趙巍，才華，吳劍飛

（長(zhǎng)春理工大學(xué)，長(zhǎng)春130022）

為解決片上網(wǎng)絡(luò)的可靠性問題，以2D-Mesh拓?fù)浣Y(jié)構(gòu)為基礎(chǔ)，將片上網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為邊緣節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)兩大類，并分別針對(duì)這兩大類節(jié)點(diǎn)的各自特征有針對(duì)性地提出相對(duì)快捷的路徑?jīng)Q策模型和轉(zhuǎn)彎模型，從而幫助路由節(jié)點(diǎn)更為快捷地確定符合自身特征的當(dāng)前任務(wù)最佳傳送路徑，算法大幅縮減了重復(fù)運(yùn)算時(shí)間，并減少了數(shù)據(jù)計(jì)算量。通過容錯(cuò)偏轉(zhuǎn)路由算法進(jìn)行仿真實(shí)驗(yàn)，應(yīng)用本文算法和XY路由算法、Flooding路由算法進(jìn)行比較分析，實(shí)驗(yàn)結(jié)果證明算法可以有效的避免產(chǎn)生死鎖和擁塞，具有很好的傳輸效率。

片上網(wǎng)絡(luò)；容錯(cuò)方法；轉(zhuǎn)彎模型

隨著集成電路工藝的不斷進(jìn)步，系統(tǒng)芯片的規(guī)模不斷增大，基于片上系統(tǒng)（SoC）［1，2］的芯片設(shè)計(jì)非常復(fù)雜，而且傳統(tǒng)的SoC體系結(jié)構(gòu)及其設(shè)計(jì)方法在多知識(shí)產(chǎn)權(quán)（IP）核的超復(fù)雜系統(tǒng)中遇到了技術(shù)瓶頸。從2000年開始，業(yè)界提出一種全新系統(tǒng)芯片設(shè)計(jì)模型—片上網(wǎng)絡(luò)（NoC）［3，4］，將計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)移植到芯片設(shè)計(jì)中來(lái)，徹底解決多IP模塊體系結(jié)構(gòu)中的問題。

本文基于2D-Mesh拓?fù)浣Y(jié)構(gòu)提出一種新的算法，展現(xiàn)一個(gè)可以在二維網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)容錯(cuò)的路由算法。

1　基于2D-Mesh拓?fù)浣Y(jié)構(gòu)的片上網(wǎng)絡(luò)偏轉(zhuǎn)容錯(cuò)路由算法

片上網(wǎng)絡(luò)是有冗余特性的一種結(jié)構(gòu)，在傳遞信息的過程，節(jié)點(diǎn)間信息傳遞都有很多不同路徑，這為研究路由容錯(cuò)算法提供了條件。本算法所要解決的技術(shù)問題是提供一種結(jié)構(gòu)簡(jiǎn)單、功耗低、占用內(nèi)存小的可重構(gòu)容錯(cuò)路由算法。

2D-Mesh片上網(wǎng)絡(luò)的容錯(cuò)路由算法需要滿足以下特點(diǎn)：

低成本：硬件成本產(chǎn)生的可重構(gòu)性必須占總路由器硅面積很小的百分比。

通用性：可重構(gòu)路由算法必須可以應(yīng)用在任何出現(xiàn)故障的路由（或出現(xiàn)故障的區(qū)域）拓?fù)浣Y(jié)構(gòu)中。

可拓展：重構(gòu)的硬件必須是獨(dú)立的二維網(wǎng)格大小。

無(wú)死鎖：任何可重構(gòu)的路由算法必須無(wú)死鎖。確定性：確保按次序發(fā)送屬性，數(shù)據(jù)是否可順利從起始點(diǎn)發(fā)送到終點(diǎn)。

1.1容錯(cuò)偏轉(zhuǎn)路由算法相關(guān)定義

定義一：相鄰節(jié)點(diǎn)

在二維網(wǎng)格上，一個(gè)節(jié)點(diǎn)（X，Y）有四個(gè)直接相鄰節(jié)點(diǎn)（東，南，西，北方向各一個(gè)），和四個(gè)間接相鄰節(jié)點(diǎn)（東北，西北，東南，西南方向各一個(gè)）。本文認(rèn)為這8個(gè)節(jié)點(diǎn)是相鄰節(jié)點(diǎn)。

定義二：內(nèi)部路由節(jié)點(diǎn)

在2D-Mesh網(wǎng)絡(luò)結(jié)構(gòu)中，如果與一個(gè)節(jié)點(diǎn)相鄰的節(jié)點(diǎn)有4個(gè)，則該節(jié)點(diǎn)叫做內(nèi)部路由節(jié)點(diǎn)（如圖1），6、7、10、11即為內(nèi)部路由節(jié)點(diǎn)。

定義三：邊緣路由節(jié)點(diǎn)

在2D-Mesh網(wǎng)絡(luò)結(jié)構(gòu)中，如果與一個(gè)節(jié)點(diǎn)相鄰的節(jié)點(diǎn)不大于三個(gè)，則將這種最多有三個(gè)相鄰路由節(jié)點(diǎn)的節(jié)點(diǎn)叫做邊緣路由節(jié)點(diǎn)（如圖1），1、2、3、4等即為邊緣路由節(jié)點(diǎn)。

圖14　*4 2D-Mesh結(jié)構(gòu)

定義四：ping命令的測(cè)試超時(shí)時(shí)間

定義計(jì)量時(shí)間的確定常數(shù)T，設(shè)置當(dāng)前路由節(jié)點(diǎn)對(duì)其相臨節(jié)點(diǎn)發(fā)送ping命令測(cè)試包。若在T時(shí)間范圍內(nèi)，測(cè)試包發(fā)送回源節(jié)點(diǎn)，則當(dāng)前路由器傳送的路徑是通路，否則是非通路。

1.2容錯(cuò)偏轉(zhuǎn)路由算法實(shí)現(xiàn)具體描述

該方法的具體步驟如下所示：

步驟一：為本容錯(cuò)偏轉(zhuǎn)路由算法定義基礎(chǔ)信息，分別定義變量，包括：內(nèi)部路由節(jié)點(diǎn)、邊緣路由節(jié)點(diǎn)和ping命令的測(cè)試超時(shí)時(shí)間并定義基礎(chǔ)X-Y傳輸規(guī)則；

步驟二：2D-mesh拓?fù)淦暇W(wǎng)絡(luò)的初始化；

步驟三：當(dāng)m×n的2D-mesh拓?fù)淦暇W(wǎng)絡(luò)開始一個(gè)以任意一個(gè)路由節(jié)點(diǎn)A為起點(diǎn)并以另外一個(gè)任意路由節(jié)點(diǎn)B為終點(diǎn)的數(shù)據(jù)傳送任務(wù)時(shí)，將路由節(jié)點(diǎn)A稱為數(shù)據(jù)源節(jié)點(diǎn)，并將目標(biāo)路由節(jié)點(diǎn)B稱為目標(biāo)節(jié)點(diǎn)；

步驟四：內(nèi)部路由節(jié)點(diǎn)的數(shù)據(jù)傳輸過程；

步驟五：邊緣路由節(jié)點(diǎn)的數(shù)據(jù)傳輸過程。

具體應(yīng)用的總體流程如圖2所示。若路由節(jié)點(diǎn)X未故障或擁塞，則以內(nèi)部數(shù)據(jù)源節(jié)點(diǎn)M為起點(diǎn)數(shù)據(jù)傳送任務(wù)將順次經(jīng)過路由節(jié)點(diǎn)C、D和X，并最終完成整個(gè)傳送任務(wù)過程，其傳送路徑遵循基礎(chǔ)X-Y傳輸規(guī)則，在圖3中以實(shí)線的折線箭頭示意。

圖2　算法總體流程圖

圖3　當(dāng)前的內(nèi)部數(shù)據(jù)源節(jié)點(diǎn)M至目標(biāo)節(jié)點(diǎn)B的繞行原理示意圖

圖4　數(shù)據(jù)包結(jié)構(gòu)

若節(jié)點(diǎn)X為非通節(jié)點(diǎn)，則由本算法確定的數(shù)據(jù)傳送繞行路徑由圖3中的虛線的折線箭頭示意。

2　仿真分析

2.1仿真數(shù)據(jù)設(shè)置

在片上網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)有發(fā)送端發(fā)送的數(shù)據(jù)包和接收端接收后發(fā)送的反饋包。發(fā)送端中將發(fā)送的數(shù)據(jù)包拆分為兩種微片，分別是包頭微片和數(shù)據(jù)微片。報(bào)頭微片、數(shù)據(jù)微片以及反饋包的具體結(jié)構(gòu)如圖4所示。

實(shí)驗(yàn)應(yīng)用這種數(shù)據(jù)包結(jié)構(gòu)，將數(shù)據(jù)包分成一個(gè)個(gè)微片，組包傳輸數(shù)據(jù)，對(duì)微片進(jìn)行計(jì)數(shù)，將地址等相關(guān)信息按照規(guī)定的包頭微片格式組裝到包頭微片中，然后將有效數(shù)據(jù)按規(guī)定的數(shù)據(jù)微片格式組裝到數(shù)據(jù)微片中，最后將所有的微片進(jìn)行編碼存儲(chǔ)。

2.2仿真環(huán)境設(shè)置

主要參數(shù)配置如表1所示。

表1　仿真平臺(tái)參數(shù)設(shè)置

實(shí)驗(yàn)構(gòu)造了10×10的2D-Mesh拓?fù)浣Y(jié)構(gòu)，為設(shè)置虛擬通道，有100個(gè)通信節(jié)點(diǎn)，數(shù)據(jù)可通過這些節(jié)點(diǎn)達(dá)到傳輸目的。并采用XY路由算法，F(xiàn)looding路由算法和本文的DTM容錯(cuò)路由算法進(jìn)行比較。每一種仿真實(shí)驗(yàn)運(yùn)行10次，以減少偏差，使結(jié)果更精確。實(shí)驗(yàn)前需設(shè)置源節(jié)點(diǎn)和目的節(jié)點(diǎn)所在位置。

分組數(shù)據(jù)根據(jù)字節(jié)數(shù)和占全部分組的百分比確定。據(jù)統(tǒng)計(jì)結(jié)果：30字節(jié)長(zhǎng)度的數(shù)據(jù)包占30%，40字節(jié)的占40%，500字節(jié)的占20%，2000字節(jié)的占的10%。失效率是指失效路由占所有路由的百分比。根據(jù)不同失效率狀態(tài)下的比較，可清晰地知道哪一種算法更有利于路由器的容錯(cuò)性能。

仿真流量模型采用低負(fù)載條件下的（即均勻分布）流量模型和高負(fù)載（即集中分布）條件下的流量模型來(lái)判斷。低負(fù)載流量模型是指：輸入較少的數(shù)據(jù)包流量，網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)傳遞信息的數(shù)據(jù)包都比較小，傳遞完信息后，每個(gè)節(jié)點(diǎn)有空閑時(shí)間等待下一節(jié)點(diǎn)傳輸過來(lái)的信息。高負(fù)載流量模型是指：數(shù)據(jù)運(yùn)行傳輸過程中，所有的節(jié)點(diǎn)向一個(gè)節(jié)點(diǎn)傳輸信息，以檢查每一個(gè)節(jié)點(diǎn)是否能夠順利到達(dá)目的節(jié)點(diǎn)，有故障路由的情況下，是否可以繞過故障節(jié)點(diǎn)同樣達(dá)到可靠傳輸。實(shí)驗(yàn)采用平均時(shí)延和網(wǎng)絡(luò)吞吐量來(lái)判斷整體的網(wǎng)絡(luò)數(shù)據(jù)傳輸性能。

2.3實(shí)驗(yàn)結(jié)果分析

仿真結(jié)果如圖5至圖8所示。采用不同容錯(cuò)路由算法時(shí)，隨路由器失效率的增加，網(wǎng)絡(luò)負(fù)載情況的改變，網(wǎng)絡(luò)延時(shí)（cycles）和網(wǎng)絡(luò)吞吐量（flits/wireless router/cycle）方面各自有變化。圖中各曲線分別代表對(duì)應(yīng)的容錯(cuò)路由算法。

圖5　低負(fù)載情況相同的失效率下不同算法延時(shí)的比較

失效率為0時(shí)，三種情況延時(shí)均為0。隨失效率增加，XY路由算法的延時(shí)增加比較快，失效率達(dá)到3%時(shí)達(dá)到最高值，失效率為4%時(shí)，出現(xiàn)擁塞，由于信息停止傳輸，所以也就沒有所謂的延時(shí)。Flooding路由算法在有一定的失效率情況下同樣能將信息有效的傳輸，但當(dāng)失效率達(dá)到4%時(shí)，延時(shí)隨之增加很快，所以Flooding路由算法對(duì)于延時(shí)控制不佳。DTM路由算法在低負(fù)載的情況下優(yōu)勢(shì)明顯，當(dāng)失效率在3%時(shí)，DTM算法還是能夠穩(wěn)步的傳遞可靠信息，當(dāng)失效率達(dá)到6%的時(shí)候，DTM路由算法還是在一定延時(shí)狀態(tài)下將信息順利的從源節(jié)點(diǎn)傳遞到目的節(jié)點(diǎn)。

圖6　高負(fù)載情況下相同的失效率下不同算法延時(shí)的比較

相對(duì)于低負(fù)載情況，XY路由算法在失效率為2%的時(shí)候就已經(jīng)達(dá)到飽和狀態(tài)，信息無(wú)法繼續(xù)傳遞。Flooding路由算法在失效率為3%時(shí)延時(shí)開始迅速增加，最終每一個(gè)路由節(jié)點(diǎn)均達(dá)到飽和無(wú)法傳輸信息。而DTM路由算法在高負(fù)載的情況下只是比低負(fù)載時(shí)在失效率相同的情況增加了一些延時(shí)，每一個(gè)數(shù)據(jù)包都能達(dá)到有效的傳輸目的。

圖7　低負(fù)載情況相同的失效率下不同算法吞吐量的比較

在失效率為0的情況下，三種算法網(wǎng)絡(luò)吞吐量差不多。隨失效率的增加，XY路由算法的網(wǎng)絡(luò)吞吐量在失效率達(dá)到3%時(shí)明顯下降很快，網(wǎng)絡(luò)吞吐量快速降低。Flooding路由算法在達(dá)到3%時(shí)網(wǎng)絡(luò)吞吐量還算正常，但隨著網(wǎng)絡(luò)繼續(xù)傳遞信息，當(dāng)失效率達(dá)到4%時(shí)，網(wǎng)絡(luò)吞吐量也急劇下降。DTM路由算法無(wú)論是在失效率達(dá)到3%、4%或以上的情況都有相對(duì)其他兩種算法較高的網(wǎng)絡(luò)吞吐量，能在容錯(cuò)的基礎(chǔ)上實(shí)現(xiàn)信息的有效傳輸。

圖8　高負(fù)載情況相同的失效率下不同算法吞吐量的比較

由于負(fù)載較高，開始時(shí)XY路由的網(wǎng)絡(luò)吞吐量就相對(duì)較低。Flooding路由算法相對(duì)DTM路由算法較低，說明高負(fù)載失效率為零的情況下Flooding路由算法也會(huì)受到影響，同時(shí)，F(xiàn)looding路由算法和DTM路由算法與低負(fù)載的情況比較相同，區(qū)別就是Flooding路由算法在失效率和時(shí)間逐漸增強(qiáng)的時(shí)候吞吐量會(huì)達(dá)到飽和，信息也就不會(huì)繼續(xù)傳輸。而DTM路由算法在一般情況下能夠滿足有效傳輸信息。

2.4性能比較

2.4.1延時(shí)比較

在相同網(wǎng)絡(luò)負(fù)載環(huán)境下，3個(gè)數(shù)據(jù)傳輸算法均有不同的表現(xiàn)，在三種不同的網(wǎng)絡(luò)環(huán)境下設(shè)定相同的源節(jié)點(diǎn)和目的節(jié)點(diǎn)，開始的時(shí)候三種路由算法的延時(shí)大體相同，但隨著網(wǎng)絡(luò)負(fù)載的增加，可看出偏轉(zhuǎn)容錯(cuò)路由算法時(shí)延明顯比其他兩種方法低很多。

2.4.2網(wǎng)絡(luò)吞吐量比較

在相同網(wǎng)絡(luò)負(fù)載和失效率情況下，三種數(shù)據(jù)傳輸算法也有不同的網(wǎng)絡(luò)吞吐量，在低負(fù)載時(shí)開始相同，隨著失效率增加，DTM路由算法有明顯的優(yōu)勢(shì)。在高負(fù)載的情況下，DTM路由算法在一開始的網(wǎng)絡(luò)吞吐量就比其他兩種要高。綜上所述，在網(wǎng)絡(luò)吞吐量方面，DTM路由算法是一種比較有優(yōu)勢(shì)的容錯(cuò)偏轉(zhuǎn)路由算法。

圖5至圖8顯示，在不同網(wǎng)絡(luò)負(fù)載情況下，最開始無(wú)失效率的情況下，三種算法在延遲和吞吐量方面的差異不大。隨著失效率不斷增加，網(wǎng)絡(luò)負(fù)載的提高，各種路由算法對(duì)網(wǎng)絡(luò)性能都會(huì)產(chǎn)生不同的影響，2D-Mesh拓?fù)浣Y(jié)構(gòu)下的片上網(wǎng)絡(luò)偏轉(zhuǎn)容錯(cuò)路由算法優(yōu)勢(shì)明顯。上述對(duì)比結(jié)果表示，DTM路由算法在不同的數(shù)據(jù)流量模式，在性能上都有比較明顯的優(yōu)勢(shì)。能夠更好地解決網(wǎng)絡(luò)中出現(xiàn)的擁塞、死鎖等問題，在路由器出現(xiàn)故障的情況下，都會(huì)將信息傳遞到位，使網(wǎng)絡(luò)性能維持在一個(gè)良好的狀態(tài)。

通過上述實(shí)驗(yàn)，證明了2D-Mesh拓?fù)浣Y(jié)構(gòu)下的片上網(wǎng)絡(luò)偏轉(zhuǎn)容錯(cuò)路由算法可以實(shí)現(xiàn)數(shù)據(jù)的有效傳輸，當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障路由的時(shí)候，容錯(cuò)路由算法可以通過繞過故障的方式傳遞信息，即2D-Mesh拓?fù)浣Y(jié)構(gòu)下的片上網(wǎng)絡(luò)偏轉(zhuǎn)容錯(cuò)路由算法具有容錯(cuò)功能。

3　結(jié)論

2D-Mesh網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在設(shè)計(jì)中具有實(shí)現(xiàn)簡(jiǎn)單、規(guī)則性、設(shè)計(jì)成本低、便于操控等優(yōu)勢(shì)，所以在片上網(wǎng)絡(luò)中應(yīng)用這一結(jié)構(gòu)很有優(yōu)勢(shì)?；?D-Mesh網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)提出了一種新的容錯(cuò)算法。利用轉(zhuǎn)彎模型和邊緣路由的路由表信息實(shí)現(xiàn)了一種低成本、結(jié)構(gòu)簡(jiǎn)單、功耗消耗低、占用內(nèi)存小的可重構(gòu)容錯(cuò)路由算法。該算法實(shí)用性強(qiáng)、容錯(cuò)性能高、硬件開銷少。在網(wǎng)絡(luò)性能需求上，能夠滿足路由器之間的可靠性連接的需求。

［1］Ditomaso D，Kodi A，Kaya S，et al.IWise：Inter-router wireless scalable egress channels for Network-on-Chips（NoCs）architecture［C］.The 19th Annual System on High Performance Interconnects. IEEE，2011：11-18.

［2］ Chen X，Lu Z，Jantsch A，et al.Supporting distributedsharedmemoryonmulticorenetwork-onchips using a dual microcode controller［C］.ProceedingsofDesign，AutomationandTestinEurope Conference and Exhibition，2010：39-44.

［3］AisoposK，ChenCHO，PehLS.EnablingSystem-levelmodelingofvariation-inducedfaultsin networks-on-chips［C］.IEEEDesignAutomation Conference，2011：930-935.

［4］Ditomaso D，aha S，Kodi A，et al.Evaluation and performanceanalysisofenergyefficientwireless NoC architecture［C］.Midwest Symposium on Circuits&Systems，2012，59（5）：798-801.

［5］ Dumitras T，Marculescu R.On-chip stochastic communication［SoCapplications］［DB］.InProceedings of the Design，Automation and Test in Europe Conference and Exhibition（DATE’03）.2003：790-795.

［6］Tang M，Lin X.Network-on-chip routing algorithmsbybreakingcycles［C］.ICA3PP2010：163-173.

［7］Ganguly A，Pande PP，Belzer B.Crosstalk-aware channel coding schemes for energy efficient and reliable NOC interconnects［J］.IEEE Transactions on VeryLargeScaleIntegration（VLSI） Systems，2009，17（11）：1626-1639.

［8］ 張媛緩.片上互連網(wǎng)絡(luò)關(guān)鍵問題研究［D］.北京：清華大學(xué)，2012.

［9］Murali S，Theocharides T，Vijaykrishnan N，et al. Analysis of error recovery schemes for networks on chips［J］.IEEE Design Test of Computers 2005，22 （5）：434-442.

A Fault Tolerant Routing Algorithm for Network on Chip

ZHAO Wei，CAI Hua，WU Jianfei
（Changchun University of Science and Technology，Changchun 130022）

In order to solve the reliability of the on-chip network problems，the nodes of Network-on-Chip will be divided into two types which are edge node and internal nodes on the basis of 2D-Mesh topology structure，and according to the respective characteristics of two kinds of nodes puts forward relatively fast path decision-making model and turning model，helping routing node to determine the best way which is the current task and accordes with its own characteristics more quickly.This algorithm greatly reduces the repeated operation time，and reduces the amount of data calculation.By using fault-tolerant deflection routing algorithm to do simulation experiment，and proposed algorithm and the XY routing algorithm，flooding routing algorithm to do comparative analysis，the experimental results show that the proposed algorithm can avoid deadlock and congestion effectively and has great transmission efficiency.

Network-on-Chip；fault-tolerance approach；turning model

TN47

A

1672-9870（2015）06-0145-05

2015-12-21

趙?。?980-），男，博士研究生，工程師，E-mail：zhaowei@cust.edu.cn