一種片上網絡容錯路由算法

趙巍，才華，吳劍飛

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

一種片上網絡容錯路由算法

趙巍，才華，吳劍飛

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

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

片上網絡；容錯方法；轉彎模型

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

本文基于2D-Mesh拓撲結構提出一種新的算法，展現一個可以在二維網絡拓撲結構容錯的路由算法。

1　基于2D-Mesh拓撲結構的片上網絡偏轉容錯路由算法

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

2D-Mesh片上網絡的容錯路由算法需要滿足以下特點：

低成本：硬件成本產生的可重構性必須占總路由器硅面積很小的百分比。

通用性：可重構路由算法必須可以應用在任何出現故障的路由（或出現故障的區域）拓撲結構中。

可拓展：重構的硬件必須是獨立的二維網格大小。

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

1.1容錯偏轉路由算法相關定義

定義一：相鄰節點

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

定義二：內部路由節點

在2D-Mesh網絡結構中，如果與一個節點相鄰的節點有4個，則該節點叫做內部路由節點（如圖1），6、7、10、11即為內部路由節點。

定義三：邊緣路由節點

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

圖14　*4 2D-Mesh結構

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

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

1.2容錯偏轉路由算法實現具體描述

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

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

步驟二：2D-mesh拓撲片上網絡的初始化；

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

步驟四：內部路由節點的數據傳輸過程；

步驟五：邊緣路由節點的數據傳輸過程。

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

圖2　算法總體流程圖

圖3　當前的內部數據源節點M至目標節點B的繞行原理示意圖

圖4　數據包結構

若節點X為非通節點，則由本算法確定的數據傳送繞行路徑由圖3中的虛線的折線箭頭示意。

2　仿真分析

2.1仿真數據設置

在片上網絡中傳輸的數據有發送端發送的數據包和接收端接收后發送的反饋包。發送端中將發送的數據包拆分為兩種微片，分別是包頭微片和數據微片。報頭微片、數據微片以及反饋包的具體結構如圖4所示。

實驗應用這種數據包結構，將數據包分成一個個微片，組包傳輸數據，對微片進行計數，將地址等相關信息按照規定的包頭微片格式組裝到包頭微片中，然后將有效數據按規定的數據微片格式組裝到數據微片中，最后將所有的微片進行編碼存儲。

2.2仿真環境設置

主要參數配置如表1所示。

表1　仿真平臺參數設置

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

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

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

2.3實驗結果分析

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

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

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

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

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

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

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

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

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

2.4性能比較

2.4.1延時比較

在相同網絡負載環境下，3個數據傳輸算法均有不同的表現，在三種不同的網絡環境下設定相同的源節點和目的節點，開始的時候三種路由算法的延時大體相同，但隨著網絡負載的增加，可看出偏轉容錯路由算法時延明顯比其他兩種方法低很多。

2.4.2網絡吞吐量比較

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

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

通過上述實驗，證明了2D-Mesh拓撲結構下的片上網絡偏轉容錯路由算法可以實現數據的有效傳輸，當網絡中出現故障路由的時候，容錯路由算法可以通過繞過故障的方式傳遞信息，即2D-Mesh拓撲結構下的片上網絡偏轉容錯路由算法具有容錯功能。

3　結論

2D-Mesh網絡拓撲結構在設計中具有實現簡單、規則性、設計成本低、便于操控等優勢，所以在片上網絡中應用這一結構很有優勢。基于2D-Mesh網絡拓撲結構提出了一種新的容錯算法。利用轉彎模型和邊緣路由的路由表信息實現了一種低成本、結構簡單、功耗消耗低、占用內存小的可重構容錯路由算法。該算法實用性強、容錯性能高、硬件開銷少。在網絡性能需求上，能夠滿足路由器之間的可靠性連接的需求。

［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］ 張媛緩.片上互連網絡關鍵問題研究［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