不使用虛擬通道的2D?Mesh容錯路由算法

張弘博 段新明

摘 要： 提出一種2D?Mesh上不使用虛擬通道的容錯路由算法。目前，同類算法要犧牲掉網絡邊緣的所有節點，還要把所有錯誤都包含到一個錯誤塊中。所提算法雖然也將錯誤包含到錯誤塊中，但是不會犧牲掉網絡邊緣的所有節點，而是在錯誤處形成一個矩形區域，使包在路由時可以發現并繞開它。該算法不使用虛擬通道，能容一個甚至更多錯誤，允許錯誤發生在任何位置，不僅不會降低網絡性能，而且還能獲得與其他算法相似的傳輸延遲。

關鍵詞： 2D?Mesh； 虛擬通道； 容錯路由； 錯誤塊； 網絡無死鎖； 傳輸延遲

中圖分類號： TN915.02?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2018）15?0034?05

Fault?tolerant routing algorithm without virtual channel in 2D?Mesh

ZHANG Hongbo， DUAN Xinming

（Tianjin Polytechnic University， Tianjin 300387， China）

Abstract： A fault?tolerant routing algorithm without virtual channel in 2D?Mesh is proposed in this paper， with which all nodes of network edge aren′t sacrificed， and a rectangular region is formed at the error position to make the routing package find and bypass the error though the error is contained in the error block as the other same kinds of algorithms do. The proposed algorithm doesn′t use any virtual channel， but still can accommodate one or more errors， and allows errors to occur in any locations， which can′t reduce the network performance， but can obtain the transmission delay similar to other algorithms.

Keywords： 2D?Mesh； virtual channel； fault?tolerant routing； error block； network without deadlock； transmission delay

0 引 言

多核處理器通常利用片上網絡來提供片上通信[1]。2D?Mesh因其平面的拓撲結構而被廣泛應用于集成電路制造業。大多數多核處理器使用確定性路由算法，如XY路由算法[2?4]，因為它能充分利用路由器的設計，但XY路由不容錯。設計容錯路由算法的一個主要挑戰就是保證網絡無死鎖。在不使用虛擬通道的片上網絡上，通常用轉彎模型來避免死鎖[5?7]。文獻[6]證明當去掉所有最右列時網絡就是無死鎖的，但是沒有最右列，網絡左側邊緣就很難容錯[8?10]。為了解決這一問題，文獻[8?10]提出了解決方案，但這些解決方案需要犧牲大量的無錯節點。

本文提出一種不使用虛擬通道的2D?Mesh容錯路由算法來解決這一問題。

1 相關知識

文獻[8]提出轉彎模型的概念。如果所有通道之間的轉彎都不能形成環路，那么網絡就不會出現死鎖。轉彎模型的基本思想就是通過禁止最少數量的轉彎，即斷開環路中的一個或幾個轉彎避免形成環路。因此，只要禁止足夠數量的轉彎就可以斷開所有的環路，也就能解決網絡死鎖的問題。

確定性XY路由算法是最簡單的路由算法，該算法禁止4種轉彎，剩下的4種轉彎不能形成環路，因此能解決網絡死鎖的問題。實際上，對于2D?Mesh網絡來說，并不是必須禁止4種轉彎才能斷開環路，最少只要禁止2種轉彎同樣也能斷開環路。路由算法轉彎模型如圖1所示。

本文采用矩形錯誤模型[11]，假設錯誤塊之間不共享邊界。如果兩個錯誤塊共享邊界，那么就會建立一個更大的錯誤塊來代替原來的兩個錯誤塊。同時，本文假設錯誤塊是靜態的[10]，即包在路由時網絡不會出現新的錯誤塊。

1） 2D?Mesh下的錯誤塊是包含危險節點的矩形區域。

2） 危險節點就是錯誤節點或不安全節點。

3） 無錯節點一開始是安全的，當只有一個鄰居是危險節點時，安全節點會變成半安全的節點。

4） 當有兩個危險鄰居或兩個半安全鄰居時，安全或半安全節點會變成不安全的節點。

5） 錯誤塊的邊界包含水平的、垂直的和斜對角的安全節點。

6） 當錯誤塊的邊界形成環時稱為錯誤環，否則稱為錯誤鏈。

矩形錯誤模型如圖2所示。

2 算法介紹

本文算法根據錯誤塊的具體位置分為9種情況，每種情況都結合類西向優先算法產生容一個錯誤塊的路由算法，錯誤塊的具體分類如圖3所示。

類西向優先算法是當目的節點在源節點的左側時，包向西路由；當目的節點在源節點的正北側或東北側時，包向北路由；當目的節點在源節點的正南側或東南側時，包向南路由；否則包向東路由。

當錯誤出現在網絡西北角時，即FB?1的情況，原本向西路由的包因錯誤塊的東邊界而沿著邊界向南路由；原本向北路由的包因錯誤塊的南邊界而沿著邊界向東路由。

當錯誤出現在網絡北邊界時，即FB?2的情況，原本向西路由的包因錯誤塊的東邊界而沿著邊界向南路由；原本向北路由的包因錯誤塊的南邊界而沿著邊界向東路由；原本向東路由的包因錯誤塊的西邊界而向南路由。

當錯誤出現在東北角時，即FB?3的情況，仍然采用類西向優先算法。

當錯誤出現在西邊界時，即FB?4的情況，原本向西路由的包因錯誤塊的東邊界而沿著邊界路由，若目的節點在北側，則向北路由，否則向南路由；原本向南路由的包因錯誤塊的北邊界而沿著邊界向東路由；原本向北路由的包因錯誤塊的南邊界而沿著邊界向東路由。

當錯誤塊出現在網絡中間時，即FB?5的情況，原本向西路由的包因錯誤塊的東邊界而沿著邊界向南路由；原本向南路由的包因錯誤塊的北邊界而沿著邊界向西路由；原本向東路由的包因錯誤塊的西邊界而沿著邊界向南路由；原本向北路由的包因錯誤塊的南邊界而沿著邊界路由，若目的節點在錯誤塊的北側，則向西路由，否則向東路由。

當錯誤出現在東邊界時，即FB?6的情況，原本向北路由的包因錯誤塊的南邊界而沿著邊界向西路由；原本向南路由的包因錯誤塊的北邊界而沿著邊界向西路由。

當錯誤出現在西南角時，即FB?7的情況，原本向西路由的包因錯誤塊的東邊界而沿著邊界向北路由；原本向南路由的包因錯誤塊的北邊界而沿著邊界向東路由。

當錯誤出現在南邊界時，即FB?8的情況，原本向西路由的包因錯誤塊的東邊界而沿著邊界向北路由；原本向南路由的包因錯誤塊的北邊界而沿著邊界向東路由；原本向東路由的包因錯誤塊的西邊界而沿著邊界向北路由。

當錯誤出現在東南角時，即FB?9的情況，仍然采用類西向優先算法。

3 算法證明

文獻[12]證明當相關通道依賴圖無環時網絡是無死鎖的。之后，文獻[6]證明當破壞掉順時針和逆時針環的最右列時，相關通道依賴圖是無環的。因此，為了證明提出的算法是無死鎖的，本文將對相關通道依賴圖無環做如下證明：如果錯誤沒有出現在網絡左側邊緣，就不會生成最右列；如果錯誤出現在網絡左側邊緣，最右列不會構成環。

由默認的類西向優先路由算法可知，西北彎、西南彎、北東彎和南東彎是合理的轉彎，并且它們之間的組合也不會出現環，其余轉彎只在幾個特殊情況中出現。如圖4所示，默認情況下的類西向優先算法允許出現的轉彎只有4個。

聲明1：東南彎只出現在FB?4，FB?7，FB?8的東北角和FB?2，FB?5的西邊界。

聲明2：東北彎只出現在FB?1，FB?2，FB?4，FB?5的東南角和FB?8的西邊界。

聲明3：南西彎只出現在FB?1，FB?2，FB?4，FB?5的東南角和FB?5，FB?6的北邊界。

聲明4：北西彎只出現在FB?4，FB?7，FB?8的東北角和FB?5，FB?6的南邊界。

聲明5：FB?5東北角既不能出現東南彎，也不能出現北西彎。

聲明6：不允許出現0°和180°的轉彎。

如圖5所示，其余的轉彎只能出現在網絡中特定的位置，并且需要特別標明的是，為了防止形成環路，FB?5的東北角既不允許出現北西彎，也不允許出現東南彎。

引理1 在FB?7，FB?8東北角和FB?2，FB?5西邊界出現的東南彎不屬于任何最右列。

證明：當東南彎出現在FB?7，FB?8的東北角時，無法在其南側形成南西彎來與其組成最右列，因為FB?7，FB?8已經到達網絡南側邊緣；當東南彎出現在FB?2，FB?5的西邊界時，無法在其南側形成南西彎來與其組成最右列。

引理2 在FB?1，FB?2，FB?5東南角和FB?8西邊界出現的東北彎不屬于任何最右列。

證明：當東北彎出現在FB?1，FB?2的東南角時，無法在其北側形成北西彎來與其組成最右列，因為FB?1，FB?2已經到達網絡北側邊緣；當東北彎出現在FB?5的東南角或FB?8的西邊界時，無法在其北側形成北西彎來與其組成最右列。

引理3 在FB?1，FB?2，FB?5東南角和FB?5，FB?6北邊界出現的南西彎不屬于任何最右列。

證明：當南西彎出現在FB?1，FB?2的東南角時，無法在其北側形成東南彎來與其組成最右列，因為FB?1，FB?2已經到達網絡北側邊緣；當南西彎出現在FB?5的東南角或FB?5，FB?6的北邊界時，無法在其北側形成東南彎來與其組成最右列。

引理4 在FB?7，FB?8東北角和FB?5，FB?6南邊界出現的北西彎不屬于任何最右列。

證明：當北西彎出現在FB?7，FB?8的東北角時，無法在其南側形成東北彎來與其組成最右列，因為FB?7，FB?8已經到達網絡南側邊緣；當北西彎出現在FB?5，FB?6的南邊界時，無法在其南側形成東北彎來與其組成最右列。

引理5 當且僅當東南彎出現在FB?4東北角并且南西彎出現在FB?4東南角時才會出現順時針最右列。

證明：根據聲明1和聲明3可知，東南彎可以出現在FB?4的東北角，南西彎可以出現在FB?4的東南角，即可以組成順時針最右列；再根據引理1，引理3可知，順時針最右列只能出現在FB?4的東邊界上。

引理6 當且僅當東北彎出現在FB?4東南角并且北西彎出現在FB?4東北角時才會出現逆時針最右列。

證明：根據聲明2和聲明4可知，東北彎可以出現在FB?4的東南角，北西彎可以出現在FB?4的東北角，即可以組成逆時針最右列；再根據引理2，引理4可知，逆時針最右列只能出現在FB?4的東邊界上。

引理7 FB?4右側即使出現最右列也不會構成環。

證明：由引理5和引理6可知，最右列只能出現在FB?4的右側；并且由聲明6可知，不允許出現180°的轉彎，因為FB?4已經到了網絡的左側邊緣，所以就不存在構成環的左列，即FB?4右側即使出現最右列也不會構成環。

定理1 本文提出的算法是無死鎖的。

證明：當網絡中不存在錯誤時，路由采用的是默認的類西向優先路由，所以網絡是無死鎖的。當網絡中存在錯誤時，如果網絡左側邊緣沒有錯誤，即網絡不存在最右列，所以網絡是無死鎖的；如果網絡左側邊緣存在錯誤，根據引理7，即使出現最右列也不會構成環，所以網絡是無死鎖的。

4 實驗仿真

本文采用的仿真環境是BookSim 1.0，通過在不同通信模式下改變注入率的方法來測試算法的性能，依賴的指標是平均延遲，通信模式選用Uniform，對比的算法選用本文提出的算法在網絡中存在一個錯誤塊時的情況，DOR，ROMM，MAD和VAL。因通信模式對網絡基數的限制，實驗采用8×8的網絡結構，其余設置均為BookSim 1.0的默認設置。

如圖6所示，在Uniform通信模式下，當網絡存在一個錯誤塊時，在注入率達到5%之前，FB?1～FB?4算法的平均延遲相近且緩慢增加；當注入率達到6%之后，各算法的平均延遲開始顯著增加并逐漸顯現出差異，其中FB?4增幅最大。需要特別指出的是，FB?0為網絡不存在錯誤塊的情況，平均延遲最小。

如圖7所示，在Uniform通信模式下，當網絡存在一個錯誤塊時，在注入率達到5%之前，FB?5～FB?9算法的平均延遲相近且緩慢增加；當注入率達到6%之后，各算法的平均延遲開始顯著增加并逐漸顯現出差異，其中FB?8增幅最大。

如圖8所示，在Uniform通信模式下，當網絡存在一個錯誤塊時，在注入率達到5%之前，最差、最優和平均情況下的平均延遲相近且緩慢增加；當注入率達到6%之后，各情況的平均延遲開始顯著增加并逐漸顯現出差異。值得注意的是，最差情況為錯誤塊出現在FB?4時，平均情況為FB?1～FB?9按概率出現的加權平均值。

如圖9所示，在Uniform通信模式下，隨著注入率逐漸增大，本文提出的算法和DOR，ROMM和MAD有著相似的性能，并且比VAL在任何注入率下的性能都要好。

從圖9分析可知，本文提出的算法基本達到了理論預期的效果，這可以說是一個比較樂觀的結果。因為DOR，ROMM，MAD和VAl是幾個性能比較好的Oblivious路由算法，而本文提出的算法是基于類西向優先的容錯路由算法；DOR算法和MAD算法雖然不使用虛擬通道，但是卻不能容錯；ROMM算法和VAL算法都使用了2條虛擬通道，否則網絡會形成死鎖；本文提出的算法不但不使用虛擬通道，而且還能容一個甚至更多錯誤，在注入率較低時可以獲得不錯的性能。

5 結 語

本文提出的2D?Mesh無虛擬通道的容錯路由算法在2D?Mesh上不使用虛擬通道，而且能容一個甚至更多錯誤，減少了犧牲的無錯節點數目，保證了網絡無死鎖。實驗結果也表明，該算法在網絡存在錯誤時不僅不會降低網絡性能，而且還能獲得與其他算法相似的傳輸延遲。值得一提的是，各FB算法的性能相差無幾，這使得網絡流量分布更加均勻，并且錯誤可以出現在網絡的任何一個位置，這無疑使得該算法更具適應性和魯棒性。通過對錯誤塊的限制，還可以容更多的錯誤，犧牲更少的無錯節點，這將是以后研究的方向。

參考文獻

[1] DALLY W， TOWLES B. Principles and practices of interconnec?tion networks [M]. San Mateo， CA： Morgan Kaufmann， 2004.

[2] BELL S， EDWARDS B， ZOOK J， et al. Tile64?processor： a 64?core SoC with mesh interconnect [C]// 2008 Solid?State Circuits Conference. [S.l.： s.n.]， 2008： 588?598.

[3] FAN D R， YUAN N， LIU L. Godson?T： an efficient many?core architecture for parallel program executions [J]. Journal of computer science and technology， 2009， 24（6）： 1061?1073.

[4] VANGAL S， HOWARD J， BORKAR S. An 80?tile sub?100?W TeraFLOPS processor in 65?nm CMOS [J]. IEEE journal of solid?state circuits， 2008， 43（1）： 29?41.

[5] GLASS C J， NI L M. The turn model for adaptive routing [J]. Journal of the ACM， 1994， 41（5）： 874?902.

[6] CHIU G. The odd?even turn model for adaptive routing [J]. IEEE transactions on parallel distribution systems， 2000， 11（7）： 729?738.

[7] FU B， HAN Y， MA J， et al. An abacus turn model for time/space?efficient reconfigurable routing [C]// 2011 the 38th Annual International Symposium on Computer Architecture. San Jose： IEEE， 2011： 259?270.

[8] GLASS C J， NI L M. Fault?tolerant wormhole routing in meshes [C]// 1993 23rd International Symposium on Fault?Tolerant Computing. Toulouse： IEEE， 1993： 240?249.

[9] WU J. A fault?tolerant and deadlock?free routing protocol in 2D meshes based on odd?even turn model [J]. IEEE transactions on computing， 2003， 52（9）： 1154?1169.

[10] ZHANG Z， GREINER A， TAKTAK S. A reconfigurable routing algorithm for a fault?tolerant 2D?mesh network?on?chip [C]// 2008 ACM/IEEE Design Automation Conference. Anaheim： IEEE， 2008： 441?446.

[11] BOPPANA R， CHALASANI S. Fault?tolerant routing with non?adaptive wormhole algorithms in mesh networks [C]// Procee?dings of 1994 Supercomputing Conference. Washington， D.C.： IEEE， 1994： 693?702.

[12] DALLY W， SEITZ C. Deadlock?free message routing in multiprocessor interconnection networks [J]. IEEE transactions on computing， 1987， 36（5）： 547?553.