基于重構的片上網絡容錯機制*

歐陽一鳴，屠 強，梁華國，郭 凱

(合肥工業大學計算機與信息學院 合肥 230009)

1 引言

隨著半導體工藝的不斷發展和SoC(system-on-chip)技術的不斷完善,SoC中所包含的IP核數目不斷增加?；诠蚕砜偩€互連機制的傳統SoC通信體系結構將遇到無法逾越的障礙,主要表現在以下幾方面：可擴展性差；平均通信效率低；和單一時鐘同步。因此，現有的以總線結構為通信基礎的SoC技術面臨著性能、功耗、延時和可靠性等方面的問題。

鑒于上述原因，在20世紀90年代末，一些研究機構借鑒和吸收了計算機通信網絡中的一些思想，提出了一種全新的互連結構——片上網絡(networks on chip，NoC)，并成為 IC(integrated circuit)主流設計技術[1～3]。NoC技術從體系結構上徹底解決了SoC總線結構所固有的三大問題：由于地址空間有限引起的可擴展性問題；由于分時通信而引起的通信效率問題；由于全局同步引起的功耗和面積問題。NoC采用全局異步—局部同步GALS(globally asynchronous locally synchronous)的通信機制，提供了良好的并行通信能力，使得NoC成為面向納米工藝的新型體系結構。

隨著電路集成規模的提高，片上網絡系統在芯片面積增加和特征尺寸減小的趨勢下，其芯片上可能出現的故障概率也不可忽視。在NoC提供的服務質量中,可靠性是重要的一個方面。在深亞微米和納米工藝條件下,NoC的容錯通信機制已經是不可或缺的一個重要方面。導致片上傳輸不可靠的因素主要有兩方面[4]:一是由電轉移、制作工藝和測試挑戰等引起的加速老化效應導致的永久性錯誤；二是由串擾、噪聲耦合和瞬間錯誤引起的軟故障。由于功耗和芯片面積的限制,傳統的容錯算法不再適合NoC，而必須有專門的針對NoC的容錯算法和機制。

[5]提出了一種可重構的容錯路由算法，通過在無路由器故障區域使用XY路由算法，在路由器故障區域使用特定的路由路徑，達到容忍故障路由器的目的。該算法將NoC中路由器的損壞狀況分成9種，然后規定了這9種狀況下的通信路徑，并通過路由器中設置的狀態寄存器標志出該路由器所處的狀態；通信時依據路由器狀態選擇相應的路由路徑。但是該算法沒有能夠解決NoC中出現多個路由器故障形成不規則區域的問題。參考文獻[6]提出的直接擴散算法，雖然能達到容錯的目的，但是需要在網絡中復制并傳輸大量的冗余數據包，會造成網絡擁塞，從而帶來很大的網絡開銷。參考文獻[7]提出源路由算法，在數據傳輸時先從源節點開始探索路徑，通過探索機制可以得到多條路徑，從多條路徑中選擇3條用于傳輸數據，該方法雖然能夠容錯，但是路徑探索機制復雜，路由表開銷較大。以上參考文獻給出的容錯方法是在路由器出現故障時采用重路由的方法繞過故障路由器，沒有考慮到故障路由器連接的IP核的數據通信。參考文獻[8]通過添加冗余鏈路解決了路由器出現故障時所連接的IP核的通信問題，但是只能解決單個路由器出現故障時的IP通信，且只適用于特定的應用編碼(如MMS、VOPD、MWD)技術。

本文提出一種新容錯機制：通過在IP核和相鄰路由器之間建立冗余鏈路恢復故障路由器連接的IP通信。相應的容錯路由算法是：通過為路由器設置狀態寄存器來存儲相鄰路由器的安全狀態，通過比較寄存器內鄰居路由器的狀態，選擇一個最優路由器作為下一個路由節點。通過壓力值來反映相鄰路由器的擁塞狀況，用多級擁塞控制機制來選擇擁塞程度較小的路由器。這樣可以使數據包在路由器故障的情況下能正確地傳輸到目的路由器。與現有的方法相比，該方法在容忍路由器故障、恢復IP核通信的情況下，有較高的可靠性、較低的延遲。

2 IP核通信恢復

本文采用的是2D-Mesh拓撲結構，圖1給出的是4×4的2D-Mesh結構，NoC系統是由路由器(router,R)、通信節點(intellectual property core,IP)、雙向通道(channel)和網絡接口(network interface,NI)組成。

NoC的設計流程[9]：通過靜態分析或模擬的方法提取給定應用的通信特征來得到任務圖。將任務圖劃分為一組并發的任務,分配并調度到合適的處理單元上得到核圖。

定義1關鍵IP核：絕大部分處理單元只分配到一項任務，有些處理單元分配到多項任務，分配多項任務的處理單元所映射的IP核稱為關鍵IP核。

路由器故障導致相連接IP核不能通信，由于關鍵IP核內存儲多項任務，本文只恢復關鍵核的通信。本文通過在關鍵IP核與故障路由器相鄰的路由器之間建立冗余鏈路的方法來恢復關鍵IP核的通信。關鍵IP通信時數據包首先向本地路由器轉發，當本地路由節點路障時，根據轉發機制選擇建立冗余鏈路的鄰居路由器(稱冗余路由器)轉發數據包。關鍵IP核通信恢復分為兩步：冗余鏈路數的確定和最優鄰居路由器的選取。

對于一個由n個IP核組成的NoC，根據它們的通信關系可以組成一個通信矩陣 T=tij(0≤i,j≤n-1),如式（1）所示。

其中，tij表示的是第 i個IP核到第 j個 IP核的通信量，該通信量可以由通信任務圖得出。因此，可以計算出該NoC的總通信量個IP核的平均通信量為，單個IP核的通信量可由得出，那么根據單個IP核的通信量和平均通信量確定該IP核與故障路由器的鄰居所建立的冗余鏈路數Numi：如果Wi﹤Wavg，則 Numi=1，否則Σ（冗余鏈路數最大為4），確定了要建立的冗余鏈路數后，再根據貪婪算法選擇鄰居路由器，算法每執行一次選擇出一個鄰居路由器(其Wi值最小)，直到算法執行次數等于Numi。

如圖1所示，R5是故障路由器其所連接的核IP5為關鍵核，由上述公式可以得出 IP5的Numi，假設Numi=2，再根據貪婪算法從故障節點的鄰居路由器（R2、R4、R6、R8）中選擇通信量最小的路由器，假如選擇了R6和R8，則IP5同時與R6和R8相連接，同時把R6和R8路由器的地址廣播給所有鄰居路由器。當R5出現故障，其他路由器向R5發數據包，當R5鄰居路由器收到數據包，比較當前路由器和目的路由器(R6、R8)的曼哈頓距離，選擇路徑短的路由器接收數據包，如果R6收到數據包，解析包頭，根據包頭地址判斷數據包是傳給IP5還是IP6。若IP5向其他核發送數據包，首先判斷本地路由器(R5)是否故障，本地路由節點故障，選擇建立冗余路徑的路由器發送數據包，比較當前路由器(R6、R8)與目的路由器的曼哈頓距離，選擇曼哈頓距離短的路由器轉發數據包，如果距離相等則根據多級擁塞機制，選擇擁塞程度小的路由器轉發數據包。具體流程如圖2所示。

3 容錯模型

片上網絡中路由器故障會影響其周圍節點的安全性，與故障路由器越近安全性越差，越遠安全性越高。危險路由器為此路由器相鄰一個故障路由器。不安全路由器為此路由器相鄰兩個危險路由器。

定義2路由器安全度：2D-Mesh結構的NoC結構中，在路由器中設置一個狀態標志寄存器包含八位二進制數，用來標識4個不同方向上的相鄰路由器的安全狀態。

00表示此方向無路由器或者是故障路由器；01表示此方向上是危險路由器（此路由器相鄰一個故障路由器）；10表示此方向上的路由器是不安全路由器（此路由器相鄰兩個危險路由器）；11表示此方向上的路由器是正常的。

安全度大小比較：11>10>01>00轉發數據包時，首先選擇安全度高的路由器進行數據轉發。

擁塞度是指路由器中某一方向上輸入緩沖區內的數據包的個數與輸入緩沖區的大小的比值，即:

為了避免網絡擁塞，減少網絡延遲，本文采用多級擁塞控制機制。根據擁塞度的大小把擁塞分為三個等級：重度擁塞（0.6～1）>中度擁塞（0.4～0.6）>輕度擁塞（0～0.4），轉發數據包時遇到擁塞度不同的路由器，首先選擇數據擁塞度輕的路由節點。

在數據通信前，先使用內建自測試機制（built-in self test,BIST）對片上網絡進行測試，定位出故障路由器。網絡中的路由節點都向自己的鄰居節點發送自己的狀態信息，每個節點都能接收并存儲鄰居節點的狀態信息。路由節點的初始狀態信息都設置為11。當節點的狀態會發生變化時，鄰居節點中存儲此節點的狀態信息也會發生相應的變化。

本文提出一種新的基于重構的動態容錯路由算法是具有部分自適應[10]的,通過使用內建自測試來定位錯誤，把路由器的安全度劃分為4個不同的狀態，在路由器內設置狀態標識寄存器，存儲相鄰路由器的安全度狀態。為了降低網絡延遲，本文采用了多級擁塞控制機制，這個機制可以在最大程度上降低網絡延遲，在傳輸數據時首先根據路由安全狀態選擇安全度較高的路由器轉發數據包，當傳輸方向上的路由節點安全度相同時，再根據多級擁塞狀況選擇擁塞程度較低的路由器轉發數據包。本文采用端到端的循環冗余校驗和重傳機制解決數據包的軟錯誤問題。另外，文章使用虛通道機制避免死鎖。

算法簡述如下：設(cx，cy)為當前節點坐標，(dx，dy)為目的節點坐標，當節點接收到數據包時會先比較目的地址和當前節點地址。如果地址相同轉發到本地IP核，否則根據目的地址選擇轉發方向。當cx和dx、cy和dy都不相等時保持最短路徑的轉發方向上有兩個最優鄰居路由節點，這時就要比較狀態寄存器中這兩個方向上的路由節點的損壞狀態，選擇安全度高的路由節點，作為下一節點轉發數據包。如果安全度相同（且無故障），則根據多級擁塞控制機制選擇擁塞度小的節點進行轉發。如果最短路徑上的兩個節點都故障，則從剩下的兩個路由節點中根據多級擁塞控制機制選擇擁塞度較小的路由節點轉發數據。

當cx和dx、cy和dy中有一個相等時，保持最短路徑的轉發方向只有一個，如果此方向上的路由節點無故障，則傳輸數據。如果最短路徑上的路由節點故障，比較與轉發方向垂直的兩個相鄰路由節點的安全度，選擇安全度高的一個節點轉發數據包。如果這兩個路由節點的安全度相同，根據多級擁塞控制機制選擇擁塞度較小的路由節點轉發數據包。容錯路由算法流程如圖3所示。

4 仿真實驗與分析

本文基于OPNET平臺構建的一個5×5的雙通道2D-Mesh結構的NoC通信模型[11]。模型采用存儲轉發交換機制，仿真環境中數據的最小單元是數據包，數據包之間的時間間隔由數據注入率確定。仿真實驗過程是在轉置模式下對本文提出的容錯路由算法和參考文獻[5]中提出的路由算法網絡性能進行比較；比較的技術指標為平均傳輸延遲。在轉置模式下，對于一個N×N規模NoC，位于(i,j)(i,j∈[0,N-1])的IP核，只能發送數據包至位于(N-i-1,N-j-1)的IP核，該轉發模式更加接近于NoC的實際通信[12]。

NoC中的節點根據其連接狀況可以分為以下幾類：頂點（只有2個鄰居節點）、邊節點（有3個鄰居節點），其他節點（有4個鄰居節點）包括中心節點和非中心節點。為了使仿真實驗更接近實際的網絡通信，實驗隨機設置了這幾種不同類型的節點故障個數。

由圖4可以看出，當故障節點出現在中心節點時，本文的路由算法延遲明顯小于參考文獻[5]中路由算法的延遲。這是由于中心節點處于NoC模型的中心位置，數據傳輸包時使用該節點的頻率很高，因此容錯路由算法對于數據延遲的影響更加明顯，本文使用多級擁塞控制機制使其他節點分擔了中心節點的負載，因而比參考文獻[5]大大地減少了延遲。

當故障節點出現在中心節點和邊緣節點時，本文的路由算法和參考文獻[5]中的路由算法在平均延遲上的比較如圖5所示。當頂點、邊節點、中心節點和非中心節點都出現故障時，本文的路由算法和參考文獻[5]中的路由算法平均延遲的比較如圖6所示。

從圖5和圖6中可以看出本文所提出的路由算法的延遲小于參考文獻 [5]中所提出的路由算法，這是因為隨著故障節點個數的增加，路由數據包時使用到故障節點的次數增多，不同的容錯路由算法對于數據包傳輸延遲的影響增大，導致延遲差異增大。

為了更好地比較延遲情況，測試容錯路由算法的性能，本次實驗從上述4種節點類型的故障中任意設置了6個節點故障，從圖7中可以看出本文所提出的路由算法的延遲優于參考文獻[5]中所提出的路由算法的延遲。這是由于隨著故障節點的增多，網絡中可以進行傳輸數據的節點減少，會導致網絡節點擁塞，延遲增加，本文提出的路由算法，利用到多級擁塞控制機制避免了延遲增加，隨著故障節點的增多，不同的路由算法所表現的延遲性能有著明顯的差別。

上述實驗結果可以得出，在設置不同類型和不同數目的故障節點的情況下，和參考文獻[5]中的路由算法相比，本文所提出的容錯路由算法在保障NoC正常通信的情況下，具有更小的傳輸延遲，網絡性能更穩定。因此，本文提出的路由算法更加適合片上網絡的容錯通信。

5 結束語

隨著片上網絡的發展，容錯成為研究的熱點和重點。本文提出了一種新的容錯機制，在路由節點出現故障的情況下恢復IP核通信，通過為路由節點設置標識寄存器存儲相鄰節點的安全狀態，在傳輸數據時避免故障節點。通過使用多級擁塞控制機制，避免網絡擁塞，減少延遲。仿真實驗是在OPNET平臺的一個NoC仿真模型上運行的，在這個模型上，進行5×5 2D-Mesh結構的實驗。仿真結果表明：本文提出的可重構的動態容錯路由算法優于參考文獻[5]中的容錯路由算法，網絡延遲更小，網絡性能更穩定。

參考文獻

1 Sha Shi,Kumar,Axel Jantsch,et al.A network on chip architecture and design methodology.In:Proceeding of IEEE Computer Society Annual Symposium on VLSI,April 25～26,2002

2 Benini L,Micheli G D.Networks on chips:a new soc paradigm.IEEE Computer,2002,35(1):70～78

3 Dally William J,Towles Brian1.Route packets,not wires:on chip interconnection networks. In: Proceeding of Design Automation Conference,Las Vegas,Nevada,2001

4 Dongkook Park.Design space exploration forfault-tolerant on-chip intereonnects.In:The 2006 International Conference on Dependable Systems and Networks,Philadelphia,Pennsylvania,June 2006

5 Zhen Zhang,Alain Greiner,Sami Taktak.A reconfigurable routing algorithm for a fault-tolerant 2D-mesh network-on-chip.In:45th ACM/IEEE Design Automation Conference,2008

6 Pirretti M,Link G,Brooks R,et al.Fault tolerant algorithms for network-on-chip interconnect.In:Proceeding of IEEE Computer Society Annual Symposium on VLSI,2004

7 Young Bok Kim,Yong-Bin Kim.Fault tolerant source routing for network-on-chip.In:22nd IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems,2007

8 Renan F,Alemzadeh H,Kabiri P,et al.Application specific configuration of a fault-tolerant NoC architecture.In:Proceeding of Electronics Conference, BEC 2008 11th International Biennial Baltic,Oct 2008

9 Hu J,Marculescu R.Energy-aware mapping for tile-based NoC architectures under performance constraints.In:Proceeding of Asia South Pacific Design Automation,Kitakyushu,2003

10 Xiaohu Zhu,Yang Cao,Liwei Wang.A multilevel congestion control routing algorithm for network-on-chip.Journal of Beijing University of Posts and Telecommunications,2007,30(5):91～94

11 Ning Wu,Fen Ge,Qi Wang.Simulation and performance analysis of network on chip architectures using OPNET.In:Proceeding of ASICON'07,International Conference,2007

12 Daneshtalab M,Sobhani A,Afzali-Kusha A,et al.NoC hot spot minimization using antnet dynamic routing algorithm.In:Proceeding of 17th ASAP,IEEE Press,USA,Sep 2006