基于NoC的容錯路由算法

屈凌翔，劉海鵬，潘能智，趙寶功

（中國電子科技集團(tuán)公司第58研究所，江蘇 無錫 214035）

1 前言

隨著半導(dǎo)體工藝的不斷發(fā)展，芯片的集成度越來越高，規(guī)模也越來越大。傳統(tǒng)的基于總線結(jié)構(gòu)的片上系統(tǒng)（SoC）遇到了巨大的瓶頸，在系統(tǒng)的可擴(kuò)展性、時鐘的同步性、芯片的設(shè)計效率和能耗上均存在局限性，無法有效解決片上多用戶的同時通信問題。因此，找到一種新的解決方案來突破這層瓶頸成為各國專家學(xué)者們共同致力研究的問題。2000年，瑞典皇家技術(shù)學(xué)院等提出“Network-on-Chip”概念，把NoC 定義為一塊芯片上實(shí)現(xiàn)的，由交換開關(guān)網(wǎng)絡(luò)互連的計算資源、存儲資源以及I/O資源的片上網(wǎng)絡(luò)。片上網(wǎng)絡(luò)借鑒了計算機(jī)網(wǎng)絡(luò)的設(shè)計思想，將計算機(jī)網(wǎng)絡(luò)技術(shù)移植到芯片設(shè)計中來，在單個芯片上構(gòu)建一個微網(wǎng)絡(luò)。NoC的出現(xiàn)有效地解決了SoC總線結(jié)構(gòu)的局限性[1,2]，具有更高的帶寬[3]。NoC采用全局異步-局部同步（GALS）的通信機(jī)制, 從而很好地解決了全局同步所帶來的問題。NoC通過通信節(jié)點(diǎn)連接資源節(jié)點(diǎn)，每個資源節(jié)點(diǎn)只要符合片上通信協(xié)議即可，資源節(jié)點(diǎn)、通信節(jié)點(diǎn)和軟件可以獨(dú)立設(shè)計和驗證。

NoC設(shè)計的關(guān)鍵技術(shù)有：拓?fù)浣Y(jié)構(gòu)、交換機(jī)制、路由算法、服務(wù)質(zhì)量、擁塞控制和路由器結(jié)構(gòu)等。路由算法的優(yōu)劣和全局的性能以及片上網(wǎng)絡(luò)的穩(wěn)定性是密切相關(guān)的。確定性路由算法由于其唯一的路由路徑和簡單的邏輯，能夠帶來較好的網(wǎng)絡(luò)性能和較低的功耗，但它缺乏自適應(yīng)性和容錯能力[4～6]。自適應(yīng)路由算法能夠解決網(wǎng)絡(luò)堵塞問題，但它同樣缺乏容錯能力，降低了網(wǎng)絡(luò)的可靠性。本文提出了基于NoC的容錯路由算法，不僅能夠有效地解決片上網(wǎng)絡(luò)的堵塞問題，同時增強(qiáng)了片上網(wǎng)絡(luò)的可靠性。

2 基于2D-Mesh結(jié)構(gòu)的容錯路由算法

基本維序XY路由算法有很多優(yōu)點(diǎn)：邏輯簡單、傳輸效率高、沒有死鎖和活鎖、容易實(shí)現(xiàn)等。同時它的缺點(diǎn)也很明顯：沒有容錯能力且自適應(yīng)性很差。本節(jié)介紹了維序XY路由算法，并在此基礎(chǔ)上提出改進(jìn)的XY容錯路由算法，不僅能夠自適應(yīng)地容錯，同時也能避免死鎖和活鎖。

2.1 確定性維序XY路由算法

在一個2D-Mesh結(jié)構(gòu)里，維序XY路由算法中分組的路由只取決于源節(jié)點(diǎn)和目的節(jié)點(diǎn)的地址，而與網(wǎng)絡(luò)狀況無關(guān)。分組首先在X維上路由，當(dāng)分組到達(dá)與目的節(jié)點(diǎn)同一列時，轉(zhuǎn)向在Y維上的路由，最后到達(dá)目的節(jié)點(diǎn)。如圖1所示：源節(jié)點(diǎn)是A，目的節(jié)點(diǎn)是B，分組首先沿X維到達(dá)與目的節(jié)點(diǎn)同一列的C點(diǎn)，然后轉(zhuǎn)向Y維的路由。該算法硬件設(shè)計和實(shí)現(xiàn)簡單，在網(wǎng)絡(luò)流量不大時，具有小的時延，并且可防死鎖和活鎖。

圖1 確定性維序XY路由算法

但是，當(dāng)源節(jié)點(diǎn)和目的節(jié)點(diǎn)被確定時，路由路徑被唯一確定，因此路徑中有一條鏈路發(fā)生故障時，分組就不能被正確傳輸。同時該算法容易造成網(wǎng)絡(luò)中央負(fù)載過大，產(chǎn)生熱點(diǎn)或熱點(diǎn)區(qū)域。

2.2 改進(jìn)的容錯路由算法

在經(jīng)典的確定性維序XY路由算法基礎(chǔ)上，本文提出了一種改進(jìn)的容錯路由算法，適用于任何方向的單向或者雙向鏈路故障。

在2D-Mesh結(jié)構(gòu)里，每條鏈路有兩個直接相連的節(jié)點(diǎn)，我們定義水平方向為東西（E，W），垂直方向為南北（S，N）。同時最多有4個間接相鄰的節(jié)點(diǎn)，我們定義為NW、NE、SW、SE或者WN、EN、WS、ES四個方向，如圖2中所示。

圖2 鏈路故障的原始路徑（虛線）和新路徑（實(shí)線）

對于一條無邊界的鏈路，鏈路情形如圖2所示。而對有邊界的鏈路來說，鏈路故障共有4種情形，如圖3所示。

圖3 邊界鏈路故障

當(dāng)有一條鏈路發(fā)生故障時，我們重新定義一條新的唯一確定的路徑來替代故障路徑，其他不使用當(dāng)前故障鏈路的路由仍然按照XY路由算法計算傳輸路徑。在圖2的D1和D2中，將包含故障鏈路的路由路徑稱為初始路徑（original path），將改正后的路由路徑稱為新路徑（new path）。確定新路徑的準(zhǔn)則同樣是除了故障路徑之外，連接源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間最短的路由路徑。表1列出了初始路徑和對應(yīng)的新路徑。

表1 鏈路故障的初始路徑以及替代的新路徑

3 容錯路由算法仿真

容錯路由算法的仿真包括FPGA仿真平臺的搭建和初始化硬件平臺架構(gòu)，整個驗證過程如圖4所示。

本文仿真使用Xilinx公司的Virtex6 FPGA， 型號XC6VLX760，采用3×3的2D-Mesh結(jié)構(gòu)，如圖5所示。對其中X方向鏈路故障1和Y方向鏈路故障2在Xilinx的ISE 14.7環(huán)境下進(jìn)行仿真驗證。圖6是將數(shù)據(jù)00010011從（1, 3）傳向（1, 2），圖7是將數(shù)據(jù)00100001從（2, 1）傳向（3, 1），仿真波形顯示在鏈路故障的情況下傳輸數(shù)據(jù)成功。

圖4 FPGA仿真平臺

圖5 X方向鏈路故障1和Y方向鏈路故障2

圖6 仿真波形1

圖7 仿真波形2

最后，將本文提出的容錯路由算法與目前常用的幾種路由算法在所適用的拓?fù)浣Y(jié)構(gòu)、是否采用最短路徑、是否能夠容錯以及死鎖處理機(jī)制逐一進(jìn)行比較，如表2所示。

表2 容錯路由算法和其他路由算法的性能對比

4 總結(jié)

本文在單鏈路故障的情況下，提出了改進(jìn)的XY容錯路由算法。根據(jù)仿真結(jié)果分析并和其他算法性能進(jìn)行對比，改進(jìn)的容錯路由算法能夠成功地在單鏈路故障情況下進(jìn)行數(shù)據(jù)的傳輸，而且能有效地避免死鎖。

[1] Davide BIertozz, Shashi Kumar A P. Networks-on-chip∶emerging research topics and novel ideas [Z]. VLSI Design, 2007.

[2] Kariniemi H, Nurmi J. Arbitration and routing schemes for onchip packet networks [C]. Interconnect-Centric Design for Advanced SoC and NoC, 2005∶ 253-282.

[3] 張楠. 高效的片上網(wǎng)絡(luò)體系結(jié)構(gòu)：核內(nèi)路由[D]. 浙江：浙江大學(xué)碩士學(xué)位論文，2008.

[4] 張磊，李華偉，李曉維. 用于片上網(wǎng)絡(luò)的容錯通信算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2007, 19（4）：508-514.

[5] H M Pham, S Pillement, D Demigny. A fault-tolerant layer for dynamically reconfigurable multi-processor systemon-chip [C]. in Proc. Int Conf. Reconfigurable Comput.FPGAs, Quintana Roo, Mexico, 2009. 284-289.

[6] C C Feng, Z H Lu, A Jantsch, J W Li, M X Zhang. A reconfigurable fault-tolerant de flection routing algorithm based on reinforce-ment learning for network-on-chip [C]. in Proc. Int. Workshop Netw. Chip Architectures, Stockholm,Sweden, 2010. 11-16.