李 娇，晁月斌，冉 峰，蔡 升，郭润龙，季 渊
（1.上海大学 微电子研究与开发中心，上海 200444；2.上海大学 新型显示技术及应用集成教育部重点实验室，上海 200072）
0 引 言
结合二维片上网络与三维集成电路发展而来的三维片上网络（Three-Dimensional Network-on-Chip，3D NoC）以其更短的全局互连、更高的封装密度、更小的体积等诸多优势，逐渐成为提高芯片性能的重要研究方向[1-2]。然而，随着设计规模的扩大以及电路特征尺寸的减小，整个芯片的复杂度提升。此时，3D NoC 出现链路故障的概率上升，从而使得网络性能下降，甚至整个系统失效。为了解决链路故障的问题，同时提升路由路径的多样性，高效均衡的容错路由算法是一种保证3D NoC 性能以及可靠性的有效方法[3-4]。
在3D NoC 路由算法的研究中，较早提出的是确定性维序xyz路由算法[5]，但其在有多条路径的情况下，仅选择其中一条固定路径，在流量均衡性上的表现很差。为了提高路径的多样性，有一些路由算法选取多条路径作为数据通路。文献[6]提出了一种多路径路由算法，可以得出三种路径：zxyxz路径、xyzyx路径和yzxzy路径。相较于传统的确定性路由算法，路径多样性有所提升，但在规模较大的网络结构中路径利用率仍旧很低。在容错算法的研究中，文献[7]提出了一种基于B-OE 转向模型的容错路由算法，该算法在垂直方向分为奇偶平面进行不同的上下转向，但其性能依赖于垂直方向流量负载的大小，无法实现流量的均衡。文献[8]提出的VMCD算法，只设计了水平边界链路故障的绕行规则，并不能解决水平内部链路以及垂直链路的故障，所以需要设计包含更多故障类型的绕行规则以增加网络的可靠性。
本文对上述问题进行研究，从路径多样性出发，结合均衡的容错绕行规则，提出一种具有路径多样性的流量均衡容错路由算法。实验结果表明，本文算法能够有效降低传输延时，同时提高网络的吞吐量。
1 路径多样性分析
图1 为基于Mesh 架构的3D NoC 通信架构图，图中圆形结构代表路由器，各个路由器之间的连线为通信链路[9]。在实际应用中，路由器还会与网络接口以及专门的知识产权核（Intellectual Property core，IP 核）相连，以实现数据的通信与运算。在图1 中，数据包从S 节点到D 节点进行传输。根据xyz路由算法，数据包先在x方向上完成路由，随后完成y方向的路由，最后在z方向上路由实现数据的传输。 所以路由路径为S →A →B →G →D（简写为SABGD），但路径SEIKD以及路径SCHKD 等都可以完成数据传输的任务。通过分析多条路由路径可知，无论选择哪条路由路径，在不强制规定路由顺序的情况下，只要数据包在x，y，z三个方向路由的距离为目的节点与源节点坐标的差值，就能够确保将数据包发送到目的节点。上述路由都是在以源节点与目的节点连线为对角线的长方体内进行的，数据包在此最短路径范围内传输，且不发生绕行，否则会因额外的路由路径导致传输延时的增加，影响算法的性能。
图1 路由路径分析
基于转向模型的West-South-First 路由算法[10]在进行数据传输时，首先适应性地向西或者南路由数据包，然后适应性地向东、北、上、下路由数据包，以此机制实现数据的传输。但由于转向模型禁止了部分转向，只有当源节点与目的节点处于特殊的位置，即目的节点x坐标小于源节点的x坐标、目的节点y坐标大于源节点的y坐标时，数据包在路由的过程中才不触发禁止转向的机制，算法的适应性才能生效。否则会因多次的转向使路由路径变为非最短路径，影响数据包的传输延时等指标。
xyz等确定性路由算法只能选择最短路径范围内的一条或几条路由路径，无法实现路径的多样性。基于转向模型的路由算法只有在源节点与目的节点处于特殊的位置关系时才能体现最短路由路径下的路径多样性。为了充分利用最短路径范围内的路由路径，实现路径多样性，需要对路由路径进行多样性分析[11]，总结出合理的路由策略。首先定义路径多样性（Path Diversity，PD）：
PD=f(R,T,D(local node,destination node)) （1）式中：R是转向模型给出的可用路径；T是与拓扑结构及其规模大小相关的参数；D是通信节点的相对距离，即源节点与目的节点在x，y，z三个方向的路由距离。
从路由算法的角度考虑，转向模型限制越小，R的值就会越大，路径多样性PD 的值就越大；从拓扑结构方面考虑，如果网络结构中两个相邻节点之间的链路越多，T的值就会越大，路径多样性就越大；此外，通信节点之间的路由距离越长，路径多样性就会越大。把PD值看作是数据包从源节点到目的节点不同路由路径的数量。本文采用3D-Mesh 拓扑结构，因此路径多样性的大小由路径选择策略以及源节点到目的节点的相对距离决定。
图1 中，根据源节点S 和目的节点D 的相对位置可知，A，C，E 三个节点是节点S 下一步路由的可选节点，节点S 的路径多样性用下一步路由可选择节点的路径多样性之和表示：
同理，A，C，E 三个节点路径多样性可以表示为：
按照上述规则，将最短路径范围内的各个节点的路径多样性量化后可以得到：PDA=3，PDC=3，PDE=6，PDS=12。这意味着源节点S 的数据包在最短路径范围内有12条不同的路径可以到达目的节点D，同理，节点A有3 条不同的路由路径、节点C 有3 条不同的路由路径、节点E 有6 条不同的路由路径。在上述情况下，要使每条路径被选择的概率相同，数据包由源节点S 向A，C，E三个节点路由的比例应该是每个节点的路径多样性之比，也就是3∶3∶6。如果按照1∶1∶1 的比例路由，数据包不会等可能地选择每条可用路径，流量分布不均的问题难以避免。
在确定路径选择策略后，对路径数量进行分析。数据包路由路径的数量与数据包当前节点和目的节点的相对位置有关。设Cx，Cy，Cz为当前节点的坐标，Dx，Dy，Dz为目的节点的坐标。Nx，Ny，Nz表示当前节点与目的节点在x，y，z三个方向上需要经过的跳数。则路径多样性的公式可以表示为：
当数据在yz平面传输时，向y，z方向路由的比例为：
当数据在x，y或z方向传输时，数据路由的方向是确定的。
图2 为基于路径多样性的路由选择模型。源节点S的坐标为（0，0，0），目的节点D 的坐标为（1，1，2），最短路径范围内节点中的数值表示该节点路径多样性的大小。显然，路由选择模型能够正确地表示出下一步路由方向的选择概率，保证路径的多样性和流量的均衡性。
图2 路由选择模型
2 故障模型及绕行规则
数据包在路由的过程中遇到故障链路，容易产生拥塞，导致流量分布不均衡。路径拥塞甚至会从故障区域扩展到源节点，减少最短路径范围内的路径多样性，进一步恶化网络的通信状态。为了克服上述问题，需要进一步优化容错路由算法。
文献[8]中提出的故障模型及绕行规则是3D NoC 路由算法研究中的典型。其将故障分为8 种类型，分别是xy平面东/西方向的4 种故障类型以及南/北方向的4 种故障类型，但这8 种故障类型都是边界故障。3D NoC 中的链路故障可能出现在任意位置，只建立边界故障绕行规则对NoC 网络容错能力的提升十分有限。因此，本文建立了新的链路故障模型，对3D NoC 中的水平以及垂直方向的边界、内部链路建立故障模型，且针对不同位置的故障建立相应的绕行规则。
如图3 所示，根据故障可能出现的位置，将故障模型分为8 种类型：xy平面奇/偶行的链路故障、xy平面奇/偶列的链路故障、xz平面奇/偶列的链路故障、yz平面奇/偶列的链路故障，其中东、西、南、北四个方向的链路故障在xy平面进行绕行，上、下方向的链路故障在xz和yz平面进行绕行。
图3 故障模型及绕行规则
以东向链路故障为例，链路故障分为两种类型：Type1 和Type2。当故障位于偶行，为Type1 型故障；当故障位于奇行，为Type2 型故障。以Type1 型故障为例进行分析：当前节点为15，目标节点是14，节点15 中的数据包首先向南路由发送到节点8。在节点8 中，路由器将计算下一步路由方向，在上述多样性的选择策略下，数据包有概率向节点15 路由。但是，如果数据包再次发送到节点15 后，它并不能直接到达节点14 并且会发生死锁。设计先行策略可以解决这种问题：当数据包由节点15 发送到节点8 后，不经任何判断的向东路由发送到节点9，并将节点9 作为此次绕行的终点，不需要将数据包继续路由到节点14。根据前文路径多样性的路由规则，目的节点如果在节点14 的南方向时，直接从节点9 向南路由，而不必向北路由到节点14 后再向南路由，这样就避免了不必要的路由。如果目的节点在节点14 的北面或者东面，只需要根据路由规则从节点9 继续完成路由即可。
如果在容错绕行的过程中再次遇到链路故障，那么仍按照初始故障位置的绕行规则绕行。在上述节点15到节点14 的绕行分析中，如果节点8 到节点9 的链路也发生故障，那么数据包将发送到节点7，然后不经任何判断直接发送到节点6，完成故障绕行。其他链路故障模型的具体绕行规则如下：
Type1：xy平面偶行故障，先向南绕行，再分别向东或西路由。
Type2：xy平面奇行故障，先向北绕行，再分别向东或西路由。
Type3：xy平面偶列故障，先向东绕行，再分别向南或北路由。
Type4：xy平面奇列故障，先向西绕行，再分别向南或北路由。
Type5：xz平面偶列故障，先向东绕行，再分别向上或下路由。
Type6：xz平面奇列故障，先向西绕行，再分别向上或下路由。
Type7：yz平面偶列故障，先向东绕行，再分别向上或下路由。
Type8：yz平面奇列故障，先向西绕行，再分别向上或下路由。
图4 为本文故障绕行的示例，数据包从源节点S 传输到目的节点D，图中标“x”的链路为故障链路。对于VMCD 算法无法解决的内部链路故障Fault2、Fault3 以及垂直链路故障Fault4，本文算法都可以进行有效绕行。链路故障Fault2 为绕行过程中遇到的链路故障，仍可以通过Fault1 的绕行规则完成故障绕行。本文故障链路的绕行规则在面对复杂链路故障时，仍有着不错的容错能力，能减少数据拥塞问题，进一步提升网络的稳定性和流量的均衡性。
图4 故障绕行示例
3 实验结果与分析
利用Access Noxim 系统仿真平台测试本文所提出的算法。此仿真平台基于System C 设计开发，其源代码开放性、扩展性好，能够基于用户定义的维度参数生成NoC 的3D 体系结构。仿真器的参数配置如表1 所示。
表1 仿真器参数配置
本文主要从平均延时和吞吐量两个方面来衡量所提算法对网络性能的改善。图5 为两种算法在0%链路故障率、2%链路故障率和5%链路故障率下，吞吐量随数据包注入率变化的曲线图。当注入率低于0.03 时，由于数据包数量较少，两种算法在不同故障率下吞吐量差别较小。当注入率大于0.09 时，从图5 中可以看出，本文算法相较于VMCD 算法在吞吐量方面具有明显的优势，在5%链路故障率的情况下吞吐量提高了20.9%，这是因为本文算法容错机制完善、均衡性强。
图5 算法吞吐量比较
图6 为两种算法在不同链路故障率下平均延时的对比图。当注入率较低时，由于数据包数量较少，两种算法性能差别不大。随着注入率的增加，在0%链路故障率的情况下，本文算法相比于VMCD 算法，平均延时降低了17.1%。随着链路故障率的增加，本文算法和VMCD 算法的平均延时都会上升，但是本文算法具有路径多样、绕行规则完备的特点，在5%链路故障率时，相较于VMCD 算法，平均延时降低5.8%。
图6 算法平均延时比较
4 结 语
本文提出了一种具有路径多样性的流量均衡容错路由算法。在数据传输的最短路径范围内，该算法能够确定每条可用路径的选择概率，进而实现路由路径的多样性。面对不同位置的链路故障，实施对应的绕行规则，并保证数据包在网络中的路由是无死锁的。实验结果表明，本文算法具有路径多样、转向均衡的特点，故在吞吐量和平均延时方面要优于VMCD 算法。
