端口故障粒度劃分的虛通道動態分配式容錯路由器設計

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

(1.信息工程大學，鄭州 450001； 2.專用集成電路與系統國家重點實驗室(復旦大學),上海 201203)

端口故障粒度劃分的虛通道動態分配式容錯路由器設計

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

(1.信息工程大學，鄭州 450001； 2.專用集成電路與系統國家重點實驗室(復旦大學),上海 201203)

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

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

片上網絡；路由器；容錯；端口故障

0 引言

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

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

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

1 故障及擁塞預測模型建立

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

1.1 虛通道動態分配式路由器結構

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

1.2 故障粒度劃分

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

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

圖1 虛通道動態分配式路由器結構

圖2 路由器端口

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

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

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

圖3 端口故障粒度劃分

1.3 粒度劃分的故障及擁塞預測模型

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

1.3.1 排隊論

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

(1)

s.t.ρ=λ/u

其中：Pn表示隊列中有n個顧客等待的概率；ρ為隊列的利用率，其值為顧客到達速率λ與服務速率μ的比值。

1.3.2 模型假設

構建一個2D-mesh型大小為m×n的片上網絡拓撲結構，借鑒文獻[4]提出的虛通道動態分配方式，所建模型基于如下假設：

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

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

3)路由器本地輸入端口上的緩存為無限大，因為處理單元(Processing Element, PE)內有存儲器，且數據包一旦到達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為節點(x,y)處dir端口輸入通道的數據注入率;ux,y,dir為節點(x,y)處dir端口輸入通道的服務速率;Tx,y,dir為節點(x,y)處dir端口輸入通道的平均服務時間。

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

(3)

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

為了計算出εx,y,dir，還需要計算出服務時間Tx,y,dir，服務時間指數據包的頭微片進入路由節點到尾微片離開路由節點的時間。在無阻塞發生的情況下，有：

Tx,y,dir=TH+W×TM

(4)

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

其中：TRC為完成對頭微片的路由計算的時間；TVA為頭微片發出虛通道分配請求及仲裁成功的時間，若路由器控制邏輯固定，則TH為定值；TM為轉發單個體微片所需的時間；TST為交叉開關分配的時間;TCS為微片經交叉開關傳輸的時間;TLINK為微片在鏈路傳輸的時間。TCS和TLINK都和數據包長度有關。當數據包遇到阻塞時，有：

(5)

(6)

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

其中：a為發生細粒度緩存故障時的緩存數目；b為發生粗粒度緩存故障時的緩存數目。

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

2 路由器架構及容錯原理

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

2.1 容錯路由器整體設計

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

圖4 容錯路由器整體架構

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

2.2 故障實時檢測與容忍模塊

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

圖5 3端口共享方式

圖6 故障實時檢測與容忍模塊

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

2.3 鄰端口共享模塊設計

當發生粗粒度端口故障時，若繼續使用該端口則會造成端口嚴重堵塞以至于片上網絡功能失效，為此，本文設計了APS模塊來避免這種情況的發生。相鄰兩端口的APS結構如圖7所示。

圖7 鄰端口共享模塊結構

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

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

2.4 虛通道容錯控制邏輯設計

對于虛通道動態分配式路由器，最關鍵的是控制邏輯的設計，控制邏輯主要有三種實現方式：基于鏈接表實現[7-8]、基于映射表實現[9]和基于快速讀寫電路實現[4]，一般最常見的是基于鏈接表的實現方式。為保證路由器在發生細粒度端口故障時，仍能充分利用剩余緩存資源，本文結合后兩種實現方式的優缺點，提出一種故障表和快速讀寫電路相結合的虛通道容錯控制邏輯結構。

1)寫指針容錯生成電路

控制邏輯中的寫指針容錯生成電路如圖8所示。主要由緩沖槽狀態表、緩沖槽故障表以及寫指針生成電路構成，緩沖槽狀態表中的0表示緩沖槽空，1表示有數據微片；緩沖槽故障表中的0表示緩沖槽無故障，1表示緩沖槽經故障測試后存在故障，與其相連的slot_update信號負責對緩沖槽故障表進行更新。

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

2)讀指針容錯生成電路

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

圖8 寫指針生成電路

圖9 讀指針生成電路

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

3 容錯與擁塞緩解方案

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

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

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

圖10 容錯方案

3.2 端口擁塞緩解方案

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

4 實驗結果

在容錯路由器性能評估方面，本文采用修改后的周期精確的片上網絡仿真器，搭建8×8的2D-mesh拓撲結構，端口緩存深度為32個數據槽，路由算法采用XY維序路由方式；在面積開銷方面，本文采用55nm工藝標準單元庫對本文所提出的路由器進行綜合。

4.1 性能評估

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

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

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

圖13分別為在混合故障模式下的網絡的延時與吞吐率對比。在混合故障模式下，對于采用基準虛通道靜態分配路由器的網絡，相比前兩種模式，在相同注入率下，其延時更長，且延時增加得更快，吞吐率較低。而DRS路由器因能容忍一定的粗粒度端口故障，在相同的注入率下，其延時較普通的DAVC路由器較小，吞吐率也比DAVC高，但因無法容忍細粒度端口故障，性能改善不大。對于本文提出的FDVC路由器，在混合故障模式下其性能也有一些損失，這是因為在粗粒度端口故障存在時，有些相鄰通道需要用一個端口分時路由數據微片，也會帶來一定的延時，但是相比其他三種路由器性能改善較為明顯，在注入率為0.5左右時，其吞吐率相比普通的DAVC路由器提高了37.12%。

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

圖12 細粒度端口故障模式性能對比

4.2 面積開銷與評估

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

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

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

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

5 結語

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

)

[1] 周端,彭景,張劍賢,等.低功耗片上網絡路由器設計[J].計算機應用,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] 鄭小富,顧華璽,楊銀堂,等.基于提前分配路徑的低時延片上路由器結構[J].電子與信息學報,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] 姚磊,蔡覺平,李贊,等.基于內建自測技術的Mesh結構NoC無虛通道容錯路由算法[J].電子學報,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] 歐陽一鳴,陳義軍,梁華國,等.一種故障通道隔離的低開銷容錯路由器設計[J].電子學報,2014,42(11):2142-2149.(OUYANGYM,CHENYJ,LIANGHG,etal.Designofalow-overheadfaultchannelisolatedfault-tolerantrouter[J].ActaElectronicaSinica, 2014, 42(11): 2142-2149.)

[19] 王堅,李玉柏,蔣勇男.片上網絡通信性能分析建模與緩存分配優化算法[J].電子與信息學報,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—)，男，江蘇無錫人，碩士研究生，主要研究方向：片上系統測試與驗證、片上網絡互連結構設計、片上網絡容錯設計； 徐金甫(1965—)，男，河南鄭州人，副教授，博士，主要研究方向：片上系統與微處理器設計、嵌入式系統設計、安全專用芯片設計、可重構計算、可信片上系統設計； 南龍梅(1982—)，女，陜西渭南人，講師，博士，主要研究方向：大規模集成電路設計、安全專用芯片設計、片上網絡互連結構設計； 郭朋飛(1987—)，男，河南漯河人，講師，碩士，主要研究方向：集成電路測試與驗證、可信片上系統設計。

1001- 9081(2017)06- 1560- 09

10.11772/j.issn.1001- 9081.2017.06.1560

TP

A