基于HERMESNoC的片上網(wǎng)絡容錯方法研究*

方亮亮，胡慶生

(東南大學射頻與光電集成電路研究所， 南京210096)

隨著集成電路工藝的不斷進步，系統(tǒng)芯片的規(guī)模不斷增大，微小的芯片上包含上億支晶體管，使得基于片上系統(tǒng)(SoC)的芯片設計將會非常復雜，而且傳統(tǒng)的SoC體系結(jié)構及其相應的設計方法在多知識產(chǎn)權(IP)核的超復雜系統(tǒng)中遇到了技術瓶頸。從2000年開始，業(yè)界提出了一種全新的系統(tǒng)芯片設計模型—片上網(wǎng)絡(NoC， Network on Chip)， NoC將計算機網(wǎng)絡技術移植到芯片設計中來，徹底解決多IP模塊體系結(jié)構中的問題，是更高層次、更大規(guī)模的片上系統(tǒng)，同時可提供包括帶寬、延遲、可靠性等在內(nèi)的服務質(zhì)量。

1 片上網(wǎng)絡的容錯機制

一個典型的NoC組成如圖1所示，主要由交換器(Switch)、鏈 路(Link)和 網(wǎng) 絡接 口(NI， Network Interface)組成，其中網(wǎng)絡接口負責IP核與網(wǎng)絡的連接，協(xié)調(diào)向/從IP核傳輸包，交換器和鏈路則實現(xiàn)IP核的連接和通信。

圖1 一個典型的NoC組成

在NoC提供的服務質(zhì)量中，通信的可靠性是最重要的方面之一。隨著特征尺寸的縮小，芯片的供電電壓和器件閾值電壓減小，互連線對串擾、耦合噪聲、電磁干擾、軟錯誤和工藝不穩(wěn)定等深亞微米噪聲源變得日益敏感，從而降低了通信的可靠性。通常，由串擾、耦合噪聲、電磁干擾等引起的故障，具有隨機性和瞬時性，多發(fā)生在鏈路和網(wǎng)絡接口處。而由于交換節(jié)點失效、鏈路失效等引起的故障，一旦發(fā)生，就會一直存在，具有永久性，這時需要為信號重新選擇路由，繞過出錯的交換器和鏈路。

對于串擾、耦合等引起的隨機性故障，雖然在設計階段不能完全避免或消除，但通過采用容錯機制提高通信的可靠性，可以盡量減小這類故障對系統(tǒng)性能的影響，不僅如此，容錯機制還可以在很大程度上降低芯片的測試和驗證成本。隨著NoC研究的深入并逐步走向?qū)嶋H應用，國際上已對NoC的容錯設計給予了越來越多的關注。

美國Stanford大學的Srinivasan Murali等人提出的端到端(E-E， End-End)、交換到交換(S-S， Switch-Switch)以及兩者結(jié)合的流量控制機制[1]，用糾錯碼和檢錯碼分別實現(xiàn)前向糾錯(FEC)和檢錯重傳(ARQ)，并分析了功耗-性能-可靠性的折衷問題。

德國Paderborn大學和奧地利Innsbruck大學于2007年提出的一種瞬時故障的容錯機制[2]，該機制在包傳輸協(xié)議的端到端請求重傳中加入了包集的概念，通過應答信號ack提高發(fā)送端的流水性，處理數(shù)據(jù)包出錯或丟失。

M.Pirretti等人則采用隨機通信機制容錯，提出N-冗余隨機走動算法[3]。該算法中只在第一跳采用泛洪機制，數(shù)據(jù)包的拷貝數(shù)量N是事先定義好的。算法關鍵在于N的確定，文中利用Markov鏈進行隨機走動理論的推導。

本文重點研究在HERMESNoC平臺上如何實現(xiàn)有效的容錯機制，并分析實現(xiàn)的各種容錯機制的面積、延遲和功耗開銷。

1.1 HERMESNoC簡介

HERMES是巴西PUCRS大學研究開發(fā)的基于包交換的NoC平臺，可以實現(xiàn)不同的拓撲結(jié)構、緩沖器深度和路由算法。通過采用蟲孔交換機制和XY路由算法， HERMES可實現(xiàn)OSI的低三層參考模型：在物理層實現(xiàn)交換器的物理連接接口；鏈路層定義交換器間的數(shù)據(jù)傳輸協(xié)議；交換操作則是在網(wǎng)絡層實現(xiàn)的。

圖2所示為一個3×3的HERMES結(jié)構框圖，它由1個RS232串口Serial， 4個RISC處理器R8， 4個容量為1k字的Memory以及9個交換器Switch組成。Serial數(shù)據(jù)打包后經(jīng)過交換器與4個R8處理器及4個Memory IP核通訊。交換器是HERMES的主要模塊，它由交換控制單元(Control)和5個I/O端口組成，交換控制單元負責將接收的數(shù)據(jù)傳送到正確的輸出信道， 5個端口中的本地端口通過網(wǎng)路接口(NI)與IP核通訊，其余端口分別在東南西北四個方向與相鄰交換器通訊。每個端口均包含一個緩沖器(Buffer)。圖3為HERMESNoC的交換器結(jié)構。

圖2 3×3網(wǎng)格型HERMES NoC

圖3 HERMESNoC中的交換器

1.2 基于HERMES的容錯機制設計

基于HERMESNoC，本文研究了兩種容錯機制：端到端(E-E)和交換到交換(S-S)。所謂E-E就是差錯控制只發(fā)生在NI處，中間的路由節(jié)點僅僅負責數(shù)據(jù)包的轉(zhuǎn)發(fā)，不進行差錯控制。而S-S則是在路由的每個節(jié)點上都進行差錯控制，其結(jié)果是能夠更好地保證數(shù)據(jù)的正確性，代價也相對較高。圖4為E-E型容錯機制，可以看到，差錯控制是通過在交換器的本地接口處增加了一個編碼器和解碼器實現(xiàn)的。

圖4 E-E容錯機制

本文對S-S型容錯設計了兩種方式，一種為面積節(jié)省型，另一種為低延遲型，如圖5 和圖6所示。圖5中，在每個交換節(jié)點四個方向的輸入、輸出接口上，均添加了一個解碼器和編碼器。這樣，數(shù)據(jù)從IP核發(fā)出后，每到達一個交換器，就先進行解碼，再進行交換。交換之后，若需要繼續(xù)轉(zhuǎn)發(fā)，則重新編碼；否則，通過本地接口直接送達目的地。這種方式下，在鏈路中傳輸?shù)臄?shù)據(jù)是經(jīng)過編碼后的數(shù)據(jù)，由于加入了校驗位的緣故，這些數(shù)據(jù)的位寬通常大于原始的信息位；而交換器中傳輸?shù)臄?shù)據(jù)為解碼后的數(shù)據(jù)，因此，交換器的位寬并沒有增加。

圖5 面積節(jié)省型S-S容錯機制

圖6 低延遲型容錯機制

圖6所示的低延遲型容錯機制中，只在本地NI的接收方向加入了編碼器，其它4個NI則在接收方向增加了解碼器，發(fā)送方向保持不變。在每個交換節(jié)點，來自IP核的數(shù)據(jù)首先通過編碼器編碼，之后，編碼數(shù)據(jù)(信息位+校驗位)被送往交換器進行交換和轉(zhuǎn)發(fā)。對于來自相鄰交換器的數(shù)據(jù)，則先進行解碼，再進行交換和轉(zhuǎn)發(fā)。但與面積節(jié)省型不同的是，解碼后，不僅保留信息位，將校驗位也保留下來，并使它與信息位一起參與數(shù)據(jù)的交換和轉(zhuǎn)發(fā)，這樣做，省去了發(fā)送方向的編碼器，但會使得參與交換的數(shù)據(jù)位寬增加，最終導致交換器面積增大。

下面先分析引入容錯機制所導致的延遲。假定選擇的差錯控制碼為c(n， k)，其中，n表示碼長， k為信息位，m=n-k為校驗位。用Tenc、Tdec分別表示編、解碼器的延遲， Nmax表示每個包片(flit)經(jīng)過的最大跳數(shù)，由圖4、5和6可知， E-E型引入的延遲為Tenc+Tdec；面積節(jié)省型S-S的延遲為Nmax×(Tenc+Tdec)；低延遲S-S則為Tenc+N×Tdec，可以看到E-E型引起的延遲最小，而面積節(jié)省型S-S引入的延遲最大。

在面積開銷方面，采用E-E方式，只需在每個交換節(jié)點增加1個編碼器和1個解碼器，但交換器的數(shù)據(jù)位寬需要增加。面積節(jié)省型S-S需要增加4個編碼器和解碼器，但交換器的位寬保持不變。低延遲型S-S，則需要增加1個編碼器和4 個解碼器，同樣需要增加交換器的位寬。

1.3 差錯控制編碼

本文的差錯控制采用了FEC和ARQ兩種方式。漢明碼(Hamming)作為一種常見的線性編碼，最小碼距為3，能糾正單個錯誤或者檢測兩個錯誤，更重要的是它實現(xiàn)簡單，因此，常被用于NoC的容錯機制中。另一方面，在深亞微米(DSM)工藝下，相鄰走線間的耦合電容已成為互連線電容的主要部分。資料顯示DSM工藝下，降低總線的串擾對于提高數(shù)據(jù)傳輸?shù)目煽啃浴p少信號的延時已經(jīng)越來越重要了。串擾避免碼(CAC)[4]就是針對這一問題提出的，它可以降低總線最壞情況下的延遲，但并不具備糾錯功能。因此，為了提高系統(tǒng)穩(wěn)定性，通常采用CAC碼與差錯控制碼相結(jié)合的聯(lián)合編碼。BSC(Boundary Shift Code)[4]和DAP(Duplicate Add Parity)碼[4]正是這類編碼，它們均能糾正一位錯碼。然而，這兩種碼編碼后位寬增加很多，例如， 8位數(shù)據(jù)經(jīng)DAP編碼后位寬為17位，使得E-E和低延遲S-S方案中的交換器具有較大的面積開銷，因此，它們不適合在E-E和低延遲S-S方案中使用。另外，當源節(jié)點和目的節(jié)點相隔很遠的時候， E-E方案中也不適合采用ARQ，因為會帶來較大的延遲。因此，本文采用以下六種容錯方案：E-EHamming，低延遲型S-S Hamming，面積節(jié)省型S-S Hamming，面積節(jié)省型S-S DAP和面積節(jié)省型S-SBSC，以上均為糾錯型，重傳方案只有一種即面積節(jié)省型S-SARQ Hamming。

1.4 基于HERMES的重傳方案

本文對5種糾錯方案不再贅述，下面重點介紹基于HERMES的重傳方案，其中Hamming碼作為檢錯碼使用。如圖7所示，接收端一旦發(fā)現(xiàn)錯誤，則產(chǎn)生nack信號并通過專門的反饋通道通知發(fā)送端，發(fā)送端則將重傳緩沖器的數(shù)據(jù)重新發(fā)送。該機制無需使用應答信號(ack)指示數(shù)據(jù)的正確性，只在錯誤發(fā)生后發(fā)送nack信號報錯，在一定程度上解決了ack信號大量充斥網(wǎng)絡的問題。

具體工作原理如下：假設數(shù)據(jù)被劃分為流片(flit)進行傳送，首先，到達發(fā)送節(jié)點的數(shù)據(jù)經(jīng)過交換器路由到正確的輸出端口后，采用漢明碼編碼，由選擇器選中并輸出到下個節(jié)點。接收節(jié)點采用漢明檢測碼檢測收到的數(shù)據(jù)是否有誤，若有錯誤，則產(chǎn)生錯誤標志error給重傳控制單元，進一步產(chǎn)生nack信號并反饋到發(fā)送節(jié)點。相應的發(fā)送節(jié)點收到nack信號后讀出重傳緩沖器中的數(shù)據(jù)，同時阻塞交換器中隊列FIFO繼續(xù)讀數(shù)據(jù)。

圖7 面積節(jié)省型S-SHamming重傳電路結(jié)構

下面討論重傳緩沖器的深度和工作原理。根據(jù)HERMESNoC采用的流量控制協(xié)議， 1個flit傳輸需要2個時鐘，而從error標志產(chǎn)生到收到nack信號至少有兩個時鐘的延遲，即 傳輸1個flit的時間，因此重傳緩沖器至少需要緩存1個flit，緩沖器的寬度為編碼后位寬。為了保證nack信號在信道中傳輸?shù)目煽啃裕O計中使用能夠保存3個flit的緩沖器。重傳緩沖器讀寫不能同時進行，當nack信號無效時， wr_en有效，寄存1個flit；當nack信號有效后，緩沖器讀有效，將之前一個時鐘寫的數(shù)據(jù)讀出來。另外，為了防止數(shù)據(jù)在接受過程中頻繁出錯而重傳，在該機制中加入了最大重傳次數(shù)門檻，當同一流片重傳次數(shù)超過這個值時則不再重傳，接收節(jié)點丟棄該flit。

2 實驗結(jié)果及分析

我們對本文提出的六種容錯方案進行了仿真。仿真中數(shù)據(jù)的原始位寬為8位，采用hamming編碼后位寬增加到12位， DAP和BSC編碼后位寬為17，表1為六種容錯方案的面積和延遲開銷，其中Dec代表解碼器， Enc代表編碼器。

表1 六種容錯方案的面積和延遲開銷

從表1中可以看出， E-E和低延遲S-S容錯機制交換器位寬為碼字寬度(12 bit)，占用的面積較大；E-E方案需要加入編解碼器各一個，低延遲S-S需要加入4個解碼器和1個編碼器，面積節(jié)省型S-S需要加入編解碼器各4個；而面積節(jié)省型S-SARQ方案中， Hamming檢測電路比糾錯碼電路簡單，另外需要加入12 bit×3的重傳緩沖器。

延遲方面，加入編解碼器引入的額外延遲在1.2節(jié)中已討論。 ARQ方案另外需要加入控制邏輯以及重傳出錯數(shù)據(jù)引入的額外延遲，因此，重傳機制的延遲稍大。

根據(jù)上述容錯機制設計方案，在HERMESNoC上搭建容錯模型，設計采用VHDL語言，并用Modelsim進行仿真。圖8為面積節(jié)省型S-SHamming FEC模式下兩個節(jié)點nm0和nm2的仿真波形，圖中cordet=' 1'表明電路工作在FEC模式。 data_out(3)為nm0節(jié)點編碼器enc4 的輸入， 編碼器的輸出為hamout。編碼數(shù)據(jù)在鏈路上發(fā)生錯誤由H01C變成H05C，但經(jīng)過nm2節(jié)點的解碼器后，數(shù)據(jù)被糾錯，恢復成原來的H01，這個數(shù)據(jù)最終傳輸?shù)絥m2的本地端口data_out(4)。這樣就達到了數(shù)據(jù)糾錯的目的。

圖8 面積節(jié)省型S-SHamm ing FEC電路仿真

圖9為面積節(jié)省型S-SHamming ARQ模式下的電路仿真波形，此時， cordet=' 0'。同樣考慮兩個發(fā)送節(jié)點nm0和接收nm2， reg4為重傳緩沖器。假設數(shù)據(jù)在兩者鏈路之間出現(xiàn)了兩bit的錯誤，由H12C變?yōu)镠14C，這時， errror信號置高，控制重傳控制單元產(chǎn)生nack信號。nack信號一旦有效，即阻止節(jié)點nm0繼續(xù)向外傳出數(shù)據(jù)，使得交換器輸出數(shù)據(jù)保持不變。并將剛剛存儲在重傳緩沖器中的數(shù)據(jù)(data信號)H12C通過選擇器讀出傳到節(jié)點nm2。節(jié)點nm2將接收的錯誤數(shù)據(jù)和重傳的新數(shù)據(jù)一同傳輸送入緩沖器，通過指針操作將先前寫入的錯誤數(shù)據(jù)H14C用H12C覆蓋，這樣進入到交換器的即為正確的數(shù)據(jù)。

圖9 面積節(jié)省型S-SHamm ing ARQ電路仿真

我們還采用SMIC 130nm的工藝，用綜合工具Design Compiler對電路進行了綜合， 電源電壓1.2 V，仿真的時鐘周期為3 ns。表2給出了綜合后的面積和功耗開銷。

表2 六種方案面積開銷的綜合結(jié)果

從表2可以看出， Hamming， DAP和BSC這三種碼的編解碼器的面積和功耗均遠遠小于交換器的面積和功耗。低延遲S-S或E-E方案中，由于交換器的位寬為12bit，面積開銷比較大，而面積節(jié)省型S-S交換器的面積沒有增加。因此在編解碼器耗資源比較少的情況下，面積節(jié)省型比低延遲S-S更節(jié)省開銷。對于Hamming、DAP、BSC三種碼型，做糾錯碼時， DAP碼面積開銷最小， Hamming碼最大。當Hamming碼檢錯時，面積開銷依然比DAP碼大。因此DAP相對于Hamming、BSC性能更優(yōu)。但采用重傳卻能保證片上網(wǎng)絡在出錯數(shù)量比較高的情況下依然保持良好的容錯性能。

3 結(jié)術語

本文首先介紹了當前片上網(wǎng)絡常見的容錯機制，并給出了基于HERMESNoC具有容錯功能的容錯路由器；并采取Hamming、DAP、BSC三種碼型實現(xiàn)FEC和ARQ容錯機制；最后對各種方案用Synopsys公司的Design Compiler對幾種方案進行了綜合，分析面積和功耗開銷。結(jié)論得出面積節(jié)省型比低延遲S-S更節(jié)省開銷， DAP碼面積和功耗開銷最小，然而重傳卻具有更好的容錯性能。因此需要合理選擇以更好滿足芯片性能和功耗折衷。本文采用簡單的碼型在HERMES上搭建出FEC和ARQ容錯模型。為了更進一步研究容錯機制，需要尋找更復雜更有效的碼型和重傳機制并應用于HERMES。

[ 1] MuraliS， Theocharides T， Vijaykrishnan N.Analysisof Error Recovery Schemes for Networks on Chips[ J] .IEEE Design＆Test of Computers， 2005：434-442.

[ 2] Muhammad Ali， MichaelWelzl， Sven Hessler.A Fault Tolerant Mechanism for Handling Permanent and Transient Failures in a Network on Chip[ C] //Fourth International Conference on Information Technology(ITNG'07)， IEEE， Apr， 2007：1027-1032.

[ 3] Pirretti M， Link G M， Brooks R R.Fault Tolerant Algorithms for Network-on-Chip Interconnect[ C] //Proceedings of IEEE International Annual Symposium on VLSI， Lafayette， LA， 2004：46-51.

[ 4] Srinivasa R， Sridhara， Naresh R， Shanbhag.Coding for System-on-Chip Networks：AUnified Framework[J] .IEEETransactionson Very Large Scale Integration(VLSI)Systems， 2005， 13(6)：655-667.

[ 5] Daniele Rossi， Paolo Angelini， Cecilia Metra.Configurable Error Control Scheme for NoC Signal Integrity[ J] .IOLTS 07：43-48.

[ 6] Marculescu R.Networks-On-Chip：The Quest for On-Chip Fault-Tolerant Communication[ C] //Proc.IEEE Computer Soc.Ann.Symp.VLSI， IEEE Press， 2003：8-12.

[ 7] Zimmer H， Jantsch A.A Fault Model Notation and Error-Control Scheme for Switch-to-Switch Buses in a Network-on-Chip[ C] //Proc.1st Int' l Conf.Hardware/Software Codesign and System Synthesis(CODES 03)， IEEE Press， 2003：188-193.Volume 24， Issue 6， June 2005：818-831.

[ 8] Vellanki P， Banerjee N， Chatha K S.Quality-of-Serviceand Error Control Techniques for Network-on-Chip Architectures[C] //Proc.14th Great Lakes Symp.VLSI， ACM Press， 2004：45-50.

[ 9] Dongkook Park， Chrysostomos Nicopoulos.Exploring Fault-Tolerant Network-on-Chip Architectures[ C] //IEEE Proc.of 2006 Int'l Conf.on Dependable Systems and Networks， 2006：93-104.

[ 10] Ganguly A， Partha Pratim Pande， BelzerB Grecu C.Addressing Signal Integrity in Networks on Chip Interconnects through Crosstalk-Aware Double Error Correction Coding[ C] //VLSI，2007.ISVLSI'07.IEEE Computer Society Annual Symposium on 9-11 March 2007：317-324.

[ 11] 張磊，李華偉，李曉維.用于片上網(wǎng)絡的容錯通信算法[ J] .計算機輔助設計與圖形學學報， 2007， 19(4)：508-514.