，徐海，，

(1.上海大學 微電子研究與開發(fā)中心，上海 200072；2.吉林大學 軟件學院，長春 130012)

一種無虛通道NoC負載均衡容錯路由算法

劉鵬1，徐海鵬1，崇云鋒1，趙倩倩2

(1.上海大學微電子研究與開發(fā)中心，上海200072；2.吉林大學軟件學院，長春130012)

隨著芯片復雜度的不斷增大，設計一個高效的片上網絡容錯路由算法面臨著巨大的挑戰(zhàn)；由于芯片面積開銷的限制，擁有低面積開銷的無虛通道片上網絡路由器受到學術界的廣泛關注；但目前對無虛通道片上網絡容錯路由算法的研究卻停留在容錯性能上，而忽略了容錯路由算法的路由路徑過于單一所造成的負載不均、數(shù)據(jù)包平均延遲較大等問題；文章在借鑒已有的奇偶轉向容錯路由算法的基礎上，對算法的故障模型和故障繞行策略進行優(yōu)化，并在算法中融入負載均衡策略，以形成新的容錯算法緩解上述問題；在9x9的2D mesh網絡中對新提出的算法和參考算法的仿真結果表明：與參考算法相比，新算法在降低數(shù)據(jù)延遲和吞吐量方面有著明顯的優(yōu)勢，在最優(yōu)情況下能減少8.92%數(shù)據(jù)延遲和增加10.46%的吞吐量。

虛通道；容錯；故障模型；負載均衡

0 引言

在集成電路設計中，將多個物理核集成在同一個芯片中用于提升計算性能已成為一個重要的發(fā)展趨勢。隨著多核芯片的發(fā)展，各物理核之間的通信量迅速增長，分時復用的片上總線互連結構已不能滿足多核芯片在擴展性、并行性和功耗等方面的要求。為了解決多核互聯(lián)所面臨的上述問題，專家和學者們提出了一種以通信為中心、采用全局異步局部同步的片上互連結構，片上網絡(network on chip, NoC)[1]。

然而，伴隨著多核芯片的密集度和復雜度的不斷增大，以NoC為互聯(lián)結構的多核芯片對制造工藝偏差和外界干擾也變得越來越敏感，發(fā)生故障的概率也越來越大。這些故障可能會使NoC的性能急劇下降或直接癱瘓[2]。為確保芯片的可靠性，設計一種高效的容錯路由算法是非常有必要的[3]。

當前，由于芯片面積開銷的限制，擁有低面積開銷的無虛通道片上路由器受到學術界的廣泛關注。對無虛通道NoC容錯路由器的設計主要可以分為硬件容錯和算法容錯。硬件容錯需要在NoC路由器中添加備份單元，以保證故障發(fā)生時，NoC路由器仍能正常運作[4]。然而增加備份單元將增大芯片面積開銷。因此算法容錯方案逐漸在無虛通道NoC路由器的容錯設計中成為主流。

1 無虛通道容錯算法的相關研究

當前無虛通道NoC容錯路由算法可大致分為基于泛洪機制的容錯路由算法[5]、基于查找表的容錯路由算法[6]和基于轉向模型的容錯路由算法[7-9]?；诜汉闄C制的容錯路由算法會向網絡中發(fā)送大量的冗余數(shù)據(jù)包，隨著網絡負載的增大，網絡性能將急劇下降。采用查找表的容錯路由算法，需要在NoC路由器中增加一張路由表，以確定數(shù)據(jù)包的路由路徑。然而，隨著NoC尺寸的擴大，路由表的尺寸也隨之增大，造成面積開銷、功耗和數(shù)據(jù)包延遲迅速增加。而基于轉向模型的容錯路由算法在硬件開銷和性能上均優(yōu)于上述兩類容錯算法，因此基于轉向模型的容錯路由算法已成為NoC容錯的一個重要研究方向。

基于轉向模型的NoC容錯方案主要面臨網絡死鎖和故障繞行這兩個問題。為了解決這兩個問題的，基于轉向模型的容錯算法將在遵守已有的無死鎖轉向規(guī)則基礎之上，對基于該轉向規(guī)則的路由算法進行擴展，使之具備故障繞行功能，以達到容錯的要求。死鎖是數(shù)據(jù)包在傳輸過程中所形成的循環(huán)等待隊列引發(fā)的?；谵D向模型的無死鎖轉向規(guī)則[10]最早是由Glass和Ni提出，它是通過禁用部分90度轉向以破壞循環(huán)等待隊列的形成條件來杜絕死鎖的發(fā)生。目前，大部分基于轉向模型的無虛通道容錯路由算法都是基于Glass和Ni的轉向規(guī)則擴展設計的，典型的有Yusuke借鑒Glass和Ni的無死鎖轉向模型，提出一種Message-based容錯路由算法[7]。這種算法使用矩形故障模型對故障節(jié)點進行擴展，并在不同路由方向的數(shù)據(jù)包上施加不同的轉向限制，通過這些方法在賦予算法容錯能力的同時避免死鎖的發(fā)生。Fu也基于Glass和Ni的轉向模型提出一種ZoneDefense的容錯路由算法[8]。此算法在每個節(jié)點中增加Ceiling 和Floor寄存器，分別記錄著該節(jié)點南、北方向上故障區(qū)的位置信息。并利用Ceiling 和Floor中矩形故障區(qū)的位置信息在故障區(qū)之間構成了叫做ZoneDefense的區(qū)域。當數(shù)據(jù)包在ZoneDefense區(qū)域路由時，算法會禁用那些使數(shù)據(jù)包垂直撞向故障區(qū)而引發(fā)死鎖的轉向，從而避免了死鎖的發(fā)生。

Glass和Ni的路由算法存在有路徑分配不均的問題，在某個方向上僅能提供一條路由路徑，而基于它的容錯算法也存在這樣的問題。因此Chiu對Glass和Ni的轉向規(guī)則進行改進，提出奇偶(Odd-Even, OE)轉向模型[11]。它將不同的轉向限制分別施加在奇數(shù)和偶數(shù)列節(jié)點，并通過這種方式將路徑均勻分配到各個方向路由的數(shù)據(jù)包。具體的OE轉向規(guī)則如Rule1：

1) 任何數(shù)據(jù)包在偶數(shù)列不允許使用由東向北轉向(EN)和由東向南轉向(ES)。

2) 任何數(shù)據(jù)包在奇數(shù)列不允許使用由北向西轉向(NW)和由南向西轉向(SW)。

Wu提出一種典型的基于OE轉向規(guī)則的容錯路由算法[9]。為了使算法能夠容忍更多的故障節(jié)點，Wu的算法需要禁用一些無故障節(jié)點，以形成矩形的故障區(qū)，并且在故障區(qū)的東、西方向上需要預留兩條故障邊界。

然而無論是基于Glass和Ni還是Chiu的轉向規(guī)則的容錯算法都存在一個共同的問題：他們把工作過多的集中在容錯上，而忽略了各個節(jié)點的負載不均所導致的網絡局部擁塞、數(shù)據(jù)包平均延遲較大等問題。為了緩解這些問題，將對Wu的故障繞行策略和故障模型進行優(yōu)化和改進，然后在此基礎上融入負載均衡策略，最終形成一種無虛通道NoC負載均衡容錯路由算法，它可以借助負載策略把數(shù)據(jù)負載分配到各個節(jié)點上，使得空閑的帶寬資源能被充分的利用，以緩解局部擁塞和關鍵路徑上數(shù)據(jù)包延遲較大等問題，提升了NoC的性能。

2 基于轉向規(guī)則的負載均衡容錯算法

新提出的無虛通道NoC負載均衡容錯路由算法是基于路徑分配均勻的OE轉向規(guī)則擴展而來，它主要包含三部分內容：故障模型、故障繞行策略、負載均衡策略。這里將對算法的這3個部分進行具體的展開說明。

2.1 故障模型

目前大部分基于轉向模型的無虛通道容錯路由算法采用的是矩形故障模型，這種故障模型在形成過程中需要犧牲大量的安全節(jié)點，并且不適用于新算法的負載均衡策略。因此新算法將對 Wu的矩形故障模型[9]進行優(yōu)化和改進，以形成適用于新算法的故障模型。

為簡化算法的復雜度、容忍更多的故障節(jié)點，Wu在故障模型中定義了安全節(jié)點、危險節(jié)點和活動節(jié)點以形成矩形故障區(qū)和適用于故障繞行的故障邊界。其中，危險節(jié)點是由網絡中的無故障節(jié)點轉化而來，它的轉化方案如Rule2。

Rule2：在初始狀態(tài)下所有的無故障節(jié)點都是安全節(jié)點，一個安全節(jié)點只要滿足下列任意一個條件時，則轉變成危險節(jié)點：

1) 相鄰位置上至少有兩個危險節(jié)點或故障節(jié)點。

2) 東方向或西方向的相鄰位置上有一個危險節(jié)點或者故障節(jié)點，且這個節(jié)的西方向或東方向相鄰節(jié)點的南、北方向上有相鄰的危險節(jié)點或者故障節(jié)點。

重復1)、2)過程直到無新的危險節(jié)點生成，最終把危險節(jié)點和故障節(jié)點統(tǒng)稱為禁用節(jié)點，然后由這些禁用節(jié)點形成矩形的故障區(qū)。

然而，形成上述矩形故障區(qū)將犧牲過多的安全節(jié)點。針對這個問題，新的故障模型將在上述規(guī)則之上增加一條規(guī)則，以激活矩形故障區(qū)西邊緣上部分險節(jié)點，減少安全節(jié)點損失的數(shù)量。危險節(jié)點激活規(guī)則如Rule3。

Rule3：當一個危險節(jié)點在西方向上和南、北方向上有一個相鄰的安全節(jié)點，這個危險節(jié)點將被激活成安全節(jié)點。

重復上述過程直到沒有新的危險節(jié)點被激活，最終形成左凸多邊形故障區(qū)。由于OE轉向規(guī)則是通過破壞循環(huán)等待隊列右邊界的形成條件以杜絕死鎖的發(fā)生，在Wu的故障繞行策略下，激活故障區(qū)右邊緣上的危險節(jié)點可能會導致數(shù)據(jù)包在故障繞行時形成循環(huán)等待隊列的右邊界。因此新算法僅對故障區(qū)的西邊緣進行優(yōu)化。

圖1 故障模型應用實例

圖1是新故障模型的應用實例。在初始狀態(tài)下所有的無故障節(jié)點都是安全節(jié)點，執(zhí)行Rule2后，網絡中犧牲了大量安全節(jié)點。新算法將會采用Rule3激活故障區(qū)西邊緣的部分危險節(jié)點。在執(zhí)行完Rule3后，危險節(jié)點的數(shù)量將明顯的下降。

新算法使用的故障繞行策略和負載均衡策略都是基于OE轉向規(guī)則擴展而來，為了給東向、西向故障繞行的數(shù)據(jù)包提供足夠多的轉向許可，在故障區(qū)的東、西方向上會有一條由活動節(jié)點相互連接所形成奇數(shù)列和偶數(shù)列故障邊。而這里的活動節(jié)點是由與禁用節(jié)點相鄰的安全節(jié)點轉化而來，它的具體的生成方案如Rule4。

Rule4：故障區(qū)形成之后，網絡中只有禁用節(jié)點和安全節(jié)點，一個安全節(jié)點滿足以下任意一種條件時，則變?yōu)檫吔绻?jié)點。

1) 以該安全節(jié)點為原點，在其南、北方向相鄰位置上存在禁用節(jié)點。

2) 以該安全節(jié)點為原點，在其東、西方向上相距兩跳之內存在禁用節(jié)點。

重復執(zhí)行Rule4，直到不再產生活動節(jié)點，然后這些活動節(jié)點將相互連接形成故障邊。

由于新算法借鑒了Wu的故障繞行策略對需要進行故障繞行的數(shù)據(jù)包進行故障路由。而按照Wu的故障繞行規(guī)則，南、北方向故障路由的數(shù)據(jù)包需要優(yōu)先沿南、北方向路由，以確定數(shù)據(jù)包是否要進行故障路由，且只能沿著故障區(qū)的西邊界進行繞行。為了在容錯算法中融入負載均衡策略，在新故障模型中將故障區(qū)南、北兩個方向上的安全節(jié)點稱為臨界節(jié)點，其轉化方案如Rule5。

Rule5：在故障邊界形成之后網絡將有禁用節(jié)點、活動節(jié)點和安全節(jié)點，其中部分處于故障區(qū)南、北方向上的安全節(jié)點在滿足以下任一條件時，將轉化為臨界節(jié)點，其轉化規(guī)則如下。

1) 在南向上與活動節(jié)點或者臨界點相鄰的安全節(jié)點。

2) 在北向上與活動節(jié)點或者臨界節(jié)點相鄰的安全節(jié)。

重復Rule5直到不再有臨界節(jié)點生成。臨界節(jié)點位于故障區(qū)的南、北方向上，算法將對數(shù)據(jù)包是否需要故障繞行進行預判，以確定數(shù)據(jù)包是否能施行負載均衡策略。

2.2 故障繞行策略

故障模型的主要作用在于簡化容錯路由算法的復雜度、容忍更多故障節(jié)點。而故障繞行策略則是容錯路由算法中至關重要的部分，它直接決定算法的容錯能力。新算法將在Wu的故障繞行策略中融入網絡邊界故障繞行規(guī)則，以形成具有能容忍網絡邊界故障區(qū)的故障繞行策略。在Wu的故障繞行策略中，南、北向故障路由的數(shù)據(jù)包將一律沿著故障區(qū)西邊界進行故障繞行，因此Wu的故障繞行策略不支持無故障西邊界的網絡西邊界故障區(qū)的故障容錯。為解決網絡西邊界故障區(qū)的容錯問題，新算法規(guī)定網絡邊界故障區(qū)南、北故障邊界與內側東邊界的交界節(jié)點為輔助節(jié)點，且允許輔助節(jié)點使用OE轉向規(guī)則所禁用的轉向。下面將對改進后的繞行策略的繞行規(guī)則Rule6進行介紹。

Rule6：在敘述故障繞行規(guī)則之前，先對部分字母符號做以下定義：dx為數(shù)據(jù)包的目的節(jié)點橫坐標與當前節(jié)點橫坐標的差值，dy為數(shù)據(jù)包的目的節(jié)點縱坐標與當前節(jié)點縱坐標的差值，S為源節(jié)點，E代表偶數(shù)列、O代表奇數(shù)列。算法將根據(jù)不同的故障邊界、節(jié)點的類型和路由方向為數(shù)據(jù)包選擇不同的路由路徑：

1) 如果dx、dy為零，當前節(jié)點為目的節(jié)點，數(shù)據(jù)包則被本地節(jié)點吸收。dx或dy不為0時轉向2)。

2) 如果dy不為零，當前節(jié)點為安全節(jié)點或臨界節(jié)點，數(shù)據(jù)包則優(yōu)先向西路由到最近的偶數(shù)節(jié)點，然后沿著南、北方向路由，直到dy為零或遇到故障邊界。當前節(jié)點為活動節(jié)點則轉向3)。

3) 如果dx或dy不為零，當前節(jié)點為活動節(jié)點，且路由方向與所處的故障邊平行，數(shù)據(jù)包則沿著原來方向繼續(xù)路由。路由方向與故障邊垂直時則轉向4)。

4) 如果dx不為零，當前節(jié)點為故障東邊界上的活動節(jié)點，且路由方向與所處的故障邊界垂直，數(shù)據(jù)包則優(yōu)先向西路由到最近的偶數(shù)列活動節(jié)點，然后沿著靠近目的節(jié)點的故障邊界向目的節(jié)點路由。當前節(jié)點在故障西邊界上則轉5)。

5) 如果dx不為零，當前節(jié)點為故障西邊界上的活動節(jié)點，且路由方向與所處的故障邊界垂直，數(shù)據(jù)包則優(yōu)先向東路由到最近的奇數(shù)列活動節(jié)點，然后沿著靠近目的節(jié)點的故障邊界向目的節(jié)點路由。當前節(jié)點在故障南、北邊界上則轉6)。

6) 如果dy不為零，當前節(jié)點為網絡邊界故障區(qū)南、北邊界上的活動節(jié)點，且數(shù)據(jù)包的路由方向與所處的故障邊界垂直，路由算法需要根據(jù)東、西故障邊界的存在情況為數(shù)據(jù)包選擇不同的路由方向。當故障區(qū)只有東邊界或西邊界時，數(shù)據(jù)包將分別向東或向西發(fā)送，經過輔助節(jié)點或故障邊的交界點，沿著故障東邊界或西邊界進行故障繞行；當故障區(qū)既有東邊界又有西邊界時，數(shù)據(jù)包則沿著靠近目的節(jié)點的方向路由。網絡內部故障區(qū)的故障繞行轉向7)。

7) 如果dy不為零，當前節(jié)點為網絡內部故障區(qū)南、北邊界上的活動節(jié)點，且數(shù)據(jù)包的路由方向與所處的故障邊界垂直，數(shù)據(jù)包將向西發(fā)送，沿故障區(qū)西邊界繞行。其他情況轉8)。

8) 當數(shù)據(jù)包所處節(jié)點的狀態(tài)、dx，dy的值、路由方向不滿足上述條件時，數(shù)據(jù)包優(yōu)先沿南、北方向路由，直到dy為0或遇到活動節(jié)點，然后沿著東、西方向路由。

2.3 負載均衡策略

在奇偶轉向規(guī)則和最短路徑的限制下，dx、dy都不為零的數(shù)據(jù)包可能存在多個輸出端口，負載均衡策略則根據(jù)輸出端口上一時段的輸出情況為數(shù)據(jù)包選擇輸出端口，以實現(xiàn)負載均衡。為了施行均衡策略，在每個路由節(jié)點中會有一個4 bit的寄存器balac_bit[x](x=0,1,2,3)用于決定負載均衡模式下的數(shù)據(jù)的輸出端口。表1為數(shù)據(jù)包在負載均衡模式下的輸出端口，balac_bit[x](x=0,1,2,3)分別決定了數(shù)據(jù)包dxgt;0amp;amp;dygt;0、dxgt;0amp;amp;dylt;0、dxlt;0amp;amp;dygt;0和dxlt;0amp;amp;dylt;0時端口的輸出情況。

表1 負載均衡模式下數(shù)據(jù)包的輸出端口

數(shù)據(jù)包確定輸出端口后會把相應的balac_bit[x]位取反，在下一個數(shù)據(jù)到達這個節(jié)點時，會把它分配到另外一條路徑上，以實現(xiàn)負載的均衡和空余的帶寬資源的充分利用。

2.4 算法的執(zhí)行步驟

新的容錯路由算法主要由一個故障模型和兩種路由策略構成，故障模型用于容忍更多的故障節(jié)點和簡化算法復雜度，兩種路由策略則被固化在路由計算單元中為處于不同情況下的數(shù)據(jù)包選擇路由路徑，當數(shù)據(jù)包進入NoC路由節(jié)點的緩存單元后，路由計算單元將根據(jù)數(shù)據(jù)包的目的地址坐標、當前節(jié)點的地址坐標和當前節(jié)點的狀態(tài)選擇不同的路由策略。算法具體執(zhí)行流程如圖3所示。

1)當數(shù)據(jù)進入NoC路由器的緩存單元后，路由器首先判斷當前節(jié)點是否為目的節(jié)點，如果當前節(jié)點為目的節(jié)點，數(shù)據(jù)包則被本地節(jié)點吸收，否則轉向步驟2) 。

2)當前節(jié)點為安全節(jié)點時，算法將根據(jù)負載均衡策略為數(shù)據(jù)包選擇輸出端口。如果當前節(jié)點不是安全節(jié)點則轉向步驟3)。

3)當前節(jié)點為臨界節(jié)點或活動節(jié)點，路由算法則會先根據(jù)數(shù)據(jù)包的目的地址坐標與當前節(jié)點坐標對數(shù)據(jù)包是否要故障繞行進行預判，如果數(shù)據(jù)包需要進行故障繞行，算法則采用故障繞行策略為數(shù)據(jù)包選擇路由路徑。反之則采用負載均衡策略為數(shù)據(jù)包選擇路由路徑。

圖2 算法的執(zhí)行流程圖

未到達目的節(jié)點的數(shù)據(jù)包將重復上述步驟為數(shù)據(jù)包選擇輸出端口，直到到達目的節(jié)點，其算法流程如圖2所示。數(shù)據(jù)包在路由過程中可能會交替使用負載均衡策略和故障繞行策略，以應對不同路由環(huán)境。圖3是南、北向數(shù)據(jù)包的路由實例，數(shù)據(jù)包A和B的目的節(jié)點被無西故障邊界的網絡西邊界故障區(qū)隔斷，因此它們將一律向東借助輔助節(jié)點沿故障東邊界路由；數(shù)據(jù)包C路由到南邊界故障區(qū)的邊界時，由于故障區(qū)既有東邊界又有西邊界，這時數(shù)據(jù)將沿著靠近目的節(jié)點的方向進行故障繞行；數(shù)據(jù)包D和E繞行的是網絡內部故障區(qū)，因此數(shù)據(jù)包D和E將一律沿著故障西邊界進行路由。

圖3 南、北向數(shù)據(jù)包路由實例

圖4是東、西向數(shù)據(jù)包的路由實例，數(shù)據(jù)包F和G需要沿無北故障邊界的網絡北邊界故障區(qū)繞行，它們將被向南發(fā)送，沿故障南邊界進行故障繞行；而數(shù)據(jù)包H和I到達網絡內部故障區(qū)的邊界后，它們將沿著靠近目的節(jié)點的方向路由。

圖4 東、西向數(shù)據(jù)包路由實例

2.5 無死鎖的證明

新算法使用了負載均衡策略和故障繞行策略為數(shù)據(jù)包選擇路由路徑，負載均衡策略是在遵循OE轉向規(guī)則下對多輸出端口的數(shù)據(jù)包進行端口輸出選擇，南、北向數(shù)據(jù)包繞行網絡西邊界故障區(qū)的路由策略和東、西向數(shù)據(jù)包繞行故障區(qū)的路由策略都與Wu的路由策略一致，遵循OE轉向規(guī)則，不會引發(fā)死鎖。而南、北向數(shù)據(jù)包沿故障東邊界進行繞行時，在輔助節(jié)點使用了OE轉向規(guī)則所禁用的轉向，可能會形成循環(huán)等待隊列的右邊界，但卻不會引發(fā)死鎖，具體證明如下：

假設采用輔助節(jié)點路由的數(shù)據(jù)包在網絡中形成了循環(huán)等待隊列的右邊界，并且導致網絡中發(fā)生死鎖。那么這個引發(fā)死鎖的循環(huán)等待隊列一定要包含該輔助節(jié)點和其繞行的網絡邊界故障區(qū)。然而網絡邊界的故障區(qū)不存在完整的故障邊界，假設不成立，網絡不會出現(xiàn)死鎖。因此借助輔助節(jié)點繞行網絡邊界故障區(qū)的數(shù)據(jù)包不滿足循環(huán)等待隊形成的條件，故障繞行策略和新算法都是無死鎖的。

3 實驗分析與結論

本文將采用NIRGAM[12]仿真器對算法的性能進行仿真與驗證，它是一種基于System C的NoC專用模擬器，能對NoC的數(shù)據(jù)包的延遲和節(jié)點的吞吐量進行的仿真。性能仿真實驗將在負載不均的熱點模式下，向9x9的2D mesh網絡中注入4%和8%的故障節(jié)點對新提出的算法、Wu的算法[9]和文獻[7]的算法進行仿真。通過對比3種算法在熱點模式下平均延遲和吞吐量的差距以證明新算法的優(yōu)越性。在熱點模式下將會隨機地選取10%的節(jié)點作為通信熱點，這些通信熱點的通信量將比普通節(jié)點的通信量高出40%。

3.1 實驗結果分析

圖5和圖6分別為熱點模式下數(shù)據(jù)包平均延遲和節(jié)點吞吐量的仿真結果曲線圖。在熱點模式下，數(shù)據(jù)負載在網絡中負載的分配相對集中，在關鍵路徑上容易引發(fā)局部擁塞和數(shù)據(jù)包延遲較大等問題。而在這種情況下，新算法中的負載均衡策略可以把集中的數(shù)據(jù)負載分配到其他帶寬相對富裕的節(jié)點上。因此從曲線圖中可以看出，隨著網絡負載率的增大新算法在數(shù)據(jù)包

圖5 熱點模式下數(shù)據(jù)包的平均延遲

圖6 熱點模式下節(jié)點的平均吞吐量

延遲和節(jié)點吞吐量的優(yōu)勢都將逐漸增大，相對Wu的算法，在下最優(yōu)情況下能降低8.92%的數(shù)據(jù)包平均延遲和增加10.48%的節(jié)點吞吐量；但隨著故障注入率增加到8%，能施行均衡策略的節(jié)點數(shù)量也在不斷的減少，在網絡帶寬利用率到達最大值時，新算法在數(shù)據(jù)包平均延遲和節(jié)點吞吐量的優(yōu)勢將逐漸減小。但由于犧牲的無故障節(jié)點較少，新算法的性能仍會優(yōu)于其他兩種算法。

3.2 結論

文章針對當前無虛通道容錯路由算法存在的負載分配不均的問題，借鑒Wu的故障繞行策略提出了一種無虛通道NoC負載均衡容錯路由算。該算法能將數(shù)據(jù)負載分配到其他空閑的通信節(jié)點上，在保證網絡不發(fā)生死鎖的同時降低了數(shù)據(jù)包的平均延遲、增加了節(jié)點的吞吐量。實驗結果表明在故障率適中、負載較大的情況下新算法能取得一個良好的效果。

[1] Benini L, De M G. Networks on chips: a new SoC paradigm [J]. Computer, 2002, 35(1):70-78.

[2] L Xiaowei, Yu H, Lei Z et al. The fault tolerant design of digital IC [M]. Beijing: Science Press, 2011.

[3] Wu M S, Lee L C. Using a periodic square wave test signal to detect crosstalk faults [J]. IEEE Design amp; Test of Computer, 2005, 22(2):160-169.

[4] Feng C C, Lu Z H, Jantsch A, et al. A reconfigurable fault-tolerant deflection routing algorithm basesd on reinforcement learning from network-on-chip [A]. the 3rd International Workshop on Network on Chip Architecture [C]. New York, 2010.

[5] Pirretti M, Link G, Brooks R, et al. Fault tolerant algorithm for network on Chip interconnect [A]. Computer Society Annual Symposium on VLSI [C]. Lafayette, 2004.

[6] Fick D, Deorio A, Chen G, et al. A highly resilient routing algorithm for fault tolerant NoCs [A]. Design, Automation and Test Europe Conference amp; Exhibition [C], Nice, 2009.

[7] Yusuke F, Masaru F, Susumu H. Fault Tolerant Routing Algorithm for Network on Chip without Virtual Channels [A]. International Symposium on Defect and Fault Tolerance in VLSI Systems [C], Chicago, 2009.

[8] F Binzhang, H Yinhe, L Huawei, et al. ZoneDefense: A Fault Tolerant Routing for 2D Meshes Without Virtual Channels [J]. IEEE Transactions on very large scale integration system 2014, 22(1):113-126.

[9] Wu Jie. A Fault-Tolerant and Deadlock-Free Routing Protocol in 2D Meshes Based on Odd-Even Turn Model [J]. IEEE Transactions on computers 2003, 52(9):1154-1169.

[10] Glass C J, Ni L M. The Turn Model for Adaptive Routing [A]. Computer Architecture. Los Alamitos [C], Los Alamitos, 1992.

[11] Chiu Geming.The Odd-Even Turn Model for Adaptive Routing [J]. IEEE transactions on parallel and distributed systems 2000, 11(7):729-738.

[12] Lavina J. A simulator for NoC interconnect routing and application modeling [D]. UK: University of Southampton, 2007.

ALoad-balancingFault-tolerantNoCRoutingAlgorithmBasedonTurnRulesWithoutVirtualChannel

Liu Peng1, Xu Haipeng1, Chong Yunfeng1, Zhao Qianqian2

(1.Microelectronics Ramp;D Center, Shanghai University, Shanghai 200072, China;2.College of software, Jilin University, Changchun 130012, China)

As structure of chip is becoming more complex, an efficient routing algorithm designed for Network on Chip has became increasingly challenging. Currently, the research of fault-tolerant routing algorithm without virtual channels mainly focus on routing around fault, but neglects issues of load-balancing and latency caused by communication hotspot and single path between source and destination. To address the problems, a fault-tolerant routing algorithm based on Odd-Even turn rules with load-balancing strategy is proposed based on existing OE fault-tolerant strategy. The novel algorithm extend Odd-Even fault model and Odd-Even fault-tolerant strategy to enhance capacity of fault-tolerant and also fuse a load-balance strategy to relieve the issues. The simulation results demonstrate that the proposed algorithm outperforms in average package latency and throughout compared to reference algorithms in the 9x9 2D mesh NoC. In the best case, it reduces 8.92% average delay and increase 10.46% throughout.

virtual channel; fault-tolerance; fault model; load-balancing

2017-03-01；

2017-03-24。

劉 鵬(1991-)，男，江西贛州人，碩士，碩士研究生，主要從事集成電路容錯設計方向的研究。

1671-4598(2017)09-0126-04

10.16526/j.cnki.11-4762/tp.2017.09.033

TP336

A