宋冠軍，韓江雪

（1.華北計算技術(shù)研究所，北京100083；2.清華大學(xué) 軟件學(xué)院，北京100084）

0 引 言

對于互聯(lián)網(wǎng)絡(luò)而言，她主要由下述4個部分組成：路由算法、流控技術(shù)、交換技術(shù)和拓?fù)浣Y(jié)構(gòu)。在上述四部分中，核心部分是路由算法。也就是說，影響性能的關(guān)鍵的因素在于如何給某一拓?fù)渚W(wǎng)絡(luò)設(shè)計適合的路由算法，讓其在進(jìn)行消息傳遞時花費相對較少的時間。

當(dāng)前已經(jīng)有很多用于構(gòu)造機群系統(tǒng)的交換式高速互聯(lián)網(wǎng)，其中Myinet，Autonet，等都是已經(jīng)成熟的幾個。這些網(wǎng)絡(luò)，一般采用不規(guī)則的拓?fù)浣Y(jié)構(gòu)和蟲孔路由交換技術(shù)。然而由于不規(guī)則網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的復(fù)雜性和不可控性，網(wǎng)絡(luò)中出現(xiàn)環(huán)路即通信重疊的可能性大大增加，進(jìn)而網(wǎng)絡(luò)中更加容易出現(xiàn)死鎖現(xiàn)象。

Sancho，等［1］提出了一種基于深度優(yōu)先搜索的多棵樹路由算法，從而降低了傳統(tǒng)breadthfirst路由算法的路由表數(shù)量，它的啟發(fā)式up／down生成算法，大大提高了路由的效率。Puente，等［2］提出了一種基于不規(guī)則網(wǎng)絡(luò)以偽哈密頓周期為基礎(chǔ)的自適應(yīng)路由機制，明顯削減了傳統(tǒng)的up＊／down＊路由算法的額外開銷，有效地避免死鎖的出現(xiàn)，但也同時造成了路由路徑的增長。A.Jouraku的文章［3］提出的一種自適應(yīng)路由算法，使數(shù)據(jù)包分布的盡可能均衡。Levitin，Karpovsky，和 Mustafa［4］中提出的新算法通過保證最小的路由回路被禁止以消除思索和維護(hù)圖的連通性。

因此，如何提高系統(tǒng)性能并避免死鎖，是本論文主要討論與解決的問題，也是本研究的核心貢獻(xiàn)所在。up＊／down＊路由現(xiàn)在已被廣泛使用，在包括上文提及的多篇論文［5－11］中分別對NOWs系統(tǒng)路由進(jìn)行了不同角度的闡述，但是這些路由方法存在很多問題，比如自適應(yīng)性差，根節(jié)點的瓶頸等問題。在此之上，本文將提出一種新的路由機制即多根節(jié)點自適應(yīng)路由，來在一定程度上彌補原始up＊／down＊路由方式的不足。

1 不規(guī)則網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下的算法介紹

1.1 NOWS體系的構(gòu)成

本文的研究對象是不規(guī)則網(wǎng)絡(luò)的路由新機制。其基本的體系結(jié)構(gòu)如圖1所示。

圖1 基于開關(guān)的不規(guī)則互聯(lián)網(wǎng)絡(luò)

基于開關(guān)的不規(guī)則互連網(wǎng)絡(luò)主要由開關(guān)（switch），處理單元（processing elements）和雙向物理鏈路（bidirectional link）組成。

圖1中可以看到，0－8號是開關(guān)（Switch），每個開關(guān)上有若干個端口（此圖為8個端口）。每個端口可以連接其他開關(guān)的端口，也可以連接本地處理單元（processing elements，PE），還可以空閑不接。

本文以不規(guī)則開關(guān)網(wǎng)絡(luò)為研究對象，所提出的算法可以應(yīng)用到所有不規(guī)則網(wǎng)絡(luò)。

一個互連網(wǎng)絡(luò)可以用網(wǎng)絡(luò)拓?fù)?、交換機制、流控機制和路由算法來描述。由于課題本身已經(jīng)限制了研究的對象是不規(guī)則的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)，因此主要著重于對交換機制、流控機制和路由算法做出更有效率的改進(jìn)。

1.2 up＊／down＊路由算法

網(wǎng)絡(luò)的路由算法也分為直接網(wǎng)絡(luò)的路由和間接網(wǎng)絡(luò)的路由，規(guī)則網(wǎng)絡(luò)的路由和不規(guī)則網(wǎng)絡(luò)的路由。

本文這里濾去與核心問題不相關(guān)的部分，集中介紹不規(guī)則間接網(wǎng)絡(luò)的路由研究情況。

規(guī)則網(wǎng)絡(luò)中由于拓?fù)浣Y(jié)構(gòu)的可控制性，使得一些死鎖問題變得簡單。然而，在網(wǎng)絡(luò)拓?fù)洳灰?guī)則的前提下，路由算法的設(shè)計就變得十分困難，尤其是如何解決死鎖避免就更困難了?，F(xiàn)有的路由算法只是解決了網(wǎng)絡(luò)的死鎖問題，然而與此同時在網(wǎng)絡(luò)的其他特性上就無法兼得。這里主要介紹經(jīng)典的up＊／down＊路由算法。

up＊／down＊路由算法是一種禁止拐彎模型，在DEC Autonet網(wǎng)絡(luò)的路由算法中首次被提出。簡單來說，up＊／down＊路由算法的目的是給每條鏈路標(biāo)注上方向（up）或下方向（down），將網(wǎng)絡(luò)改造成一個無回路的有向圖，最后禁止消息由下方向拐向上方向，以此避免了路由算法中的死鎖。

下面為up＊／down＊算法的步驟：

在拓?fù)渚W(wǎng)絡(luò)中選擇一個根節(jié)點（通常為節(jié)點ID最小的那個節(jié)點），以該節(jié)點為根，生成整個拓?fù)渚W(wǎng)絡(luò)的寬度優(yōu)先搜索樹（BFS樹）；

指定每條物理鏈路的方向。對于鏈路的上方向（up）定義如下：當(dāng)鏈路連接的兩個節(jié)點處在BFS中深度不同的兩層時，從層數(shù)較深的節(jié)點指向?qū)訑?shù)較淺的節(jié)點的方向為上；當(dāng)鏈路連接的兩個節(jié)點處在BFS中深度相同的兩層時，從ID較大的節(jié)點指向ID較小的節(jié)點的方向為上。和上述上方向（up）相反的方向即為下方向（down）；

計算路由表。對于每個節(jié)點計算它與其他各個節(jié)點的最短路徑，但是為了避免死鎖，路徑中只允許出現(xiàn)從上到上（up to up）、從下到下（down to down）和從上到下（up to down）3種拐彎，從下到上（down to up）是非法的。通過屏蔽環(huán)路形成條件中的一個，我們能夠確保最后生成的路由路徑不存在回路依賴關(guān)系，也就避免了死鎖。

圖2顯示了一個包含9個結(jié)點的網(wǎng)絡(luò)圖G（V，E），圖3（圖中箭頭方向為up方向）所對應(yīng)的廣度優(yōu)先搜索（BFS）生成樹T（G）以及該生成樹各個邊上方向的指定情況。需要注意的一點是對于每條邊的up方向通道，都有一條反向的down方向的通道組成雙向連接，考慮到圖示效果需清晰的原則，該圖中未標(biāo)出down方向。

圖2 基于開關(guān)的不規(guī)則拓?fù)浼捌渫ǖ老嚓P(guān)

up＊／down＊算法的優(yōu)勢在于全部結(jié)點的硬件構(gòu)造與軟件設(shè)計簡易，與此同時該算法還提供了一定的網(wǎng)絡(luò)自適應(yīng)性。

但是，up＊／down＊算法也存在許多缺點。比如：

首先，由于路由算法背身的算法原理，導(dǎo)致在很多情況下所選的路徑并不是最短路徑，這樣一來，消息的傳輸延時明顯上升，嚴(yán)重影響網(wǎng)絡(luò)性能。

第二，由于樹本身的結(jié)構(gòu)使然，網(wǎng)絡(luò)擁塞容易趨向于根結(jié)點附近，同時較難疏散，這就是的網(wǎng)絡(luò)關(guān)鍵路徑傳輸效率大幅降低，直接影響了網(wǎng)絡(luò)的吞吐率。

最后，由于算法在高層結(jié)點處即算法對應(yīng)生成樹的葉結(jié)點處屏蔽的轉(zhuǎn)彎數(shù)較多，使得整個網(wǎng)絡(luò)的通道利用率出現(xiàn)了嚴(yán)重的不平衡，降低了網(wǎng)絡(luò)的性能。并且隨著網(wǎng)絡(luò)規(guī)模的擴大，上述問題變得尤其凸顯。

2 多棵樹路由算法

在上節(jié)中，介紹了不規(guī)則網(wǎng)絡(luò)拓?fù)渲械囊环N無死鎖算法up＊／down＊算法。但是該算法有許多顯而易見的問題，主要有以下三點問題最為嚴(yán)重：

第一網(wǎng)絡(luò)中單根節(jié)點的路由會使得網(wǎng)絡(luò)的負(fù)載分布不平衡，進(jìn)而使得根節(jié)點成為網(wǎng)絡(luò)的瓶頸；第二由于拐彎的限制使得高層節(jié)點附近通道利用率增加；第三網(wǎng)絡(luò)中路由的平均距離明顯增加。這是我們研究多棵樹路由算法的直接動機。

那么我們所提出的新路由算法就應(yīng)該具有以下長處：新路由算法要做到平衡各個通道之間的負(fù)載，不能出現(xiàn)網(wǎng)絡(luò)的負(fù)載大部分集中在少部分通道的情況；新路由算法要盡量降低網(wǎng)絡(luò)中鏈路的長度，同時還要兼顧避免或減少死鎖發(fā)生的特性；若新路由算法可能包含死鎖，那么應(yīng)含有解決死鎖的流控機制。

多棵樹路由算法就是將以上三點作為研發(fā)的最終目的而提出的一種新的路由算法。

本文所提出的多棵樹路由算法由三部分組成，第一部分是路由表的生成規(guī)則，也就是路徑的生成算法；第二部分是多棵樹路由采用的交換技術(shù)；第三部分是多棵樹路由采用的流控機制，其中包括平時的流控方式和產(chǎn)生死鎖后用于死鎖恢復(fù)的特殊流控方式。

2.1 路由表的生成算法

我們將圖2所對應(yīng)的不規(guī)則網(wǎng)絡(luò)拓?fù)溥m當(dāng)簡化，去掉雙鏈路，將之抽象后得到如圖4所示的模擬拓?fù)浣Y(jié)構(gòu)。

圖4 原始物理模型抽象簡化后的模擬拓?fù)浣Y(jié)構(gòu)

根據(jù)圖4的模擬拓?fù)浣Y(jié)構(gòu)，我們分別選擇節(jié)點1或者節(jié)點8為根節(jié)點，按照up＊／down＊規(guī)則產(chǎn)生的路由路徑是不同的，在總共的72條路徑中，有17條發(fā)生了變化，其中以節(jié)點8為根節(jié)點產(chǎn)生的新路徑比原路徑短的有四條，新路徑比原路徑長的同樣是四條，而新路徑和原路徑一樣長的有九條。若我們將原來的節(jié)點1稱為主根，節(jié)點8稱為輔助根，在輔助根生成的新路由表中選擇那些比原有路由表短的路徑代替主根生成的路由表，那么就可以起到縮減路由表中鏈路的平均長度、平衡主根節(jié)點附近通道負(fù)載的作用。我們將這種在原有主根基礎(chǔ)上增加輔助根的路由算法稱為多棵樹路由算法。

該算法的具體定義如下：

算法1：createMTRRouter（net，n）

功能：多棵樹路由表生成算法

輸入：用無向圖表示的不規(guī)則拓?fù)渚W(wǎng)絡(luò)net，根節(jié)點數(shù)量n

輸出：路由表routerTable

過程：

1.隨機選定一個節(jié)點r作為主根節(jié)點；

2.net＝setLevel（net，r）；

3.routerTable＝findRoute（net）；

4.for（k＝1；k＜n；k＋＋ ）

5.隨機選定一個節(jié)點r’作為副根節(jié)點；

6.net＝setLevel（net，r’）；

7.routerTable’＝findRoute（net）；

8.for（i＝0；i＜net中的節(jié)點數(shù) ；i＋＋）

9.for（j＝0；j＜net中的節(jié)點數(shù) ；j＋＋）

10.if（routerTable［i］［j］.length＞ router－Table’［i］［j］.length）

11.將routerTable［i］［j］的路徑替換成routerTable’［i］［j］的路徑；

12.end if

13.end for

14.end for

15.end for

16.返回routerTable；

算法2：setLevel（net，root）

功能：對一個不規(guī)則拓?fù)渚W(wǎng)絡(luò)中的鏈路設(shè)定方向。

輸入：鏈路未分配方向的拓?fù)渚W(wǎng)絡(luò)net，根節(jié)點的ID root。

輸出：鏈路已分配方向的拓?fù)渚W(wǎng)絡(luò)net。

過程：

1.根據(jù)root節(jié)點，用BFS算法計算所有節(jié)點的深度；

2.for（net的第一條鏈路k－＞最后一條鏈路）

3.if（k的源節(jié)點深度 ＞k的目的節(jié)點深度 ）

4.k的方向附為0； ／／up

5.end if

6.if（k的源節(jié)點深度 ＜k的目的節(jié)點深度 ）

7.k的方向附為1； ／／down

8.end if

9.if（k的源節(jié)點深度＝＝k的目的節(jié)點深度）

10.if（k的源節(jié)點ID＞ k的目的節(jié)點ID）

11.k的方向附為0； ／／up

12.end if

13.if（k的源節(jié)點ID＜ k的目的節(jié)點ID）

14.k的方向附為1； ／／down

15.end if

16.end if

17.end for

18.返回net；

算法3：findRoute（net）

功能：對一個拓?fù)渚W(wǎng)絡(luò)建立路由表。

輸入：鏈路已分配方向的拓?fù)渚W(wǎng)絡(luò)net。

輸出：路由表routerTable。

過程：

1.for（i＝0；i＜net的節(jié)點數(shù) ；i＋＋ ）

2.for（j＝0；j＜net的節(jié)點數(shù) ；j＋＋ ）

3.visit［節(jié)點j］＝false； ／／訪問記錄

4.end for

5.for（節(jié)點i的第一條鏈路link－＞ 節(jié)點i的最后一條鏈路）

6.if（visit［link的目的節(jié)點］＝＝false）

7.visit［link的目的節(jié)點］＝true；

8.nodeQueue.addLast（link的目的節(jié)點）；

9.directionQueue.addLast（link的方向）；

10.linkQueue.addLast（new queue（link））；

11.routerTable［i］［link的目的節(jié)點］.add（link）；

12.end if

13.end for

14.while（nodeQueue不為空）

15.node＝nodeQueue.removeFirst；

16.lastDirection＝directionQueue.removeFirst；

17.lastRoute＝linkQueue.removeFirst；

18.for（節(jié)點node的第一條鏈路link－＞ 節(jié)點i的最后一條鏈路）

19.if（visit［link的目的節(jié)點］＝＝false）

20.if（link的方向 ＞＝lastDirection）

21.／／只允許路徑中出現(xiàn)0－＞0，0－＞1，1－＞1的拐彎，屏蔽1－＞0的拐彎

22.visit［link的目的節(jié)點］＝true；

23.nodeQueue.addLast（link的目的節(jié)點）；

24.directionQueue.addLast（link的方向）；

25.newRoute＝lastRoute.copy；

26.newRoute.addLast（link）；

27.routerTable［i］［link的目的節(jié)點］.add（newRoute）；

28.linkQueue.addLast（newRoute）；

29.end if

30.end if

31.end for

32.end while

33.end for

34.返回routerTable；

通過該算法，我們就得到了用多棵樹算法計算得到的路由表。但是由于將輔助根的路由表的一部分替換掉了主根生成的路由表，因此up＊／down＊規(guī)則產(chǎn)生的無死鎖特性將不復(fù)存在。因此，我們需要在流控方式上采取與up＊／down＊算法不同的，帶有死鎖恢復(fù)功能的特殊流控方式。

2.2 多棵樹路由的流控機制

我們知道兩種解決死鎖問題的流控機制，虛通道和冒泡通道。通過研究兩種流控方式我們發(fā)現(xiàn)，以一條物理通道劃分為兩條虛通道為例，虛通道流控機制在沒有死鎖發(fā)生時，只有一條虛擬通道被利用，物理通道的利用率很低，在死鎖發(fā)生后可以通過第二條虛擬通道有效的解決死鎖問題；冒泡通道的流控機制只拿出一個flit的buffer，即冒泡通道，來解決死鎖問題，在死鎖未發(fā)生時通道用幾乎全部的buffer來運送消息，但是一旦發(fā)生死鎖，系統(tǒng)就會選擇一條消息，用冒泡通道運送該消息，所以當(dāng)死鎖發(fā)生時，每次只能運送一條消息，其他消息都要停滯。因此，虛通道技術(shù)在死鎖發(fā)生不頻繁時效率較低，而死鎖發(fā)生時效率較高；與之相反，冒泡通道在死鎖未發(fā)生時效率較高，但死鎖發(fā)生頻繁時效率較低。

我們發(fā)現(xiàn)，在多棵樹算法選用一個輔助根時，實際上路由表只有四條鏈路選擇了比原來只有主根的時候更短的路由路徑，因此，表中的絕大部分路徑還是滿足原來的up＊／down＊算法提供的無死鎖特征的。那么可以想見，在系統(tǒng)實際運行、系統(tǒng)負(fù)載不高的情況下，一定是處于正常狀態(tài)的時間更長，而只有少數(shù)時間處在死鎖狀態(tài)。因此如果我們選擇虛通道的流控方式，等于在絕大部分時間內(nèi)都處于效率不高的正常狀態(tài)。因此，我們在多棵樹路由算法中，選擇冒泡通道作為系統(tǒng)的特殊流控機制。

2.3 多棵樹路由的交換機制

我們知道兩種最為常見的交換方式，虛跨步交換和蟲孔交換。兩種交換方式的主要區(qū)別在于，虛跨步交換在消息發(fā)生堵塞時依然轉(zhuǎn)移報文，因此需要每個通道的buffer至少要能夠緩沖整個消息；而蟲孔交換在消息發(fā)生堵塞時，就地緩沖報文，不再向前推進(jìn)，所以對通道的buffer長度沒有要求，在buffer較小的情況下依然適用（理論上只有一個flit就夠）。但是一旦拉得很長的消息被就地緩沖，勢必會引起更多消息的堵塞，造成更多的死鎖。

在蟲孔交換和虛通道流控被廣泛使用的現(xiàn)在，研究人員會在不規(guī)則網(wǎng)絡(luò)中考慮將這兩種方式聯(lián)合使用。然而，西班牙瓦倫西亞大學(xué)的J.Duato先生等人在中指出在不規(guī)則網(wǎng)絡(luò)中蟲孔交換并不是最好的選擇，通過測試比較發(fā)現(xiàn)：

（1）對于蟲孔交換緩沖空間的大小限制了線路的長度，然而虛跨步交換就不會出現(xiàn)這樣的問題。

（2）由于在報文阻塞時蟲孔交換就地緩沖報文，而虛跨步轉(zhuǎn)移報文，所以虛跨步方式使得路由具有了更大的自適應(yīng)性。

（3）在簡單的開關(guān)架構(gòu)之下，虛跨步交換表現(xiàn)出與蟲孔交換相同的性能，在長報文的情況下，表現(xiàn)更為出色。

網(wǎng)絡(luò)的鏈路的不確定性從而使得網(wǎng)絡(luò)延時和緩沖及通道等資源難以確定。該論文指出，在不規(guī)則拓?fù)渚W(wǎng)絡(luò)中虛跨步交換技術(shù)是最合理的選擇。在通道的buffer不是非常珍惜的情況下，采取虛跨步交換在死鎖發(fā)生是也會有更好的表現(xiàn)。

3 算法性能模擬與比較

本實驗是通過模擬器仿真真實的機群環(huán)境，并通過調(diào)整模擬器的輸入?yún)?shù)來達(dá)到模擬不同的硬件條件下，多棵樹路由算法的表現(xiàn)。本文用于對照實驗的是經(jīng)典的up＊／down＊路由算法，選取該算法作為對照是因為該算法是不規(guī)則拓?fù)渚W(wǎng)絡(luò)常用的路由算法之一，因此對照試驗的結(jié)果更有參考價值和意義。

我們進(jìn)行了多種角度的實驗，因此在每條實驗結(jié)果前都會有關(guān)于該實驗條件的詳細(xì)說明。所有圖表中的數(shù)據(jù)都是在相同參數(shù)下反復(fù)試驗20次，以取平均值的方式得出的統(tǒng)計結(jié)果，因此結(jié)果的偶然性和隨機性很低，參考價值更大。

實驗中輸入?yún)?shù)的詳細(xì)說明如下：

·nodeNumber：網(wǎng)絡(luò)中的節(jié)點數(shù)，也就是網(wǎng)絡(luò)中的處理單元／開關(guān)數(shù)量；

·nodeBuffer：網(wǎng)絡(luò)中一條通道的緩沖區(qū)大?。?/p>

·degree：節(jié)點的出入度限制；

·totalCycle：系統(tǒng)運行的總周期數(shù)；

·messageLength：系統(tǒng)生成消息時的長度；

·messagePerCycle：系統(tǒng)每隔多少周期注入一條消息；

·rootNumber：多棵樹算法中根的總數(shù)；

·Continue：系統(tǒng)在執(zhí)行完totalCycle之后是否繼續(xù)執(zhí)行。

實驗結(jié)果反饋的輸出參數(shù)如下：

·AverageLength：平均長度，即路由表中所有路徑的平均長度；

·ArrivalPercentage：到達(dá)率，即totalCycle執(zhí)行完畢時送到的消息占發(fā)送出的所有消息的百分比；

·Traffic－R：送達(dá)的消息總長度（以Flit為單位）／（總周期數(shù)＊網(wǎng)絡(luò)節(jié)點數(shù)），衡量網(wǎng)絡(luò)能力的重要參數(shù)之一；

·AddCycles：附加周期數(shù)，即totalCycle執(zhí)行完后，系統(tǒng)又附加了多少周期才將系統(tǒng)中所有未送達(dá)的消息送達(dá)。

3.1 路由表平均路徑長度的比較

使用多棵樹算法解決了路由表中路徑過長的問題，我們測試時分別對節(jié)點數(shù)8、16、32、64，及degree＝2、3、4、5的情況下對兩種算法生成的路由表平均長度進(jìn)行比較，其中多棵樹算法的rootNumber設(shè)為4。結(jié)果如圖5及圖6所示。

圖5 up＊／down＊算法平均路徑長度

從兩圖對比我們能夠明顯看出，多棵樹算法的平均路徑長度比相同條件下的up＊／down＊算法減少明顯，特別是在degree＝2的情況下，節(jié)點數(shù)為64的網(wǎng)絡(luò)的平均路徑由6.77827下降到4.69940，下降幅度高達(dá)30.6%。這說明多棵樹路由算法對降低路由平均路徑由非常明顯的效果。

圖7是一張逐漸增加輔助根節(jié)點，路徑平均長度的變化圖，節(jié)點數(shù)量固定在64個，從該圖中可以看出，隨著輔助根增加，路徑平均長度不斷減小，但輔助根數(shù)量從2增至3后，路徑長度變化已很不明顯，說明3個輔助根（root Number＝4）是一個比較理想的極值。

3.2 在負(fù)載變化的網(wǎng)絡(luò)中的性能比較

通過修改messagePerCycle參數(shù)的大小，我們可以任意修改消息注入的快慢。于是我們選擇nodeNumber＝64、nodeBuffer＝32、degree＝2、totalCycle＝10000、message－Length＝30作為不變量，來檢查messagePerCycle從9（網(wǎng)絡(luò)負(fù)載低）到3（網(wǎng)絡(luò)負(fù)載極高）的變化過程中，up＊／down＊算法和多棵樹（MTR）算法（rootNumber＝4）的各項指標(biāo)差異，實驗結(jié)果如圖8～圖10所示。

圖8 AddCycles隨負(fù)載變化（節(jié)點數(shù)64）

我們可以看出，多棵樹算法在負(fù)載由低到高的過程中，性能發(fā)揮非常穩(wěn)定。圖8中，當(dāng)messagePerCycle從6變?yōu)?時，up＊／down＊算法的附加周期出現(xiàn)了一個突變，隨后則一路飆升；多棵樹路由算法的附加周期的增長卻十分緩慢，證明多棵樹路由算法依然能在短時間內(nèi)將系統(tǒng)囤積的消息消耗掉。圖9也很好的證明了這一點，在高負(fù)載條件下，多棵樹算法的運載能力開始大幅度領(lǐng)先于up＊／down＊算法。圖10顯示了隨著系統(tǒng)的負(fù)載增大，消息在指定的周期內(nèi)被送達(dá)目的節(jié)點的概率。多棵樹算法即使在系統(tǒng)負(fù)載很大的情況下，仍然能夠保持接近1的送達(dá)率；而up＊／down＊算法的送達(dá)率卻在高負(fù)載條件下出現(xiàn)了明顯的下滑。

為了證明多棵樹算法在不同網(wǎng)絡(luò)規(guī)模下的表現(xiàn)，我們又對節(jié)點數(shù)為32的網(wǎng)絡(luò)進(jìn)行了同樣的實驗，實驗結(jié)果證明32個節(jié)點產(chǎn)生的結(jié)果基本與64節(jié)點下的實驗結(jié)果相類似。

64節(jié)點和32節(jié)點均屬于大規(guī)模網(wǎng)絡(luò)，那么為了驗證在小型網(wǎng)絡(luò)（8節(jié)點、16節(jié)點）中兩種算法的效率如何，我們又進(jìn)行了兩輪實驗，第一輪針對16節(jié)點的網(wǎng)絡(luò)（nodeNumber＝16、nodeBuffer＝32、degree＝2、totalCycle＝10000、messageLength＝30），二輪針對8節(jié)點網(wǎng)絡(luò)的實驗（nodeNumber＝8、nodeBuffer＝32、degree＝2、totalCycle＝10000、messageLength＝30），8節(jié)點的小規(guī)模網(wǎng)絡(luò)的實驗結(jié)果與16節(jié)點時類似，多棵樹的算法在高負(fù)載條件下的運載能力沒有明顯高于up＊／down＊算法；多棵樹算法的送達(dá)率在高負(fù)載情況下也有了明顯的下降。實驗結(jié)果顯示出多棵樹算法在網(wǎng)絡(luò)規(guī)模變小時出現(xiàn)了效率的下滑，究其原因，在于多棵樹算法提高網(wǎng)絡(luò)路由性能的主要途徑是降低了路由表路徑的平均長度，但當(dāng)網(wǎng)絡(luò)規(guī)模變小時，up＊／down＊規(guī)則生成的路徑的平均長度本身就會減小，多棵樹算法的提升空間非常有限，而且由于多棵樹是有死鎖的算法，在平均路徑小的網(wǎng)絡(luò)中，死鎖的產(chǎn)生會更加頻繁，因此多棵樹算法在死鎖恢復(fù)上的開銷時間將會比網(wǎng)絡(luò)規(guī)模增大時更多。這兩種因素結(jié)合起來就導(dǎo)致了在網(wǎng)絡(luò)規(guī)模變小時，多棵樹路由算法的效率出現(xiàn)了下降。

通過以上3個參數(shù)的驗證，我們證明了多棵樹算法在網(wǎng)絡(luò)規(guī)模較大時存在很大優(yōu)勢：對于系統(tǒng)的負(fù)載情況的敏感度遠(yuǎn)遠(yuǎn)低于up＊／down＊算法，在任何種類的負(fù)載下都能發(fā)揮出穩(wěn)定的性能和表現(xiàn)。但在網(wǎng)絡(luò)規(guī)模較小時，多棵樹算法由于自身局限性效率有所下降，但還是略高于up＊／down＊算法。

3.3 實驗總結(jié)

多棵樹算法在靜態(tài)時的優(yōu)越性。通過比較所生成路由表中路徑的平均長度，我們發(fā)現(xiàn)多棵樹算法在網(wǎng)絡(luò)規(guī)模較大時能夠有效地降低系統(tǒng)中路徑的平均長度，降幅最大可達(dá)30%，避免了up＊／down＊算法中個別路徑長度遠(yuǎn)大于最短路徑長度的問題，但在網(wǎng)絡(luò)規(guī)模較小時，平均路徑長度的縮小量并不明顯；

多棵樹算法在動態(tài)時的優(yōu)越性。通過比較負(fù)載增加時消息運送能力的變化，我們可以看出當(dāng)網(wǎng)絡(luò)規(guī)模較大時，多棵樹算法對網(wǎng)絡(luò)負(fù)載的適應(yīng)能力很強，無論是低負(fù)載狀態(tài)下還是高負(fù)載狀態(tài)下，消息送達(dá)率都穩(wěn)定維持在1左右，這是up＊／down＊算法所遠(yuǎn)遠(yuǎn)達(dá)不到的，同時up＊／down＊算法在高負(fù)載時消息的消化處理時間陡然增高，但多棵樹算法依然平穩(wěn)上升，且上升幅度只有up＊／down＊算法的5%，這說明多棵樹算法很好的處理了up＊／down＊算法因為過于強調(diào)無死鎖，而忽略了網(wǎng)絡(luò)自適應(yīng)能力的問題。但是當(dāng)網(wǎng)絡(luò)規(guī)?？s小時，由于路由表平均距離的縮小量有限，因此多棵樹路由算法出現(xiàn)效率下降的情況，對負(fù)載的增大也變的更為敏感，同時在死鎖恢復(fù)方面花了更多的時間開銷。但對比發(fā)現(xiàn)，多棵樹算法的效率還是要高于up＊／down＊算法。

4 結(jié)束語

本研究提出了一個針對不規(guī)則網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的新算法－多棵樹路由算法，該算法大大降低了路由表的平均路徑長度，平衡了網(wǎng)絡(luò)中各個通道的利用率，同時能夠及時有效的進(jìn)行死鎖恢復(fù)，解決了先前路由算法中通道負(fù)載集中、通道利用率低、路由表平均路徑長度過長的問題。當(dāng)網(wǎng)絡(luò)規(guī)模較大時該算法表現(xiàn)了很強的自適應(yīng)能力，和極高的效率；當(dāng)網(wǎng)絡(luò)規(guī)模較小時也能夠有效地防止死鎖的出現(xiàn)。尤其針對不規(guī)則網(wǎng)絡(luò)該算法有很強的普適性。無論在靜態(tài)特性還是動態(tài)特性上都確實體現(xiàn)出了其優(yōu)秀的能力，達(dá)到了我們預(yù)期的效果。但在小規(guī)模網(wǎng)絡(luò)時效率還有待進(jìn)一步提升。

［1］Sancho J C，Robles A，Duato J.An effective methodology to improve the performance of the Up＊／Down＊ routing algorithm［J］.IEEE Trans on Parallel and Distributed Systems，2004，15（8）：740－754.

［2］Puente V，Gregorio J A，Vallejo F，et al.Highperformance adaptive routing for networks with arbitrary topology［J］.Journal of Systems Architecture，2006，52（6）：345－358.

［3］Jouraku A，Koibuchi M，Amano H.An effective design of deadlock－free routing algorithms based 2Dturn model for irregular networks［J］.IEEE Trans on Parallel and Distributed Systems，2007，18（3）：320－333.

［4］Levitin L，Karpovsky K，Mustafa M.Minimal sets of turns for breaking cycles in graphs modeling networks［J］.IEEE Trans Parallel and Distributed Systems，2010，21（9）：1342－1953.

［5］Moraveiji R，Sarbazi－Azad H，Zomaya A Y.A general methodology for routing in irregular networks［C］／／Proc 17th Euromicro Int Conf on Parallel，Distributed and Network－Based Processing，2009：155－160.

［6］Moraveiji R，Sarbazi－Azad H，Zomaya A Y.Multispanning tree zone－ordered label－based routing algorithms for irregular networks［J］.IEEE Trans on Parallel and Distributed Systems，2011，22（5）：817－832.

［7］Lysne O，Skeie T，Reiemo S，et al.Layered routing in irregular networks［J］.IEEE Trans on Parallel and Distributed Systems，2006，17（1）：51－65.

［8］Theiss I，Lysne O.FRoots：A fault－tolerant and topologyflexible routing technique［J］.IEEE Trans on Parallel and Distributed Systems，2006，17（10）：1136－1150.

［9］Akiya Jouraku.An effective design of deadlock－free routing algorithms based on 2Dturn model for irregular network［J］.IEEE Transactions on Parallel and Distributed Systems，2007，18（3）：320－333.

［10］Li Xiaoming，F(xiàn)u Fangfa，Yang Chao，et al.A solution to irregular 2－D mesh topology network－on－chip［J］.Energy Procedia，2011，13：888－895.

［11］Moraveji R，Sarbazi－Azad H，Zomaya A Y.A general methodology for direction－based irregular routing algorithms［J］.Journal of Parallel and Distributed Computing，2010，70（4）：363－370.