三維mesh網中無死鎖的平面自適應路由方法

2023-10-08 23:12:54 1

專利名稱：三維mesh網中無死鎖的平面自適應路由方法
三維mesh網中無死鎖的平面自適應路由方法技術領域三維mesh網中無死鎖的平面自適應路由方法屬於分布式高性能容錯計算技術領域。
技術背景在當今的實驗用及商用的多計算機系統中，mesh網是一種被廣泛利用的拓撲結構。k元 n維mesh網是指一個n維的網格結構，在每一維上有k個結點。多計算機系統的性能在最大 程度上取決於系統中點到點的通訊方法的性能。因此，很有必要提出一些應用於mesh網的高 性能的容錯路由方法。Glass和Ni提出的轉彎模型是一個具有重要意義的部分自適應的路由方法。基於轉彎模 型，路由方法可以通過限制某些轉彎消除通道間的環相關，達到避免死鎖的效果，而不必添 加額外的虛擬通道。基於轉彎模型也可以擴展出具有容錯性能的方法。Duato對中的Duato 協議進行了擴展，實現了 mesh網中的無死鎖完全自適應容錯路由。Chien和Kim提出了另一個具有重要意義的部分自適應路由方法一一平面自適應路由 (Planar Adaptive Routing),此方法將路由限制在一系列連續的平面內，只需三條虛擬通 道就可以在任何維數的網絡內避免死鎖。然而，在這種方法所應用的塊狀故障模型中，都會 有一部分非故障點像故障點一樣失效，這對於高維的mesh網會造成很嚴重的計算能力的損 失。Gomez提出了一種通過選擇中間節點而實現的兩階段容錯路由方法，從源節點到中間節 點和從中間節點到目標節點分別使用不同的虛擬子網，在每一子網內部使用Duato的完全自 適應協議，兩個子網使用相同的自適應虛擬通道，但使用不同的逃逸通道，也就是說，共需要三條虛擬通道。向東提出了局部安全性信息並將其用於指導超立方體中的容錯路由，在整個超立方體不 安全時仍然可以在子立方裡實現有效的路由。向東等提出了一種新的擴展局部安全性信息， 並且中平面故障塊模型來指導mesh網中的容錯路由，這種方法在建立故障塊是不需要使任何 非故障點失效。塊狀故障模型是一種最為常用的故障模型，但是這種模型會使一些非故障節點失效。少 數的故障節點可能會使很多甚至全部的非故障節點失效，這種現象在高維的網絡中更為明顯。 Wang提出了最小連通部件(MCC)故障模型的概念，對於平面的MCC，每個節點在其所在每個 平面內兩份安全性信息。MCC比塊狀模型使更少的非故障節點失效，可以更有效指導最短路 徑路由。三維的MCC比平面MCC使更少的非故障節點失效，但是對於本發明中所使用的平面 自適應路由，平面MCC更為適用。對於自適應的容錯路由方法，通常需要將每條物理通道劃分為一定數量的虛擬通道來實 現死鎖避免方法，通道上的物理資源(如緩存、帶寬)會分配到各個虛擬通道之上。因此， 實現死鎖避免所需要虛擬通道個數成為影響路由方法資源利用效率的重要因素，使用更少的 虛擬通道，可以使每條虛擬通道分配到更多的資源，提高方法效率，尤其是在物理資源比較 有限的情況下；但是，更少的虛擬通道也會使得設計死鎖避免方法的難度增加。一個A元"維mesh網有r個節點，兩個節點ra a u2a々和^A./…6力^之間有連 接若且唯若兩節點坐標有且只有一位不同，並且I"M,I = 1。一個mesh網中的非故障節點的安全性信息可通如下遞歸方式定義如果節點在兩個不同 維上存在故障或不安全的鄰居節點，那就該節點為不安全節點；否則該節點為安全節點。故 障點與不安全共同構成矩型的故障區域，不安全點在某些平面內仍然可以被使用。在本發明 中，如果源節點到目標節點的路由路徑長度等於兩點之間的距離，並且路徑上的節點均為非 故障點，那麼我們稱此路徑為最短可用路徑。二維mesh網中故障點與不安全點集合F構成的故障塊具有如下特點(1)在矩型區域 的邊界處沒有故障點；(2)矩型區域的內部包含所有的集合F中的故障點與不安全點；(3) 矩型區域的內部不包含任何集合F之外的節點。Mesh網中的節點根據其安全性可以分為故障節點、不安全節點與安全節點三類。如果一 個網絡系統內所有的節點均為不安全點或故障點，那麼稱這個網絡系統為不安全的。 需要強調的是，已有的大多數方法都將不安全節點標記為失效，已失效的節點不能作為消息 的源節點或目標節點。而在本發明中，不安全節點仍然可以作為源節點或目標節點使用，這 也使得路由方法的性能有了很大的提高。平面自適應路由方法(PAR)給出了一個簡單的用於n維mesh網的死鎖避免方法，每條 物理通道需要三條虛擬通道。下面我們以三維的mesh網為例來說明平面自適應路由方法的方 法。mesh網首先被劃分為一系列的平面，對於三維的mesh網，分為x-y和y-z兩種平面。路 由消息首先在x-y平面內路由，當x方向的偏移量變為0以後，消息跳轉至y-z平面繼續路由。 x-y平面又進一步被分成上升子網(圖la)與下降子網(圖lb)。 x-y平面中的虛擬通道分配方案如下上升子網中X方向使用虛擬通道C;, y方向使用Q+;下降子網中X方向使用C2，y方向使用q-。在y-z平面，上升子網(圖lc)中y方向使用虛擬通道c/， z方向使用q+; 下降子網中y方向使用C2， z方向使用o-。在三維mesh中使用以上的虛擬通道分配方案，可以有效的避免死鎖。但是，可以發現， Z方向的C7和C2通道，X方向的Q通道，並沒有得到利用。這些空閒通道的存在意味著，在 三維mesh網中避免死鎖所需的虛擬通道的個數仍然有可以減少的空間。 發明內容該發明的目的在於設計了一種三維mesh網中無死鎖的平面自適應路由方法，在三維mesh 網的各節點中依次按以下步驟實現的 步驟(l):初始化把每條物理通道被劃分為兩條虛擬通道C7和Q，這兩條通道均為兩向通道，C/通道分為o+和q-兩個方向的通道，q通道分為q+和q-兩個方向的通道，"+"和"_"表示消息傳 輸的正負方向；把三維mesh網中的虛擬子網的劃分為xy平面和yz平面；xy平面劃分為上升子網與下降子網。在上升子網中，x方向分配雙向通道C;， y方向分 配單向通道G+，在下降子網中，x方向分配雙向通道C2， y方向分配單向通道C;-;yz平面劃分為上升子網與下降子網。在上升子網中，z方向分配雙向通道C;， y方向分配 單向通道C2+，在下降子網中，z方向分配雙向通道C2， y方向分配單向通道Cr;步驟(2):依次按以下步驟進行消息路由步驟(2.1):路由消息首先在xy平面路由，路由開始時，優先選擇x方向進行路由，根據 源節點或當前節點相對於目的節點在y方向上的偏移方向，選擇將消息插入xy子平面上升子 網或下降子網，並且始終保持在此子網內進行自適應路由，直到x方向偏移量變為零，其中， 所述偏移量指的是目的節點和當前節點在各維上的坐標之差；步驟(2.2):當x方向偏移量變為零時路由消息跳轉到yz平面繼續路由，根據y方向上的 偏移方向，選擇將消息插入yz平面的上升或下降子網，並在此平面內保持自適應路由，直到 消息到達目的節點；在步驟(2.1)和歩驟(2.2)中，所述平面自適應路由是指先計算當前節點和目的節點在最短 路徑方向上的自由度，若其中一個方向上存在故障或不安全節點，則選擇另一個方向，若兩 個方向上均為故障或不安全節點，則路由失敗；若路由消息在所述最短路徑上只有一個候選方向，且此方向上的鄰居節點為故障節點或 不安全節點，則路由消息應在非最短路徑上進行繞行路由，並且在之後返回最短路徑路由。在進行所述平面自適應路由時，先要計算當前節點和目的節點在各方向上的偏移量，當 當前節點和目的節點在同一個xy或yz平面內時，如果當前節點在xy或yz平面內有不安全 節點，則找到當前節點的一個在所述平面內安全的鄰居節點進行消息路由，如果目的節點在 xy或yz平面內有不安全節點，則把目的節點的一個在所述平面內安全的鄰居節點作為新的 目的節點。在進行所述平面自適應路由時若當前節點和目的節點在x和y方向偏移均不為零時，如果當前節點在x偏移方向的鄰 居節點安全，則將消息沿x偏移方向路由至下一節點，否則將消息沿y偏移方向路由至下一 節點；若當前節點與目的節點在x方向有偏移，y方向無偏移時，如果當前節點在x偏移方向的 鄰居節點安全，則將消息沿x偏移方向路由至下一節點，否則，將消息沿y方向繞行路由， 當到目標節點的最短路徑存在時，恢復到沿x偏移方向路由；若當前節點與目的節點在y方向有偏移，x方向無偏移時，如果當前節點在y偏移方向的 鄰居節點安全，則將消息沿y偏移方向路由至下一節點，否則將消息沿x方向繞行路由，當 到目標節點的最短路徑存在時，恢復到沿y偏移方向路由。在進行所述平面S適應路由時若當前節點和目的節點在y和z方向偏移均不為零時，如果當前節點在y偏移方向的鄰 居節點安全，則將消息沿y偏移方向路由至下一節點，否則將消息沿z偏移方向路由至下一 節點；若當前節點與目的節點在y方向有偏移，z方向無偏移時，如果當前節點在y偏移方向的 鄰居節點安全，則將消息沿y偏移方向路由至下一節點，否則，將消息沿z方向繞行路由， 當到目標節點的最短路徑存在時，恢復到沿y偏移方向路由；若當前節點與目的節點在z方向有偏移，y方向無偏移時，如果當前節點在z偏移方向的 鄰居節點安全，則將消息沿z偏移方向路由至下一節點，否則將消息沿y方向繞行路由，當 到目標節點的最短路徑存在時，恢復到沿z偏移方向路由。所述方法採用平面最小連通部件MCC故障模型後，擴展為一種用於三維蟲孔交換mesh 網的平面自適應容錯路由方法，其步驟如下先在三維mesh網的xy和yz的各個子平面內分別建立最小連通部件故障模型；其次，在每個平面上，平面內的節點在兩條對角線方向上分別計算安全性信息， 一個節 點若在兩個與對角線成對稱關係的方向存在故障或不安全節點，那麼此節點被標記為不安全 節點，將安全性進行多輪計算，直至各節點安全性達到穩定狀態；在路由時，根據當前節點與目標節點之間的偏移方向選擇相應方向上的安全性信息指導 路由，其中，所述的兩條對角線方向分別為x+y+和x-y-以及x+y-和x-y+兩個方向。 採用我們改進的方法在mesh網格中進行容錯路由，與傳統的PAR方法相比，當標準化輸入負載和網絡中故障節點數提高時，我們的方法明顯可以提高網絡實際流量，並降低傳輸延遲，從而提高整個網絡的傳輸性能。


圖l平面自適應路由的虛擬通道分配。圖2改進的虛擬通道的分配方案。圖3無故障網絡中節點緩存大小對性能的影響輸入負載0.8故障個數0OPAR uniform Of" AR transpose —來一 PAR uniform ~O~~ PAR transpose管-》—— Gomez uniform 々 Gomez transpose —A—。圖4容錯mesh網中標準化實用負載對性能的影響節點緩存180微片故障個數50OPAR uniform ■ XOPAR transpose —米一 PAR uniform OPAR transpose —貨— Gomez uniform ~Gomez transpose -_ A--。圖5容錯mesh網中故障節點個數對性能的影響節點緩存216微片輸入負載0.2iPAR uniform ~O~ iPAR transpose —PAR uniform X PAR transpose —米一。圖6三維mesh網中無死鎖的平面自適應路由方法流程圖。
具體實施方式
基於以上的虛擬通道分配策略，我們提出了新的自適應無死鎖路由方法，在一般情況下， 路由消息首先在x-y平面路由，當x方向的偏移量變為0時，跳轉到y-z平面繼續路由。在開 始x-y平面路由時，根據源節點與目標節點之間在y方向的偏移方向，選擇將消息插入上升 子網或下降子網，並且始終保持在此子網內路由。在跳轉到y-z平面時，同樣根據y方向上 的偏移方向選擇上升或下降子網並在y-z平面內保持在此子網內路由。如下分別為x-y上升子網、x-y下降子網以及y-z平面上升子網中的路由方法描述。y-z平面 下降子網的路由方法與上升子網中的方法類似，y方向通道由C變為Q-， z方向通道由O 變為Q。值得注意的是，在x-y平面內路由，消息優先選擇x方向進行路由，這樣做是為了 保證路由的自適應性，而在y-z平面，y方向與z方向的路由具有相同的優先級別。下面解釋 每個子網的路由方法 l.x-y平面上升子網路由輸入為當前點cw/t,目標點cfe z，先計算cw r與在各個方向上的距離，其中= XofeW - Icwrr, yq訴d = - :Kcwrr;如果Zo炎er > 0且X方向上q+通道可用，則C/;a朋e/ = Zfb; ;如果 0則0 a""e/ =Se/ec^Z^j, ^Tq+J力如果= 0且JTq^" 〉 0貝lj C/z朋we/ = X(^+力如果Ky^" = 0 且 0且X方向上q+通道可用，則CAa""e/ = 如果J^^ef〈0且X方向上C2-通道可用，則C/za"""-;^"—;如果K#5"<0，則 Ow""e/ = &/ec《Zfc2A J7c/匿;),-如果K j^^ = 0且義o^i" > 0 ，貝U C/ a",ze/ = Xfe+J;如果7oi^e/1 =0且Xo/sW < 0，則C/ww"e/ = Z「C2一；如果1biTsW = 0且％0_僑"=0,則Oza""e/ = /WerwaZ。3. y-z平面上升子網路由輸入為當前點cwr，目標點&W，先計算cm/r與&W在各個方向上的距離，其中Zq膽ef-— Zcz/rr, Ky^" =- 7cwr;如果Zo,W > 0且Z方向上c,+通道可用，貝U C^""e/ =如果Zo炎ef 〈0且Z方向上c廠通道可用，則CAa""e/= Zfc/-);如果〉 0，則 C7 a""e/ = Se/ec^Zfb", ;T(^+;」；如果Jbjf犯f = 0且> 0，則C7w朋e/ = Z(^+人如果1bJ&" =0且Zojfsd 0且Z方向上q+通道可用，則Ow""e/ = Zfe+力如果Zq^" 0,則 CAa""e/ = &/ec《Zfc2), :Ffe+」」；如果= 0且Zo#sef > 0，則C/ a""W = Zfc2+J;如果=0且Zo/se/ < 0，則C7w""e/ = Z(bd;如果= 0且Zo," = 0，貝U C7 a"we/ = /"ter"a/; 下面為用於三維蟲孔交換mesh網的平面自適應容錯路由方法，其死鎖避免方法與前面所述完 全一致輸入為當前點cwr，目標點deW，先計算cwr與在各個方向上的距離，當cwr和 在同 一個x-y (y-z)平面內時，如果cwrr在x-y (y-z)平面內不安全，則找到cwr的一個在 此平面內安全的鄰居v，將消息路由到v;如果&W在x-y (y-z)平面內不安全，則找到 的一個在此平面內安全的鄰居v，將v作為新的目標節點。如果c"7t與&W僅在x或y方向 有偏移，則調用route-in-plane-xy (cmat， deW);如果ckk與c/eW在x禾Q y方向有偏移，則調用 route-in-plane-xy (ci/ r， cfes0; 如果cwr與^fesf在x， y, z方向上均有偏移，貝ll調用 route-in-plane-xy (cwr， c es;如果cw r與僅在z方向上有偏移，貝U調用route習in匿plane-yz (cwn-, 如果cwr與在y禾口 z方向上有偏移，貝!j調用route-in-plane-yz (cwr， (ieW)。當CM/r和^W在x和y方向均有偏移時，如果cwr在x偏移方向的鄰居節點安全，則將 消息沿x偏移方向路由至下一節點；否則將消息沿y偏移方向路由至下一節點。當cw庁與 在x方向有偏移，y方向無偏移吋，如果c^r在x偏移方向的鄰居節點安全，則將消息沿x 偏移方向路由至下一節點；否則，將消息沿y方向繞行路由，當到目標節點的最短路徑存在 時，恢復到沿x偏移方向路由。當cwr與ctew在y方向有偏移，x方向無偏移時，如果cwr 在y偏移方向的鄰居節點安全，則將消息沿y偏移方向路由至下一節點；否則將消息沿x方 向繞行路由，當到目標節點的最短路徑存在時，恢復到沿y偏移方向路由。 方法(c"'T， ctes":當和在z和y方向均有偏移時，如果cwr在z禾Q y偏移方向的鄰居節點均安全， 則隨機選取z或y偏方向，將消息路由至下一節點；如果cwrr在只在一個偏移方向的鄰居節 點安全，則將消息路由至此安全的鄰居節點。當c"/r與^W在z方向有偏移，y方向無偏移 時，如果c" r在z偏移方向的鄰居節點安全，則將消息沿z偏移方向路由至下一節點；否則， 將消息沿y方向繞行路由，當到目標節點的最短路徑存在時，恢復到沿z偏移方向路由。'當 ctz/r與afeW在y方向有偏移，z方向無偏移時，如果o r在y偏移方向的鄰居節點安全，則將消息沿y偏移方向路由至下一節點；否則將消息沿z方向繞行路由，當到目標節點的最短 路徑存在時，恢復到沿y偏移方向路由。在當今的商用與實驗用多計算機系統的網絡設計中，經常用到的是二維和三維的mesh/torus拓撲結構，更高維的網絡拓撲幾乎很少有應用。在傳統的平面自適應路由方法中， 每條物理通道只需要三條虛擬通道就可以在n維的mesh網中避免死鎖，但是在最低維和最高 維上存在著空閒的虛擬通道。本發明提出了一種專門用於三維mesh網的新的平面自適應路由 方法，每條物理通道只需兩條虛擬通道就可以避免死鎖的產生。同時，本發明將此方法擴展 為具有容錯性，使用了平面最小連通部件(MCC)故障模型來指導蟲孔交換網絡中的容錯路 由。大量的模擬實驗數據表明，本方法與原始的平面自適應方法相比，無論在無故障網絡或 是容錯網絡中，都具有更好的性能表現。
權利要求
1、三維mesh網中無死鎖的平面自適應路由方法，其特徵在於所述方法是在三維mesh網的各節點中依次按以下步驟實現的步驟(1)初始化把每條物理通道被劃分為兩條虛擬通道c1和c2，這兩條通道均為兩向通道，c1通道分為c1+和c1-兩個方向的通道，c2通道分為c2+和c2-兩個方向的通道，「+」和「-」表示消息傳輸的正負方向；把三維mesh網中的虛擬子網的劃分為xy平面和yz平面；xy平面劃分為上升子網與下降子網，在上升子網中，x方向分配雙向通道C1，y方向分配單向通道C1+，在下降子網中，x方向分配雙向通道C2，y方向分配單向通道C1-；yz平面劃分為上升子網與下降子網，在上升子網中，z方向分配雙向通道C1，y方向分配單向通道C2+，在下降子網中，z方向分配雙向通道C2，y方向分配單向通道C2-；步驟(2)依次按以下步驟進行消息路由步驟(2.1)路由消息首先在xy平面路由，路由開始時，優先選擇x方向進行路由，根據源節點或當前節點相對於目的節點在y方向上的偏移方向，選擇將消息插入xy子平面上升子網或下降子網，並且始終保持在此子網內進行自適應路由，直到x方向偏移量變為零，其中，所述偏移量指的是目的節點和當前節點在各維上的坐標之差；步驟(2.2)當x方向偏移量變為零時路由消息跳轉到yz平面繼續路由，根據y方向上的偏移方向，選擇將消息插入yz平面的上升或下降子網，並在此平面內保持自適應路由，直到消息到達目的節點；在步驟(2.1)和步驟(2.2)中，所述平面自適應路由是指先計算當前節點和目的節點在最短路徑方向上的自由度，若其中一個方向上存在故障或不安全節點，則選擇另一個方向，若兩個方向上均為故障或不安全節點，則路由失敗；若路由消息在所述最短路徑上只有一個候選方向，且此方向上的鄰居節點為故障節點或不安全節點，則路由消息應在非最短路徑上進行繞行路由，並且在之後返回最短路徑路由。
2、 根據權利要求l所述的在三維mesh網中的無死鎖的平面自適應路由方法，其特徵在於， 在進行所述平面自適應路由時，先要計算當前節點和目的節點在各方向上的偏移量，噹噹前 節點和目的節點在同一個xy或yz平面內時，如果當前節點在xy或yz平面內有不安全節點， 則找到當前節點的一個在所述平面內安全的鄰居節點進行消息路由，如果目的節點在xy或 yz平面內有不安全節點，則把目的節點的一個在所述平面內安全的鄰居節點作為新的目的節 點。
3、 根據權利要求l所述的在三維mesh網中無死鎖的平面自適應路由方法，其特徵在於，在 進行所述平面自適應路由時若當前節點和目的節點在x和y方向偏移均不為零時，如果當前節點在x偏移方向的鄰 居節點安全，則將消息沿x偏移方向路由至下一節點，否則將消息沿y偏移方向路由至下一 節點；若當前節點與目的節點在x方向有偏移，y方向無偏移時，如果當前節點在x偏移方向的 鄰居節點安全，則將消息沿x偏移方向路由至下一節點，否則，將消息沿y方向繞行路由， 當到目標節點的最短路徑存在時，恢復到沿x偏移方向路由；若當前節點與目的節點在y方向有偏移，x方向無偏移時，如果當前節點在y偏移方向的鄰居節點安全，則將消息沿y偏移方向路由至下一節點，否則將消息沿x方向繞行路由，當 到目標節點的最短路徑存在時，恢復到沿y偏移方向路由。
4、 根據權利要求l所述的在三維mesh網中無死鎖的平面自適應路由方法，其特徵在於，在 進行所述平面自適應路由時若當前節點和目的節點在y和z方向偏移均不為零時，如果當前節點在y偏移方向的鄰 居節點安全，則將消息沿y偏移方向路由至下一節點，否則將消息沿z偏移方向路由至下一 節點；若當前節點與目的節點在y方向有偏移，z方向無偏移時，如果當前節點在y偏移方向的 鄰居節點安全，則將消息沿y偏移方向路由至下一節點，否則，將消息沿z方向繞行路由， 當到目標節點的最短路徑存在時，恢復到沿y偏移方向路由；若當前節點與目的節點在z方向有偏移，y方向無偏移時，如果當前節點在z偏移方向的 鄰居節點安全，則將消息沿z偏移方向路由至下一節點，否則將消息沿y方向繞行路由，當 到目標節點的最短路徑存在時，恢復到沿z偏移方向路由。
5、 根據權利要求l所述的在三維mesh網中無死鎖的平面自適應路由方法，其特徵在於，所 述方法採用平面最小連通部件MCC故障模型後，擴展為一種用於三維蟲孔交換mesh網的平 面自適應容錯路由方法，其步驟如下先在三維mesh網的xy和yz的各個子平面內分別建立最小連通部件故障模型；其次，在每個平面上，平面內的節點在兩條對角線方向上分別計算安全性信息， 一個節點若在兩個與對角線成對稱關係的方向存在故障或不安全節點，那麼此節點被標記為不安全節點，將安全性進行多輪計算，直至各節點安全性達到穩定狀態；在路由時，根據當前節點與目標節點之間的偏移方向選擇相應方向上的安全性信息指導路由，其中，所述的兩條對角線方向分別為x+y+和x-y-以及x+y-和x-y+兩個方向。
全文摘要
三維mesh網中無死鎖的平面自適應路由方法屬於分布式高性能容錯計算技術領域，其特徵在於，把節點之間的每條物理通道被劃分為兩條虛擬通道，這兩條通道均為兩向通道，把三維mesh網分為xy和yz兩類平面，每個平面分為上升子網和下降子網，先從x方向開始，在xy平面上進行路由，當x方向偏移量為零時，再跳轉到yz平面進行路由，消息在通往目的節點的最短路徑上有兩個方向的自由度，選擇不存在不安全鄰居節點的方向進行消息路由，當只有一個候選方向時，要在非最短路徑方向繞行路由，之後再返回最短路徑路由；本發明使用故障模型，為平面建立最小連通部件故障模型，為平面內每個節點在兩條對角線方向上分別尋找不安全節點，再按當前節點和目的節點之間的偏移方向選擇安全性路由；本發明顯著提高了網絡的傳輸性能。
文檔編號H04L12/56GK101267394SQ20081010159
公開日2008年9月17日 申請日期2008年3月10日 優先權日2008年3月10日
發明者東 向, 張躍鯉 申請人:清華大學