2DMesh片上網(wǎng)絡(luò)分區(qū)容錯(cuò)路由算法

胡哲琨 楊升春 陳杰

Abstract： In order to reduce the entries of routing tables and avoid using large numbers of Virtual Channels （VC）， a Regionbased Fault Tolerant Routing （RFTR） algorithm was proposed for wormhole switching 2D Mesh Network on Chip （NoC） to reduce the amount of hardware resources. According to the positions of faulty nodes and links， the 2D Mesh network was divided into several rectangular regions. Within each region the packet could be routed by deterministic or adaptive routing algorithms， while among these regions the routing path was determined by up*/down* routing algorithm. Besides， with the Channel Dependency Graph （CDG） model， the proposed algorithm was proved to be deadlockfree using only two VCs. In a 6×6 Mesh network， the RFTR algorithm can reduce the amount of routing table resources by 25%. Simulation results show that， with the same amount of buffer resources， the RFTR algorithm can achieve an equivalent or even higher performance compared to up*/down* and segmentbased routing algorithms.

Key words：Network on Chip （NoC）； fault tolerant routing； deadlock avoidance； routing table； Channel Dependency Graph （CDG）

0 引言

隨著集成電路工藝技術(shù)的發(fā)展，芯片內(nèi)部可集成的IP核數(shù)目不斷增加，出于對(duì)可擴(kuò)展性、連線延時(shí)和功耗等因素的考慮，片上網(wǎng)絡(luò)（Network on Chip， NoC）逐漸成為多核間通信的主流方式。2D Mesh是一種常用的片上網(wǎng)絡(luò)結(jié)構(gòu)，具有規(guī)則的平面布局，且易于實(shí)現(xiàn)高效無死鎖的數(shù)據(jù)包路由。然而，集成電路制造過程中產(chǎn)生的缺陷和工藝變化等因素可能導(dǎo)致芯片中的部分節(jié)點(diǎn)或鏈路不能正常工作，從而打破了Mesh結(jié)構(gòu)的規(guī)則性，且隨著工藝尺寸的進(jìn)一步縮小，該現(xiàn)象會(huì)更加明顯。為了有效利用芯片中剩余的資源進(jìn)行計(jì)算，片上網(wǎng)絡(luò)需具有一定的容錯(cuò)特性，而其中一個(gè)重要方面就是容錯(cuò)路由算法的設(shè)計(jì)。

目前針對(duì)2D Mesh網(wǎng)絡(luò)已存在多種容錯(cuò)算法。傳統(tǒng)的基于故障塊模型的容錯(cuò)路由算法[1-2]需要3至4個(gè)虛通道（Virtual Channels， VC）才能避免死鎖，然而在片上網(wǎng)絡(luò)中，較多的虛通道不僅會(huì)占用大量的緩存資源，還會(huì)導(dǎo)致路由器工作頻率降低，因此這類算法并不適用于片上網(wǎng)絡(luò)。拓?fù)錈o關(guān)的路由算法[3]也能用于容錯(cuò)路由，如up*/down*路由算法[4-5]和segment路由算法[6]。這些算法在不使用虛通道的情況下就能避免死鎖，但需依賴路由表才能實(shí)現(xiàn)路由計(jì)算，而路由表的總項(xiàng)數(shù)與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的平方成正比，當(dāng)片上網(wǎng)絡(luò)的規(guī)模增大時(shí)，會(huì)導(dǎo)致芯片面積和功耗的急劇增加，因此這類算法缺乏良好的可擴(kuò)展性。文獻(xiàn)[7]提出了一種基于邏輯運(yùn)算的分布式容錯(cuò)路由機(jī)制，無需虛通道就能避免死鎖，但只能針對(duì)某些特定的拓?fù)浣Y(jié)構(gòu)（如“P”型、“+”型網(wǎng)絡(luò)）適用。此外，文獻(xiàn)[8-9]也分別針對(duì)2D Mesh片上網(wǎng)絡(luò)提出了容錯(cuò)路由算法。

為了減小路由表的規(guī)模，同時(shí)避免使用較多虛通道，本文針對(duì)蟲孔交換的2D Mesh片上網(wǎng)絡(luò)提出了一種分區(qū)容錯(cuò)路由（Regionbased Fault Tolerant Routing， RFTR）算法。該算法根據(jù)故障節(jié)點(diǎn)和鏈路的分布，將整個(gè)網(wǎng)絡(luò)劃分為若干個(gè)相連的矩形區(qū)域，數(shù)據(jù)包在區(qū)域內(nèi)可按照確定性路由算法（如XY算法[4]）或自適應(yīng)路由算法（如westfirst算法）進(jìn)行路由，而在區(qū)域之間則按照up*/down*算法確定路由路徑。該算法僅需2個(gè)虛通道就能避免死鎖，且能顯著減少路由表的使用。6×6 Mesh網(wǎng)絡(luò)中的仿真結(jié)果表明，在路由器緩存資源相同的情況下，本文提出的RFTR算法能達(dá)到與up*/down*算法和segment算法相當(dāng)甚至更優(yōu)的性能。

1 分區(qū)容錯(cuò)模型

本文對(duì)片上網(wǎng)絡(luò)采用靜態(tài)故障模型，即已通過故障檢測手段事先獲得了故障節(jié)點(diǎn)和鏈路的位置，然后在此基礎(chǔ)上計(jì)算路由表并對(duì)片上網(wǎng)絡(luò)進(jìn)行配置。一旦配置完成，數(shù)據(jù)包在網(wǎng)絡(luò)中即可實(shí)現(xiàn)高效無死鎖的傳輸。

圖1示意了在一個(gè)6×6的Mesh網(wǎng)絡(luò)中，節(jié)點(diǎn)N（8）、N（22）及鏈路C（9，15）發(fā)生故障時(shí)的情況。根據(jù)故障節(jié)點(diǎn)和鏈路的分布，整個(gè)網(wǎng)絡(luò)被劃分為若干個(gè)相連的矩形區(qū)域，每個(gè)矩形區(qū)域均為一個(gè)完整的子Mesh網(wǎng)絡(luò)，且這些區(qū)域之間互不相交。每個(gè)節(jié)點(diǎn)除了記錄自身的（x， y）坐標(biāo)以外，還用一個(gè)區(qū)域寄存器記錄其所屬的區(qū)域。未被劃分進(jìn)矩形區(qū)域的節(jié)點(diǎn)則被設(shè)置為連接節(jié)點(diǎn)，如節(jié)點(diǎn)N（2）和N（16），這些節(jié)點(diǎn)根據(jù)路由表的配置進(jìn)行區(qū)域間的數(shù)據(jù)包傳遞，但不參與網(wǎng)絡(luò)中的并行計(jì)算。此外，如果一個(gè)區(qū)域中的節(jié)點(diǎn)與另一區(qū)域的節(jié)點(diǎn)相連（直接相連或通過連接節(jié)點(diǎn)相連），則稱該節(jié)點(diǎn)為邊界節(jié)點(diǎn)。因此通過矩形區(qū)域的劃分和連接節(jié)點(diǎn)的設(shè)置，2D Mesh網(wǎng)絡(luò)中的容錯(cuò)路由問題就轉(zhuǎn)換為多個(gè)子Mesh網(wǎng)絡(luò)間的路由問題。

2 分區(qū)容錯(cuò)路由算法設(shè)計(jì)

本文使用一種查表與邏輯運(yùn)算相結(jié)合的方法來實(shí)現(xiàn)容錯(cuò)路由（RFTR），以使數(shù)據(jù)包在區(qū)域內(nèi)可以按照確定性或自適應(yīng)路由算法進(jìn)行路由，而在區(qū)域之間則能繞過故障節(jié)點(diǎn)和故障鏈路實(shí)現(xiàn)無死鎖的傳輸。本章首先給出矩形區(qū)域間的路由方法，繼而描述路由表的結(jié)構(gòu)，然后給出虛通道的使用規(guī)則及具體的路由算法，最后分析該算法的死鎖特性。

2.1 區(qū)域間路由

與圖1所示的矩形區(qū)域?qū)?yīng)，圖2（a）給出了其區(qū)域連接圖，其中每個(gè)頂點(diǎn)都代表一個(gè)矩形區(qū)域，且兩個(gè)頂點(diǎn)之間存在一條邊當(dāng)且僅當(dāng)在2D Mesh網(wǎng)絡(luò)中存在一對(duì)相連的節(jié)點(diǎn)分別位于這兩個(gè)頂點(diǎn)所對(duì)應(yīng)的矩形區(qū)域中。然后在區(qū)域連接圖中按照up*/down*路由算法確定各條邊的方向，其步驟[4]為：選取某個(gè)頂點(diǎn)作為樹根，求得該區(qū)域連接圖的一棵生成樹，并將屬于原圖但不屬于生成樹的邊（也稱余邊）添加到樹中；如果一條邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)位于生成樹的不同層中，則靠近樹根的方向?yàn)橄蛏系模╱p），否則，靠近編號(hào)較小的頂點(diǎn)的方向?yàn)橄蛏系?，而與向上方向相反的方向則被稱為向下的（down）。如果用箭頭表示向上方向，那么根據(jù)以上規(guī)則所得到的有向圖中不存在環(huán)，或者說從任意一個(gè)頂點(diǎn)出發(fā)，要再回到該頂點(diǎn)，至少需要經(jīng)過一條向上的邊和一條向下的邊，這一性質(zhì)對(duì)于保證RFTR算法不會(huì)發(fā)生死鎖十分重要。

依據(jù)區(qū)域連接圖中邊的方向，數(shù)據(jù)包在區(qū)域間的傳輸規(guī)則為：禁止從向下的邊到向上的邊的轉(zhuǎn)向，即數(shù)據(jù)包的傳輸應(yīng)經(jīng)過零次或多次向上的邊，再經(jīng)過零次或多次向下的邊（因此算法取名為up*/down*，其中*表示重復(fù)0次或1次以上）。圖2（b）所示的是選取頂點(diǎn)0作為樹根時(shí)得到的有向圖，例如數(shù)據(jù)包由區(qū)域3到達(dá)區(qū)域2后可以再轉(zhuǎn)發(fā)給區(qū)域4，但是到達(dá)區(qū)域4后不能再向區(qū)域1傳輸。將區(qū)域連接圖中所確定的邊的方向映射到2D Mesh網(wǎng)絡(luò)后，則得到圖1所示的區(qū)域間連接的方向，數(shù)據(jù)包在網(wǎng)絡(luò)中的傳輸應(yīng)滿足同樣的規(guī)則，圖1中示意了從N（20）到N（17）的數(shù)據(jù)包的傳輸路徑。

2.2 路由表結(jié)構(gòu)

為了使數(shù)據(jù)包在矩形區(qū)域間的傳輸符合上述規(guī)則，每個(gè)路由器中均使用一個(gè)路由表來指定數(shù)據(jù)包的傳輸路徑，并利用標(biāo)志位來區(qū)分表項(xiàng)的含義，如圖3（a）所示。在執(zhí)行路由計(jì)算時(shí)，用數(shù)據(jù)包的目的區(qū)域號(hào)對(duì)該表進(jìn)行索引，如果其標(biāo)志位為N（Node），則表項(xiàng)指定了數(shù)據(jù)包應(yīng)該首先到達(dá)的邊界節(jié)點(diǎn)的坐標(biāo)；如果其標(biāo)志位為D（Direction），則表明當(dāng)前節(jié)點(diǎn)是一個(gè)邊界節(jié)點(diǎn)，其表項(xiàng)指示了數(shù)據(jù)包應(yīng)使用的輸出端口（東/南/西/北）及其對(duì)應(yīng)的up/down方向，該方向?qū)⒂脕碇付ㄌ撏ǖ赖氖褂?。圖3（a）以節(jié)點(diǎn)N（20）為例示意了路由表的結(jié)構(gòu)，其中目的節(jié)點(diǎn)位于區(qū)域0或區(qū)域1中的數(shù)據(jù)包應(yīng)使用向南的輸出端口，且其對(duì)應(yīng)的區(qū)域間連接的方向是向上的，而目的節(jié)點(diǎn)位于區(qū)域4的數(shù)據(jù)包應(yīng)該先到達(dá)節(jié)點(diǎn)N（15），其對(duì)應(yīng)的坐標(biāo)為（3，2）。

此外，為了表示連接節(jié)點(diǎn)的連接狀態(tài)，每個(gè)路由器中還需提供一個(gè)連接表，該表可以是分布在各個(gè)輸入端口的，也可以是集中式的。圖3（b）以連接節(jié)點(diǎn)N（16）為例示意了連接表的結(jié)構(gòu)，其中西、北兩個(gè)端口相互連接。在計(jì)算路由表的內(nèi)容時(shí)，應(yīng)確保數(shù)據(jù)包不會(huì)從未指定連接關(guān)系的端口進(jìn)入連接節(jié)點(diǎn)，如在圖1中，數(shù)據(jù)包到達(dá)節(jié)點(diǎn)N（17）后不能向西傳輸。

2.3 RFTR算法

路由表和連接表僅指示了數(shù)據(jù)包在區(qū)域間的路由路徑，而數(shù)據(jù)包在矩形區(qū)域內(nèi)則可按照已有的確定性或自適應(yīng)路由算法進(jìn)行路由，如XY路由算法或westfirst路由算法。由于每個(gè)矩形區(qū)域均為完整的子Mesh網(wǎng)絡(luò)，因此區(qū)域內(nèi)的路由計(jì)算可以采用邏輯運(yùn)算的方式實(shí)現(xiàn)。這樣，路由表的項(xiàng)數(shù)僅與矩形區(qū)域的數(shù)目有關(guān)，而與每個(gè)區(qū)域內(nèi)節(jié)點(diǎn)的數(shù)目并無關(guān)系，因此這種查表與邏輯運(yùn)算相結(jié)合的路由計(jì)算方式為矩形區(qū)域的劃分提供了靈活性，且有助于減少路由表的資源用量。

然而當(dāng)數(shù)據(jù)包在多個(gè)矩形區(qū)域之間路由時(shí)，網(wǎng)絡(luò)中可能會(huì)發(fā)生死鎖[10]，其原因?yàn)椋横槍?duì)某一矩形區(qū)域而言，從進(jìn)入該區(qū)域的連接到離開該區(qū)域的連接之間，可能會(huì)存在由通道依賴關(guān)系形成的通路，因此當(dāng)兩個(gè)或多個(gè)區(qū)域之間存在連接時(shí)，其通道依賴關(guān)系就可能形成回路。為了避免死鎖的發(fā)生，本文對(duì)文獻(xiàn)[11]的死鎖避免方案進(jìn)行了擴(kuò)展，具體為：網(wǎng)絡(luò)中使用兩個(gè)虛通道VC0和VC1，如果數(shù)據(jù)包的目的節(jié)點(diǎn)與源節(jié)點(diǎn)位于同一矩形區(qū)域內(nèi)，則數(shù)據(jù)包可以選擇任何一個(gè)虛通道進(jìn)入網(wǎng)絡(luò)，且一直使用該虛通道進(jìn)行路由，直到被目的節(jié)點(diǎn)接收；而當(dāng)數(shù)據(jù)包的目的節(jié)點(diǎn)與源節(jié)點(diǎn)不在同一區(qū)域時(shí)，數(shù)據(jù)包通過VC0進(jìn)入網(wǎng)絡(luò)，僅當(dāng)數(shù)據(jù)包穿過向下方向的區(qū)域間連接時(shí)，才切換到VC1中，并繼續(xù)使用VC1進(jìn)行路由，直到被目的節(jié)點(diǎn)接收。由于一個(gè)數(shù)據(jù)包通過向下方向的連接后，不能再使用向上方向的連接，因此不會(huì)發(fā)生從VC1到VC0的切換。最后，注意到只有邊界節(jié)點(diǎn)的路由表才指定了區(qū)域間連接的方向，因此只有在邊界節(jié)點(diǎn)中才能發(fā)生虛通道的切換，而在矩形區(qū)域內(nèi)和連接節(jié)點(diǎn)上的傳輸均不改變數(shù)據(jù)包所占用的虛通道。

RFTR算法首先檢查當(dāng)前端口是否處于連接狀態(tài)，如果是則選擇與其相連的輸出端口作為路由結(jié)果。否則，如果當(dāng)前區(qū)域就是目的區(qū)域，則使用westfirst算法路由到目的節(jié)點(diǎn)；而如果當(dāng)前區(qū)域不是目的區(qū)域，則使用目的區(qū)域號(hào)對(duì)路由表進(jìn)行索引，如果得到的標(biāo)志位為N，則使用westfirst算法路由到其所指定的邊界節(jié)點(diǎn)，否則，直接使用表項(xiàng)所指定的輸出端口作為路由結(jié)果，并根據(jù)其方向使用相應(yīng)的虛通道。

2.4 RFTR算法的死鎖特性

為了說明RFTR算法是無死鎖的，本節(jié)首先引入通道依賴圖（Channel Dependency Graph， CDG）的概念及路由算法無死鎖的充分條件[12]，繼而證明RFTR算法的死鎖特性。

定義1 在一個(gè)由非空節(jié)點(diǎn)集N和非空通道集C組成的網(wǎng)絡(luò)I=G（N， C）中，給定一個(gè)路由算法R，如果數(shù)據(jù)包在路由過程中會(huì)連續(xù)地使用通道cij和cjk，則存在從cij到cjk的通道依賴關(guān)系。

定義2 網(wǎng)絡(luò)I和路由算法R所對(duì)應(yīng)的通道依賴圖是一個(gè)有向圖D=G（V， E），該圖中的頂點(diǎn)vij對(duì)應(yīng)網(wǎng)絡(luò)I中的通道cij，該圖中的邊e（vij， vjk）則對(duì)應(yīng)從cij到cjk的通道依賴關(guān)系。如果在網(wǎng)絡(luò)I中一條物理通道對(duì)應(yīng)了多個(gè)虛通道，則在通道依賴圖D中對(duì)每個(gè)虛通道均用一個(gè)頂點(diǎn)來表示。

引理1 在網(wǎng)絡(luò)I中，對(duì)一個(gè)給定的路由算法R，如果其對(duì)應(yīng)的通道依賴圖D中不存在回路，則該路由算法不會(huì)發(fā)生死鎖[12]。

圖4給出了在2×3 Mesh網(wǎng)絡(luò)中使用westfirst路由算法時(shí)的通道依賴圖，可以看出該圖中不存在回路，其原因?yàn)槿魏我粋€(gè)回路都必須包含由南向西或者由北向西的邊，而westfirst算法禁止這兩種類型的路由轉(zhuǎn)向。

定理1 對(duì)于RFTR算法，如果矩形區(qū)域內(nèi)使用的路由算法所對(duì)應(yīng)的通道依賴圖不存在回路，則該算法不會(huì)發(fā)生死鎖。

證明 由于矩形區(qū)域內(nèi)的通道依賴圖不存在回路，因此如果要形成回路，則必須通過多個(gè)矩形區(qū)域。為此，任意選擇一個(gè)矩形區(qū)域，考慮如下兩種情況：

1）數(shù)據(jù)包通過向下方向的區(qū)域間連接傳輸?shù)搅硪痪匦螀^(qū)域，由虛通道的使用規(guī)則可知，數(shù)據(jù)包離開該區(qū)域后一定位于VC1中，而根據(jù)up*/down*路由算法的規(guī)則可知，所有處于VC1中的數(shù)據(jù)包均不能使用向上方向的連接，因此在通道依賴圖中沿著其通道依賴關(guān)系不能再返回到該區(qū)域，所以不能構(gòu)成回路；

2）數(shù)據(jù)包通過向上方向的區(qū)域間連接傳輸?shù)搅硪痪匦螀^(qū)域，則該數(shù)據(jù)包一定位于VC0中，而在其所構(gòu)成的通道依賴圖中，為了能沿著通道依賴關(guān)系返回該區(qū)域，則一定需要使用向下方向的連接，那么返回該區(qū)域的通道依賴關(guān)系一定是針對(duì)VC1的依賴關(guān)系，如圖5所示，而由于VC1中的數(shù)據(jù)包不能切換到VC0中，所以其通道依賴關(guān)系不能再回到VC0構(gòu)成回路。

綜合以上情況，RFTR算法對(duì)應(yīng)的通道依賴圖中不存在回路，所以該算法無死鎖。

注意到在以上證明過程中，如果所考慮的區(qū)域?yàn)闃涓鶇^(qū)域，則所有離開該區(qū)域的連接均為向下方向的連接，因此對(duì)該區(qū)域不會(huì)發(fā)生上述的第二種情況，所以數(shù)據(jù)包在樹根區(qū)域中路由時(shí)可在VC0和VC1間隨意切換，而不必?fù)?dān)心發(fā)生死鎖，其唯一需保證的就是數(shù)據(jù)包離開該區(qū)域后使用VC1進(jìn)行路由。由于在up*/down*路由算法中，樹根節(jié)點(diǎn)通常會(huì)承受更多的數(shù)據(jù)包負(fù)載，因此使用該優(yōu)化措施可提高對(duì)樹根區(qū)域的帶寬利用率，緩解因樹根區(qū)域負(fù)載過重而使網(wǎng)絡(luò)過早達(dá)到飽和的情況。最后，各矩形區(qū)域內(nèi)的路由算法僅需保證其對(duì)應(yīng)的通道依賴圖中不存在回路，而不同區(qū)域內(nèi)使用的路由算法可以不同。

3 路由表硬件開銷

在系統(tǒng)設(shè)計(jì)階段，由于故障節(jié)點(diǎn)和鏈路的位置和數(shù)目是未知的，因此對(duì)路由表項(xiàng)的數(shù)目，或者說網(wǎng)絡(luò)中可劃分出的矩形區(qū)域的數(shù)目，就存在一定的權(quán)衡：更多的路由表項(xiàng)能容納更多的故障，然而也需要消耗更多的硬件資源。本文對(duì)一個(gè)n×n（其中n∈{4，6，8，10}）的2D Mesh網(wǎng)絡(luò)，分別按照5%和10%的比例隨機(jī)生成了一系列的故障節(jié)點(diǎn)，然后在此基礎(chǔ)上計(jì)算矩形區(qū)域和連接節(jié)點(diǎn)的數(shù)目，表1給出了其統(tǒng)計(jì)平均值。

從表1可以看出，在一個(gè)n×n的2D Mesh網(wǎng)絡(luò)中使用n個(gè)路由表項(xiàng)即可覆蓋大多數(shù)的故障情況，在這種情況下，RFTR算法中路由表和連接表的比特?cái)?shù)總和為：

[（1+2「lb n）×n+3×4]×n2

而傳統(tǒng)的路由表所需的比特?cái)?shù)為2n4。當(dāng)n等于6時(shí)，RFTR算法能節(jié)省25%的路由表資源，而當(dāng)n增加到8時(shí)，其所節(jié)省的路由表資源能達(dá)到46%以上。

需要指出的是，矩形區(qū)域的劃分方式會(huì)對(duì)連接節(jié)點(diǎn)的數(shù)量產(chǎn)生影響，由于連接節(jié)點(diǎn)僅作為區(qū)域間通信的通道，并不參與并行計(jì)算，因此在劃分矩形區(qū)域時(shí)應(yīng)在路由表項(xiàng)允許的范圍內(nèi)盡量覆蓋較多的非故障節(jié)點(diǎn)。

4 仿真結(jié)果及分析

為了對(duì)RFTR算法進(jìn)行性能驗(yàn)證，本文用SystemC搭建了周期精確的片上網(wǎng)絡(luò)仿真平臺(tái)。該平臺(tái)中的路由器采用蟲孔交換策略，具有5級(jí)流水，且為了保證數(shù)據(jù)包傳輸?shù)墓叫?，?duì)虛通道分配和交叉開關(guān)分配均采用基于延時(shí)（agebased）優(yōu)先策略，即先進(jìn)入網(wǎng)絡(luò)的數(shù)據(jù)包擁有較高優(yōu)先級(jí)。此外，本文還設(shè)計(jì)了基于傳統(tǒng)路由表的路由器，用于對(duì)up*/down*算法和segment算法進(jìn)行仿真，并將其結(jié)果與RFTR算法比較。

在配置路由表時(shí)，數(shù)據(jù)包均按照最短路徑路由。在RFTR算法中，數(shù)據(jù)包在區(qū)域內(nèi)采用westfirst路由算法，而在區(qū)域間如果有多個(gè)邊界節(jié)點(diǎn)可用，則選擇離當(dāng)前路由器最近的邊界節(jié)點(diǎn)進(jìn)行路由；對(duì)于up*/down*路由算法，其生成樹的計(jì)算方式對(duì)網(wǎng)絡(luò)性能具有重要影響，而本文使用的則是基于深度優(yōu)先搜索生成樹的算法[5]，該算法對(duì)比基于廣度優(yōu)先搜索生成樹的算法[4]在性能上有很大提高；此外，在對(duì)segment路由算法進(jìn)行仿真時(shí)，對(duì)其路由轉(zhuǎn)向的限制也從負(fù)載均衡的角度進(jìn)行了優(yōu)化。

本文在6×6 Mesh網(wǎng)絡(luò)中，分別按照5%和10%的比例隨機(jī)產(chǎn)生故障節(jié)點(diǎn)，并在此基礎(chǔ)上生成路由表進(jìn)行仿真。對(duì)RFTR算法而言，其路由器具有2個(gè)虛通道，每個(gè)虛通道的緩存隊(duì)列容量為6個(gè)微片；而由于up*/down*算法和segment算法無需使用虛通道，為了保證各算法使用相同的緩存資源，其路由器緩存隊(duì)列的容量被設(shè)置為12個(gè)微片。在仿真過程中，每個(gè)節(jié)點(diǎn)均按照均勻分布的概率r隨機(jī)選取一個(gè)有效目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)包，且數(shù)據(jù)包的長度均勻分布在區(qū)間[2，10]內(nèi)。

圖6和圖7分別給出了故障節(jié)點(diǎn)率為5%和10%時(shí)，四種隨機(jī)故障模式下的數(shù)據(jù)包延時(shí)。從圖中可以看出，當(dāng)數(shù)據(jù)包注入率較小時(shí)，這三種算法所提供的數(shù)據(jù)包傳輸延時(shí)基本一致；然而隨著注入率的增大，各算法逐漸呈現(xiàn)出性能上的差異：up*/down*算法最先達(dá)到飽和，其次是segment算法，最后是RFTR算法。但根據(jù)故障節(jié)點(diǎn)位置的不同，這種差異并不是一定的，如在圖7（c）中，這三種算法的飽和注入率就非常接近，其原因?yàn)?，故障?jié)點(diǎn)的具體位置對(duì)矩形區(qū)域的劃分方式會(huì)產(chǎn)生影響，當(dāng)區(qū)域間連接的數(shù)目較少，或者大量數(shù)據(jù)包的傳輸集中在少數(shù)邊界節(jié)點(diǎn)時(shí)，這些連接和邊界節(jié)點(diǎn)會(huì)成為瓶頸而限制網(wǎng)絡(luò)吞吐率。因此從整體來看，RFTR算法能達(dá)到與up*/down*算法和segment算法相當(dāng)甚至更優(yōu)的性能。

5 結(jié)語

本文針對(duì)2D Mesh片上網(wǎng)絡(luò)提出了一種分區(qū)容錯(cuò)路由算法，通過劃分矩形區(qū)域和設(shè)置連接節(jié)點(diǎn)，將2D Mesh中的容錯(cuò)路由問題轉(zhuǎn)換成多個(gè)子Mesh網(wǎng)絡(luò)間的路由問題。該算法僅需2個(gè)虛通道就能避免死鎖，且通過查表與邏輯運(yùn)算相結(jié)合的路由計(jì)算方式，減少了路由表資源的用量。仿真結(jié)果表明，在路由器緩存資源相同的情況下，本文算法能達(dá)到與up*/down*算法和segment算法相當(dāng)甚至更優(yōu)的性能?？紤]到矩形區(qū)域的劃分方式對(duì)RFTR算法的性能會(huì)產(chǎn)生影響，因此在給定故障節(jié)點(diǎn)和鏈路的具體位置的情況下，尋求優(yōu)化的區(qū)域劃分方法是下一步工作的重點(diǎn)。

參考文獻(xiàn)：

[1] CHEN C L， CHIU G M. A faulttolerant routing scheme for meshes with nonconvex faults[J]. IEEE Transactions on Parallel and Distributed Systems， 2001， 12（5）： 467-475.

[2] ZHOU J P， LAU F C M. Multiphase minimal faulttolerant wormhole routing in meshes[J]. Parallel Computing， 2004， 30（3）：423-442.

[3] FLICH J， SKEIE T， MEJIA A， et al. A survey and evaluation of topologyagnostic deterministic routing algorithms[J]. IEEE Transactions on Parallel and Distributed Systems， 2012， 23（3）： 405-423.

[4] DUATO J， YALAMANCHILI S， NI L. Interconnection Networks： An Engineering Approach[M]. San Francisco： Morgan Kaufmann Publishers， 2003： 190-194.

[5] SANCHO J， ROBLES A， DUATO J. An effective methodology to improve the performance of the up*/down* routing algorithm[J]. IEEE Transactions on Parallel and Distributed Systems， 2004， 15（8）： 740-753.

[6] MEJIA A， FLICH J， DUATO J， et al. Segmentbased routing： an efficient faulttolerant routing algorithm for meshes and tori[C]// Proceedings of the 20th International Parallel and Distributed Processing Symposium. Washington， DC： IEEE Computer Society， 2006： 10-19.

[7] FLICH J， RODRIGO S， DUATO J. An efficient implementation of distributed routing algorithms for NoCs[C]// Proceedings of the 2nd ACM/IEEE International Symposium on NetworksonChip. Washington， DC： IEEE Computer Society， 2008： 87-96.

[8] 姚磊， 蔡覺平， 李贊， 等. 2DMesh結(jié)構(gòu)片上網(wǎng)絡(luò)無虛通道容錯(cuò)路由算法[J]. 西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2012， 39（6）： 26-33. （YAO L， CAI J P， LI Z， el al. Faulttolerant routing algorithm for the 2DMesh networkonchip without using virtual channels[J]. Journal of Xidian University（Natural Science）， 2012， 39（6）： 26-33.）

[9] 周磊， 吳寧， 李云. 一種基于2Dmesh的片上網(wǎng)絡(luò)無死鎖容錯(cuò)路由算法[J]. 上海交通大學(xué)學(xué)報(bào)， 2013， 47（1）： 18-22. （ZHOU L， WU N， LI Y. A faulttolerant and deadlockfree routing algorithm in 2Dmesh for network on chip[J]. Journal of Shanghai Jiaotong University， 2013， 47（1）： 18-22.）

[10] HOLSMARK R， KUMAR S， PALESI M， et al. HiRA： a methodology for deadlock free routing in hierarchical networks on chip[C]// Proceedings of the 3rd ACM/IEEE International Symposium on NetworksonChip. Washington， DC： IEEE Computer Society， 2009：2-11.

[11] DUBOIS F， SHEIBANYRAD A， PETROT F， et al. Elevatorfirst： a deadlockfree distributed routing algorithm for vertically partially connected 3DNoCs[J]. IEEE Transactions on Computers， 2013， 62（3）： 609-615.

[12] DALLY W J， SEITZ C L. Deadlockfree message routing in multiprocessor interconnection networks[J]. IEEE Transactions on Computers， 1987， 36（5）：547-553.