，徐海，，

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

一種無(wú)虛通道NoC負(fù)載均衡容錯(cuò)路由算法

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

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

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

虛通道；容錯(cuò)；故障模型；負(fù)載均衡

0 引言

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

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

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

1 無(wú)虛通道容錯(cuò)算法的相關(guān)研究

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

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

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

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

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

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

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

2 基于轉(zhuǎn)向規(guī)則的負(fù)載均衡容錯(cuò)算法

新提出的無(wú)虛通道NoC負(fù)載均衡容錯(cuò)路由算法是基于路徑分配均勻的OE轉(zhuǎn)向規(guī)則擴(kuò)展而來(lái)，它主要包含三部分內(nèi)容：故障模型、故障繞行策略、負(fù)載均衡策略。這里將對(duì)算法的這3個(gè)部分進(jìn)行具體的展開說(shuō)明。

2.1 故障模型

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

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

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

1) 相鄰位置上至少有兩個(gè)危險(xiǎn)節(jié)點(diǎn)或故障節(jié)點(diǎn)。

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

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

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

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

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

圖1 故障模型應(yīng)用實(shí)例

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

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

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

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

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

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

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

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

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

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

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

2.2 故障繞行策略

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

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

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

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

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

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

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

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

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

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

2.3 負(fù)載均衡策略

在奇偶轉(zhuǎn)向規(guī)則和最短路徑的限制下，dx、dy都不為零的數(shù)據(jù)包可能存在多個(gè)輸出端口，負(fù)載均衡策略則根據(jù)輸出端口上一時(shí)段的輸出情況為數(shù)據(jù)包選擇輸出端口，以實(shí)現(xiàn)負(fù)載均衡。為了施行均衡策略，在每個(gè)路由節(jié)點(diǎn)中會(huì)有一個(gè)4 bit的寄存器balac_bit[x](x=0,1,2,3)用于決定負(fù)載均衡模式下的數(shù)據(jù)的輸出端口。表1為數(shù)據(jù)包在負(fù)載均衡模式下的輸出端口，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時(shí)端口的輸出情況。

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

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

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

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

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

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

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

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

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

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

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

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

2.5 無(wú)死鎖的證明

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

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

3 實(shí)驗(yàn)分析與結(jié)論

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

3.1 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

3.2 結(jié)論

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

[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-)，男，江西贛州人，碩士，碩士研究生，主要從事集成電路容錯(cuò)設(shè)計(jì)方向的研究。

1671-4598(2017)09-0126-04

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

TP336

A