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

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

1 引言

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

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

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

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

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

2 IP核通信恢復(fù)

本文采用的是2D-Mesh拓?fù)浣Y(jié)構(gòu)，圖1給出的是4×4的2D-Mesh結(jié)構(gòu)，NoC系統(tǒng)是由路由器(router,R)、通信節(jié)點(intellectual property core,IP)、雙向通道(channel)和網(wǎng)絡(luò)接口(network interface,NI)組成。

NoC的設(shè)計流程[9]：通過靜態(tài)分析或模擬的方法提取給定應(yīng)用的通信特征來得到任務(wù)圖。將任務(wù)圖劃分為一組并發(fā)的任務(wù),分配并調(diào)度到合適的處理單元上得到核圖。

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

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

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

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

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

3 容錯模型

片上網(wǎng)絡(luò)中路由器故障會影響其周圍節(jié)點的安全性，與故障路由器越近安全性越差，越遠(yuǎn)安全性越高。危險路由器為此路由器相鄰一個故障路由器。不安全路由器為此路由器相鄰兩個危險路由器。

定義2路由器安全度：2D-Mesh結(jié)構(gòu)的NoC結(jié)構(gòu)中，在路由器中設(shè)置一個狀態(tài)標(biāo)志寄存器包含八位二進制數(shù)，用來標(biāo)識4個不同方向上的相鄰路由器的安全狀態(tài)。

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

安全度大小比較：11>10>01>00轉(zhuǎn)發(fā)數(shù)據(jù)包時，首先選擇安全度高的路由器進行數(shù)據(jù)轉(zhuǎn)發(fā)。

擁塞度是指路由器中某一方向上輸入緩沖區(qū)內(nèi)的數(shù)據(jù)包的個數(shù)與輸入緩沖區(qū)的大小的比值，即:

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

在數(shù)據(jù)通信前，先使用內(nèi)建自測試機制（built-in self test,BIST）對片上網(wǎng)絡(luò)進行測試，定位出故障路由器。網(wǎng)絡(luò)中的路由節(jié)點都向自己的鄰居節(jié)點發(fā)送自己的狀態(tài)信息，每個節(jié)點都能接收并存儲鄰居節(jié)點的狀態(tài)信息。路由節(jié)點的初始狀態(tài)信息都設(shè)置為11。當(dāng)節(jié)點的狀態(tài)會發(fā)生變化時，鄰居節(jié)點中存儲此節(jié)點的狀態(tài)信息也會發(fā)生相應(yīng)的變化。

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

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

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

4 仿真實驗與分析

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

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

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

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

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

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

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

5 結(jié)束語

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

參考文獻

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