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

趙巍，才華，吳劍飛

（長春理工大學，長春　130022）

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

趙巍，才華，吳劍飛

（長春理工大學，長春130022）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義四：ping命令的測試超時時間

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

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

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

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

步驟二：2D-mesh拓撲片上網(wǎng)絡(luò)的初始化；

步驟三：當m×n的2D-mesh拓撲片上網(wǎng)絡(luò)開始一個以任意一個路由節(jié)點A為起點并以另外一個任意路由節(jié)點B為終點的數(shù)據(jù)傳送任務(wù)時，將路由節(jié)點A稱為數(shù)據(jù)源節(jié)點，并將目標路由節(jié)點B稱為目標節(jié)點；

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

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

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

圖2　算法總體流程圖

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

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

若節(jié)點X為非通節(jié)點，則由本算法確定的數(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ù)微片。報頭微片、數(shù)據(jù)微片以及反饋包的具體結(jié)構(gòu)如圖4所示。

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

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

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

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

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

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

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

2.3實驗結(jié)果分析

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

圖5　低負載情況相同的失效率下不同算法延時的比較

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

圖6　高負載情況下相同的失效率下不同算法延時的比較

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

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

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

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

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

2.4性能比較

2.4.1延時比較

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

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

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

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

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

3　結(jié)論

2D-Mesh網(wǎng)絡(luò)拓撲結(jié)構(gòu)在設(shè)計中具有實現(xiàn)簡單、規(guī)則性、設(shè)計成本低、便于操控等優(yōu)勢，所以在片上網(wǎng)絡(luò)中應(yīng)用這一結(jié)構(gòu)很有優(yōu)勢?；?D-Mesh網(wǎng)絡(luò)拓撲結(jié)構(gòu)提出了一種新的容錯算法。利用轉(zhuǎn)彎模型和邊緣路由的路由表信息實現(xiàn)了一種低成本、結(jié)構(gòu)簡單、功耗消耗低、占用內(nèi)存小的可重構(gòu)容錯路由算法。該算法實用性強、容錯性能高、硬件開銷少。在網(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］.北京：清華大學，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

趙巍（1980-），男，博士研究生，工程師，E-mail：zhaowei@cust.edu.cn