基于HERMESNoC的片上网络容错方法研究*

方亮亮，胡庆生

(东南大学射频与光电集成电路研究所， 南京210096)

随着集成电路工艺的不断进步，系统芯片的规模不断增大，微小的芯片上包含上亿支晶体管，使得基于片上系统(SoC)的芯片设计将会非常复杂，而且传统的SoC体系结构及其相应的设计方法在多知识产权(IP)核的超复杂系统中遇到了技术瓶颈。从2000年开始，业界提出了一种全新的系统芯片设计模型—片上网络(NoC， Network on Chip)， NoC将计算机网络技术移植到芯片设计中来，彻底解决多IP模块体系结构中的问题，是更高层次、更大规模的片上系统，同时可提供包括带宽、延迟、可靠性等在内的服务质量。

1 片上网络的容错机制

一个典型的NoC组成如图1所示，主要由交换器(Switch)、链 路(Link)和 网 络接 口(NI， Network Interface)组成，其中网络接口负责IP核与网络的连接，协调向/从IP核传输包，交换器和链路则实现IP核的连接和通信。

图1 一个典型的NoC组成

在NoC提供的服务质量中，通信的可靠性是最重要的方面之一。随着特征尺寸的缩小，芯片的供电电压和器件阈值电压减小，互连线对串扰、耦合噪声、电磁干扰、软错误和工艺不稳定等深亚微米噪声源变得日益敏感，从而降低了通信的可靠性。通常，由串扰、耦合噪声、电磁干扰等引起的故障，具有随机性和瞬时性，多发生在链路和网络接口处。而由于交换节点失效、链路失效等引起的故障，一旦发生，就会一直存在，具有永久性，这时需要为信号重新选择路由，绕过出错的交换器和链路。

对于串扰、耦合等引起的随机性故障，虽然在设计阶段不能完全避免或消除，但通过采用容错机制提高通信的可靠性，可以尽量减小这类故障对系统性能的影响，不仅如此，容错机制还可以在很大程度上降低芯片的测试和验证成本。随着NoC研究的深入并逐步走向实际应用，国际上已对NoC的容错设计给予了越来越多的关注。

美国Stanford大学的Srinivasan Murali等人提出的端到端(E-E， End-End)、交换到交换(S-S， Switch-Switch)以及两者结合的流量控制机制[1]，用纠错码和检错码分别实现前向纠错(FEC)和检错重传(ARQ)，并分析了功耗-性能-可靠性的折衷问题。

德国Paderborn大学和奥地利Innsbruck大学于2007年提出的一种瞬时故障的容错机制[2]，该机制在包传输协议的端到端请求重传中加入了包集的概念，通过应答信号ack提高发送端的流水性，处理数据包出错或丢失。

M.Pirretti等人则采用随机通信机制容错，提出N-冗余随机走动算法[3]。该算法中只在第一跳采用泛洪机制，数据包的拷贝数量N是事先定义好的。算法关键在于N的确定，文中利用Markov链进行随机走动理论的推导。

本文重点研究在HERMESNoC平台上如何实现有效的容错机制，并分析实现的各种容错机制的面积、延迟和功耗开销。

1.1 HERMESNoC简介

HERMES是巴西PUCRS大学研究开发的基于包交换的NoC平台，可以实现不同的拓扑结构、缓冲器深度和路由算法。通过采用虫孔交换机制和XY路由算法， HERMES可实现OSI的低三层参考模型：在物理层实现交换器的物理连接接口；链路层定义交换器间的数据传输协议；交换操作则是在网络层实现的。

图2所示为一个3×3的HERMES结构框图，它由1个RS232串口Serial， 4个RISC处理器R8， 4个容量为1k字的Memory以及9个交换器Switch组成。Serial数据打包后经过交换器与4个R8处理器及4个Memory IP核通讯。交换器是HERMES的主要模块，它由交换控制单元(Control)和5个I/O端口组成，交换控制单元负责将接收的数据传送到正确的输出信道， 5个端口中的本地端口通过网路接口(NI)与IP核通讯，其余端口分别在东南西北四个方向与相邻交换器通讯。每个端口均包含一个缓冲器(Buffer)。图3为HERMESNoC的交换器结构。

图2 3×3网格型HERMES NoC

图3 HERMESNoC中的交换器

1.2 基于HERMES的容错机制设计

基于HERMESNoC，本文研究了两种容错机制：端到端(E-E)和交换到交换(S-S)。所谓E-E就是差错控制只发生在NI处，中间的路由节点仅仅负责数据包的转发，不进行差错控制。而S-S则是在路由的每个节点上都进行差错控制，其结果是能够更好地保证数据的正确性，代价也相对较高。图4为E-E型容错机制，可以看到，差错控制是通过在交换器的本地接口处增加了一个编码器和解码器实现的。

图4 E-E容错机制

本文对S-S型容错设计了两种方式，一种为面积节省型，另一种为低延迟型，如图5 和图6所示。图5中，在每个交换节点四个方向的输入、输出接口上，均添加了一个解码器和编码器。这样，数据从IP核发出后，每到达一个交换器，就先进行解码，再进行交换。交换之后，若需要继续转发，则重新编码；否则，通过本地接口直接送达目的地。这种方式下，在链路中传输的数据是经过编码后的数据，由于加入了校验位的缘故，这些数据的位宽通常大于原始的信息位；而交换器中传输的数据为解码后的数据，因此，交换器的位宽并没有增加。

图5 面积节省型S-S容错机制

图6 低延迟型容错机制

图6所示的低延迟型容错机制中，只在本地NI的接收方向加入了编码器，其它4个NI则在接收方向增加了解码器，发送方向保持不变。在每个交换节点，来自IP核的数据首先通过编码器编码，之后，编码数据(信息位+校验位)被送往交换器进行交换和转发。对于来自相邻交换器的数据，则先进行解码，再进行交换和转发。但与面积节省型不同的是，解码后，不仅保留信息位，将校验位也保留下来，并使它与信息位一起参与数据的交换和转发，这样做，省去了发送方向的编码器，但会使得参与交换的数据位宽增加，最终导致交换器面积增大。

下面先分析引入容错机制所导致的延迟。假定选择的差错控制码为c(n， k)，其中，n表示码长， k为信息位，m=n-k为校验位。用Tenc、Tdec分别表示编、解码器的延迟， Nmax表示每个包片(flit)经过的最大跳数，由图4、5和6可知， E-E型引入的延迟为Tenc+Tdec；面积节省型S-S的延迟为Nmax×(Tenc+Tdec)；低延迟S-S则为Tenc+N×Tdec，可以看到E-E型引起的延迟最小，而面积节省型S-S引入的延迟最大。

在面积开销方面，采用E-E方式，只需在每个交换节点增加1个编码器和1个解码器，但交换器的数据位宽需要增加。面积节省型S-S需要增加4个编码器和解码器，但交换器的位宽保持不变。低延迟型S-S，则需要增加1个编码器和4 个解码器，同样需要增加交换器的位宽。

1.3 差错控制编码

本文的差错控制采用了FEC和ARQ两种方式。汉明码(Hamming)作为一种常见的线性编码，最小码距为3，能纠正单个错误或者检测两个错误，更重要的是它实现简单，因此，常被用于NoC的容错机制中。另一方面，在深亚微米(DSM)工艺下，相邻走线间的耦合电容已成为互连线电容的主要部分。资料显示DSM工艺下，降低总线的串扰对于提高数据传输的可靠性、减少信号的延时已经越来越重要了。串扰避免码(CAC)[4]就是针对这一问题提出的，它可以降低总线最坏情况下的延迟，但并不具备纠错功能。因此，为了提高系统稳定性，通常采用CAC码与差错控制码相结合的联合编码。BSC(Boundary Shift Code)[4]和DAP(Duplicate Add Parity)码[4]正是这类编码，它们均能纠正一位错码。然而，这两种码编码后位宽增加很多，例如， 8位数据经DAP编码后位宽为17位，使得E-E和低延迟S-S方案中的交换器具有较大的面积开销，因此，它们不适合在E-E和低延迟S-S方案中使用。另外，当源节点和目的节点相隔很远的时候， E-E方案中也不适合采用ARQ，因为会带来较大的延迟。因此，本文采用以下六种容错方案：E-EHamming，低延迟型S-S Hamming，面积节省型S-S Hamming，面积节省型S-S DAP和面积节省型S-SBSC，以上均为纠错型，重传方案只有一种即面积节省型S-SARQ Hamming。

1.4 基于HERMES的重传方案

本文对5种纠错方案不再赘述，下面重点介绍基于HERMES的重传方案，其中Hamming码作为检错码使用。如图7所示，接收端一旦发现错误，则产生nack信号并通过专门的反馈通道通知发送端，发送端则将重传缓冲器的数据重新发送。该机制无需使用应答信号(ack)指示数据的正确性，只在错误发生后发送nack信号报错，在一定程度上解决了ack信号大量充斥网络的问题。

具体工作原理如下：假设数据被划分为流片(flit)进行传送，首先，到达发送节点的数据经过交换器路由到正确的输出端口后，采用汉明码编码，由选择器选中并输出到下个节点。接收节点采用汉明检测码检测收到的数据是否有误，若有错误，则产生错误标志error给重传控制单元，进一步产生nack信号并反馈到发送节点。相应的发送节点收到nack信号后读出重传缓冲器中的数据，同时阻塞交换器中队列FIFO继续读数据。

图7 面积节省型S-SHamming重传电路结构

下面讨论重传缓冲器的深度和工作原理。根据HERMESNoC采用的流量控制协议， 1个flit传输需要2个时钟，而从error标志产生到收到nack信号至少有两个时钟的延迟，即 传输1个flit的时间，因此重传缓冲器至少需要缓存1个flit，缓冲器的宽度为编码后位宽。为了保证nack信号在信道中传输的可靠性，设计中使用能够保存3个flit的缓冲器。重传缓冲器读写不能同时进行，当nack信号无效时， wr_en有效，寄存1个flit；当nack信号有效后，缓冲器读有效，将之前一个时钟写的数据读出来。另外，为了防止数据在接受过程中频繁出错而重传，在该机制中加入了最大重传次数门槛，当同一流片重传次数超过这个值时则不再重传，接收节点丢弃该flit。

2 实验结果及分析

我们对本文提出的六种容错方案进行了仿真。仿真中数据的原始位宽为8位，采用hamming编码后位宽增加到12位， DAP和BSC编码后位宽为17，表1为六种容错方案的面积和延迟开销，其中Dec代表解码器， Enc代表编码器。

表1 六种容错方案的面积和延迟开销

从表1中可以看出， E-E和低延迟S-S容错机制交换器位宽为码字宽度(12 bit)，占用的面积较大；E-E方案需要加入编解码器各一个，低延迟S-S需要加入4个解码器和1个编码器，面积节省型S-S需要加入编解码器各4个；而面积节省型S-SARQ方案中， Hamming检测电路比纠错码电路简单，另外需要加入12 bit×3的重传缓冲器。

延迟方面，加入编解码器引入的额外延迟在1.2节中已讨论。 ARQ方案另外需要加入控制逻辑以及重传出错数据引入的额外延迟，因此，重传机制的延迟稍大。

根据上述容错机制设计方案，在HERMESNoC上搭建容错模型，设计采用VHDL语言，并用Modelsim进行仿真。图8为面积节省型S-SHamming FEC模式下两个节点nm0和nm2的仿真波形，图中cordet=' 1'表明电路工作在FEC模式。 data_out(3)为nm0节点编码器enc4 的输入， 编码器的输出为hamout。编码数据在链路上发生错误由H01C变成H05C，但经过nm2节点的解码器后，数据被纠错，恢复成原来的H01，这个数据最终传输到nm2的本地端口data_out(4)。这样就达到了数据纠错的目的。

图8 面积节省型S-SHamm ing FEC电路仿真

图9为面积节省型S-SHamming ARQ模式下的电路仿真波形，此时， cordet=' 0'。同样考虑两个发送节点nm0和接收nm2， reg4为重传缓冲器。假设数据在两者链路之间出现了两bit的错误，由H12C变为H14C，这时， errror信号置高，控制重传控制单元产生nack信号。nack信号一旦有效，即阻止节点nm0继续向外传出数据，使得交换器输出数据保持不变。并将刚刚存储在重传缓冲器中的数据(data信号)H12C通过选择器读出传到节点nm2。节点nm2将接收的错误数据和重传的新数据一同传输送入缓冲器，通过指针操作将先前写入的错误数据H14C用H12C覆盖，这样进入到交换器的即为正确的数据。

图9 面积节省型S-SHamm ing ARQ电路仿真

我们还采用SMIC 130nm的工艺，用综合工具Design Compiler对电路进行了综合， 电源电压1.2 V，仿真的时钟周期为3 ns。表2给出了综合后的面积和功耗开销。

表2 六种方案面积开销的综合结果

从表2可以看出， Hamming， DAP和BSC这三种码的编解码器的面积和功耗均远远小于交换器的面积和功耗。低延迟S-S或E-E方案中，由于交换器的位宽为12bit，面积开销比较大，而面积节省型S-S交换器的面积没有增加。因此在编解码器耗资源比较少的情况下，面积节省型比低延迟S-S更节省开销。对于Hamming、DAP、BSC三种码型，做纠错码时， DAP码面积开销最小， Hamming码最大。当Hamming码检错时，面积开销依然比DAP码大。因此DAP相对于Hamming、BSC性能更优。但采用重传却能保证片上网络在出错数量比较高的情况下依然保持良好的容错性能。

3 结术语

本文首先介绍了当前片上网络常见的容错机制，并给出了基于HERMESNoC具有容错功能的容错路由器；并采取Hamming、DAP、BSC三种码型实现FEC和ARQ容错机制；最后对各种方案用Synopsys公司的Design Compiler对几种方案进行了综合，分析面积和功耗开销。结论得出面积节省型比低延迟S-S更节省开销， 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] 张磊，李华伟，李晓维.用于片上网络的容错通信算法[ J] .计算机辅助设计与图形学学报， 2007， 19(4)：508-514.