張弘博 段新明

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

關(guān)鍵詞： 2D?Mesh； 虛擬通道； 容錯(cuò)路由； 錯(cuò)誤塊； 網(wǎng)絡(luò)無死鎖； 傳輸延遲

中圖分類號： TN915.02?34； TP393 文獻(xiàn)標(biāo)識碼： 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 引 言

多核處理器通常利用片上網(wǎng)絡(luò)來提供片上通信[1]。2D?Mesh因其平面的拓?fù)浣Y(jié)構(gòu)而被廣泛應(yīng)用于集成電路制造業(yè)。大多數(shù)多核處理器使用確定性路由算法，如XY路由算法[2?4]，因?yàn)樗艹浞掷寐酚善鞯脑O(shè)計(jì)，但XY路由不容錯(cuò)。設(shè)計(jì)容錯(cuò)路由算法的一個(gè)主要挑戰(zhàn)就是保證網(wǎng)絡(luò)無死鎖。在不使用虛擬通道的片上網(wǎng)絡(luò)上，通常用轉(zhuǎn)彎模型來避免死鎖[5?7]。文獻(xiàn)[6]證明當(dāng)去掉所有最右列時(shí)網(wǎng)絡(luò)就是無死鎖的，但是沒有最右列，網(wǎng)絡(luò)左側(cè)邊緣就很難容錯(cuò)[8?10]。為了解決這一問題，文獻(xiàn)[8?10]提出了解決方案，但這些解決方案需要犧牲大量的無錯(cuò)節(jié)點(diǎn)。

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

1 相關(guān)知識

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

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

本文采用矩形錯(cuò)誤模型[11]，假設(shè)錯(cuò)誤塊之間不共享邊界。如果兩個(gè)錯(cuò)誤塊共享邊界，那么就會(huì)建立一個(gè)更大的錯(cuò)誤塊來代替原來的兩個(gè)錯(cuò)誤塊。同時(shí)，本文假設(shè)錯(cuò)誤塊是靜態(tài)的[10]，即包在路由時(shí)網(wǎng)絡(luò)不會(huì)出現(xiàn)新的錯(cuò)誤塊。

1） 2D?Mesh下的錯(cuò)誤塊是包含危險(xiǎn)節(jié)點(diǎn)的矩形區(qū)域。

2） 危險(xiǎn)節(jié)點(diǎn)就是錯(cuò)誤節(jié)點(diǎn)或不安全節(jié)點(diǎn)。

3） 無錯(cuò)節(jié)點(diǎn)一開始是安全的，當(dāng)只有一個(gè)鄰居是危險(xiǎn)節(jié)點(diǎn)時(shí)，安全節(jié)點(diǎn)會(huì)變成半安全的節(jié)點(diǎn)。

4） 當(dāng)有兩個(gè)危險(xiǎn)鄰居或兩個(gè)半安全鄰居時(shí)，安全或半安全節(jié)點(diǎn)會(huì)變成不安全的節(jié)點(diǎn)。

5） 錯(cuò)誤塊的邊界包含水平的、垂直的和斜對角的安全節(jié)點(diǎn)。

6） 當(dāng)錯(cuò)誤塊的邊界形成環(huán)時(shí)稱為錯(cuò)誤環(huán)，否則稱為錯(cuò)誤鏈。

矩形錯(cuò)誤模型如圖2所示。

2 算法介紹

本文算法根據(jù)錯(cuò)誤塊的具體位置分為9種情況，每種情況都結(jié)合類西向優(yōu)先算法產(chǎn)生容一個(gè)錯(cuò)誤塊的路由算法，錯(cuò)誤塊的具體分類如圖3所示。

類西向優(yōu)先算法是當(dāng)目的節(jié)點(diǎn)在源節(jié)點(diǎn)的左側(cè)時(shí)，包向西路由；當(dāng)目的節(jié)點(diǎn)在源節(jié)點(diǎn)的正北側(cè)或東北側(cè)時(shí)，包向北路由；當(dāng)目的節(jié)點(diǎn)在源節(jié)點(diǎn)的正南側(cè)或東南側(cè)時(shí)，包向南路由；否則包向東路由。

當(dāng)錯(cuò)誤出現(xiàn)在網(wǎng)絡(luò)西北角時(shí)，即FB?1的情況，原本向西路由的包因錯(cuò)誤塊的東邊界而沿著邊界向南路由；原本向北路由的包因錯(cuò)誤塊的南邊界而沿著邊界向東路由。

當(dāng)錯(cuò)誤出現(xiàn)在網(wǎng)絡(luò)北邊界時(shí)，即FB?2的情況，原本向西路由的包因錯(cuò)誤塊的東邊界而沿著邊界向南路由；原本向北路由的包因錯(cuò)誤塊的南邊界而沿著邊界向東路由；原本向東路由的包因錯(cuò)誤塊的西邊界而向南路由。

當(dāng)錯(cuò)誤出現(xiàn)在東北角時(shí)，即FB?3的情況，仍然采用類西向優(yōu)先算法。

當(dāng)錯(cuò)誤出現(xiàn)在西邊界時(shí)，即FB?4的情況，原本向西路由的包因錯(cuò)誤塊的東邊界而沿著邊界路由，若目的節(jié)點(diǎn)在北側(cè)，則向北路由，否則向南路由；原本向南路由的包因錯(cuò)誤塊的北邊界而沿著邊界向東路由；原本向北路由的包因錯(cuò)誤塊的南邊界而沿著邊界向東路由。

當(dāng)錯(cuò)誤塊出現(xiàn)在網(wǎng)絡(luò)中間時(shí)，即FB?5的情況，原本向西路由的包因錯(cuò)誤塊的東邊界而沿著邊界向南路由；原本向南路由的包因錯(cuò)誤塊的北邊界而沿著邊界向西路由；原本向東路由的包因錯(cuò)誤塊的西邊界而沿著邊界向南路由；原本向北路由的包因錯(cuò)誤塊的南邊界而沿著邊界路由，若目的節(jié)點(diǎn)在錯(cuò)誤塊的北側(cè)，則向西路由，否則向東路由。

當(dāng)錯(cuò)誤出現(xiàn)在東邊界時(shí)，即FB?6的情況，原本向北路由的包因錯(cuò)誤塊的南邊界而沿著邊界向西路由；原本向南路由的包因錯(cuò)誤塊的北邊界而沿著邊界向西路由。

當(dāng)錯(cuò)誤出現(xiàn)在西南角時(shí)，即FB?7的情況，原本向西路由的包因錯(cuò)誤塊的東邊界而沿著邊界向北路由；原本向南路由的包因錯(cuò)誤塊的北邊界而沿著邊界向東路由。

當(dāng)錯(cuò)誤出現(xiàn)在南邊界時(shí)，即FB?8的情況，原本向西路由的包因錯(cuò)誤塊的東邊界而沿著邊界向北路由；原本向南路由的包因錯(cuò)誤塊的北邊界而沿著邊界向東路由；原本向東路由的包因錯(cuò)誤塊的西邊界而沿著邊界向北路由。

當(dāng)錯(cuò)誤出現(xiàn)在東南角時(shí)，即FB?9的情況，仍然采用類西向優(yōu)先算法。

3 算法證明

文獻(xiàn)[12]證明當(dāng)相關(guān)通道依賴圖無環(huán)時(shí)網(wǎng)絡(luò)是無死鎖的。之后，文獻(xiàn)[6]證明當(dāng)破壞掉順時(shí)針和逆時(shí)針環(huán)的最右列時(shí)，相關(guān)通道依賴圖是無環(huán)的。因此，為了證明提出的算法是無死鎖的，本文將對相關(guān)通道依賴圖無環(huán)做如下證明：如果錯(cuò)誤沒有出現(xiàn)在網(wǎng)絡(luò)左側(cè)邊緣，就不會(huì)生成最右列；如果錯(cuò)誤出現(xiàn)在網(wǎng)絡(luò)左側(cè)邊緣，最右列不會(huì)構(gòu)成環(huán)。

由默認(rèn)的類西向優(yōu)先路由算法可知，西北彎、西南彎、北東彎和南東彎是合理的轉(zhuǎn)彎，并且它們之間的組合也不會(huì)出現(xiàn)環(huán)，其余轉(zhuǎn)彎只在幾個(gè)特殊情況中出現(xiàn)。如圖4所示，默認(rèn)情況下的類西向優(yōu)先算法允許出現(xiàn)的轉(zhuǎn)彎只有4個(gè)。

聲明1：東南彎只出現(xiàn)在FB?4，F(xiàn)B?7，F(xiàn)B?8的東北角和FB?2，F(xiàn)B?5的西邊界。

聲明2：東北彎只出現(xiàn)在FB?1，F(xiàn)B?2，F(xiàn)B?4，F(xiàn)B?5的東南角和FB?8的西邊界。

聲明3：南西彎只出現(xiàn)在FB?1，F(xiàn)B?2，F(xiàn)B?4，F(xiàn)B?5的東南角和FB?5，F(xiàn)B?6的北邊界。

聲明4：北西彎只出現(xiàn)在FB?4，F(xiàn)B?7，F(xiàn)B?8的東北角和FB?5，F(xiàn)B?6的南邊界。

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

聲明6：不允許出現(xiàn)0°和180°的轉(zhuǎn)彎。

如圖5所示，其余的轉(zhuǎn)彎只能出現(xiàn)在網(wǎng)絡(luò)中特定的位置，并且需要特別標(biāo)明的是，為了防止形成環(huán)路，F(xiàn)B?5的東北角既不允許出現(xiàn)北西彎，也不允許出現(xiàn)東南彎。

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

證明：當(dāng)東南彎出現(xiàn)在FB?7，F(xiàn)B?8的東北角時(shí)，無法在其南側(cè)形成南西彎來與其組成最右列，因?yàn)镕B?7，F(xiàn)B?8已經(jīng)到達(dá)網(wǎng)絡(luò)南側(cè)邊緣；當(dāng)東南彎出現(xiàn)在FB?2，F(xiàn)B?5的西邊界時(shí)，無法在其南側(cè)形成南西彎來與其組成最右列。

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

證明：當(dāng)東北彎出現(xiàn)在FB?1，F(xiàn)B?2的東南角時(shí)，無法在其北側(cè)形成北西彎來與其組成最右列，因?yàn)镕B?1，F(xiàn)B?2已經(jīng)到達(dá)網(wǎng)絡(luò)北側(cè)邊緣；當(dāng)東北彎出現(xiàn)在FB?5的東南角或FB?8的西邊界時(shí)，無法在其北側(cè)形成北西彎來與其組成最右列。

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

證明：當(dāng)南西彎出現(xiàn)在FB?1，F(xiàn)B?2的東南角時(shí)，無法在其北側(cè)形成東南彎來與其組成最右列，因?yàn)镕B?1，F(xiàn)B?2已經(jīng)到達(dá)網(wǎng)絡(luò)北側(cè)邊緣；當(dāng)南西彎出現(xiàn)在FB?5的東南角或FB?5，F(xiàn)B?6的北邊界時(shí)，無法在其北側(cè)形成東南彎來與其組成最右列。

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

證明：當(dāng)北西彎出現(xiàn)在FB?7，F(xiàn)B?8的東北角時(shí)，無法在其南側(cè)形成東北彎來與其組成最右列，因?yàn)镕B?7，F(xiàn)B?8已經(jīng)到達(dá)網(wǎng)絡(luò)南側(cè)邊緣；當(dāng)北西彎出現(xiàn)在FB?5，F(xiàn)B?6的南邊界時(shí)，無法在其南側(cè)形成東北彎來與其組成最右列。

引理5 當(dāng)且僅當(dāng)東南彎出現(xiàn)在FB?4東北角并且南西彎出現(xiàn)在FB?4東南角時(shí)才會(huì)出現(xiàn)順時(shí)針最右列。

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

引理6 當(dāng)且僅當(dāng)東北彎出現(xiàn)在FB?4東南角并且北西彎出現(xiàn)在FB?4東北角時(shí)才會(huì)出現(xiàn)逆時(shí)針最右列。

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

引理7 FB?4右側(cè)即使出現(xiàn)最右列也不會(huì)構(gòu)成環(huán)。

證明：由引理5和引理6可知，最右列只能出現(xiàn)在FB?4的右側(cè)；并且由聲明6可知，不允許出現(xiàn)180°的轉(zhuǎn)彎，因?yàn)镕B?4已經(jīng)到了網(wǎng)絡(luò)的左側(cè)邊緣，所以就不存在構(gòu)成環(huán)的左列，即FB?4右側(cè)即使出現(xiàn)最右列也不會(huì)構(gòu)成環(huán)。

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

證明：當(dāng)網(wǎng)絡(luò)中不存在錯(cuò)誤時(shí)，路由采用的是默認(rèn)的類西向優(yōu)先路由，所以網(wǎng)絡(luò)是無死鎖的。當(dāng)網(wǎng)絡(luò)中存在錯(cuò)誤時(shí)，如果網(wǎng)絡(luò)左側(cè)邊緣沒有錯(cuò)誤，即網(wǎng)絡(luò)不存在最右列，所以網(wǎng)絡(luò)是無死鎖的；如果網(wǎng)絡(luò)左側(cè)邊緣存在錯(cuò)誤，根據(jù)引理7，即使出現(xiàn)最右列也不會(huì)構(gòu)成環(huán)，所以網(wǎng)絡(luò)是無死鎖的。

4 實(shí)驗(yàn)仿真

本文采用的仿真環(huán)境是BookSim 1.0，通過在不同通信模式下改變注入率的方法來測試算法的性能，依賴的指標(biāo)是平均延遲，通信模式選用Uniform，對比的算法選用本文提出的算法在網(wǎng)絡(luò)中存在一個(gè)錯(cuò)誤塊時(shí)的情況，DOR，ROMM，MAD和VAL。因通信模式對網(wǎng)絡(luò)基數(shù)的限制，實(shí)驗(yàn)采用8×8的網(wǎng)絡(luò)結(jié)構(gòu)，其余設(shè)置均為BookSim 1.0的默認(rèn)設(shè)置。

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

如圖7所示，在Uniform通信模式下，當(dāng)網(wǎng)絡(luò)存在一個(gè)錯(cuò)誤塊時(shí)，在注入率達(dá)到5%之前，F(xiàn)B?5～FB?9算法的平均延遲相近且緩慢增加；當(dāng)注入率達(dá)到6%之后，各算法的平均延遲開始顯著增加并逐漸顯現(xiàn)出差異，其中FB?8增幅最大。

如圖8所示，在Uniform通信模式下，當(dāng)網(wǎng)絡(luò)存在一個(gè)錯(cuò)誤塊時(shí)，在注入率達(dá)到5%之前，最差、最優(yōu)和平均情況下的平均延遲相近且緩慢增加；當(dāng)注入率達(dá)到6%之后，各情況的平均延遲開始顯著增加并逐漸顯現(xiàn)出差異。值得注意的是，最差情況為錯(cuò)誤塊出現(xiàn)在FB?4時(shí)，平均情況為FB?1～FB?9按概率出現(xiàn)的加權(quán)平均值。

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

從圖9分析可知，本文提出的算法基本達(dá)到了理論預(yù)期的效果，這可以說是一個(gè)比較樂觀的結(jié)果。因?yàn)镈OR，ROMM，MAD和VAl是幾個(gè)性能比較好的Oblivious路由算法，而本文提出的算法是基于類西向優(yōu)先的容錯(cuò)路由算法；DOR算法和MAD算法雖然不使用虛擬通道，但是卻不能容錯(cuò)；ROMM算法和VAL算法都使用了2條虛擬通道，否則網(wǎng)絡(luò)會(huì)形成死鎖；本文提出的算法不但不使用虛擬通道，而且還能容一個(gè)甚至更多錯(cuò)誤，在注入率較低時(shí)可以獲得不錯(cuò)的性能。

5 結(jié) 語

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

參考文獻(xiàn)

[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.