基于拥塞感知的三维片上网络容错路由算法*

胡春雷 陈 锋 方 杰

(1合肥工业大学计算机与信息学院；2安徽职业技术学院信息工程学院 安徽合肥 230011)

1研究概述

随着集成电路制造工艺的不断发展，芯片上可集成的晶体管的数目和芯片的集成度都在不断增加，这使得单个芯片上可以集成数十甚至上百个IP核。这样基于总线通讯架构的片上系统(system-on-chip，SOC)将面临可扩展性问题、通讯效率问题、全局时钟同步困难等问题。为了解决以上问题，片上网络(network-on-chip，NoC)作为一种全新的互连结构被提了出来[1]。由于该种架构具有很好的扩展性、更高的吞吐量以及更小的功耗开销，因此被用于解决复杂片上系统的核间通信。随着单平面片上网络(2D NoC)中IP核的增加，2D NoC并没有在根本上解决缩短物理连线和减小信号延迟的问题。三维集成电路设计和片上网络多核互连架构，在学术界已经进行了多年的研究，三维集成电路设计工艺与先进的片上网络架构相结合而产生的三维片上网络(three dimension network on chip，3D NoC)，以其优良的性能、良好的可扩展性被认为是纳米工艺下最有前途的多核互连通信架构[2]。3D NoC的结构如图1所示，由资源节点(IP核)、资源网络接口(resource network interface，RNI)、路由器(router)、垂直通信链路、水平通信链路等几部分组成，是在2D片上网络的基础上进行垂直方向的扩展。这种结构大大缩短了IP核之间的平均跳数，使得片内通信效率大大提高。硅通孔(through—silicon-via，TSV)是业界最常见也被认为是最有前途的层间互连技术，将多个晶片(die)在垂直方向进行堆叠，有效缩短了IP核连线长度，减少了延时、降低了功耗，更好的满足了多核系统对通信效率的需求。但是随着芯片特征尺寸的缩小，集成电路密度的增加以及TSV的引入，都将导致芯片的可靠性问题[2]。ITRS[3]中预测，到2025年集成电路的特征尺寸将达到10nm，单个芯片将集成更多的晶体管，从而引起芯片内部发生更多的缺陷。主要体现在：①受制造工艺水平的限制，芯片在生产过程中将存在更多缺陷。②芯片在使用过程中，由于电路老化、电子迁移、负偏压温度不稳定性、电介质击穿等原因，造成芯片出现故障不断增多。③芯片在使用过程中极易受到串扰、噪声、α粒子撞击、电磁干扰、宇宙辐射等因素影响，导致芯片出现瞬时故障。这些因素都将导致芯片的可靠性问题。三维片上网络的通讯架构出现错误，将导致芯片通信性能急剧下降甚至系统瘫痪，如何保证三维片上网络的通讯架的可靠性成为学术界研究的热点[4]。

图1 3DNoC结构图

2拥塞感知的三维片上网络容错路由算法

2.1三维片上网络路由介绍

图2显示了一个3×3×3的标准的3D Mesh结构三维片上网络，为了方便显示，并未画出每个节点的IP核及NI接口，仅在图中画出了各个节点的路由器。为了标识路由器，需要为每个路由器都设置一个地址。为了方便路由控制，通常使用该路由器在空间上的坐标值(x，y，z)来表示该路由器的地址，其中z坐标代表路由器所处的层，如坐标(1，2，3)代表的是处于第3层的x坐标为1、y坐标为2的路由器节点。三维片上网络通常采用维序路由算法如XYZ路由算法、ZXY路由算法等。下面以XYZ路由算法为例，来介绍三维片上网络的数据路由过程。XYZ路由算法的原理是让数据先沿着X维进行传输，直到数据传输到和目标节点处于同一X坐标后再让数据沿着Y维进行传输，直到数据传输到和目标节点处于同一Y坐标后再让数据沿着Z维进行传输，直到数据到达目标节点。如图所示，假设源节点S(3，3，3)给目标节点D(1，2，1)发送数据，数据的传输过程为(3，3，3)→(2，3，3)→(1，3，3)→(1，2，3)→(1，2，2)→(1，2，1)。

图2 3D MeshNoC通信架构图

2.2拥塞感知容错路由算法

文章提出的容错路由算法能够感知到路由器或通信链路的故障，根据故障程度和拥塞程度来为数据包选择合适路径。同时，在容错路由算法的设计上考虑到温度对通信架构可靠性的影响。文章假定芯片所用的散热器安装在第一层下方，这样第一层的热量散失最快，第二层居中，第三层最慢。根据热量散失的分布特性，在控制数据包路由的时候可以考虑让数据包在水平方向传输所产生的热量尽可能的在靠近散热器的底层散失掉。容错路由算法流程如图3所示。

图3 路由算法流程图

由图3可知，假设(Cx，Cy，Cz)代表发送数据节点即源节点的地址，(Dx，Dy，Dz)代表接收数据节点即目标节点的地址，Cx、Cy、Cz和Dx、Dy、Dz分别代表原节点和目标节点X、Y、Z坐标对应的值。当源节点和目标节点不在同一平面时(即Dz!=Cz)，如果目标节点在源节点的上方(即Dz>Cz)，则让数据包在当前平面进行XY路由；如果当前平面X方向和Y方向都无故障，则可根据两个方向的通信拥塞程度来选择拥塞程度低的方向传输；如果当前平面的X方向或Y方向存在一个方向有故障，则选择无故障的方向进行传输；如果XY两个方向都存在故障，则选择使数据包沿着Z方向向目标节点前进一步，当数据包到另外一个平面后还是按照同样的策略进行路由。如果目标节点在源节点的下方(即Dz

在图4中，假设数据包从源节点S(3，3，3)发送给目标节点D(1，2，1)，根据文章提出的容错路由算法，目标节点位于下层，则数据包先沿Z轴向下传输一步到达节点(3，3，2)，然后在沿节点(3，3，2)再向下传输。但是此时节点(3，3，2)与下层路由相连的链路出现了故障，根据路由算法节点(3，3，2)将会从选择让数据包现在当前层沿X轴或者Y轴向目标节点前进一步，若节点(3，3，2)与在Y轴相连的节点(3，2，2)之间的链路也出现了故障，则这时会选择将数据包发送给节点(2，3，2)，数据包到达(2，3，2)还是优先选择向下传输，将数据包交给节点(2，3，1)。此时数据包已经到达目标层，但数据包在X维和Y维还没有达到目标。节点(2，3，1)到目标节点(1，2，1)有两条最短路径，即沿X维传输或者沿Y维传输，如果这两条路径都可用，则根据两条路径的拥塞程度选择拥塞程度轻的路径传输。假设节点(2，3，1)→节点(1，3，1)的流量小于节点(2，3，1)→节点(2，2，1)，则会选择将数据包传递给节点(1，3，1)，然后再由节点(1，3，1)将数据包传递给目标节点(1，2，1)。

图4 含故障链路3D MeshNoC通信架构图

路由算法除了应该能够快速地为数据包进行路由，还应该保证保证路由算法时无死锁的。片上网络容错路由算法通常都是采用绕过故障链路或路由器节点来达到容错的目的，在绕的过程中极易形成环路而产生死锁，如果不采用相应的方法去避免，将导致数据包在网络中不断的兜圈子，浪费网络的带宽资源并产生大量的功耗。目前片上网络路由算法中主要采用拐弯模型、虚拟通道技术、维序路由等技术来避免死锁。该研究采用广泛使用的虚拟通道技术来避免死锁的产生。

3实验结果

为评估文章算法，通过实验对其性能进行分析。实验使用的是Booksim 2.0模拟器，该模拟器是美国斯坦福大学CVA小组开发研制的仿真平台，是一个用于NoC路由算法仿真的仿真器。它模块化了NoC的各个组成部分，支持多种拓扑结构、路由算法、路由器结构、仲裁器结构与算法等。实验对象为4×4×4的3D Mesh NoC ，通信方式使用的是均匀随机模式，链路故障率为10%，通过对文献[5]和[6]以及文章提出的容错路由算法进行模拟。下面对评价的重要指标做具体说明。

(1)数据包时延。是指一个数据包从它的首部进入网络开始计时，直到该数据包的尾部离开网络所使用的时间。

(2)平均延时。网络中传输的所有数据包的时延求平均值。是衡量网络通信传输性能的重要指标。

其中pk_num指接收到的数据包总数。

(3)丢包率。数据传输过程中因故障等原因丢失数据包的数目占所发送数据包总数的百分比,是衡量网络可靠性的重要指标。

Lossrate=(loss/(receiver+loss))×100%

其中：loss为3DNoC丢弃的数据包的总数目；receiver为3D NoC接收到的数据包的数目。

图5显示了在数据包注入速率为0.02、0.04、0.06、0.08时文献[5]、文献[6]和文章在链路故障率为10%下的数据包平均时延的比较。由实验结果可以发现，相比较文献[5]、文献[6]，该方案所提出的容错路由算法能够在不同注入率都具有较低的数据包平均时延，与文献[5]相比，平均时延提升了20%，与文献[6]相比，平时时延提升了约14.6%，得益于该算法具有拥塞感知功能，在网络通信量较大时能够选择拥塞程度低的链路传输，有效地降低数据包的平时时延。

图5 故障率为10%时数据包注入率与平均时延比较

表1显示了在数据包注入率为0.06时，3DNoC通信架构中链路故障分别为5%、10%、15%情况下，三种不同路由算法的丢包率情况，可以看到，随着3D NoC中故障链路数目的增加，文章在丢包率上的优势越为明显，这主要是因为文章方案提出的拥塞感知容错路由算法更加具有灵活性，在多条路径中选择无故障且拥塞程度轻的路径传输数据，而且在传输的过程中考虑到热量对芯片可靠性的影响，让数据包在水平方向传输所产生的热量尽可能的在靠近散热器的底层散失掉，大大减少了温度热点对芯片可靠性带来的负面影响。

表1 不同链路故障占比下丢包率比较(%)

4小结

文章根据3DNoC通信架构中故障路由器或者链路带来的可靠性问题，设计了一种拥塞感知的容错路由算法。该路由算法能够指导数据包绕过故障链路或者路由器从而达到一定程度的容错，并且能够根据拥塞程度不同选择合适的路径传输数据包。实验结果表明，文章所设计的容错路由算法在提高3D NoC的通信的可靠性的同时，能够有效地降低数据包传输的平均时延。