杭彥希，徐金甫，南龍梅，郭朋飛

(1.信息工程大學(xué)，鄭州 450001； 2.專用集成電路與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室(復(fù)旦大學(xué)),上海 201203)

端口故障粒度劃分的虛通道動態(tài)分配式容錯路由器設(shè)計(jì)

杭彥希1*，徐金甫1，南龍梅2，郭朋飛1

(1.信息工程大學(xué)，鄭州 450001； 2.專用集成電路與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室(復(fù)旦大學(xué)),上海 201203)

(*通信作者電子郵箱yanxih@foxmail.com)

高可靠性是高性能片上網(wǎng)絡(luò)路由器發(fā)展的重要方面，針對目前虛通道動態(tài)分配式路由器端口易發(fā)生故障的問題，提出了一種基于端口故障粒度劃分的容錯路由器設(shè)計(jì)。首先，結(jié)合虛通道動態(tài)分配方式的特殊性以及故障發(fā)生特性，建立了一種粒度劃分的端口故障與擁塞預(yù)測模型；然后在此模型的基礎(chǔ)上結(jié)合實(shí)時(shí)故障檢測方法設(shè)計(jì)相關(guān)容錯電路，增加鄰端口共享模塊，設(shè)計(jì)容錯讀寫指針控制邏輯電路；最后依據(jù)設(shè)計(jì)的電路提出容錯與擁塞緩解方案。實(shí)驗(yàn)結(jié)果表明，在各種端口故障模式下，該路由器均能保持較好的容錯特性，性能衰減較小，并且具有較好的性能提升與面積開銷比。

片上網(wǎng)絡(luò)；路由器；容錯；端口故障

0 引言

隨著大數(shù)據(jù)和云計(jì)算等大批量、高速數(shù)據(jù)處理應(yīng)用的出現(xiàn)，單核處理系統(tǒng)已經(jīng)遠(yuǎn)遠(yuǎn)不能滿足數(shù)據(jù)處理的需求，基于片上網(wǎng)絡(luò)互連的多核系統(tǒng)逐漸成為高性能數(shù)據(jù)處理系統(tǒng)發(fā)展的趨勢。路由器作為多核互聯(lián)的核心部件，承擔(dān)著網(wǎng)絡(luò)路由和數(shù)據(jù)交換的重要任務(wù)。目前對于路由器的研究主要集中在低功耗/低成本、高性能和可靠性三個(gè)方面。在低功耗/低成本方面：文獻(xiàn)[1]在系統(tǒng)級對影響路由器功耗的關(guān)鍵因素進(jìn)行分析，提出了一種低功耗路由器；文獻(xiàn)[2]提出了一種新的輕量級靈活緩存結(jié)構(gòu)，在不影響性能的情況下最小化緩存面積。在高性能方面，文獻(xiàn)[3]提出了一種提前分配路徑的低延時(shí)片上網(wǎng)絡(luò)結(jié)構(gòu)，明顯改善了網(wǎng)絡(luò)的延時(shí)和吞吐率；文獻(xiàn)[4]提出了一種新穎的虛通道高效動態(tài)分配的路由器，被認(rèn)為是目前最高效的虛通道組織方案。在可靠性方面：文獻(xiàn)[5]采取通道切片技術(shù)設(shè)計(jì)了一款能高效容錯的路由器；文獻(xiàn)[6]提出了一種高可靠，低成本的容錯路由器，分別修改了路由計(jì)算、虛通道分配、交叉開關(guān)分配和交叉開關(guān)結(jié)構(gòu)，實(shí)現(xiàn)了路由器的全方位容錯。

目前得到廣泛應(yīng)用的是虛通道靜態(tài)分配式路由器，但其緩存利用率較低且仍然存在隊(duì)列頭阻塞等問題，而虛通道動態(tài)分配式路由器通過為每個(gè)虛通道動態(tài)分配緩存容量，提高緩存利用率，最大化虛通道并行轉(zhuǎn)發(fā)粒度，也最大化消除了頭阻塞的發(fā)生，能大大提高片上網(wǎng)絡(luò)性能，因此，對虛通道動態(tài)分配式路由器的研究是高性能路由器發(fā)展的一個(gè)重要方面。對于虛通道動態(tài)分配式路由器，其虛通道組織方式主要有三種：第一種是基于鏈接表實(shí)現(xiàn)的，如文獻(xiàn)[7-8]等使用的動態(tài)分配多隊(duì)列(Dynamically Allocated Multi-Queue, DAMQ)方式；第二種是基于映射表實(shí)現(xiàn)的，最典型的是文獻(xiàn)[9]提出的動態(tài)虛擬通道分配器(Dynamic Virtual Channel Regulator, ViCHaR)以及文獻(xiàn)[10]提出的虛通道固定動態(tài)分配方式(Fixed VC Assignment with Dynamic VC Allocation, FVADA)和虛通道可調(diào)節(jié)式動態(tài)分配方式(Adjustable VC Assignment with Dynamic VC Allocation, AVADA)；第三種是基于硬件控制電路實(shí)現(xiàn)的，如文獻(xiàn)[4]提出的高效的虛擬通道動態(tài)分配方式(Efficient Dynamic Virtual Channel organization, EDVC)。但是不管哪種實(shí)現(xiàn)方式都需要龐大集中的緩存資源和復(fù)雜的控制邏輯，這些都極大增加了虛通道動態(tài)分配式路由器端口發(fā)生故障的概率，也使得對其端口故障的研究顯得十分必要。目前針對路由器的容錯技術(shù)主要分成兩種：1)利用容錯路由算法繞開故障節(jié)點(diǎn)。如文獻(xiàn)[11]提出了一種基于內(nèi)建自測試技術(shù)的無虛通道容錯路由算法；文獻(xiàn)[12]提出的粗粒度和細(xì)粒度的前瞻性容錯路由算法。但是這些方法容錯粒度較大，一旦發(fā)現(xiàn)故障節(jié)點(diǎn)就選擇繞開或者丟棄，極大地浪費(fèi)了片上緩存等資源。2)修改路由器微結(jié)構(gòu)進(jìn)行容錯。如文獻(xiàn)[13]提出了一種可靠的容錯路由器架構(gòu)，稱其為Vicis；文獻(xiàn)[14]提出了一種全方位防護(hù)的容錯路由器，將其命名為Shield。但是這些研究大都集中于虛通道靜態(tài)分配式路由器，并且也主要都是針對路由計(jì)算、虛通道分配和交叉開關(guān)等的容錯設(shè)計(jì)，缺少對虛通道動態(tài)分配式路由器龐大集中的緩存資源和復(fù)雜的控制邏輯的故障研究。

綜合以上問題，本文根據(jù)虛通道動態(tài)分配式路由器的特點(diǎn)，針對其端口故障，設(shè)計(jì)了一款對端口容錯的路由器。本文主要工作如下：1)根據(jù)虛通道動態(tài)分配式路由器緩存組織方式特點(diǎn)，提出了一種基于粒度劃分的統(tǒng)一的端口故障與擁塞預(yù)測模型；2)設(shè)計(jì)了一種高度可靠的鄰端口共享模塊；3)設(shè)計(jì)了一種容錯式讀寫指針控制邏輯電路。

1 故障及擁塞預(yù)測模型建立

針對國內(nèi)外對高性能虛通道動態(tài)分配式路由器的研究現(xiàn)狀，本文著重對最易發(fā)生故障的路由器端口進(jìn)行研究，提出了端口故障的粒度劃分，并根據(jù)排隊(duì)論原理建立了端口故障粒度劃分的故障與擁塞預(yù)測模型。

1.1 虛通道動態(tài)分配式路由器結(jié)構(gòu)

虛通道動態(tài)分配式路由器的結(jié)構(gòu)如圖1所示，借鑒文獻(xiàn)[4]提出的路由器輸入端口架構(gòu)，其與一般虛通道靜態(tài)分配式路由器的區(qū)別主要在于輸入端口緩存的組織方式以及數(shù)據(jù)包進(jìn)出虛通道的方式上。對于虛通道動態(tài)分配式路由器，一般采用集中式緩存組織方式，數(shù)據(jù)包進(jìn)出由控制邏輯(Control Logic, CL)來實(shí)現(xiàn)，控制邏輯可由鏈接表、組合電路或硬件電路實(shí)現(xiàn)。虛通道動態(tài)分配式路由器端口主要由緩存和控制邏輯組成。

1.2 故障粒度劃分

虛通道動態(tài)分配式路由器端口架構(gòu)如圖2所示。緩存使用靜態(tài)隨機(jī)存取存儲器(Static Random Access Memory, SRAM)實(shí)現(xiàn)，假設(shè)緩存塊深度為L個(gè)緩沖槽，寬度根據(jù)實(shí)際采用的虛通道動態(tài)分配方式確定。

由文獻(xiàn)[13]可知，緩存占用整個(gè)路由器80%～94%的面積，而在虛通道動態(tài)分配式路由器端口中90%以上都是緩存資源，故其端口緩存發(fā)生故障概率大于70%，再加上復(fù)雜的控制邏輯，使得其端口故障發(fā)生概率遠(yuǎn)高于其他部件發(fā)生故障的概率，因此需要對其端口故障進(jìn)行容錯設(shè)計(jì)。

圖1 虛通道動態(tài)分配式路由器結(jié)構(gòu)

圖2 路由器端口

在端口中可能發(fā)生兩種形式的故障：緩存故障和控制邏輯故障。當(dāng)發(fā)生緩存故障時(shí)會出現(xiàn)兩種情況：一種是剩余緩存不能滿足節(jié)點(diǎn)間通信需求，棄用整個(gè)端口；另一種是剩余緩存仍能滿足節(jié)點(diǎn)當(dāng)前通信需求，可保留整個(gè)端口，但控制邏輯需作出相應(yīng)的改變。當(dāng)發(fā)生控制邏輯故障時(shí)，則必須放棄整個(gè)端口。為此，本文對端口故障粒度劃分如下：

1)細(xì)粒度端口故障。當(dāng)緩存塊中a(0≤a≤L-1)個(gè)緩沖槽發(fā)生故障，而剩余的L-a個(gè)緩沖槽仍然能夠滿足當(dāng)前節(jié)點(diǎn)間通信需求，并且不造成節(jié)點(diǎn)阻塞，則認(rèn)為發(fā)生了端口細(xì)粒度緩存故障。

2)粗粒度端口故障。本文中的粗粒度端口故障分為兩種：一種是當(dāng)緩存塊中的b(1≤b≤L)個(gè)緩沖槽發(fā)生故障，而剩余的L-b個(gè)緩沖槽無法滿足當(dāng)前節(jié)點(diǎn)間通信需求，造成數(shù)據(jù)包阻塞；二是控制邏輯發(fā)生故障，數(shù)據(jù)包進(jìn)出SRAM產(chǎn)生未知錯誤。這兩種情況歸納為端口粗粒度故障。對端口故障劃分如圖3所示。

圖3 端口故障粒度劃分

1.3 粒度劃分的故障及擁塞預(yù)測模型

端口故障的發(fā)生勢必會導(dǎo)致端口堵塞或端口失效，劃分完故障粒度后，需要針對不同粒度的端口故障采取不同的容錯方案，最大限度地減小故障對系統(tǒng)性能產(chǎn)生的影響，關(guān)鍵問題是如何定量確定端口故障粒度。為此，本文借鑒文獻(xiàn)[15]提出的一種故障現(xiàn)場實(shí)時(shí)檢測方法，利用一種可以對緩存故障和控制邏輯故障現(xiàn)場實(shí)時(shí)檢測的方法，提出一種統(tǒng)一的粒度劃分的故障及擁塞預(yù)測模型。當(dāng)發(fā)生故障時(shí)，先通過故障檢測模塊區(qū)分出是緩存故障還是控制邏輯故障，再根據(jù)排隊(duì)論原理對緩存故障進(jìn)行劃分；在無故障發(fā)生時(shí)，可對各端口擁塞程度預(yù)測，選擇相鄰端口中擁塞程度最小的端口進(jìn)行傳輸。

1.3.1 排隊(duì)論

當(dāng)數(shù)據(jù)包進(jìn)入虛通道動態(tài)分配式的路由器時(shí)，其本質(zhì)上是采用一種先來先服務(wù)的服務(wù)方式，路由器控制邏輯可看作單服務(wù)臺。數(shù)據(jù)包到達(dá)各節(jié)點(diǎn)的過程是隨機(jī)且相互獨(dú)立的，可以將這一過程看作服從泊松分布，則對于路由器東、南、西、北、本地五個(gè)方向上的每一個(gè)緩沖都可以看作一個(gè)服從M/M/1/K規(guī)律的排隊(duì)模型(第一個(gè)M表示數(shù)據(jù)包到達(dá)服從泊松到達(dá)，第二個(gè)M表示服務(wù)時(shí)間服從負(fù)指數(shù)分布，1表示單服務(wù)臺，K表示隊(duì)列容量)。根據(jù)排隊(duì)論原理，有以下公式：

(1)

s.t.ρ=λ/u

其中：Pn表示隊(duì)列中有n個(gè)顧客等待的概率；ρ為隊(duì)列的利用率，其值為顧客到達(dá)速率λ與服務(wù)速率μ的比值。

1.3.2 模型假設(shè)

構(gòu)建一個(gè)2D-mesh型大小為m×n的片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，借鑒文獻(xiàn)[4]提出的虛通道動態(tài)分配方式，所建模型基于如下假設(shè)：

1)采用蟲孔交換方式以及確定性路由算法，通信基本單位為微片(flit)。

2)數(shù)據(jù)包長度可變，其長度用W表示，鏈路帶寬為Bflit/s。

3)路由器本地輸入端口上的緩存為無限大，因?yàn)樘幚韱卧?Processing Element, PE)內(nèi)有存儲器，且數(shù)據(jù)包一旦到達(dá)PE就立即被接收。

1.3.3 模型建立

(2)

s.t.ρx,y,dir=λx,y,dir/ux,y,dir=λx,y,dir×Tx,y,dir

其中：ρx,y,dir為Bufferx,y,dir的利用率;λx,y,dir為節(jié)點(diǎn)(x,y)處dir端口輸入通道的數(shù)據(jù)注入率;ux,y,dir為節(jié)點(diǎn)(x,y)處dir端口輸入通道的服務(wù)速率;Tx,y,dir為節(jié)點(diǎn)(x,y)處dir端口輸入通道的平均服務(wù)時(shí)間。

一般認(rèn)為，路由器緩存中會發(fā)生兩種類型的堵塞：由輸出資源競爭導(dǎo)致的隊(duì)列頭阻塞以及由緩存資源不足引起的隊(duì)列內(nèi)阻塞。虛通道動態(tài)分配式路由器的出現(xiàn)就是為了消除隊(duì)列頭阻塞，因此本文只考慮緩存資源不足導(dǎo)致的隊(duì)列內(nèi)阻塞。為確定緩存故障粒度，本文提出故障粒度閾值這一概念，用δ表示。當(dāng)堵塞概率εx,y,dir小于等于δ時(shí)，認(rèn)為是細(xì)粒度緩存故障；當(dāng)堵塞概率εx,y,dir大于δ時(shí)，則認(rèn)為發(fā)生粗粒度緩存故障。根據(jù)排隊(duì)論，對于M/M/1/K排隊(duì)模型的有限長隊(duì)列，數(shù)據(jù)包被堵塞在隊(duì)列內(nèi)的概率εx,y,dir可近似等于隊(duì)列中有m個(gè)微片(1≤m≤L)的概率之和。則有:

(3)

其中：λi, j表示節(jié)點(diǎn)(i,j)處的PE向網(wǎng)絡(luò)中注入數(shù)據(jù)的平均速率;Pi, j,i′, j′表示(i,j)處的PE向(i′,j′)發(fā)送數(shù)據(jù)的概率;R(i,j,i′,j′,x,y,dir)表示路由算法，如果從節(jié)點(diǎn)(i,j)到(i′,j′)的數(shù)據(jù)要經(jīng)過(x,y)處dir端口，則R(i,j,i′,j′,x,y,dir)為1，否則為0。對于一個(gè)確定的應(yīng)用來說，Pi, j,i′, j′是已知的，而本文針對的是確定性路由算法，所以R(i,j,i′,j′,x,y,dir)也可以確定下來。對于λi, j，本文在每個(gè)路由器的本地網(wǎng)絡(luò)接口上增加流量監(jiān)測模塊，檢測在一定的時(shí)鐘周期內(nèi)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的PE向網(wǎng)絡(luò)中發(fā)送的數(shù)據(jù)流量，從而計(jì)算出λi, j，最后可計(jì)算出λx,y,dir。

為了計(jì)算出εx,y,dir，還需要計(jì)算出服務(wù)時(shí)間Tx,y,dir，服務(wù)時(shí)間指數(shù)據(jù)包的頭微片進(jìn)入路由節(jié)點(diǎn)到尾微片離開路由節(jié)點(diǎn)的時(shí)間。在無阻塞發(fā)生的情況下，有：

Tx,y,dir=TH+W×TM

(4)

s.t.TH=TRC+TVA，TM=TST+TCS+TLINK

其中：TRC為完成對頭微片的路由計(jì)算的時(shí)間；TVA為頭微片發(fā)出虛通道分配請求及仲裁成功的時(shí)間，若路由器控制邏輯固定，則TH為定值；TM為轉(zhuǎn)發(fā)單個(gè)體微片所需的時(shí)間；TST為交叉開關(guān)分配的時(shí)間;TCS為微片經(jīng)交叉開關(guān)傳輸?shù)臅r(shí)間;TLINK為微片在鏈路傳輸?shù)臅r(shí)間。TCS和TLINK都和數(shù)據(jù)包長度有關(guān)。當(dāng)數(shù)據(jù)包遇到阻塞時(shí)，有：

(5)

(6)

聯(lián)立式(3)、(5)～(6)，可求解出平均服務(wù)時(shí)間Tx,y,dir，再代入式(3)，即可得到數(shù)據(jù)包被堵塞在隊(duì)列內(nèi)的概率εx,y,dir與隊(duì)列長L的關(guān)系。根據(jù)故障粒度閾值δ，即可求出故障粒度，建立的粒度劃分的故障模型如下：

其中：a為發(fā)生細(xì)粒度緩存故障時(shí)的緩存數(shù)目；b為發(fā)生粗粒度緩存故障時(shí)的緩存數(shù)目。

在無故障發(fā)生時(shí)，可用εx,y,dir=f(L)擁塞預(yù)測模型預(yù)測各個(gè)端口將要發(fā)生擁堵的概率。

2 路由器架構(gòu)及容錯原理

本文綜合考慮虛通道動態(tài)分配式路由器發(fā)生粗粒度和細(xì)粒度端口故障的情況，提出了一種虛通道動態(tài)分配式容錯路由器(Fault-tolerantDynamicVirtualChannelrouter,FDVC)。主要原理是根據(jù)提出的故障及擁塞預(yù)測模型，采用鄰端口共享方式實(shí)現(xiàn)對粗粒度端口故障容錯，通過修改控制邏輯指針讀寫電路對細(xì)粒度端口故障容錯，且可在無故障出現(xiàn)時(shí)，預(yù)測端口擁堵情況，提前作出路由決策。

2.1 容錯路由器整體設(shè)計(jì)

FDVC路由器整體架構(gòu)如圖4所示，相比傳統(tǒng)的虛通道動態(tài)分配式路由器，本文增加了故障實(shí)時(shí)檢測與容忍(FaultReal-timeTestandTolerant,FRTT)模塊、鄰端口共享(AdjacentPortSharing,APS)模塊，并修改了讀寫指針電路。故障實(shí)時(shí)檢測與容忍模塊負(fù)責(zé)對虛通道端口故障進(jìn)行實(shí)時(shí)檢測，并對故障粒度進(jìn)行劃分，通知路由器采用不同的容錯方案；鄰端口共享模塊可在本端口發(fā)生故障或擁塞時(shí)提供一個(gè)備份端口，完成粗粒度端口容錯及緩解端口擁塞；通過設(shè)計(jì)指針讀寫電路，可為細(xì)粒度緩存故障提供容錯方案。

圖4 容錯路由器整體架構(gòu)

在實(shí)際應(yīng)用中，對于2D-mesh型網(wǎng)絡(luò)中的路由器，網(wǎng)絡(luò)中間的路由器有5個(gè)端口，邊界路由器有4個(gè)端口，角落路由器有3個(gè)端口，所以對于不同端口數(shù)目的路由器需采用不同的鄰端口共享方案。對于每一種共享方式可用(x,y,z)表示，其中：x、y、z表示端口共享的數(shù)目，當(dāng)x、y、z為1時(shí)，表示該端口不采用共享方式。對于3端口共享方式，可采用如圖5(a)所示的(2,1)共享方式或圖5(b)所示的(3)共享方式。這樣對于5端口路由器，可采用(2,2,1)或(2,3)共享方式，4端口可采用(2,2)共享方式。

2.2 故障實(shí)時(shí)檢測與容忍模塊

故障實(shí)時(shí)檢測與容忍模塊主要由實(shí)時(shí)端口故障檢測(Real-timeBufferTest,RBT)模塊、故障粒度診斷(FaultGranularityDiagnosis,FGD)模塊和端口分配(PortAllocation,PA)模塊組成，其整體結(jié)構(gòu)如圖6所示。

圖5 3端口共享方式

圖6 故障實(shí)時(shí)檢測與容忍模塊

在路由器正常工作時(shí)，實(shí)時(shí)端口故障檢測模塊可實(shí)時(shí)檢測端口中發(fā)生的緩存故障以及控制邏輯故障，其檢測方法結(jié)合文獻(xiàn)[15-16]提出的故障檢測方法，在此不詳細(xì)敘述。故障測試模塊有單獨(dú)的測試時(shí)鐘和測試周期，可在路由器正常工作時(shí)對端口故障進(jìn)行實(shí)時(shí)檢測，并將故障信息發(fā)送給故障粒度診斷模塊，故障信息包括故障端口號、端口故障類型及故障內(nèi)容，若為控制邏輯故障，故障類型為1，故障內(nèi)容為空；若為緩存故障，故障類型為2，故障內(nèi)容為發(fā)生故障的緩沖槽的位置；若無故障發(fā)生，則故障類型為3，故障內(nèi)容為空。當(dāng)故障粒度診斷模塊接收到故障信息后，先判斷故障類型，若為控制邏輯故障則診斷為粗粒度端口故障，若為緩存故障，則根據(jù)預(yù)測的端口流量以及接收到的故障緩沖槽的位置信息，計(jì)算出端口擁塞程度，并與故障粒度閾值作比較，判斷出是粗粒度端口故障還是細(xì)粒度端口故障。對于細(xì)粒度端口故障，直接由故障粒度診斷模塊使能slot_update信號，該信號負(fù)責(zé)更新緩沖槽故障表(slot_fault_table)，用于啟動細(xì)粒度端口故障容錯方案；對于粗粒度端口故障，由故障診斷模塊使能port_update信號，該信號連接至端口選擇模塊，用于啟動粗粒度端口容錯方案。

2.3 鄰端口共享模塊設(shè)計(jì)

當(dāng)發(fā)生粗粒度端口故障時(shí)，若繼續(xù)使用該端口則會造成端口嚴(yán)重堵塞以至于片上網(wǎng)絡(luò)功能失效，為此，本文設(shè)計(jì)了APS模塊來避免這種情況的發(fā)生。相鄰兩端口的APS結(jié)構(gòu)如圖7所示。

圖7 鄰端口共享模塊結(jié)構(gòu)

APS主要由三路數(shù)據(jù)選擇器和數(shù)據(jù)解碼器構(gòu)成，第一路數(shù)據(jù)選擇器用于選擇輸入通道，第二路數(shù)據(jù)解碼器和第三路數(shù)據(jù)選擇器用于選擇數(shù)據(jù)輸入端口。相比文獻(xiàn)[17]提出的資源減弱共享(DecoupledResourceSharing,DRS)結(jié)構(gòu)，APS結(jié)構(gòu)能有效阻斷數(shù)據(jù)微片進(jìn)入故障端口。

圖7中列出了APS模塊中幾個(gè)關(guān)鍵的進(jìn)出信號，分別是Clock、Data、VC_ID和VC_Full信號，Clock信號用于同步通道數(shù)據(jù)發(fā)送，Data為微片數(shù)據(jù)，VC_ID為給數(shù)據(jù)包分配的虛通道ID號，VC_Full信號為下游路由器給上層路由器發(fā)送的緩沖滿信號。在默認(rèn)狀態(tài)下，各個(gè)輸入通道都選擇各自的輸入端口，如圖7所示，與端口分配模塊相連的信號Channel_sel、Port_sel1和Port_sel2默認(rèn)狀態(tài)下都為0。當(dāng)故障粒度診斷模塊發(fā)出的信號port_update有效時(shí)，端口分配模塊使能對APS模塊的控制信號，從而為相應(yīng)的通道分配無故障的輸入端口。

2.4 虛通道容錯控制邏輯設(shè)計(jì)

對于虛通道動態(tài)分配式路由器，最關(guān)鍵的是控制邏輯的設(shè)計(jì)，控制邏輯主要有三種實(shí)現(xiàn)方式：基于鏈接表實(shí)現(xiàn)[7-8]、基于映射表實(shí)現(xiàn)[9]和基于快速讀寫電路實(shí)現(xiàn)[4]，一般最常見的是基于鏈接表的實(shí)現(xiàn)方式。為保證路由器在發(fā)生細(xì)粒度端口故障時(shí)，仍能充分利用剩余緩存資源，本文結(jié)合后兩種實(shí)現(xiàn)方式的優(yōu)缺點(diǎn)，提出一種故障表和快速讀寫電路相結(jié)合的虛通道容錯控制邏輯結(jié)構(gòu)。

1)寫指針容錯生成電路

控制邏輯中的寫指針容錯生成電路如圖8所示。主要由緩沖槽狀態(tài)表、緩沖槽故障表以及寫指針生成電路構(gòu)成，緩沖槽狀態(tài)表中的0表示緩沖槽空，1表示有數(shù)據(jù)微片；緩沖槽故障表中的0表示緩沖槽無故障，1表示緩沖槽經(jīng)故障測試后存在故障，與其相連的slot_update信號負(fù)責(zé)對緩沖槽故障表進(jìn)行更新。

假設(shè)某一時(shí)刻的寫指針為1，并且緩沖槽1位置上的狀態(tài)為0，數(shù)據(jù)微片在時(shí)鐘信號作用下進(jìn)入緩沖槽1，此時(shí)緩沖槽狀態(tài)表位置1上的狀態(tài)信號立即由0變?yōu)?。如圖8所示，這時(shí)，由于數(shù)據(jù)選擇器mul1的輸出選擇信號由mul2的輸出決定，其值為當(dāng)前寫指針緩沖槽故障表上的值與緩沖槽狀態(tài)表上的值相或后變?yōu)?。則mul1選擇mul3的輸出作為其有效輸入，mul3的輸出選擇信號由mul4的輸出信號決定，mul4查詢位置為指針加1后的緩沖槽狀態(tài)，即第2個(gè)緩沖槽位置狀態(tài)，發(fā)現(xiàn)雖然其空閑但已發(fā)生故障，經(jīng)由一個(gè)或門后mul3選擇信號變?yōu)?。則mul3選擇mul5的輸出作為其有效輸入，mul5的輸出選擇信號由mul6的輸出信號決定，mul6查詢位置為指針加2后的緩沖槽狀態(tài)，即第3個(gè)緩沖槽位置狀態(tài)，無故障，輸出為0，則mul5的輸出變?yōu)?，即mul1的輸出變?yōu)?。則在下一時(shí)鐘到來時(shí)，寫指針變?yōu)?，完成了寫指針電路的快速生成以及細(xì)粒度端口容錯。

2)讀指針容錯生成電路

讀指針容錯生成電路如圖9所示。輸入到選擇器中的信號是由緩沖槽故障表信號取非后與緩沖槽狀態(tài)信號相與后得到，緩沖槽表的原理與寫指針生成電路類似。

圖8 寫指針生成電路

圖9 讀指針生成電路

假設(shè)當(dāng)前的讀指針(ReadPointer,RP)為1，并且緩沖槽狀態(tài)表1位置上值為1，對于圖中數(shù)據(jù)選擇器mul1，其輸出選擇信號由mul2的輸出信號決定，mul2查詢讀指針加1位置上的緩沖槽狀態(tài)，即槽2上的緩沖槽狀態(tài)，發(fā)現(xiàn)其雖然空閑但是存在故障，故障信號經(jīng)取非操作后與狀態(tài)信號相與為0，則mul2輸出為0，mul1選擇mul3的輸出信號作為其輸出信號，mul3輸出選擇信號由mul4的輸出信號決定，mul4查詢槽位置3上有數(shù)據(jù)微片且無故障，輸出為1，mul3選擇(RP+2)作為輸出，即mul1輸出為(RP+2)=3。在時(shí)鐘信號到來時(shí)，讀取槽1上的數(shù)據(jù)微片，并且讀指針變?yōu)?，用于讀取下一個(gè)數(shù)據(jù)微片。

3 容錯與擁塞緩解方案

虛通道動態(tài)分配式路由器端口包含最易發(fā)生故障的緩存單元以及復(fù)雜的控制邏輯，是最易發(fā)生故障和擁堵的部位，本文結(jié)合第2章提出的路由器架構(gòu)針對不同的情況提出相應(yīng)的解決方案。

3.1 端口故障粒度劃分的容錯方案

基于端口粒度劃分的容錯方案流程如圖10所示。故障實(shí)時(shí)檢測單元RBT在一定的檢測周期內(nèi)實(shí)時(shí)掌握端口的狀態(tài)，當(dāng)在某一時(shí)刻檢測到端口發(fā)生故障，將故障信息發(fā)送給故障粒度診斷模塊FGD，故障信息包括故障類型、故障端口以及故障內(nèi)容。FGD根據(jù)故障信息判斷端口故障的粒度，若為緩存故障，則根據(jù)故障模型判斷出緩存故障粒度，對于細(xì)粒度緩存故障，通過slot_update信號對緩存故障表進(jìn)行更新，由容錯讀寫指針電路對其進(jìn)行容錯，對于粗粒度緩存故障以及控制邏輯故障，F(xiàn)GD使能slot_update信號發(fā)送給端口分配單元，由端口分配模塊PA為輸入通道分配無故障輸入端口，實(shí)現(xiàn)基于端口故障粒度劃分的容錯方案。

圖10 容錯方案

3.2 端口擁塞緩解方案

路由器一般都用信貸(Credit)方式實(shí)現(xiàn)流控，即當(dāng)下游路由器某端口緩存發(fā)生擁堵或緩存滿時(shí)，通知上游路由器停止往該端口發(fā)送數(shù)據(jù)微片，直到該端口存在可用緩存才通知上游路由器繼續(xù)發(fā)送數(shù)據(jù)微片，這種方式會帶來較大的延時(shí)。結(jié)合本文提出的擁塞預(yù)測模型，本文提出的FDVC路由器能動態(tài)感知全局網(wǎng)絡(luò)流量，實(shí)時(shí)預(yù)測各個(gè)端口的擁塞程度，選擇擁塞程度低的數(shù)據(jù)端口路由數(shù)據(jù)包。當(dāng)路由器無故障發(fā)生時(shí)，F(xiàn)GD模塊根據(jù)接收到的流量信息以及擁塞預(yù)測模型，計(jì)算相鄰端口的擁塞概率，使能port_update信號，由PA模塊為數(shù)據(jù)通道分配輸入端口，在一定程度上能有效緩解網(wǎng)絡(luò)擁堵。

4 實(shí)驗(yàn)結(jié)果

在容錯路由器性能評估方面，本文采用修改后的周期精確的片上網(wǎng)絡(luò)仿真器，搭建8×8的2D-mesh拓?fù)浣Y(jié)構(gòu)，端口緩存深度為32個(gè)數(shù)據(jù)槽，路由算法采用XY維序路由方式；在面積開銷方面，本文采用55nm工藝標(biāo)準(zhǔn)單元庫對本文所提出的路由器進(jìn)行綜合。

4.1 性能評估

本文選取三種路由器作為性能比較對象，第一種是基準(zhǔn)虛通道靜態(tài)分配路由器(BaselineRouter)，每個(gè)端口設(shè)置4個(gè)虛通道，每個(gè)虛通道有8個(gè)緩沖槽(緩沖槽總數(shù)與動態(tài)分配式保持一致)；第二種是借鑒文獻(xiàn)[4]提出的動態(tài)分配方式設(shè)計(jì)的高性能路由器(DynamicAllocatedVirtualChannelrouter,DAVC)，不采取任何容錯方案；第三種是在DAVC路由器端口設(shè)置文獻(xiàn)[17]提出的減弱資源共享模塊構(gòu)造的路由器(DecoupledResourceSharingrouter,DRS)。實(shí)驗(yàn)方案為在不同的故障模式下，測試采用包括本文提出的FDVC路由器在內(nèi)的四種路由器的片上互聯(lián)網(wǎng)絡(luò)的平均延時(shí)和吞吐率。延時(shí)指數(shù)據(jù)包包頭從進(jìn)入網(wǎng)絡(luò)到包尾離開網(wǎng)絡(luò)的平均時(shí)間差，吞吐率指單位時(shí)間內(nèi)網(wǎng)絡(luò)處理的數(shù)據(jù)量，它們是衡量片上網(wǎng)絡(luò)性能的重要指標(biāo)。設(shè)置FDVC路由器的故障粒度閾值δ為0.8。分別設(shè)置3種故障模式：1)只存在粗粒度端口故障；2)只存在細(xì)粒度端口故障；3)粗粒度端口故障和細(xì)粒度端口故障共存。每種模式設(shè)定的故障數(shù)目以及位置固定，采用均勻隨機(jī)模式(uniform)，在三種故障模式下進(jìn)行性能測試。具體實(shí)驗(yàn)結(jié)果如下：

圖11為在粗粒度端口故障模式下采用四種不同路由器的網(wǎng)絡(luò)的延時(shí)和吞吐率對比。對于采用基準(zhǔn)虛通道路由器的網(wǎng)絡(luò)，在粗粒度端口故障模式下，其延時(shí)急劇增大，吞吐率也較低，在注入率為0.25左右便出現(xiàn)嚴(yán)重的網(wǎng)絡(luò)堵塞，系統(tǒng)接近飽和。而DAVC因采用動態(tài)分配方式，在故障條件下的性能一定程度上優(yōu)于普通路由器，但在注入率為0.3左右時(shí)其延時(shí)也會急劇增大，吞吐率較小。而DRS與FDVC路由器性能表現(xiàn)相似，在注入率接近于0.45時(shí)才出現(xiàn)一定的延時(shí)急劇增加，容錯能力較好，吞吐率較高，這是因?yàn)樵谶@兩種路由器端口增加了容錯模塊，能夠容忍一定的粗粒度端口故障。

圖12為在細(xì)粒度端口故障模式下的網(wǎng)絡(luò)的延時(shí)與吞吐率對比。在細(xì)粒度端口故障模式下，采用基準(zhǔn)虛通道靜態(tài)分配路由器的網(wǎng)絡(luò)，在注入率為0.3左右時(shí)其延時(shí)也會急劇增加，吞吐率較小，DRS路由器雖然采用了一定的容錯方案，但在出現(xiàn)細(xì)粒度緩存故障時(shí)未提供較好的容錯方案，其性能略優(yōu)于DAVC路由器。而對于本文提出的FDVC路由器，因設(shè)計(jì)了虛通道容錯控制邏輯，性能表現(xiàn)優(yōu)良，在注入率為0.4左右才出現(xiàn)延時(shí)大幅增加，吞吐率改善明顯。

圖13分別為在混合故障模式下的網(wǎng)絡(luò)的延時(shí)與吞吐率對比。在混合故障模式下，對于采用基準(zhǔn)虛通道靜態(tài)分配路由器的網(wǎng)絡(luò)，相比前兩種模式，在相同注入率下，其延時(shí)更長，且延時(shí)增加得更快，吞吐率較低。而DRS路由器因能容忍一定的粗粒度端口故障，在相同的注入率下，其延時(shí)較普通的DAVC路由器較小，吞吐率也比DAVC高，但因無法容忍細(xì)粒度端口故障，性能改善不大。對于本文提出的FDVC路由器，在混合故障模式下其性能也有一些損失，這是因?yàn)樵诖至６榷丝诠收洗嬖跁r(shí)，有些相鄰?fù)ǖ佬枰靡粋€(gè)端口分時(shí)路由數(shù)據(jù)微片，也會帶來一定的延時(shí)，但是相比其他三種路由器性能改善較為明顯，在注入率為0.5左右時(shí)，其吞吐率相比普通的DAVC路由器提高了37.12%。

圖11 粗粒度端口故障模式性能對比

圖12 細(xì)粒度端口故障模式性能對比

4.2 面積開銷與評估

本文對不采取任何容錯措施的虛通道動態(tài)分配式容錯路由器DAVC、僅在DAVC端口設(shè)置資源減弱共享模塊的DRS路由器以及本文的FDVC路由器進(jìn)行綜合，DRS和FDVC共享方案均設(shè)置為(2,2,1)，并提出性能提升與面積開銷比(RatioofPerformanceimprovementandAreaoverhead,RPA)這一概念，其代表路由器性能提升與面積開銷的比值。性能提升指在各種故障模式下各路由器相對DAVC路由器的飽和吞吐率改善百分比，面積開銷指路由器相對DAVC路由器增加的面積百分比，一般RPA值越大,容錯性能就越好，實(shí)驗(yàn)結(jié)果如表1所示，表1中RPA1、RPA2、RPA3分別指在細(xì)粒度故障、粗粒度故障和混合故障模式下的平均性能提升與面積開銷比。

圖13 混合故障模式下性能對比

路由器面積/μm2RPA1RPA2RPA3DAVC61387．140．000．000．00DRS64528．570．743．982．78FDVC74843．201．341．451．93

從表1中可以看出，在三種故障模式下，F(xiàn)DVC路由器均能保持較好的性能提升與面積開銷比，而對于DRS路由器而言雖然面積開銷小，但是在細(xì)粒度故障模式下其性能提升與面積開銷比并不大，因此本文提出的FDVC路由器的面積開銷在一定程度上是可以容忍的。

5 結(jié)語

本文選取高性能虛通道動態(tài)分配式路由器容錯設(shè)計(jì)作為研究內(nèi)容，結(jié)合片上網(wǎng)絡(luò)性能分析模型與路由器端口故障發(fā)生方式，建立了針對端口故障粒度劃分的故障與擁塞預(yù)測模型，在此基礎(chǔ)上設(shè)計(jì)路由器故障實(shí)時(shí)檢測與容忍模塊，鄰端口共享模塊以及容錯讀寫指針生成邏輯電路。實(shí)驗(yàn)結(jié)果表明該容錯路由器在各種端口故障模式下，均能保持良好的性能且具有容錯特性。本文的容錯研究尚且停留在端口故障部分，對于高性能路由器的其他模塊的容錯研究是未來的一個(gè)重要研究方向。

)

[1] 周端,彭景,張劍賢,等.低功耗片上網(wǎng)絡(luò)路由器設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用,2011,31(10):2621-2624.(ZHOUD,PENGJ,ZHANGJX,etal.Low-powerNoCrouterdesign[J].JournalofComputerApplications, 2011, 31(10): 2621-2624.)

[2]SEITANIDISI,PSARRASA,CHRYSANTHOUK,etal.ElastiStore:flexibleelasticbufferingforvirtual-channel-basednetworksonchip[J].IEEETransactionsonVeryLargeScaleIntegrationSystems, 2015, 23(12): 3015-3028.

[3] 鄭小富,顧華璽,楊銀堂,等.基于提前分配路徑的低時(shí)延片上路由器結(jié)構(gòu)[J].電子與信息學(xué)報(bào),2013,35(2):341-348.(ZHENGXF,GUHX,YANGYT,etal.Pre-allocatedpathbasedlowlatencyrouterarchitecturefornetwork-on-chip[J].JournalofElectronics&InformationTechnology, 2013, 35(2): 341-348.)

[4]OVEIS-GHARANM,KHANGN.EfficientdynamicvirtualchannelorganizationandarchitectureforNoCsystems[J].IEEETransactionsonVeryLargeScaleIntegrationSystems, 2016, 24(2): 465-478.

[5]LIC,YANGM,AMPADUP.Anenergy-efficientNoCrouterwithadaptivefault-toleranceusingchannelslicingandon-demandTMR[J].IEEETransactionsonEmergingTopicsinComputing, 2016,PP(99):1-1.

[6]WANGL,MAS,WANGZY.AhighperformancereliableNoCrouter[EB/OL]. [2016- 10- 19].http://www.aspdac.com/aspdac2016/technical_program/pdf/8A-1.pdf.

[7]LAIM,GAOL,SHIW,etal.Escapingfromblocking:adynamicvirtualchannelforpipelinedrouters[C]//CISIS2008:Proceedingsofthe2008InternationalConferenceonComplex,IntelligentandSoftwareIntensiveSystems.Piscataway,NJ:IEEE, 2008: 795-800.

[8]EVRIPIDOUM,NICOPOULOSC,SOTERIOUV,etal.Virtualizingvirtualchannelsforincreasednetwork-on-chiprobustnessandupgradeability[C]//ISVLSI’12:Proceedingsofthe2012IEEEComputerSocietyAnnualSymposiumonVLSI.Washington,DC:IEEEComputerSociety, 2012: 21-26.

[9]NICOPOULOSCA,PARKD,KIMJ,etal.ViChaR:adynamicvirtualchannelregulatorfornetwork-on-chiprouters[C]//Proceedingsofthe2006 39thAnnualIEEE/ACMInternationalSymposiumonMicroarchitecture.Piscataway,NJ:IEEE, 2006: 333-346.

[10]XUY,ZHAOB,ZHANGYT,etal.Simplevirtualchannelallocationforhigh-throughputandhigh-frequencyon-chiprouters[C]//HPCA16:Proceedingsofthe16thInternationalSymposiumonHigh-PerformanceComputerArchitecture.Piscataway,NJ:IEEE, 2010: 1-11.

[11] 姚磊,蔡覺平,李贊,等.基于內(nèi)建自測技術(shù)的Mesh結(jié)構(gòu)NoC無虛通道容錯路由算法[J].電子學(xué)報(bào),2012,40(5):983-989.(YAOL,CAIJP,LIZ,etal.Afault-tolerantroutingalgorithmbasedonBISTfor2D-meshnetwork-on-chipwithoutusingvirtualchannels[J].ActaElectronicaSinica, 2012, 40(5): 983-989.)

[12]LIUJX,HARKINJ,LIYH,etal.Fault-tolerantnetworks-on-chiproutingwithcoarseandfine-grainedlook-ahead[J].IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems, 2016, 35(2): 260-273.

[13]DEORIOA,FICKD,BERTACCOV,etal.AreliableroutingarchitectureandalgorithmforNoCs[J].IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems, 2012, 31(5): 726-739.

[14]POLURIP,LOURIA.Shield:areliablenetwork-on-chiprouterarchitectureforchipmultiprocessors[J].IEEETransactionsonParallelandDistributedSystems, 2016, 27(10): 3058-3070

[15]GHOSHALB,MANNAK,CHATTOPADHYAYS,etal.In-fieldtestforpermanentfaultsinFIFObuffersofNoCrouters[J].IEEETransactionsonVeryLargeScaleIntegrationSystems, 2016, 24(1): 393-397.

[16]VANDEGOORA,SCHANSTRAI,ZORIANY.BISTforring-addressSRAM-typeFIFOs[C]//Proceedingsofthe1994IEEEInternationalWorkshoponMemoryTechnology,Design,andTesting.Piscataway,NJ:IEEE, 1994: 112-118.

[17]VALINATAJM,SHAHIRIM.Alow-cost,fault-tolerantandhigh-performancerouterarchitectureforon-chipnetworks[J].Microprocessors&Microsystems, 2016, 45(PA): 151-163.

[18] 歐陽一鳴,陳義軍,梁華國,等.一種故障通道隔離的低開銷容錯路由器設(shè)計(jì)[J].電子學(xué)報(bào),2014,42(11):2142-2149.(OUYANGYM,CHENYJ,LIANGHG,etal.Designofalow-overheadfaultchannelisolatedfault-tolerantrouter[J].ActaElectronicaSinica, 2014, 42(11): 2142-2149.)

[19] 王堅(jiān),李玉柏,蔣勇男.片上網(wǎng)絡(luò)通信性能分析建模與緩存分配優(yōu)化算法[J].電子與信息學(xué)報(bào),2009,31(5):1059-1062.(WANGJ,LIYB,JIANGYN.Communicationperformanceanalyticalmodelandbufferallocationoptimizingalgorithmfornetwork-on-chip[J].JournalofElectronics&InformationTechnology, 2009, 31(5): 1059-1062.)

[20]LANGARM,BOURGUIBAR,MOUINEJ.Virtualchannelrouterarchitecturefornetworkonchipwithadaptiveinter-portbufferssharing[C]//Proceedingsofthe2016 13thInternationalMulti-ConferenceonSystems,Signals&Devices.Piscataway,NJ:IEEE, 2016: 691-694.

HANG Yanxi, born in 1992, M. S. candidate. His research interests include testing and validation of system-on-chip, design of interconnection structure for network-on-chip, fault-tolerant design of network-on-chip.

XU Jinfu, born in 1965, Ph. D., associate professor. His research interests include design of system-on-chip and micro-processor, design of embedded system, design of special secure chip, reconfigurable computing, design of trusted system-on-chip.

NAN Longmei, born in 1982, Ph. D., lecturer, His research interests include design of large scale integrated circuit, design of special secure chip, design of interconnection structure for network-on-chip.

GUO Pengfei, born in 1987, M. S. candidate, lecturer. His research interests include testing and verification of integrated circuit, design of trusted system-on-chip.

Design of fault-tolerant router for virtual channel dynamic allocation based on port fault granularity partition

HANG Yanxi1*, XU Jinfu1, NAN Longmei2, GUO Pengfei1

(1.InformationEngineeringUniversity,ZhengzhouHenan450001,China; 2.StateKeyLaboratoryofASICandSystem(FudanUniversity),Shanghai201203,China)

High reliability is an important issue in the development of high performance network-on-chip router. Concerning the problem that the ports of the router whose virtual channel is dynamic allocated are prone to fail at present, a design of fault-tolerant router based on port fault granularity partition was proposed. Firstly, a fault and congestion model for ports based on granularity partition was established combining with the specialty of the virtual channel dynamic allocation and faults’ characteristics. Then, the related fault-tolerant circuit was designed on the basis of the model combining with the real-time fault detection methods, an adjacent port sharing module was added and a fault-tolerant read/write point control logic circuit was designed. Finally, a fault-tolerant and congestion mitigation scheme was put forward based on the design. The experiments shows that the proposed router can maintain fault tolerant properties under various port failure modes with little performance degradation, and it has high ratio of performance improvement and area overhead.

Network-on-Chip (NoC); router; fault-tolerant; port fault

2016- 11- 28;

2017- 01- 13。

杭彥希(1992—)，男，江蘇無錫人，碩士研究生，主要研究方向：片上系統(tǒng)測試與驗(yàn)證、片上網(wǎng)絡(luò)互連結(jié)構(gòu)設(shè)計(jì)、片上網(wǎng)絡(luò)容錯設(shè)計(jì)； 徐金甫(1965—)，男，河南鄭州人，副教授，博士，主要研究方向：片上系統(tǒng)與微處理器設(shè)計(jì)、嵌入式系統(tǒng)設(shè)計(jì)、安全專用芯片設(shè)計(jì)、可重構(gòu)計(jì)算、可信片上系統(tǒng)設(shè)計(jì)； 南龍梅(1982—)，女，陜西渭南人，講師，博士，主要研究方向：大規(guī)模集成電路設(shè)計(jì)、安全專用芯片設(shè)計(jì)、片上網(wǎng)絡(luò)互連結(jié)構(gòu)設(shè)計(jì)； 郭朋飛(1987—)，男，河南漯河人，講師，碩士，主要研究方向：集成電路測試與驗(yàn)證、可信片上系統(tǒng)設(shè)計(jì)。

1001- 9081(2017)06- 1560- 09

10.11772/j.issn.1001- 9081.2017.06.1560

TP

A