一种转向均衡的3D NoC 感知容错路由算法

李 娇， 郭润龙， 蔡 升， 崇云锋， 徐海鹏， 冉 峰

(1. 上海大学微电子研究与开发中心， 上海200444;2. 上海大学新型显示技术及应用集成教育部重点实验室， 上海200444)

利用硅通孔(through silicon vias， TSV)技术实现三维集成电路(three-dimensional integrated circuit， 3D IC)[1]已成为可能， 与之相适应的片上网络 (network on chip， NoC)技术也从二维片上网络(two-dimensional network on chip， 2D NoC)[2]发展到三维片上网络(threedimensional network on chip， 3D NoC)[3]. 3D NoC 可以实现更短的全局互连， 并具有可扩展性， 可提高通信效率， 因此将成为复杂高性能片上系统(system on chip， SoC)中最有效的通信结构. 但芯片复杂度的增加也使得网络链路在通信时出现故障的概率变大， 网络可靠性也随之降低. 因此， 为了保证3D NoC 的性能， 已有研究者提出了容错路由算法[4].

在数据传输过程中， 由于数据包相互等待形成环形会引起网络死锁， 使得数据无法继续传输， 从而降低传输效率及可靠性; 同时死锁会造成数据拥塞导致流量不均衡， 从而引起网络性能下降. 容错路由算法可以解决网络中死锁及流量不均衡的问题， 从而保证网络的性能，因此容错路由算法是提升网络性能的一个研究重点. 为了避免额外的面积开销， 目前解决死锁问题主要采用禁止转向模型法. 在3D NoC 禁止转向模型法中， Dahir等[5]对2D NoC 中的奇偶(odd even， OE)转向模型[6]进行扩展后提出了一种B-OE 转向模型应用于3D NoC 中，并证明了该模型可以避免水平和垂直方向的死锁. Zhou等[7]基于B-OE 转向模型提出了一种低开销容错(low-overhead fault-tolerant， LOFT)算法， 该算法在XY 平面的转向模型中进行4 种行列上的变体， 再分别应用于不同的平面以提高XY 平面的流量均衡性， 但LOFT 中的B-OE 转向模型在垂直方向有多个禁止转向， 且B-OE 转向模型依赖垂直方向的流量负载，不能达到流量均衡， 在很大程度上限制了网络性能. 由此， Zhou等[8]提出了一种NeoOE 转向模型， 该模型在奇偶XY 平面上增加了特定的上下禁止转向， 使垂直方向的流量能达到相对均衡， 但在数据流越来越多的3D NoC中， 其禁止的转向较少且固定， 这势必会影响流量均衡性，造成传输延时的增加及吞吐量的降低， 因此需要设计均衡转向模型以避免死锁， 并提高流量均衡性.

为了解决上述问题， Lei等[9]提出了垂直网格动态感知(vertical-mesh-conscious-dynamic，VMCD)路由算法应用于3D NoC 中， 该算法提高了网络的吞吐量， 降低了传输延迟， 但在不同平面上应用相同的转向模型， 由于转向不均衡从而使得流量均衡性改善不明显. Su等[10]结合VMCD 算法提出了一种容错路由算法， 该算法在VMCD 中增加了水平链路故障模型， 并对每种故障模型制定了相应的容错绕行路径， 同时在网络中应用“一跳预先感知”策略以提高传输效率， 增强了网络的容错能力. 但该算法只考虑了水平边界链路故障， 并没有解决水平链路内部及垂直链路故障， 所以需要设计包含更多故障类型的模型及绕行规则以提高网络的可靠性.

由此可见， 虽然对3D NoC 容错路由算法已开展了很多研究， 但在死锁、流量均衡与故障模型等方面还存在问题. 本工作对这些问题进行了研究， 提出了一种转向均衡的感知容错路由算法. 本算法将3D NoC 中的平面进行奇偶分类， 并提出应用于不同平面的均衡转向模型， 以提高网络的流量均衡性， 进而提升吞吐量并降低传输延迟; 此外， 针对网络中可能存在的链路故障， 提出了水平及垂直方向上边界和内部链路故障模型， 根据奇偶行列制定相应的容错绕行， 从而保证数据传输效率; 最后， 提出“全平面一跳预先感知”策略， 该策略可以同时感知垂直及水平方向连续两跳的故障信息， 使得数据可以提前进入故障绕行路径， 提高了网络容错能力和网络可靠性.

1 均衡转向模型

为了解决3D NoC 中死锁的问题， 在VMCD 算法中将奇偶转向模型与XY 路由应用在 XY ， XZ 和 Y Z 平面， 模型如图 1 所示， 其中 E， W， S， N， U， D， Even 和 Odd 分别代表东、西、南、北、上、下、偶和奇. 先在网络中以资源节点建立三维坐标系， 将E， S 和D 向分别作为X， Y 和Z 坐标轴正向， 从原点出发在各方向每一跳坐标加1， 根据坐标值可将X， Y 和Z 方向分为奇偶行列， 具体奇偶分类已在图中标出; 同时， 在XY 平面上以Z 坐标分为奇偶平面，再以X 坐标分为奇偶列， 在Y Z 平面上以Z 坐标分为奇偶行， 在XZ 平面上以Z 坐标分为奇偶行.

图1 VMCD 算法中的转向模型Fig.1 Turn model in VMCD algorithm

依据上述定义的三维坐标系， VMCD 算法的转向模型在奇XY 平面上偶列禁止ES 和EN转向，奇列禁止SW 和NW 转向，在偶XY 平面上应用XY 路由;Y Z 平面上偶行禁止SD 和ND转向， 奇行禁止 US 和 UN 转向; XZ 平面上偶行禁止 UE 和 UW 转向， 奇行禁止 ED 和 WD 转向. 但该模型在每个平面上都是禁止同样的转向， 当3D NoC 规模不断增大时， 数据永远无法选择被禁止转向路径传输， 造成可传输的路径数目减少， 从而导致流量不均衡而降低网络性能.

为了解决网络中转向固定引起的流量不均衡问题， 本工作提出一种均衡转向模型， 如图2 所示. 首先， 对网络中的奇偶平面与行列进行了新的分类， 即根据X， Y 和Z 的坐标值将网络中的平面分为奇偶XY， XZ 和Y Z 共6 种类型平面. 在奇XY 平面上， 根据Y 坐标分为奇偶行， 在偶XY 平面上， 根据X 坐标分为奇偶列; 在奇XZ 平面上， 根据Z 坐标分为奇偶行， 在偶XZ 平面上， 根据X 坐标分为奇偶列; 在奇Y Z 平面上， 根据Z 坐标分为奇偶行， 在偶Y Z 平面上， 依据Y 坐标分为奇偶列. 然后， 设定了相应的转向模型， 具体转向规则如下: ①在奇XY 平面上， 奇行上禁止EN 和WN 转向， 偶行上禁止SE 和SW 转向;②在偶XY 平面上， 奇列上禁止WS 和WN 转向， 偶列上禁止SE 和NE 转向; ③在奇XZ 平面上， 奇行上禁止 UE 和 UW 转向， 偶行上禁止 ED 和 WD 转向; ④ 在偶 XZ 平面上， 奇列上禁止 UW 和 DW 转向， 偶列上禁止 ED 和 EU 转向; ⑤ 在奇 Y Z 平面上， 奇行上禁止 DS 和 DN 转向， 偶行上禁止SU 和NU 转向; ⑥在偶Y Z 平面上， 奇列上禁止SU 和SD 转向， 偶列上禁止 UN 和 DN 转向.

图2 均衡转向模型Fig.2 Turn balanced model

综上可见， 当3D NoC 规模不断增大时， 均衡转向模型在每种平面上都有不同的禁止转向，不仅可以避免环形路径解决死锁问题， 保证网络的可靠性， 同时还可避免某些转向永远禁止传输数据的情况， 增加了传输路径的选择性， 提升了流量均衡性， 从而提高吞吐量并降低传输延时.

2 故障模型与路由算法

2.1 故障模型与绕行规则

故障模型与绕行规则均是为了提高NoC 路由算法的容错性， 保障当NoC 中出现链路故障时通信可以正常进行. Su等[10]提出的故障模型及绕行规则是3D NoC 路由算法研究中的典型.该模型将XY 平面的边界故障分为8 种类型， 再设置相应的绕行规则， 如图3 所示. 以type 1为例， 其为北边界东向链路故障(即源节点15 到目的节点14 的链路故障)， 此时根据绕行规则，数据由节点15 先向南路由至节点8， 再向东路由至节点9， 最后再向北路由至目的节点14 完成路由， 其余7 种故障类型及其绕行规则在图3 中可见.

图3 无垂直故障模型及绕行规则[10]Fig.3 No vertical fault model and bypass rules[10]

可以看出， 上述故障模型及绕行规则提高了网络的容错能力， 但只解决了XY 平面边界的水平链路故障及其绕行， 而故障可以发生在任意链路， 因此本工作提出了新的故障模型， 本模型对3D NoC 中水平及垂直方向上的边界和内部链路故障均有所考虑， 并对每种链路故障设计了相应的绕行规则. 在容错路由算法中加入本故障模型， 可以保证当链路出现故障时数据能绕行传输， 避免数据拥塞导致死锁， 从而提高数据传输效率， 提高网络可靠性.

本模型根据链路故障的位置分为8 种类型: 在XY 平面根据Y 坐标在行向上分为奇偶东西向， 根据X 坐标在列向上分为奇偶南北向; 在XZ 平面根据X 坐标在列向上分为奇偶上下向; 在Y Z 平面根据Y 坐标在列向上分为奇偶上下向. 如图4 所示， 根据不同的故障制定相应的绕行规则， 具体故障模型分类和绕行规则如下.

图4 优化的故障模型及绕行规则Fig.4 Optimized fault model and bypass rule

type 1: 对XY 平面偶行上东与西向链路故障， 故障绕行先向南路由， 再分别向东与西路由， 最后再向北路由完成绕行;

type 2: 对XY 平面奇行上东与西向链路故障， 故障绕行先向北路由， 再分别向东与西路由， 最后再向南路由完成绕行;

type 3: 对XY 平面偶列上南与北向链路故障， 故障绕行先向东路由， 再分别向南与北路由， 最后再向西路由完成绕行;

type 4: 对XY 平面奇列上南与北向链路故障， 故障绕行先向西路由， 再分别向南与北路由， 最后再向东路由完成绕行;

type 5: 对XZ 平面偶列上上与下向链路故障， 故障绕行先向东路由， 再分别向上与下路由， 最后再向西路由完成绕行;

type 6: 对XZ 平面奇列上上与下向链路故障， 故障绕行先向西路由， 再分别向上与下路由， 最后再向东路由完成绕行;

type 7: 对Y Z 平面偶列上上与下向链路故障， 故障绕行先向南路由， 再分别向上与下路由， 最后再向北路由完成绕行;

type 8: 对Y Z 平面奇列上上与下向链路故障， 故障绕行先向北路由， 再分别向上与下路由， 最后再向南路由完成绕行.

上述设计的绕行路径均是在出现某一故障时， 绕行链路在无故障情形下的最简绕行路径， 若绕行路径出现故障， 数据将同向路由至下一节点再进行反向路由， 从而完成绕行， 因此可避免数据拥塞问题. 以type 1 为例， 当节点15 至节点14 的偶行东向故障时， 首先数据由节点15 向南路由至节点8， 如节点8 至节点9 存在东向故障， 数据将从节点8 向南路由至节点7，再向东路由至节点6， 最后通过向北路由经过节点9 再至节点14; 如节点9 至节点14 存在北向故障， 则数据将从节点9 向东路由至节点10， 再向北路由至节点13， 最后向西路由至节点14;当其他故障类型最简绕行路径存在故障时， 故障绕行与type 1 类似. 因此， 本工作提出的故障模型及其绕行策略可提升数据绕行灵活性， 使网络可靠性大幅提升.

2.2 “全平面一跳预先感知”策略

在3D NoC 中同一数据的传输路径具有多样性， 路径的选择是随机的， 在规模和复杂度增大致使链路故障概率增大的情形下， 如果数据在传输过程中遇到故障链路， 则必须重新选择路径， 这势必影响网络传输效率， 因此在本工作提出的故障模型可以同时解决水平及垂直链路故障的情形下， 提出了“全平面一跳预先感知”策略. 当容错路由算法未加入本策略时， 网络中的路由器仅能感知其周边一跳的链路故障信息并决定下一跳的传输路径， 若根据路由算法决定的第二跳链路存在故障， 且第一跳路径为第二跳故障链路的绕行路径， 此时数据绕行需要回传至第一跳路径的源节点， 从而引起死锁导致数据无法传输; 运用本策略后， 网络中的路由器可以感知其周边连续两跳的链路故障信息， 如果出现第二跳路径存在故障且第一跳路径为绕行路径时， 数据不会完成第一跳路由， 而是直接进入绕行路径完成路由.

本策略可以同时感知水平及垂直方向上连续两跳的链路故障信息， 从而决定所在路由平面连续两跳的方向， 使得数据在传输时可以感知故障信息， 提前绕行故障链路， 不仅可以降低传输延时， 还可以避免死锁， 从而提高网络的可靠性. 以图4(a)中的type 1 具体介绍本策略，在随机选择模式下， 数据由节点8 路由至节点14. 首先数据路由至节点9 或节点15 的概率各为50%， 如果路由器选择下一节点为节点15， 且存在节点15 至节点14 的东向链路故障， 根据绕行规则数据需从节点15 路由至节点8， 此时由于数据回传将导致死锁， 引起网络性能的降低. 应用本策略后， 当数据在节点8 路由之前， 路由器会感知连续两跳的路径是否存在故障， 此时如果感知到节点15 至节点14 的链路故障， 则路由器不再考虑节点15， 而是进入绕行路径，直接由节点8 路由至节点9， 最后再路由至节点14， 可见本策略可避免数据绕行回传造成的死锁问题. 本策略的具体运用如图3 和4 所示， 即图中的回传路径不会出现， 可以有效避免死锁而增加网络传输延时的问题， 进而提高了网络的可靠性.

2.3 路由算法

根据本工作设计的均衡转向模型， 在垂直方向上的路由可在XZ 与Y Z 平面完成， 由于在垂直方向上有更多的转向选择， 可以避免死锁以提升流量的均衡性， 所以本工作提出的算法将数据优先路由至XZ 和Y Z 垂直平面再进行路由. 设网络中源节点坐标为S(x，y，z)， 当前节点坐标为C(x，y，z)， 目的节点坐标为D(x，y，z)， e0 = Dx-Sx， e1 = Dy-Sy， e2 = Dz-Sz.基于上述提出的均衡转向模型， 本工作提出的路由算法规则如图5 所示.

图5 算法流程Fig.5 Algorithm process

具体路由算法规则如下:

(1) 当 e0， e1 和 e2 均为 0 时， 数据无需路由.

(2) 当 e0， e1 和 e2 中有 2 个为 0 时， 根据不为 0 数据的正负向 E， W， S， N， U 或 D 直接路由至目的节点.

(3) 当e0 为0 时， 数据直接根据Y Z 平面的转向模型路由; 当e1 为0 时， 数据直接根据XZ 平面的转向模型路由; 当e2 为0 时， 数据直接根据XY 平面的转向模型路由.

(4) 当 e0， e1 和 e2 均不为 0 时， 若 e0 的绝对值小于 e1 的绝对值， 则数据根据 e0 的正负向东或向西路由至与目的节点在同一个Y Z 平面， 在Y Z 平面根据转向模型路由至目的节点;若e0 的绝对值大于e1 的绝对值， 则数据根据e1 的正负向南或向北路由至与目的节点在同一个XZ 平面， 在XZ 平面根据转向模型路由至目的节点.

本工作提出的算法路由规则中加入了均衡转向模型， 提高了流量的均衡性; 结合故障模型与绕行规则可以避免出现链路故障造成的拥塞死锁问题， 提高了网络的可靠性; 同时将“全平面一跳预先感知”策略加入路由算法中， 可以提前感知故障链路并进行绕行， 从而提升传输效率. 本工作提出的容错路由算法提升了流量均衡性， 从而降低了传输延时， 同时可以避免死锁，提高了网络可靠性.

3 实验结果与分析

为了验证本工作所提出的算法， 采用由二维仿真器Noxim 扩展而来的三维仿真器Access Noxim 对算法进行仿真验证. Access Noxim 是一种基于 System C 的 3D NoC 专用仿真器， 具有代码开源、扩展性好等特点， 仿真器的配置参数如表1 所示. 将加入本工作提出的故障模型及绕行规则的VMCD1 算法和本工作提出的算法分别通过Access Noxim 进行仿真验证， 同时在网络中分别随机选取0%， 4%， 7%的水平和垂直链路故障， 对比仿真结果验证随故障率增加时的算法性能.

表1 仿真器参数配置Table 1 Configuration of simulator parameters

图6 为VMCD1 变形算法和本工作提出的算法在不同链路故障率情形下吞吐量与注入率变化的对比. 从图6(a)可以看出， 当两种算法不存在链路故障时， 本算法相对VMCD1 变形算法吞吐量有16.2%的提升; 在图6(b)中， 当网络中链路故障率增加时， 本算法在吞吐量方面也明显优于VMCD1 变形算法. 这是因为本算法使用均衡的转向模型， 使得链路中的流量均衡，降低了拥塞度. 图7 为VMCD1 变形算法和本工作提出的算法在不同链路故障率情形下平均延时与注入率变化的对比.

图6 算法吞吐量比较Fig.6 Algorithm throughput comparison

图7 算法平均延时比较Fig.7 Algorithm average delay comparison

在无链路故障下， 当注入率达到0.15 时平均延时基本稳定， 本算法相比VMCD1 变形算法平均延时有3.6%的降低. 在网络中出现链路故障下， 当注入率达到0.3 时平均延时基本稳定，且当故障率增加时， 本算法在平均延时上有明显的优势， 相比VMCD1 变形算法平均延时降低了11.8%. 从图中可看出， 当故障率增加时， 本算法传输延时比无故障时有所降低， 这是因为出现故障时数据选择绕行路径传输， 此时不受禁止转向的限制， 路径跳数有减少的可能性， 所以传输延时有所降低， 但吞吐量是随着故障率增加而下降的.

4 结束语

本工作提出一种转向均衡的感知容错路由算法， 在复杂的网络中通过对不同平面禁止不同的行列转向， 在避免网络死锁的同时有了更均衡的转向， 进而流量均衡降低了数据传输延时并提高了网络的吞吐量; 本工作提出的故障模型及绕行规则解决了网络中水平和垂直方向上的边界及内部链路故障， 提高了网络的可靠性; 同时， 运用“全平面一跳预先感知”策略提高了传输效率. 实验结果表明， 本工作提出的算法具有转向均衡的特性， 能有效降低传输延时并提高网络吞吐量， 在有链路故障时， 本算法的性能仍然优于加入本工作提出的故障模型的VMCD1 算法.