針對路徑故障與局部擁塞的NoC容錯(cuò)路由算法

歐陽一鳴，何鑫城，梁華國，易茂祥，杜高明，安 鑫

（1.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽合肥 230009；2.合肥工業(yè)大學(xué)電子科學(xué)與應(yīng)用物理學(xué)院，安徽合肥 230009）

針對路徑故障與局部擁塞的NoC容錯(cuò)路由算法

歐陽一鳴1，何鑫城1，梁華國2，易茂祥2，杜高明2，安 鑫1

（1.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽合肥 230009；2.合肥工業(yè)大學(xué)電子科學(xué)與應(yīng)用物理學(xué)院，安徽合肥 230009）

片上網(wǎng)絡(luò)作為一種新型片上互連架構(gòu)，克服了片上系統(tǒng)在發(fā)展中遭遇的瓶頸問題.然而，片上網(wǎng)絡(luò)中的路由器故障以及路由器之間的鏈路故障都會造成網(wǎng)絡(luò)性能損失.對此，文章提出一種針對路徑故障與局部擁塞的NoC容錯(cuò)路由算法.首先，設(shè)計(jì)了一種相隔節(jié)點(diǎn)間路徑故障模型，該模型下的路由器以較小的開銷為代價(jià)，動(dòng)態(tài)感知兩跳以內(nèi)的路徑故障狀態(tài).其次，提出了一種新穎的更能準(zhǔn)確反映局部網(wǎng)絡(luò)擁塞狀態(tài)的擁塞模型來均衡網(wǎng)絡(luò)流量.最后，當(dāng)網(wǎng)絡(luò)無故障時(shí)，算法保證走最優(yōu)路徑；有故障時(shí)，算法不僅可以實(shí)現(xiàn)容錯(cuò)還能保證網(wǎng)絡(luò)具有良好的性能.實(shí)驗(yàn)表明，在無故障的情況下，本文方案相較于對比對象延遲降低了10%～20%，吞吐率提高了25%左右.在有故障的情況下，本文方案較對比對象的優(yōu)勢更加明顯.

片上網(wǎng)絡(luò)；故障模型；擁塞模型；容錯(cuò)路由算法

1 引言

隨著單個(gè)芯片上集成的核越來越多，多核以及眾核系統(tǒng)中同時(shí)有超過一個(gè)任務(wù)在執(zhí)行的可能性也越來越大.這就使得單任務(wù)執(zhí)行的片上系統(tǒng)（System-on-Chip，SoC）在發(fā)展過程中遭遇瓶頸.鑒于此，有研究者提出通過借鑒計(jì)算機(jī)網(wǎng)絡(luò)和并行計(jì)算技術(shù)設(shè)計(jì)另一種新穎的片上互連架構(gòu)——片上網(wǎng)絡(luò)（Network-on-Chip，NoC），該架構(gòu)達(dá)到了傳統(tǒng)SoC不能實(shí)現(xiàn)的高帶寬、低延時(shí)和可擴(kuò)展性強(qiáng)等優(yōu)點(diǎn)［1～5］.

因?yàn)橘Y源共享和并行性是NoC的優(yōu)勢，所以網(wǎng)絡(luò)中會出現(xiàn)一項(xiàng)任務(wù)的執(zhí)行引起其他任務(wù)執(zhí)行效率下降的現(xiàn)象.為彌補(bǔ)這種現(xiàn)象帶來的性能損失，有學(xué)者提出利用路由算法［6～8］來隔離多任務(wù)，保證資源分配無沖突［9］.然而，目前的大多數(shù)算法更多的是實(shí)現(xiàn)NoC容錯(cuò)或考慮網(wǎng)絡(luò)狀態(tài)中的一種.文獻(xiàn)［10］提出一種基于奇偶轉(zhuǎn)向模型的容錯(cuò)路由算法，該算法將故障路由器劃分在水平方向不相鄰的矩形故障區(qū)域內(nèi)，但不考慮網(wǎng)絡(luò)中最左邊兩列上的路由器出現(xiàn)故障的情況.文獻(xiàn)［11］設(shè)計(jì)了一種基于轉(zhuǎn)彎模型來避免死鎖的容錯(cuò)路由算法，其不足之處在于算法只能容忍一個(gè)路由器故障.文獻(xiàn)［12］是一種分布式的容錯(cuò)路由算法，通過迭代尋找任意兩個(gè)節(jié)點(diǎn)之間的通路，并將通路信息記錄在路由表中.這種方案適用于數(shù)據(jù)注入率低的網(wǎng)絡(luò)，隨著網(wǎng)絡(luò)中數(shù)據(jù)包的增多，出現(xiàn)死鎖的可能性會增大.文獻(xiàn)［13］提出了一種擁塞感知的容錯(cuò)路由算法，該算法將與當(dāng)前節(jié)點(diǎn)相連的鏈路故障和下游節(jié)點(diǎn)輸入Buffer故障統(tǒng)一為鏈路故障，算法采用的擁塞參數(shù)為下游Buffer的占有率.然而，Buffer的占有率只能反映輸入端口Buffer的占用情況，并不能表示下游節(jié)點(diǎn)的數(shù)據(jù)傳輸狀態(tài).文獻(xiàn)［14］提出一種新穎的選擇策略，感知相鄰節(jié)點(diǎn)的除當(dāng)前節(jié)點(diǎn)外剩余三個(gè)鄰居節(jié)點(diǎn)的狀態(tài).該策略與奇偶路由算法結(jié)合，選擇一條盡量避免擁塞的路徑傳輸數(shù)據(jù)包，但是該方案僅考慮距離當(dāng)前節(jié)點(diǎn)兩跳外的節(jié)點(diǎn)狀態(tài).文獻(xiàn)［15］基于mad-y方法提出了一種擁塞感知學(xué)習(xí)模型，該模型在每個(gè)路由器內(nèi)部添加一張QTable，用于存儲數(shù)據(jù)在路徑上的延遲.文獻(xiàn)［15］提出的方案選擇局部最優(yōu)的路徑進(jìn)行路由，可以有效地避免擁塞、均衡網(wǎng)絡(luò)流量，但該方案沒有考慮網(wǎng)絡(luò)中出現(xiàn)故障的情況.

為解決以上問題，本文提出一種針對路徑故障與局部擁塞的NoC容錯(cuò)路由算法，主要有以下貢獻(xiàn)：（1）采用12-bit故障向量表示節(jié)點(diǎn)兩跳以內(nèi)的路徑故障狀態(tài)，節(jié)省了一定的硬件開銷；（2）利用下游節(jié)點(diǎn)各輸入端口請求交叉開關(guān)（Switch）無響應(yīng)的個(gè)數(shù)作為擁塞參數(shù)，使當(dāng)前節(jié)點(diǎn)更為準(zhǔn)確地感知下游節(jié)點(diǎn)的擁塞程度；（3）網(wǎng)絡(luò)無故障時(shí)，算法保證走最優(yōu)路徑；（4）網(wǎng)絡(luò)有故障時(shí)，算法不僅能容錯(cuò)而且能夠均衡網(wǎng)絡(luò)流量.

2 故障與擁塞模型

本文算法的實(shí)現(xiàn)基于五端口的虛通道路由器［3］.該路由器主要由東（E）、南（S）、西（W）、北（N）和本地（Local）五端口、輸入緩沖Buffer、Switch、控制模塊以及相應(yīng)的連接線路組成.傳統(tǒng)的無虛通道路由器在數(shù)據(jù)傳輸過程中很容易引起死鎖（Deadlock）［16］.本文采用了虛通道策略避免了死鎖的發(fā)生［17］.

2.1相隔節(jié)點(diǎn)間路徑故障模型

容錯(cuò)路由算法是針對NoC中出現(xiàn)的故障而提出，為了更好地體現(xiàn)算法的性能，定義一個(gè)好的故障模型顯得尤為重要.針對網(wǎng)絡(luò)中出現(xiàn)的永久性故障，本文提出一種新穎的故障模型，即相隔節(jié)點(diǎn)間路徑故障模型，該模型定義相隔節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)經(jīng)過兩跳到達(dá)的節(jié)點(diǎn).如圖1所示，Router 0為當(dāng)前節(jié)點(diǎn)，Router 1為下游節(jié)點(diǎn)，Router 2與Router 0互為相隔節(jié)點(diǎn).相隔節(jié)點(diǎn)間路徑故障狀態(tài)表示為L-P1P2（P1，P2∈｛E，W，S，N｝）.如L-EE表示，數(shù)據(jù)從Router 0的 E端口輸出，到達(dá) Router 1后從E端口輸出至Router 2所經(jīng)過的路徑的故障狀態(tài)（包括Router 0與Router 1之間的鏈路故障（圖1中①），Router 1的輸入 Buffer故障（圖1中②），Router 1的內(nèi)部通道故障（圖1中③），Router 1與Router 2之間的鏈路故障（圖1中④），Router 2的輸入Buffer故障（圖1中⑤））.L-EE為0時(shí)，表示Router 0與Router 2之間的路徑無故障；L-EE為1時(shí)，則可能由圖1中的①、②、③、④、⑤中一處或幾處出現(xiàn)故障所導(dǎo)致.

根據(jù)以上定義的相隔節(jié)點(diǎn)間路徑故障模型，本文提出一種適用于該故障模型的感知區(qū)域.如圖2所示，以Current Node為中心，相隔節(jié)點(diǎn)間路徑故障模型的感知區(qū)域內(nèi)共有8個(gè)相隔節(jié)點(diǎn).其中，SE Node與ES Node、NW Node和WN Node、NE Node和EN Node節(jié)點(diǎn)對由于選擇的輸出端口不同，其表示方式不一樣，但在物理分布上是同一個(gè)節(jié)點(diǎn).因此，Current Node需要12-bit的故障向量表示到所有相隔節(jié)點(diǎn)的路徑故障狀態(tài).

如表1所示，是Current Node到達(dá)感知區(qū)域內(nèi)的所有相隔節(jié)點(diǎn)的路徑故障向量.以E方向?yàn)槔?，?dāng)L-EN、L-EE、L-ES中至少有一個(gè)為0時(shí)，則表示Current Node 與E Node之間路徑無故障.當(dāng)L-EN、L-EE、L-ES均為1時(shí)分兩種情況：（1）Current Node與 E Node之間路徑故障；（2）E Node與EN Node、EE Node、ES Node三個(gè)相隔節(jié)點(diǎn)之間路徑都出現(xiàn)故障.當(dāng)出現(xiàn)以上情況，數(shù)據(jù)均不能由E Node繼續(xù)往下傳輸.因此，當(dāng)L-EN、L-EE、L-ES都為1時(shí)，本文規(guī)定E Node不可達(dá).

表1　Current Node故障向量表

2.2擁塞模型

當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，容錯(cuò)路由算法繞過故障節(jié)點(diǎn)或故障塊到達(dá)目的節(jié)點(diǎn)，但在此過程中容易出現(xiàn)擁塞［18］.因此設(shè)計(jì)容錯(cuò)路由算法的過程中，需要考慮網(wǎng)絡(luò)狀態(tài)，從而在一定程度上降低擁塞的發(fā)生.基于此，本文提出一種新穎的擁塞感知模型，以動(dòng)態(tài)感知下游節(jié)點(diǎn)的流量狀況，即對局部網(wǎng)絡(luò)流量的動(dòng)態(tài)感知.該模型采用節(jié)點(diǎn)各端口申請輸出但Switch未給予響應(yīng)的個(gè)數(shù)作為擁塞參數(shù)，存儲在擁塞寄存器（Congestion Register，CR）中.進(jìn)行路由計(jì)算（Routing Computation，RC）時(shí)，CR值會被傳輸至上游節(jié)點(diǎn)的RC模塊，用于路由決策.為了保證CR值的實(shí)時(shí)性，每個(gè)時(shí)鐘周期更新一次CR值.一旦采集到數(shù)據(jù)包申請輸出端口但Switch未響應(yīng)，CR值加1.當(dāng)Switch在給定周期內(nèi)未給予任何請求以應(yīng)答信號，表示該交叉開關(guān)分配器故障，CR值置為最大.模型定義的參數(shù)反映整個(gè)路由器的擁塞情況，路由數(shù)據(jù)包時(shí)選出CR值小的輸出通道.基于這種擁塞模型下的路由算法可以均衡網(wǎng)絡(luò)流量，降低數(shù)據(jù)包傳輸延遲.

3 容錯(cuò)路由算法設(shè)計(jì)

本文針對網(wǎng)絡(luò)中出現(xiàn)的故障和可能出現(xiàn)的擁塞，提出一種針對路徑故障與局部擁塞的NoC容錯(cuò)路由算法.算法設(shè)計(jì)了相隔節(jié)點(diǎn)間路徑故障模型，從而獲取路由過程中的路徑故障向量；利用下游節(jié)點(diǎn)各端口申請輸出但Switch未給予響應(yīng)的個(gè)數(shù)作為選取路由路徑的又一參數(shù).具體思想如下，取當(dāng)前節(jié)點(diǎn)與目的節(jié)點(diǎn)的X維和Y維的坐標(biāo)差值，分別記作ΔX、ΔY，目的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)間的曼哈頓路徑數(shù)記作

.當(dāng)靠近目的節(jié)點(diǎn)的路徑無故障時(shí)，選擇ΔX、ΔY中絕對值相差較大的方向作為輸出，保證路徑的多樣性.如果檢測到靠近目的節(jié)點(diǎn)的路徑均故障，選取另外兩個(gè)方向中CR值小的作為輸出.若出現(xiàn)回溯，將對應(yīng)的CR值置為最大，再次進(jìn)行路由選擇.具體執(zhí)行步驟：

（1）獲取故障向量表，若寄存器值均為0跳至步驟（2），否則轉(zhuǎn)（5）；

（2）取ΔX與ΔY的差.若差的絕對值大于等于2，轉(zhuǎn)（3），否則轉(zhuǎn)（4）；

（3）選擇差值較大的且靠近目的節(jié)點(diǎn)的方向輸出數(shù)據(jù)；

（4）選取CR值小的方向，若CR值相等，選擇與上一跳維數(shù)不同的方向輸出數(shù)據(jù)；

（5）當(dāng)靠近目的節(jié)點(diǎn)的下游節(jié)點(diǎn)的寄存器值均為1，轉(zhuǎn)（6），否則轉(zhuǎn)（7）；

（6）若遠(yuǎn)離目的節(jié)點(diǎn)的可選路徑存在，選取CR值小的節(jié)點(diǎn)輸出數(shù)據(jù)；否則報(bào)錯(cuò)；

（7）選取一條CR值小的備選路徑作為路由路徑.

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

在性能分析方面，本文采用改進(jìn)后的斯坦福大學(xué)開發(fā)的仿真工具Booksim2.0，搭建4*4的拓?fù)?，路由器設(shè)置雙虛通道，每個(gè)虛通道8flits，數(shù)據(jù)包采用1-6flits大小.在面積開銷方面，本文采用Synopsys公司的Design Compiler進(jìn)行硬件的邏輯綜合，工藝庫為45nm標(biāo)準(zhǔn)單元庫.

4.1網(wǎng)絡(luò)性能

如圖3所示，實(shí)驗(yàn)主要針對XY路由算法、文獻(xiàn)［14］的NoP方案、文獻(xiàn)［15］的 HARAQ方案和本文方案，在均勻（uniform）模式下比較延遲和吞吐率.其中，NoP方案、HARAQ方案以及本文方案中的路由算法（proposed即為本文方案）均為自適應(yīng)路由算法.

從圖3可以看出，本文方案性能優(yōu)于HARAQ方案、NoP方案和XY路由算法.XY路由算法因?yàn)槠渌惴ǖ拇_定性，在網(wǎng)絡(luò)流量較低的情況下和另外三種方案區(qū)別不大.隨著流量的不斷注入，算法的性能逐漸降低，所以在流量比較大的情況下，XY路由算法的性能明顯低于NoP方案、HARAQ方案和本文方案.由于NoP方案僅考慮鄰居以外的節(jié)點(diǎn)狀態(tài)，忽略直接鄰居節(jié)點(diǎn)的狀態(tài)信息，即使與完全適應(yīng)性路由算法結(jié)合，其性能也會受到影響.而HARAQ方案中每個(gè)節(jié)點(diǎn)均存有Q-Table，每次路由數(shù)據(jù)包之前選擇延遲最小的端口作為輸出.因此，HARAQ方案性能優(yōu)于NoP方案.但因?yàn)镠ARAQ方案每次路由均要讀取Q-Table，使得數(shù)據(jù)包延遲增大，故其相較于NoP方案的優(yōu)勢并不是很明顯.本文方案相對于NoP方案和HARAQ方案來說，在注入率達(dá)到0.35flit/node/cycle后優(yōu)勢逐漸明顯.這是由于本文方案在路有數(shù)據(jù)包的過程中充分考慮網(wǎng)絡(luò)狀態(tài)，即使在注入率比較大的情況下，仍然選擇擁塞度小的路徑傳輸數(shù)據(jù)，均衡網(wǎng)絡(luò)流量.

圖4所示的是在uniform模式下，針對不同的故障比例，文獻(xiàn)［13］的FTCAR方案、NoP方案、HARAQ方案和本文方案就網(wǎng)絡(luò)平均延遲和吞吐率的比較.其中，由于FTCAR方案的容錯(cuò)局限性，該方案在5%的故障率下的性能最差.NoP方案、HARAQ方案在故障率達(dá)到5%時(shí)，性能有所衰減，當(dāng)故障率達(dá)到10%時(shí)，NoP方案和HARAQ方案性能衰減得更加明顯.當(dāng)故障率達(dá)到15%時(shí)，本文方案性能衰減到與10%的故障率下的NoP方案、HARAQ方案性能接近.由此可見，本文方案的容錯(cuò)效果明顯高于NoP方案、FTCAR方案、HARAQ方案.

4.2面積開銷和功耗分析

由于Buffer/VC占據(jù)路由器面積的絕大部分［20］，因此，在相同大小的Buffer/VC前提下，對路由器內(nèi)部其他部件進(jìn)行改良均不會造成面積開銷過大.從圖5可以看出，本文方案、FTCAR方案、traditional方案、NoP方案以及HARAQ方案面積開銷依次減小.主要在于前三種方案均采用了雙虛通道策略，增加了Buffer中的多路選擇器、多路分配器以及VA控制邏輯，其次，為了實(shí)現(xiàn)容錯(cuò)和減輕擁塞，本文方案在每個(gè)路由器內(nèi)部添加了故障向量表和CR，帶來了可接受范圍內(nèi)的Control面積開銷.

由表2可知，本文方案相較于traditional方案的功耗增加了4.4mW.根據(jù)上述的面積分析可知，本文方案的硬件開銷和traditional方案相差不多，所帶來的靜態(tài)功耗基本接近，但是本文方案設(shè)計(jì)的路由算法會增加路由器的動(dòng)態(tài)功耗，因此本文方案的功耗大于traditional方案.在HARAQ方案中，數(shù)據(jù)每傳播一跳就將該段路徑上的延遲返回至上一跳節(jié)點(diǎn)的Q-Table，根據(jù)Q-Table中原有的值與返回值計(jì)算后的延遲比較，選擇其中較小的值作為該段路徑下一個(gè)數(shù)據(jù)包的傳輸延遲，因此，該方案帶來的動(dòng)態(tài)功耗開銷較大.同樣地，NoP中級聯(lián)的選擇策略也會帶來較大的動(dòng)態(tài)功耗.所以，HARAQ方案和NoP方案的功耗開銷均大于本文方案.

表2　功耗

5 總結(jié)

本文針對NoC路由器故障以及路由器之間的鏈路故障，提出了一種相隔節(jié)點(diǎn)間路徑故障模型，利用故障向量表示當(dāng)前節(jié)點(diǎn)兩跳以內(nèi)所經(jīng)歷的路徑故障狀態(tài)，再通過CR值統(tǒng)計(jì)下游節(jié)點(diǎn)的擁塞程度，進(jìn)而設(shè)計(jì)出一種針對路徑故障與局部擁塞的NoC容錯(cuò)路由算法.算法在網(wǎng)絡(luò)無故障的前提下走最優(yōu)路徑，一旦網(wǎng)絡(luò)中出現(xiàn)故障，則根據(jù)故障感知模型以及CR值選出最優(yōu)路徑，不僅實(shí)現(xiàn)容錯(cuò)還可以均衡網(wǎng)絡(luò)流量.在設(shè)計(jì)細(xì)節(jié)方面，本文采用的路由器是虛通道路由器，可以有效地避免死鎖，但又不會額外增加面積開銷.在算法實(shí)現(xiàn)過程中，采用最大化CR值的方法避免了活鎖的發(fā)生.實(shí)驗(yàn)結(jié)果表明，本文方案在可接受的硬件和功耗開銷的前提下，大幅度提高了網(wǎng)絡(luò)的性能，而且具有很好的容錯(cuò)效果.

［1］DiTomaso D，Kodi A，Louri A.QORE：A fault tolerant network-on-chip architecture with power-efficient quadfunction channel（QFC）buffers［A］.IEEE 20th International Symposium on High Performance Computer Architecture（HPCA）［C］.IEEE，2014.320-331.

［2］王新玉，向東，虞志剛.TM：一種新的片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)［J］.計(jì)算機(jī)學(xué)報(bào)，2014，37（11）：2327-2341. Wang Xin-yu，Xiang Dong，Yu Zhi-gang.TM：A new topology for networks-on-chip［J］.Chinese Journal of Computers，2014，37（11）：2327-2341.（in Chinese）

［3］歐陽一鳴，陳義軍，梁華國，等.一種故障通道隔離的低開銷容錯(cuò)路由器設(shè)計(jì)［J］.電子學(xué)報(bào)，2014，42（11）：2142 -2149. Ouyang Yi-ming，Chen Yi-jun，Liang Hua-guo.Design of a low-overhead fault channel isolated fault-tolerant router ［J］.Acta Electronica Sinica，2014，42（11）：2142-2149. （in Chinese）

［4］Liu C，Zhang L，Han Y，et al.Vertical interconnects squeezing in symmetric 3D mesh network-on-chip［A］.Proceedings of the 16th Asia and South Pacific Design Automation Conference［C］.IEEE，2011.357-362.

［5］歐陽一鳴，張一棟，梁華國，等.三維片上網(wǎng)絡(luò)故障及擁塞感知的容錯(cuò)路由器設(shè)計(jì)［J］.電子學(xué)報(bào)，2013，41（5）：912-917. Ouyang Yi-ming，Zhang yi-dong，Liang Hua-guo.A faulttolerant design of congestion-aware router in three-dimensional network-on-chip［J］.Acta Electronica Sinica，2013，41（5）：912-917.（in Chinese）

［6］付斌章，韓銀和，李華偉，等.面向高可靠片上網(wǎng)絡(luò)通信的可重構(gòu)路由算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2011，23（3）：448-455. Fu Bin-zhang，Han Yin-he，Li Hua-wei.Building resilient NoC with a reconfigurable routing algorithm［J］.Journal of Computer-Aided Design&Computer Graphics，2011，23 （3）：448-455.（in Chinese）

［7］Feng C，Zhang M，Li J，et al.A low-overhead fault-aware deflection routing algorithm for 3D network-on-chip［A］. IEEE Computer Society Annual Symposium on VLSI（ISVLSI）［C］.IEEE，2011.19-24.

［8］劉家俊，顧華璽，王長山.mesh優(yōu)先級容錯(cuò)路由［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（4）：105-107. Liu Jia-jun，Gu Hua-xi，Wang Chang-shan.Priority faulttolerant routing in mesh［J］.Computer Engineering and Applications，2009，45（4）：105-107.（in Chinese）

［9］Ma S，Jerger N E，Wang Z.DBAR：an efficient routing algorithm to support multiple concurrent applications in networks-on-chip［A］.38th Annual International Symposium on Computer Architecture（ISCA）［C］.IEEE，2011.413-424.

［10］Wu J.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. ［11］Zhang Z，Greiner A，Taktak S.A reconfigurable routing algorithm for a fault-tolerant 2D-mesh network-on-chip ［A］.45th ACM/IEEE Design Automation Conference ［C］.IEEE，2008.441-446.

［12］Fick D，DeOrio A，Chen G，et al.A highly resilient routing algorithm for fault-tolerant NoCs［A］.Proceedings of the Conference on Design，Automation and Test in Europe ［C］.European Design and Automation Association，2009.21-26.

［13］Valinataj M，Mohammadi S，Plosila J，et al.A fault-tolerant and congestion-aware routing algorithm for networkson-chip［A］.IEEE 13th International Symposium on Design and Diagnostics of Electronic Circuits and Systems （DDECS）［C］.IEEE，2010.139-144.

［14］Ascia G，Catania V，Palesi M，et al.Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip［J］.IEEE Transactions on Computers，2008，57（6）：809-820.

［15］Ebrahimi M，Daneshtalab M，F(xiàn)arahnakian F，et al. HARAQ：congestion-aware learning model for highly a-daptive routing algorithm in on-chip networks［A］.Sixth IEEE/ACM International Symposium on Networks on Chip（NoCS）［C］.IEEE，2012.19-26.

［16］Ying H，Jaiswal A，Hollstein T，et al.Deadlock-free generic routing algorithms for 3-dimensional networks-on-chip with reduced vertical link density topologies［J］.Journal of Systems Architecture，2013，59（7）：528-542.

［17］Dubois F，Sheibanyrad A，Pétrot F，et al.Elevator-first：A deadlock-free distributed routing algorithm for vertically partially connected 3D-NoCs［J］.IEEE Transactions on Computers，2013，62（3）：609-615.

［18］Chen K C，Kuo C C，Hung H S，et al.Traffic-and-thermalaware adaptive beltway routing for three dimensional network-on-chip systems［A］.IEEE International Symposium on Circuits and Systems（ISCAS）［C］.IEEE，2013. 1660-1663.

［19］Sedghi M，Koopahi E，Alaghi A，et al.An NoC test strategy based on flooding with power，test time and coverage considerations［A］.21st International Conference on VLSI Design［C］.IEEE，2008.409-414.

［20］DeOrio A，F(xiàn)ick D，Bertacco V，et al.A reliable routing architecture and algorithm for NoCs［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2012，31（5）：726-739.

歐陽一鳴 男，1963年生，博士，教授，中國計(jì)算機(jī)學(xué)會高級會員，研究方向：片上網(wǎng)絡(luò)（NoC）與片上系統(tǒng)（SoC）、嵌入式系統(tǒng)的綜合與測試、數(shù)字系統(tǒng)設(shè)計(jì)自動(dòng)化.

E-mail：oyymbox@163.com

何鑫城 女，1990年生，碩士研究生，研究方向：片上系統(tǒng)以及片上網(wǎng)絡(luò)容錯(cuò)方法.

E-mail：372521359@qq.com

A Fault-Tolerant Routing Algorithm Aiming at a Path Fault and Local Congestion in NoC

OUYANG Yi-ming1，HE Xin-cheng1，LIANG Hua-guo2，YI Mao-xiang2，DU Gao-ming2，AN Xin1

（1.School of Computer and Information，Hefei University of Technology，Hefei，Anhui 230009，China；2.School of Electronic Science&Applied Physics，Hefei University of Technology，Hefei，Anhui 230009，China）

As a new type of on-chip interconnection architecture，network-on-chip overcomes the bottleneck problem of the system-on-chip during the development.However，a failure arising in a router or a link between routers in network-onchip will cause the reduction of network performance.To avoid this phenomenon，this paper puts forward a fault-tolerant routing algorithm aiming at a path fault and local congestion in network-on-chip.Firstly，the algorithm designs a fault model that reflects the fault status of the path within two hops.As a result，this novel fault model makes the router achieve a dynamic perception of path state within two hops with less cost.Secondly，a novel congestion model has been proposed for reflecting the state of the local network more accurately，contributing to balance network traffic.Finally，when a fault occurs，the algorithm not only is fault-tolerant but also makes sure the network has a good performance.What’s more，the algorithm chooses the optimal path under the condition of fault-free.Experimental results show that the proposed algorithm has 10% ～20% lower latency in average and 25%higher throughput rate than the contrast case when the network is fault-free.In the case of defective in the network，the advantage of the present scheme has a bigger superiority.

network-on-chip；fault model；congestion model；fault-tolerant routing algorithm

TP302

A

0372-2112（2016）04-0920-06

電子學(xué)報(bào)URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.024

2014-11-15；

2015-11-23；責(zé)任編輯：李勇鋒

國家自然科學(xué)基金（No.61474036，No.61274036，No.61371025）；安徽省自然科學(xué)基金（No.1508085MF117）