負(fù)載均衡的2D Mesh 單節(jié)點(diǎn)故障容錯(cuò)路由算法

韓承浩，陳乃金，胡宇楊，李抗

（1.安徽工程大學(xué) 計(jì)算機(jī)與信息學(xué)院，蕪湖 241000；2.安徽工程大學(xué) 電氣工程學(xué)院，蕪湖 241000）

隨著可重構(gòu)多核處理器的進(jìn)一步發(fā)展，其編譯映射工具片上數(shù)據(jù)傳輸?shù)娜蒎e(cuò)顯得越來(lái)越重要[1]，片上網(wǎng)絡(luò)數(shù)據(jù)傳輸擁塞或路由器故障導(dǎo)致可重構(gòu)多核系統(tǒng)之間的數(shù)據(jù)傳輸時(shí)延顯著增加，目前針對(duì)片上網(wǎng)絡(luò)（network-on-chip，NoC）節(jié)點(diǎn)故障國(guó)內(nèi)外學(xué)者大多采用路由容錯(cuò)等解決方法。一般而言，片上網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)娜蒎e(cuò)機(jī)制大多從網(wǎng)絡(luò)傳輸層找到可以替代的傳輸路徑來(lái)避開(kāi)故障節(jié)點(diǎn)位置，因?yàn)橐淖僋oC 原有的數(shù)據(jù)傳輸路徑，所以需要解決網(wǎng)絡(luò)死鎖的問(wèn)題，根據(jù)不同的解決網(wǎng)絡(luò)死鎖的方法，被分為有虛通道路由[2-3]和無(wú)虛通道路由。有虛通道路由將物理信道分為幾個(gè)邏輯信道，通過(guò)切換不同的邏輯信道，來(lái)避免信道之間的相互依賴(lài)，從而解決死鎖問(wèn)題，然而這樣就使得路由節(jié)點(diǎn)的邏輯門(mén)個(gè)數(shù)增大，功耗增大。無(wú)虛通道路由算法大多采用轉(zhuǎn)向模型來(lái)避免死鎖，通過(guò)禁止一定數(shù)量的轉(zhuǎn)向，避免信道之間形成環(huán)形依賴(lài)[4]。由于有虛通道路由需要消耗額外的硬件達(dá)到容錯(cuò)的目的，而無(wú)虛通道路由主要依賴(lài)在故障節(jié)點(diǎn)周?chē)逆溌防@行來(lái)避開(kāi)故障節(jié)點(diǎn)以達(dá)到容錯(cuò)的目的。

1 相關(guān)工作

關(guān)于故障預(yù)測(cè)的2D Mesh 單故障節(jié)點(diǎn)的無(wú)虛通道容錯(cuò)路由相關(guān)工作闡述可分為故障位置的檢測(cè)和無(wú)虛通道容錯(cuò)路由算法。

1.1 故障位置的檢測(cè)

對(duì)于故障位置的檢測(cè)主要依賴(lài)于內(nèi)建自測(cè)技術(shù)（Built-in Self Test，BIST），將外部檢測(cè)的工具集成到電路內(nèi)部，實(shí)現(xiàn)對(duì)故障類(lèi)型、故障位置的診斷。Biswajit 等人[5]提出了一種面向在線(xiàn)分布式內(nèi)建自測(cè)試的測(cè)試機(jī)制，該機(jī)制專(zhuān)門(mén)檢測(cè)通信鏈路上的開(kāi)放故障，并從NoC 中識(shí)別故障鏈路。隨后，提出一種合適的容錯(cuò)策略。內(nèi)建自測(cè)試是實(shí)現(xiàn)高可靠性的主要測(cè)試方案之一。該方案可對(duì)NoC 的基本組件進(jìn)行故障測(cè)試和恢復(fù)。Bhowmik 等人[6]提出了一種檢測(cè)通信介質(zhì)中短路故障的內(nèi)建自測(cè)試方法，提高了NoC 的產(chǎn)量和性能。

1.2 無(wú)虛通道容錯(cuò)路由算法

Zhang 等 人[7]提 出RR 算法 在 無(wú) 故 障 時(shí) 采 用XY 路由算法，當(dāng)有故障節(jié)點(diǎn)在網(wǎng)絡(luò)非邊界區(qū)域時(shí)將故障節(jié)點(diǎn)相鄰的四個(gè)節(jié)點(diǎn)，以及間接的四個(gè)頂點(diǎn)組成繞行環(huán)路，在繞行環(huán)路的東北角（SW，ES）禁止轉(zhuǎn)向，來(lái)避免死鎖，因此當(dāng)故障節(jié)點(diǎn)出現(xiàn)在網(wǎng)絡(luò)中心區(qū)域時(shí)由于需要考慮避免死鎖，導(dǎo)致了某些數(shù)據(jù)包的長(zhǎng)距離繞行，繞行環(huán)路負(fù)載不均衡等問(wèn)題。針對(duì)此問(wèn)題，姚磊等人[8]提出了FTR 算法對(duì)RR 算法進(jìn)行了改進(jìn)，對(duì)RR 算法中在繞行環(huán)路的東北角無(wú)法轉(zhuǎn)向的數(shù)據(jù)包，在東北角節(jié)點(diǎn)的右鄰接節(jié)點(diǎn)定義為輔助拐點(diǎn)允許數(shù)據(jù)包由北向西轉(zhuǎn)向。Xie 等人[9]提出了一種具有一定容錯(cuò)能力的轉(zhuǎn)向模型（Fault-Tolerant Odd-Even，F(xiàn)TOE），使得數(shù)據(jù)包有更多的路徑進(jìn)行傳輸，從而避開(kāi)故障節(jié)點(diǎn)，可以被用于單故障節(jié)點(diǎn)容錯(cuò)，有較好的效果。Bahrebar 等人[10]利用算珠轉(zhuǎn)向模型提出一種可重構(gòu)無(wú)死鎖路由方法，通過(guò)對(duì)算珠的動(dòng)態(tài)調(diào)整，賦予數(shù)據(jù)包高度的適應(yīng)性。謝瑞蓮等人[11]提出一種低開(kāi)銷(xiāo)的無(wú)虛通道隔離路由算法，根據(jù)凸故障模型的思想劃分不規(guī)則區(qū)域，利用不規(guī)則區(qū)域的邊界傳輸數(shù)據(jù)包，來(lái)達(dá)到容錯(cuò)的目的。Rahaman 等人[12]提出無(wú)死鎖的自適應(yīng)容錯(cuò)NoC 路由（F-Route-NoCMesh，F(xiàn)RNM），該方法將NoC 中的多個(gè)故障節(jié)點(diǎn)，構(gòu)造成一個(gè)正交凸形故障區(qū)域，通過(guò)自適應(yīng)路由算法來(lái)繞過(guò)這個(gè)區(qū)域，實(shí)現(xiàn)容錯(cuò)。路由算法通過(guò)當(dāng)前數(shù)據(jù)包的位置和目的節(jié)點(diǎn)的位置來(lái)作出不同的路由策略。通過(guò)轉(zhuǎn)向模型來(lái)避免死鎖，沒(méi)有使用虛通道。通過(guò)虛擬故障塊邊界路由數(shù)據(jù)包來(lái)平衡流量，減小故障區(qū)域負(fù)載，通過(guò)實(shí)驗(yàn)表明網(wǎng)絡(luò)平均時(shí)延、平均吞吐量和功耗均有改善。Sayed 等人[13]提出一種擁塞感知、容錯(cuò)和過(guò)程變化感知的自適應(yīng)路由算法（CFPA），在每個(gè)路由器上都有一個(gè)路由表，以跟蹤所有路由器的排隊(duì)延遲。在路由決策中考慮到排隊(duì)延遲，使路由器有能力通過(guò)非擁擠路徑向目的地轉(zhuǎn)發(fā)數(shù)據(jù)信息。CFPA 通過(guò)對(duì)數(shù)據(jù)包路由進(jìn)行優(yōu)先排序來(lái)避免死鎖。因此，長(zhǎng)路徑的數(shù)據(jù)包比短路徑的數(shù)據(jù)包有更高的優(yōu)先權(quán)。CFPA 將NoC的吞吐量提高60%，使用CFPA，故障對(duì)NoC 吞吐量的影響減輕了48%，減少了網(wǎng)絡(luò)時(shí)延。

通過(guò)對(duì)上述文獻(xiàn)的研究發(fā)現(xiàn)，相關(guān)路由算法存在數(shù)據(jù)包傳輸距離長(zhǎng)、網(wǎng)絡(luò)負(fù)載不均衡等問(wèn)題。本文對(duì)此展開(kāi)深入研究，其研究方案列舉如下：

（1）設(shè)計(jì)一種基于全局容錯(cuò)的轉(zhuǎn)向模型，提出一種單節(jié)點(diǎn)故障預(yù)測(cè)無(wú)虛通道（Single-node Fault Prediction without Virtual Channels，SFPVC）路由算法。

（2）利用內(nèi)建自測(cè)機(jī)制在X方向和Y方向作出預(yù)測(cè)，避免數(shù)據(jù)包垂直或水平方向進(jìn)入繞行環(huán)路，減輕故障節(jié)點(diǎn)周?chē)?fù)載，減少數(shù)據(jù)包傳輸距離。

2 問(wèn)題定義

定義1：節(jié)點(diǎn)坐標(biāo)。

方向約定X+方向?yàn)闁|，X-方向?yàn)槲?，Y+方向?yàn)楸保琘-方向?yàn)槟?；?jié)點(diǎn)類(lèi)型符號(hào)可表示為S、D和F等三種類(lèi)型，其含義分別為源、目的和故障節(jié)點(diǎn)，S、D和F的坐 標(biāo) 分別表 示為（Sx，Sy）、（Dx，Dy）和（Fx，F(xiàn)y）。在本文中若無(wú)特殊說(shuō)明則約定為網(wǎng)絡(luò)規(guī)模為N×N。具體如圖1 所示。

圖1 路由節(jié)點(diǎn)坐標(biāo)相關(guān)說(shuō)明

定義2：故障點(diǎn)信息。

故障點(diǎn)信息可標(biāo)定為一種特殊的數(shù)據(jù)包，發(fā)送到片上網(wǎng)絡(luò)內(nèi)的任意一節(jié)點(diǎn)，并且可以存儲(chǔ)在路由器故障寄存器中。

定義3：節(jié)點(diǎn)數(shù)據(jù)傳輸轉(zhuǎn)向模型。

本節(jié)點(diǎn)數(shù)據(jù)傳輸方向模型規(guī)定與文獻(xiàn)[4]一致，NE 表示由北向東轉(zhuǎn)向，WS 表示由西向南轉(zhuǎn)向，ES 表示由東向南轉(zhuǎn)向，NW 表示由北向西轉(zhuǎn)向，SE 表示由南向東轉(zhuǎn)向，WN 表示由西向北轉(zhuǎn)向，EN 表示由東向北轉(zhuǎn)向，SW 表示由南向西轉(zhuǎn)向，具體如圖2（a）所示，圖2（b）表示非法轉(zhuǎn)向。

圖2 節(jié)點(diǎn)數(shù)據(jù)傳輸轉(zhuǎn)向模型示意圖

定義4：死鎖。

在片上網(wǎng)絡(luò)路由數(shù)據(jù)傳輸過(guò)程中出現(xiàn)的一種現(xiàn)象，即多個(gè)數(shù)據(jù)包在傳輸路徑形成了無(wú)虛通道打結(jié)環(huán)路，這種現(xiàn)象稱(chēng)為死鎖。死鎖可以通過(guò)設(shè)計(jì)路由算法和數(shù)據(jù)流控制協(xié)議來(lái)避免，本文通過(guò)設(shè)計(jì)合理的路由算法避免死鎖。

定義5：容錯(cuò)路由評(píng)價(jià)指標(biāo)。

本文約定容錯(cuò)路由算法只對(duì)片上網(wǎng)絡(luò)的時(shí)延進(jìn)行評(píng)估，評(píng)價(jià)指標(biāo)具體可分為靜態(tài)仿真[14]指標(biāo)均值μ和方差σ2，動(dòng)態(tài)仿真指標(biāo)飽和注入率η。具體說(shuō)明如下：

均值是數(shù)據(jù)包在每個(gè)路由器上被途經(jīng)的平均次數(shù)，均值越大則說(shuō)明數(shù)據(jù)包傳輸距離越長(zhǎng)，方差是每個(gè)路由器上被途經(jīng)的次數(shù)的方差，方差反映了網(wǎng)絡(luò)中的負(fù)載均衡情況，方差大則說(shuō)明網(wǎng)絡(luò)中某些區(qū)域負(fù)載過(guò)大，容易在該區(qū)域形成網(wǎng)絡(luò)擁塞。均值和方差計(jì)算方法與文獻(xiàn)[8]一致，具體公式如式（1）和式（2）所示。

式中，aij表示矩陣A中的一元素。具體計(jì)算方法如 下：把N×N的NoC中所有不重復(fù)的源-目的節(jié)點(diǎn)按照當(dāng)前路由算法只發(fā)送一個(gè)數(shù)據(jù)包，然后在每個(gè)節(jié)點(diǎn)nij（1≤i≤N，1≤j≤N）處統(tǒng)計(jì)途經(jīng)該節(jié)點(diǎn)的數(shù)據(jù)包個(gè)數(shù)aij，最終得到一個(gè)N×N矩陣A=（aij）。

注入率表示網(wǎng)絡(luò)在單位時(shí)間內(nèi)可處理的數(shù)據(jù)包個(gè)數(shù)，Ntotal_node表示網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)；Ttotal_cycle表示第一個(gè)頭微片進(jìn)入網(wǎng)絡(luò)到最后一個(gè)微片尾離開(kāi)網(wǎng)絡(luò)的時(shí)間；LENi表示Ttotal_cycle時(shí)鐘周期內(nèi)成功到達(dá)目的節(jié)點(diǎn)的第i個(gè)數(shù)據(jù)包的長(zhǎng)度，n表示所有到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)包個(gè)數(shù)，數(shù)據(jù)包長(zhǎng)度單位為filts。

本文規(guī)定隨著注入率的增大，當(dāng)網(wǎng)絡(luò)時(shí)延為零負(fù)載時(shí)延的兩倍時(shí)所對(duì)應(yīng)的注入率η記為飽和注入率。

3 實(shí)驗(yàn)動(dòng)機(jī)和容錯(cuò)路由算法設(shè)計(jì)

3.1 實(shí)驗(yàn)動(dòng)機(jī)

目前的故障節(jié)點(diǎn)繞行法，大多是先沿著正常路由傳輸，當(dāng)檢測(cè)到下一跳節(jié)點(diǎn)為故障節(jié)點(diǎn)時(shí)，才做出容錯(cuò)的策略，或者是將故障節(jié)點(diǎn)坐標(biāo)存儲(chǔ)在部分正常節(jié)點(diǎn)的故障存儲(chǔ)器中，當(dāng)數(shù)據(jù)包到達(dá)這些節(jié)點(diǎn)時(shí)，可以讀取故障信息，從而作出容錯(cuò)策略。這樣會(huì)使傳輸路徑單一，部分?jǐn)?shù)據(jù)包繞行距離過(guò)大等問(wèn)題，本文提出一種單節(jié)點(diǎn)故障預(yù)測(cè)無(wú)虛通道路由算法，使數(shù)據(jù)包從第一跳就可以判斷是否需要容錯(cuò)，以及采用何種容錯(cuò)策略，這樣做可以提前容錯(cuò)，在盡可能追求傳輸路徑最小的情況下，保證了傳輸路徑多樣性。使得負(fù)載平衡，降低網(wǎng)絡(luò)時(shí)延。

3.2 容錯(cuò)路由算法設(shè)計(jì)

策略一：轉(zhuǎn)向模型。本文是一種全局容錯(cuò)路由算法，就需要一種數(shù)據(jù)傳輸路徑多樣的轉(zhuǎn)向模型，因此本文提出一種基于全局容錯(cuò)的無(wú)死鎖轉(zhuǎn)向模型（如圖3 所示），對(duì)比RR 的轉(zhuǎn)向模型和FTR 的轉(zhuǎn)向模型，本文采用的轉(zhuǎn)向模型禁止的轉(zhuǎn)向少，使得數(shù)據(jù)傳輸路徑更為多樣。

圖3 容錯(cuò)轉(zhuǎn)向模型

策略二：X正方向繞行。當(dāng)1≤Sx

（1）當(dāng)Fx

（2）當(dāng)Fx≤Dx≤N且Dy

（3）當(dāng)Fx≤Dx≤N且Dy>Fy時(shí)，若Fx+ 2 =Dx沿YX路由傳輸?shù)剑‵x+ 1，F(xiàn)y+ 1），此后沿YX路由傳輸，否則第一跳向北發(fā)送數(shù)據(jù)包，此后沿XY路由傳輸。

策略三：X負(fù)方向繞行。當(dāng)Fx

（1）當(dāng)1 ≤Dx＜Fx且Dy=Fy時(shí)，若Fx+ 1 =Sx，第一跳向南發(fā)送數(shù)據(jù)包此后沿XY路由傳輸，否則沿XY路由發(fā)送到（Fx+ 2，F(xiàn)y+ 1），此后沿XY路由傳輸。

（2）當(dāng)1 ≤Dx≤Fx且Dy

（3）當(dāng)1 ≤Dx≤Fx且Dy>Fy時(shí)，若Fx+ 1 =Sx先以YX路由傳輸?shù)剑‵x- 1，F(xiàn)y- 1），再向北傳輸?shù)剑‵x- 1，F(xiàn)y+ 1），最后以XY算法傳輸，否則向西發(fā)送至（Fx+ 1，F(xiàn)y）此后沿YX路由傳輸。

策略四：Y正方向繞行。當(dāng)Fy

（1）當(dāng)1 ≤Sy

（2）當(dāng)1 ≤Sy

（3）當(dāng)1 ≤SyFx+ 1 時(shí)，向西發(fā)送至Fx+ 1 列，再沿YX路由傳輸。

策略五：Y負(fù)方向繞行。當(dāng)1 ≤Dy

（1）當(dāng)Fy

（2）當(dāng)Fy

（3）當(dāng)FyFx時(shí)，先向西發(fā)送至Fx+ 1 行，再按YX路由傳輸。

策略六：避免死鎖。若不滿(mǎn)足策略二到策略五的條件，則按XY路由傳輸。然而這樣會(huì)有以下兩種情況，與圖3 中禁止的轉(zhuǎn)向相違背，會(huì)形成死鎖：（1）當(dāng)數(shù)據(jù)包滿(mǎn)足在Fx+ 2 列由東向北轉(zhuǎn)向；（2）當(dāng)數(shù)據(jù)包滿(mǎn)足在Fx+ 1 列且縱坐標(biāo)小于Fy+ 2 處由東向南轉(zhuǎn)向。對(duì)于第一種情況當(dāng)數(shù)據(jù)包到達(dá)Fx+ 1 列時(shí)按YX算法路由；對(duì)于第二種情況直接按YX算法路由。

策略七：其他情況。對(duì)于策略六中的第二種情況，當(dāng)1 ≤Sx≤Fx，Sy=Fy且Dx=Fx+ 1，Dy=Fy時(shí)，沿YX路由會(huì)遇到故障節(jié)點(diǎn)。此時(shí)可分為兩種情況：

（1）Sx=Fx，先按XY算法傳輸?shù)剑‵x- 1，F(xiàn)y-1），此后沿XY路由傳輸。

（2）Sx

由策略二到策略七設(shè)計(jì)實(shí)現(xiàn)了SFPVC 算法，算法流程圖描述如圖4 所示。

圖4 SFPVC 流程圖

4 實(shí)驗(yàn)比較及分析

4.1 SFPVC 與FTR 和RR 比 較

FTR 算法在（Fx+ 2，F(xiàn)y- 1）處由東向北轉(zhuǎn)彎時(shí)需要先到達(dá)（Fx+ 1，F(xiàn)y+ 1）處再按XY算法路由，若數(shù)據(jù)包的目的節(jié)點(diǎn)為（Fx+ 1，F(xiàn)y），則比最短路徑多兩跳。N×N規(guī)模的網(wǎng)絡(luò)中，若1

如圖5 所示，數(shù)據(jù)包源節(jié)點(diǎn)為S1，目的節(jié)點(diǎn)為D1，此后均表示為S1→D1，F(xiàn)TR 算法先沿XY算法路由在到達(dá)故障點(diǎn)左鄰接點(diǎn)時(shí)開(kāi)始繞行直到當(dāng)前節(jié)點(diǎn)與目的節(jié)點(diǎn)的X坐標(biāo)相等，而本文直接以YX算法路由，在故障節(jié)點(diǎn)處避免了繞行。如圖5 中的S2→D2，F(xiàn)TR 算法由于要避免死鎖禁止在（Fx+1，F(xiàn)y- 1）處由東向北轉(zhuǎn)向，因此數(shù)據(jù)包傳輸距離較長(zhǎng)，而本文算法的傳輸路徑較短。當(dāng)時(shí)S3→D3時(shí)，F(xiàn)TR 允許了（Fx+ 2，F(xiàn)y+ 1）處的由北向西的轉(zhuǎn)彎，因此先把數(shù)據(jù)包傳輸?shù)剑‵x+2，F(xiàn)y+ 1）再以XY路由傳輸；RR 算法由于沒(méi)有提前預(yù)測(cè)，因此當(dāng)數(shù)據(jù)包發(fā)送到（Fx，F(xiàn)y- 1）時(shí)檢測(cè)到北方向有故障節(jié)點(diǎn)，因此只能沿故障點(diǎn)周?chē)@行至（Fx，F(xiàn)y+ 1）處再向北發(fā)送；而本文的轉(zhuǎn)向模型路徑更多，因此本文算法將數(shù)據(jù)包傳輸?shù)紽x+ 2 列再以YX算法路由，比起FTR 傳輸固定的某一點(diǎn)，本文傳輸路徑更為多樣，相比于RR 算法，本文算法減少數(shù)據(jù)包傳輸距離，且減輕故障節(jié)點(diǎn)周?chē)呢?fù)載。

圖5 部分?jǐn)?shù)據(jù)傳輸路徑對(duì)比

4.2 靜態(tài)仿真

為了比較三種算法的網(wǎng)絡(luò)時(shí)延，首先要分析在路由算法層面影響網(wǎng)絡(luò)時(shí)延的兩大要素，分別為：數(shù)據(jù)包從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由的平均長(zhǎng)度和網(wǎng)絡(luò)擁塞程度。為此引入均值μ和方差σ2，其計(jì)算如式（1）和式（2）所示。本小節(jié)在網(wǎng)絡(luò)規(guī)模為6×6 和8×8 網(wǎng)絡(luò)中隨機(jī)選擇4 個(gè)故障節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)，共有不重復(fù)的源-目的節(jié)點(diǎn)對(duì)1 225、3 969 對(duì)（除去包含故障節(jié)點(diǎn)的源-目的節(jié)點(diǎn)對(duì)），統(tǒng)計(jì)每個(gè)路由器節(jié)點(diǎn)被經(jīng)過(guò)的次數(shù)，得到6×6 和8×8 的矩陣，代入式（1）和式（2），算出μ和σ2，如表1 和表2 所示。在網(wǎng)絡(luò)規(guī)模為6×6 時(shí)對(duì)比FTR 和RR，μ平均減少了0.13%和1.74%，σ2平均減少了8.83%和17.48%；在網(wǎng)絡(luò)規(guī)模為8×8時(shí)對(duì)比FTR 和RR，μ平均減少了0.03%和1.21%，σ2平均減少了8.71%和15.06%。

表1 6×6均值方差對(duì)比

表2 8×8 均值方差對(duì)比

為了更直觀地看出三種算法的負(fù)載均衡情況，將上文中的矩陣以圖的形式展現(xiàn)，得到三種算法的流量分布圖，如圖6 所示，這里以8×8 故障節(jié)點(diǎn)為（5，5）舉例。圖6（c）所示相比于圖6（a）和圖6（b），本文算法改善了在故障節(jié)點(diǎn)的周?chē)纬蓳砣闆r，因而表現(xiàn)為方差σ2的減少。

圖6 流量分布圖

4.3 動(dòng)態(tài)仿真

為了進(jìn)一步地評(píng)估三種算法的性能，采用一種精確周期的NoC 模擬器Booksim 2.0[15]，仿真分別在6×6 和8×8 網(wǎng)絡(luò)中進(jìn)行，故障點(diǎn)的選取與上一節(jié)保持一致，每條鏈路的緩存大小為8 flits，數(shù)據(jù)包長(zhǎng)度為2 flits，采用uniform 流量模型，模擬器預(yù)熱了1 000 個(gè)周期，在另外3 000 個(gè)周期中測(cè)量其性能。本小節(jié)以飽和注入率η作為評(píng)價(jià)指標(biāo)，隨著注入率的增大，網(wǎng)絡(luò)進(jìn)入飽和的越晚則η越大，說(shuō)明其網(wǎng)絡(luò)性能越好。圖7 和圖8 給出了三種算法在不同網(wǎng)絡(luò)規(guī)模、不同故障點(diǎn)的網(wǎng)絡(luò)時(shí)延和注入率的關(guān)系曲線(xiàn)。得益于上文中均值和方差的優(yōu)化，使得本文算法比RR 和FTR更晚進(jìn)入網(wǎng)絡(luò)飽和狀態(tài)，隨著網(wǎng)絡(luò)規(guī)模的增大，本文數(shù)據(jù)傳輸路徑多樣的特點(diǎn)將愈發(fā)明顯，為了更精確說(shuō)明，表3 和表4 給出了三種算法的飽和注入率η，在網(wǎng)絡(luò)規(guī)模為6×6 時(shí)對(duì)比FTR 和RR 平均提高了12.02%和28.81%，在8×8 時(shí)對(duì)比FTR 和RR 平均提高了18.92%和39.42%。

圖8 8×8 網(wǎng)絡(luò)算法網(wǎng)絡(luò)時(shí)延對(duì)比

表3 6×6飽和注入率對(duì)比η

表4 8×8飽和注入率對(duì)比η

5 結(jié)論

本文通過(guò)對(duì)故障位置預(yù)測(cè)使得數(shù)據(jù)包盡可能在不使用虛通道的情況下以最小路徑傳輸，并且減少在故障節(jié)點(diǎn)周?chē)@行降低故障節(jié)點(diǎn)周?chē)呢?fù)載，針對(duì)RR 算法繞行路徑單一的問(wèn)題做出了改進(jìn)，采用多種容錯(cuò)策略，使得網(wǎng)絡(luò)負(fù)載更加均衡，針對(duì)FTR 算法在為了避免死鎖增加了繞行距離的問(wèn)題上做出了優(yōu)化，減少了部分?jǐn)?shù)據(jù)包的傳輸距離。