基于NoC的容错路由算法

屈凌翔，刘海鹏，潘能智，赵宝功

（中国电子科技集团公司第58研究所，江苏 无锡 214035）

1 前言

随着半导体工艺的不断发展，芯片的集成度越来越高，规模也越来越大。传统的基于总线结构的片上系统（SoC）遇到了巨大的瓶颈，在系统的可扩展性、时钟的同步性、芯片的设计效率和能耗上均存在局限性，无法有效解决片上多用户的同时通信问题。因此，找到一种新的解决方案来突破这层瓶颈成为各国专家学者们共同致力研究的问题。2000年，瑞典皇家技术学院等提出“Network-on-Chip”概念，把NoC 定义为一块芯片上实现的，由交换开关网络互连的计算资源、存储资源以及I/O资源的片上网络。片上网络借鉴了计算机网络的设计思想，将计算机网络技术移植到芯片设计中来，在单个芯片上构建一个微网络。NoC的出现有效地解决了SoC总线结构的局限性[1,2]，具有更高的带宽[3]。NoC采用全局异步-局部同步（GALS）的通信机制, 从而很好地解决了全局同步所带来的问题。NoC通过通信节点连接资源节点，每个资源节点只要符合片上通信协议即可，资源节点、通信节点和软件可以独立设计和验证。

NoC设计的关键技术有：拓扑结构、交换机制、路由算法、服务质量、拥塞控制和路由器结构等。路由算法的优劣和全局的性能以及片上网络的稳定性是密切相关的。确定性路由算法由于其唯一的路由路径和简单的逻辑，能够带来较好的网络性能和较低的功耗，但它缺乏自适应性和容错能力[4～6]。自适应路由算法能够解决网络堵塞问题，但它同样缺乏容错能力，降低了网络的可靠性。本文提出了基于NoC的容错路由算法，不仅能够有效地解决片上网络的堵塞问题，同时增强了片上网络的可靠性。

2 基于2D-Mesh结构的容错路由算法

基本维序XY路由算法有很多优点：逻辑简单、传输效率高、没有死锁和活锁、容易实现等。同时它的缺点也很明显：没有容错能力且自适应性很差。本节介绍了维序XY路由算法，并在此基础上提出改进的XY容错路由算法，不仅能够自适应地容错，同时也能避免死锁和活锁。

2.1 确定性维序XY路由算法

在一个2D-Mesh结构里，维序XY路由算法中分组的路由只取决于源节点和目的节点的地址，而与网络状况无关。分组首先在X维上路由，当分组到达与目的节点同一列时，转向在Y维上的路由，最后到达目的节点。如图1所示：源节点是A，目的节点是B，分组首先沿X维到达与目的节点同一列的C点，然后转向Y维的路由。该算法硬件设计和实现简单，在网络流量不大时，具有小的时延，并且可防死锁和活锁。

图1 确定性维序XY路由算法

但是，当源节点和目的节点被确定时，路由路径被唯一确定，因此路径中有一条链路发生故障时，分组就不能被正确传输。同时该算法容易造成网络中央负载过大，产生热点或热点区域。

2.2 改进的容错路由算法

在经典的确定性维序XY路由算法基础上，本文提出了一种改进的容错路由算法，适用于任何方向的单向或者双向链路故障。

在2D-Mesh结构里，每条链路有两个直接相连的节点，我们定义水平方向为东西（E，W），垂直方向为南北（S，N）。同时最多有4个间接相邻的节点，我们定义为NW、NE、SW、SE或者WN、EN、WS、ES四个方向，如图2中所示。

图2 链路故障的原始路径（虚线）和新路径（实线）

对于一条无边界的链路，链路情形如图2所示。而对有边界的链路来说，链路故障共有4种情形，如图3所示。

图3 边界链路故障

当有一条链路发生故障时，我们重新定义一条新的唯一确定的路径来替代故障路径，其他不使用当前故障链路的路由仍然按照XY路由算法计算传输路径。在图2的D1和D2中，将包含故障链路的路由路径称为初始路径（original path），将改正后的路由路径称为新路径（new path）。确定新路径的准则同样是除了故障路径之外，连接源节点和目的节点之间最短的路由路径。表1列出了初始路径和对应的新路径。

表1 链路故障的初始路径以及替代的新路径

3 容错路由算法仿真

容错路由算法的仿真包括FPGA仿真平台的搭建和初始化硬件平台架构，整个验证过程如图4所示。

本文仿真使用Xilinx公司的Virtex6 FPGA， 型号XC6VLX760，采用3×3的2D-Mesh结构，如图5所示。对其中X方向链路故障1和Y方向链路故障2在Xilinx的ISE 14.7环境下进行仿真验证。图6是将数据00010011从（1, 3）传向（1, 2），图7是将数据00100001从（2, 1）传向（3, 1），仿真波形显示在链路故障的情况下传输数据成功。

图4 FPGA仿真平台

图5 X方向链路故障1和Y方向链路故障2

图6 仿真波形1

图7 仿真波形2

最后，将本文提出的容错路由算法与目前常用的几种路由算法在所适用的拓扑结构、是否采用最短路径、是否能够容错以及死锁处理机制逐一进行比较，如表2所示。

表2 容错路由算法和其他路由算法的性能对比

4 总结

本文在单链路故障的情况下，提出了改进的XY容错路由算法。根据仿真结果分析并和其他算法性能进行对比，改进的容错路由算法能够成功地在单链路故障情况下进行数据的传输，而且能有效地避免死锁。

[1] Davide BIertozz, Shashi Kumar A P. Networks-on-chip∶emerging research topics and novel ideas [Z]. VLSI Design, 2007.

[2] Kariniemi H, Nurmi J. Arbitration and routing schemes for onchip packet networks [C]. Interconnect-Centric Design for Advanced SoC and NoC, 2005∶ 253-282.

[3] 张楠. 高效的片上网络体系结构：核内路由[D]. 浙江：浙江大学硕士学位论文，2008.

[4] 张磊，李华伟，李晓维. 用于片上网络的容错通信算法[J]. 计算机辅助设计与图形学学报, 2007, 19（4）：508-514.

[5] H M Pham, S Pillement, D Demigny. A fault-tolerant layer for dynamically reconfigurable multi-processor systemon-chip [C]. in Proc. Int Conf. Reconfigurable Comput.FPGAs, Quintana Roo, Mexico, 2009. 284-289.

[6] C C Feng, Z H Lu, A Jantsch, J W Li, M X Zhang. A reconfigurable fault-tolerant de flection routing algorithm based on reinforce-ment learning for network-on-chip [C]. in Proc. Int. Workshop Netw. Chip Architectures, Stockholm,Sweden, 2010. 11-16.