欧阳一鸣，郭 凯，梁华国

(合肥工业大学计算机与信息学院 合肥 230009)

1 引言

随着超大规模集成电路的发展，片上系统（SoC）的集成度越来越高，数以百计的十亿级晶体管集成到一个片上，这就要求片上的模块之间的通信带宽足够大，并且具有可重用性以满足快速投放市场的需求。传统的片上系统采用的总线结构受到了这两方面的严峻挑战。参考文献[1～3]介绍了一种新的片上通信结构——片上网络（network on chip，NoC），它将互联网技术移植到片上系统，数以百计的片上资源（IP核）互连起来，并将通信与计算分离。NoC不但具有良好的空间可扩展性，而且采用了全局异步-局部同步GALS（globally asynchronous locally synchronous）通信机制，提供了高效的并行通信能力。

与此同时，随着电路集成规模的提高，电路在生产和运行过程中非常容易损坏。在NoC中必须存在相应的容错策略，以便在出现故障时可以继续有效地工作。对于NoC中的IP核故障，由于NoC中通常存在大量相同的部件，因此在软件映射时不使用已经损坏的IP核就可以解决；对于NoC中的路由器和链路故障，由于在通信过程中可能会用到这些路由器和链路，因此可能会导致NoC通信错误甚至瘫痪。为了解决该问题，参考文献[4]将该问题分为以下3个子问题：

·使用适当的内建自测试（BIST）机制探测出故障的路由器和链路；

·设计一种容错的、分布式、可重构的路由算法，并在路由器中执行；

·在NoC中设置配置总线，重构的数据通过配置总线分发到每个路由器中。

本文主要是设计一种能够容错的分布式可重构路由算法，使NoC出现路由器和链路故障时能够继续正确地通信。

[4]提出了一种可重构的容错路由算法，通过在未出错区域使用XY路由算法，在出错区域使用特定的路由路径，达到容忍单个路由器（或者一个路由器区域）出现故障的目的。该算法将NoC中路由器的损坏状况分成9种，然后规定了这9种状况分配的通信路径，并通过路由器中设置的状态寄存器标识出该路由器所处的状态，通信时依据路由器状态选择相应的路由路径。但是该算法没有解决NoC出现多个不规则路由器故障和链路故障的问题。参考文献[5]和[6]提出的路由算法，通过在节点建立探测机制，探测出没有故障的传输路径。该算法虽然能够解决NoC中的路由器和链路故障，但是节点中的路由表开销较大，而且探测数据包会增加数据传输时延。参考文献[7]中采用多路径传输策略，当传输数据包时，同时在不同路径上传输多份数据包，通过冗余来防止出错造成的通信错误。该方法容易造成网络拥塞，同时增大了数据的传输时延。

本文提出了新的容错模型和基于该模型的可重构路由算法。本方法通过容错模型建立起每个路由器的输出端口状态，可重构路由算法通过对每个输出端口的状态进行标识，确认与端口相连的路由器和链路的损坏状态，决定数据的转发方向。这样可以保证数据传输能够正确地进行，并且没有额外的数据包进入网络。与现有方法相比，该方法在能够容忍路由器和链路故障的同时，保障NoC拥有较高的通信性能。

2 容错模型

NoC是由控制网络中数据传输的路由器和连通片上系统中各IP核之间进行数据传输的链路构成的网络结构。NoC 的拓扑多种多样，有 2D-Mesh、torus、fat-tree等，本文采用的是2D-Mesh拓扑，如图1所示（R表示路由器，IP表示IP核）。

下面分别给出路由器损毁度（DG）和输出端口状态寄存器（SR）的定义。

路由器损毁度：在2D-Mesh结构中，与路由器（x，y）相连的4条链路或者路由器的损坏（或者未连接）个数称为该路由器的损毁度。例如，与非边沿节点路由器（x，y）相连的一个路由器和一条链路损坏，那么该路由器的损毁度为2；边沿节点（0，1）相连的路由器和链路全部完好，那么该路由器的损毁度为1。对于一个路由器，其损毁度的范围为[0，4]。

输出端口状态寄存器：在2D-Mesh结构中，每个路由器存在4个输出端口，4个输出端口通过链路与下一个路由器相连，因此，在路由器内设置一个8位的端口状态寄存器用于标识与4个端口相连的链路或者路由器的损坏状态，每个端口对应2位，其格式如图2所示。

每个路由器的损毁度可以由该路由器的输出端口状态寄存器确定，其公式如下。

路由器的每个输出端口状态可以由与该输出端口相连的路由器损毁度确定，其转换公式如下。

式中，SRi为状态寄存器中 i对应的方向，DGNei为i对应的输出端口相连的路由器损毁度，i的取值范围为[0，3]，0代表 N方向，1代表 E方向，2代表 S方向，3代表W方向。

假设通过适当的BIST测试能够检测出NoC中出现故障的路由器或者链路的具体位置。若网络中的某个路由器出现故障或者与路由器相连的3条链路出现故障，则在软件映射时不使用与该路由器相连的IP核，因此，在NoC路由过程中，不存在数据包的目的地是与这些路由器相连的IP核。

3 基于重构的动态容错路由算法

本文提出的基于重构的动态容错路由算法是在带有一定自适应性的维序路由[8]的基础上，通过对路由器中每个端口的输出状态寄存器进行检查确定路由方向。在路由时还考虑了网络的拥塞程度，若路由时两个端口的输出状态寄存器的标识相同，那么依据拥塞程度确定路由方向。拥塞程度依据每个端口的转发率来确定。另外，该路由算法通过虚通道机制可以解决死锁问题[9]。

转发率是指该方向上已经转发出去的数据包数目与该路由器所有转发出去的数据包总数的比值，即：

路由算法描述如下：设（dx，dy）为数据的目的节点，（cx，cy）为数据传输的当前节点。当 dx和 cx、dy和 cy都不相等时保持最短路径的转发方向有两个，根据SR中这两个方向的标识选择转发的端口。若两个方向标识相等，当标识为11时，数据从余下的非数据进入方向转发；当不为11时，选择拥塞程度小的方向转发。若两个方向的标识不同，则从标识较小的方向转发。当dx和cx、dy和cy中有一个相等时，保持最短路由的转发方向只有一个，如果SR中该方向的标识不为11，则从该方向直接转发；否则，查看数据的进入端口再做相应处理。若数据是从坐标相等维的端口进入，则比较余下的端口，若这两个端口的标识相等，则从拥塞程度小的方向转发，否则从标识较小的方向转发；若数据是从非坐标相等维的端口进入路由器，检查非坐标相等维上另一转发端口的SR中的标识是否为11，不为11则从该方向转发，否则从剩余的非数据进入方向转发。路由算法流程如图3所示。

4 实验结果

4.1 实验模型

在基于OPNET编制的一个NoC仿真平台[10]进行了5×5 2D-Mesh结构的实验，路由器的每个端口具有3条虚通道。在实验中，通过评估本文提出的路由算法和参考文献[4]提出的可重构容错路由算法的时延，比较算法的优劣。本文采用的是转置模式的通信，也就是（i，j）节点的数据发送给（5－i－1，5－j－1），这是由于该转发模式更加接近于NoC的实际通信[11]。

NoC中的节点情况可以分为以下几种：

·NoC中的边角节点，如图4中R1类节点；

·NoC中的边沿节点，如图4中R2类节点；

·NoC中靠近中心位置的节点，如图4中R3类节点；

·NoC中的中心节点，如图4中R4类节点。

本文分别做了NoC没有出现故障和故障出现在上述4种位置时的时延比较实验。边角节点R1选取（0，0）节点，边沿节点 R2选取（0，2）节点，靠近中心位置节点 R3选择（1，1）节点，中心节点 R4 为（2，2）。

本文用平均时延评价网络的性能，下面对这项指标做具体的说明。

数据包时延：从数据包进入网络到数据包尾部离开网络的这段时间的差。在网络中数据包时延主要由以下3部分组成。

其中，Tdelay表示数据包的传输时延，Bdelay表示路由器内部队列的缓冲时延，Ldelay表示链路的传播时延。由于相对于传输时延和缓冲时延，链路传播时延要小得多，因此在仿真中忽略了链路传播时延，即设Ldelay=0。

平均时延：将所得到的各个数据包的时延累加取平均值。

其中pk_num定义为接收到的数据包个数。

4.2 实验结果

当NoC无故障节点时，本文提出的路由算法和参考文献[4]提出的路由算法的平均时延比较如图5所示。

从图5可以看出，当无故障节点时，在路由时延上本文提出的路由算法略高于参考文献[4]提出的路由算法。在无故障时，本文提出的路由算法性能略差于参考文献[4]提出的路由算法性能。

当故障节点出现在NoC中坐标为（0，0）节点处时，本文提出的路由算法和参考文献[4]提出的路由算法的平均时延比较如图6所示。

从图6可以看出，当故障出现在节点（0，0）处时，在路由时延上参考文献[4]提出的路由算法要小于本文提出的路由算法。这是因为（0，0）节点为NoC中的边角位置，传输数据时使用该节点的频率不是很高，所以该节点故障对数据时延的影响很小。

图7和图 8所示为当故障节点分别位于（0，2）和（1，1）时，本文提出的路由算法和参考文献[4]提出的路由算法的平均时延比较。

从图 7 和图 8 可以看出，节点（0，2）和（1，1）损坏时，在路由时延上本文提出的路由算法小于参考文献[4]提出的路由算法。这是因为在路由数据时使用该节点的次数增多，不同的容错路由算法对数据传输时延的影响增大，导致时延的差异增大。

当故障节点出现在NoC中坐标为（2，2）处时，本文提出的路由算法和参考文献[4]提出的路由算法平均时延比较如图9所示。

从图9可以看出，当故障节点出现在（2，2）处时，在路由时延上本文提出的路由算法明显小于参考文献[4]提出的路由算法。这是由于节点（2，2）处于NoC模型的中心位置，数据传输时使用该节点的频率很高，因此容错路由算法对数据时延的影响更加明显。

由上述实验结果可以得出，与参考文献[4]提出的路由算法相比，本文提出的路由算法在保障NoC通信的情况下具有更小的传输时延，因此本文提出的路由算法具有更高的通信性能，更加适合NoC的容错通信。

5 结束语

NoC作为一种新的SoC体系结构，已逐渐成为研究的热点。本文提出了基于NoC的动态容错路由算法，该算法通过重构NoC中节点每个端口的输出状态寄存器，使SR能够标识出现故障的路由器或者链路，在路由过程中不使用这些出现故障的路由器和链路，从而保证NoC的通信。

参考文献

1 Benini L,Micheli G D.Networks on chips:a new SoC paradigm.IEEE Transactions on Computers,2002,35（1）:70～78

2 Daly W J,TowlesB.Route packets,notwires:on-chip interconnection networks.In:the 38rd ACM/IEEE Design Automation Conference,Las Vegas,NV,USA,June 2001

3 高明伦，杜高明.NoC：下一代集成电路主流设计技术.微电子学,2006,36(4):461～466

4 Zhang Z,GreinerA,Taktak S.A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh network-on-chip.In:the 45rd ACM/IEEE Design Automation Conference,Anaheim,California,USA,June 2008

5 Yong-Bin Kim.Faulttolerantsource routing fornetworkon-chip.In:Proceedings of IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems 2007,Rome,Italy,Sept 2007

6 张磊,李华伟,李晓维.用于片上网络的容错通信算法.计算机辅助设计与图形学学报,2007,19(4):508～514

7 Murali S,Atienza D,Benini L,et al.A multi-path routing strategy with guaranteed in-order packet delivery and fault-tolerance for networks on chip.In:the 43rd ACM/IEEE Design Automation Conference,July 2006

8 Li M,Zeng Q A,Jone W B.DyXY-a proximity congestionaware deadlock-free dynamic routing method for network on chip.In:the 43rd ACM/IEEE Design Automation Conference,July 2006

9 Xiang D,Zhang Y,Pan Y.Practical deadlock-free fault-tolerant routing in meshes based on the planar network fault model.IEEE Transactions on Computers,2009,58(5):620～633

10 Wu Ning,Ge Fen,Wang Qi.Simulation and performance analysis of network on chip architectures using OPNET.In:the 7th International Conference on ASIC,Guilin,China,October 2007

11 Daneshtalab M,Sobhani A,Kusha A A,et al.NoC hot spot minimization using AntNetdynamic routing algorithm.In:Proceedings of 17th International Conference on Applicationspecific Systems,Architectures and Processors (ASAP 2006),Colorado,USA,September 2006