三维片上网络(3D NoC)热感知路由算法研究

刘玉玲， 宋国治

(天津工业大学 计算机科学与技术学院 天津 300387)

0 引言

片上网络是片上系统的一种较新的通信方式，与传统的基于总线的通信方式相比，具有显著的优势。片上网络是将大量的IP集成在单个硅芯片中[1]，这为数据包传输提供了路径多样性，减少等待时间，解决布线复杂性。

为了使网络中IP核之间具有较低的连接长度，从而降低功耗、增加数据包路由的灵活性，以及具有更高的映射密度[2]，基于硅通孔(through silicon via，TSV)的三维片上网络(three-dimensional network on chip, 3D NoC)逐渐兴起[3]，如图1所示。

图1 全连接的3D NoC

由于堆叠结构，3D NoC在高工作频率下，它的高集成度导致了大的功率密度和高的系统温度，也可能会出现局部过热节点，散热不平衡影响着芯片性能和可靠性。在之前的研究中，针对TSV提出了很多不同的热管理方案，包括技术解决策略，如微通道流体冷却[4]、TTSV[5]等，以及算法架构解决策略，如动态热管理和智能分组路由。由于技术解决策略会降低可靠性、增加额外的制造成本等，在本文中我们只考虑算法架构的解决策略。

TSV的嵌入也会带来一些可以预见的问题，如由于制作材料的热膨胀系数不同，3D-IC在制造过程中会承受热应力向机械应力的转换[6]。此外，两层之间的温度变化会对时间相关的介电击穿和热循环产生负面影响[7]。而且，电迁移[8-9]会增加导体的电阻，进而增加通信延迟。总而言之，采用大量的TSV会降低可靠性，增加制造成本并造成面积开销[10]。为了解决这一问题，部分连接的3D NoC(图2)成为研究热点。

图2 部分连接的3D NoC

在我们的研究中，假设散热器位于整个结构的最上层，引入A*算法并对其改进后应用于3D NoC平面路由，A*算法能够保证跨过节流节点找到一条最短路径。

1 相关工作

由于3D NoC的堆叠结构会造成散热不均衡，以及热感知3D NoC的拓扑结构在某些节点受到限制的情况下会发生改变，产生非平稳不规则网格NSI-Mesh[2]，从而导致系统性能快速下降，本文考虑通过在节点处配置节流阀使得过热节点节流，从而使温度保持在可行范围内。而对于产生的NSI-Mesh，学者们提出了很多解决的方法。比如为了在3D堆叠结构中提供有效的导热路径，提出了一种热敏垂直节流(TAVT)方案[11-12]，并在文献[12]中进一步改进，提出了一种简化的TAVT方案。该方案假设散热器位于顶层，底层离散热器最远，可将底层的节点设置为非节流节点，因此，底部逻辑层中的通道可用作旁路路径。这种方法在底层逻辑层中导致了沉重的通信负载，3D NoC网络性能快速下降。为了在NSI-Mesh中成功传送数据，文献[12]还提出了传输层辅助路由(TLAR)方案。进一步，又提出传输层辅助路由-向下横向确定性路由(TLAR-DLDR)、传输层辅助路由-向下横向自适应路由(TLAR-DLAR)、传输层辅助路由-向下横向自适应确定性路由(TLAR-DLADR)。但是为了防止数据包在节流节点中被阻塞，在将数据包发送到网络之前，需要先检查存储在传输层拓扑表(TT)中的节流信息，节流信息需要在每次拓扑更改时更新。整个过程有时间耗费，造成一定的弊端。

2 A*算法与改进后的高效寻径A*算法

2.1 A*算法

如图3，绿色方块是起点A，红色方块是终点B，蓝色方块是中间的障碍，不可通过，假设从A点到B点，在A*寻径算法中，从点A开始检查相邻方格，向外扩展直到找到目标。在A*算法中，设置了“openlist”和“closedlist”两个列表来存放节点。路径是通过反复遍历“openlist”并且选择具有最小F值的方格来生成的。

图3 寻径方格平面展示

图4展示了A*算法寻找路径的一个示例。对G值设定：令水平或垂直移动的耗费为10；对角线耗费为14。使用曼哈顿方法计算H值：从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。图4中黄色方格即是A*算法寻得的路径。

图4 A*算法寻径

2.2 改进的A*算法

在传统的A*算法中，路径可以沿着对角线方向移动，所以每个格子共有8个相邻格子，而在实际的3D NoC平面中，节点互连只有北(N)、东(E)、南(S)、西(W)4个方向，也就是每个节点只有4个相邻的节点，而对于G值的设定，为了达到温度感知的效果，选择出较冷路径，将其设定为节点温度，温度越低，G值越小，意味着更好的路径。在A*算法中，对于一个新的格子，如果它已经在“openlist”中，以G值为参考检查新的路径。G值更低就把这一格的父节点改成当前格，并且重新计算这一格的G值和F值。此处，显然不适用于3D NoC的热感知寻径，因为如果G值表示温度，当某个相邻节点已经在“openlist”中时，若它正好作为最小F值出现，则没有必要检查新的路径是否更好。温度不同于路径代价，不考虑简单叠加，选择新的路径无疑只是增加了传输跳数，反而致使延迟，因而考虑直接选择该节点的初始父节点到该节点为路径，我们用图5～7来详细说明。

图5 改进的A*算法寻径过程

图5中蓝色箭头表示第一次寻径过程，到第三跳时发现回到了源节点的相邻节点，舍弃该路径，直接从源节点发送到该相邻节点，即红色箭头路径，按照A*算法，在寻找F值最小路径的时候，有可能会出现红色箭头所示的错误路径，一旦发现错误，马上逐步退回，在“openlist”中寻找F值次之的合适路径，即图5中绿色路径。显然，我们的算法在保证温度和较短路径的同时，在延迟方面体现了一定的弊端。

图6显示了我们使用改进的A*算法进行寻径最终得到的一条路径。我们可以进一步考虑将寻径过程限制在以源节点和目的节点连线为对角线的矩形框内，这样可以进一步减小传输延迟，如图7所示。

图6 改进的A*算法寻径结果

图7 限制范围后的改进的A*算法寻径结果

3 全连接的3D NoC基于节流阀的高效热感知A*路由算法

在全连接的3D NoC中，为了保证系统温度最低，根据散热器的位置来选择水平与垂直路由的优先顺序，考虑源节点与目标节点所在平面哪个更靠近散热器，在更靠近散热器的平面内进行平面路由。记源节点S(x0,y0,z0)、目标节点D(x1,y1,z1)。需要考虑源节点与目标节点是否节流，若源节点节流，延迟发送数据包；若目标节点节流，则在上一跳等待。全连接的3D NoC路由算法描述如下。

第一步 检查源节点是否节流。

第二步 若源节点节流，延迟发送数据包，反之，进行第三步。

第三步 比较z0、z1。

若z0

若z0>z1，说明源节点所在平面更靠近散热器，考虑优先进行平面路由，在源节点所在层使用改进后的A*算法将数据包发送到目标节点在该平面内的映射节点所在位置，再通过垂直TSV将数据包路由到目的节点。

若z0=z1，说明源节点与目的节点在同一层而不需要垂直方向上的路由，所以直接在二维平面上使用改进后的A*算法进行数据包路由即可。

图8展示了在全连接结构中源节点更靠近散热器时的路由选择。图9展示了在全连接结构中目的节点更靠近散热器时的路由选择。

图8 在全连接结构中源节点更靠近散热器时的路由路径

图9 在全连接结构中目的节点更靠近散热器时的路由路径

4 非全连接的3D NoC基于节流阀的高效热感知A*路由算法

对于非全连接的3D NoC，数据包如何选择合适的垂直通道进行传输是关键，为了使数据包能够快速找到最合适的TSV进行垂直传输，使每一个节点路由器存储8个存储位的位置信息[10]，这8个存储位分别用来存储每个节点8个方位上的TSV信息，分别是北(N)、东(E)、南(S)、西(W)、东北(NE)、西北(NW)、东南(SE)、西南(SW)，存储值分别是当前节点各个方向上与之相邻最近的TSV的最短跳数，如图10所示。这样更加方便地找到距离各个节点最近的TSV。

图10 节点M的8个存储位表示

非全连接的3D NoC路由算法描述如下。

第一步 检查源节点是否节流。

第二步 若源节点节流，延迟发送数据包，反之，进行第三步。

第三步 比较z0、z1。

① 若z0>z1，说明源节点所在层更靠近散热器。

a)将目的节点映射在源节点所在平面。

b)寻找距离目的节点的映射节点最近的健康TSV。根据该映射节点的8个存储位[N,E,S,W,NE,NW,SE,SW]，存储数字为距离该映射节点的最短跳数，选择跳数最短的节点作为目标节点发送数据包，当数据包到达此节点判断TSV是否健康，若不健康马上查找此节点的8个存储位，继续寻找最近的健康TSV。

c)在平面内使用改进的A*算法将数据包路由到TSV所在节点。

d)若垂直路由数据包没有到达目标层，则根据该节点的8个存储位寻找距离该节点最近的健康TSV，重复此步骤，直到将数据包发送到目标层。

e)使用改进的A*算法进行平面路由，将数据包发送到目的节点。

② 若z0

a)寻找距离源节点的映射节点最近的健康TSV，并重复①中的c)～e)。

③ 若z0=z1，说明源节点与目的节点在同一层而不需要垂直方向上的路由，所以直接在二维平面上使用改进后的A*算法进行数据包路由即可。

图11展示了在非全连接结构中源节点更靠近散热器时的路由选择。图12展示了在非全连接结构中目的节点更靠近散热器时的路由选择。

图11 在非全连接结构中源节点更靠近散热器时的路由路径

图12 在非全连接结构中目的节点更靠近散热器时的路由路径

在此处，考虑到死锁问题，将电梯设置为独立的上行电梯和下行电梯，靠近散热器的方向记为正，反方向记为负。8个存储位中正负号标记上下行方向，如果目标节点在远离散热器的方向，即选择下行优先，在8个存储位中挑选绝对值最小的负值；反之，则挑选值最小的正值。此处，数据包路由过程中不会形成闭环，故不会产生死锁。

5 实验结果和讨论

为了验证我们所提出算法的优势，使用提供协同仿真和3D配置的AccessNoxim 3D NoC仿真器进行实验。AccessNoxim是用于3D NoC系统的联合仿真平台，它将网络模型、功率模型和热模型耦合在一起。将Noxim和HotSpot集成在一起，并采用英特尔80核处理器的功耗模型。Noxim是周期精确的SystemC NoC仿真器，而HotSpot提供了体系结构级的热模型。

本文配置的仿真参数如下：包大小为8 flits，通道缓存大小为8 flits，NoC为8×8×4的规模，包注入模式遵循泊松分布。

使用4种热感知路由算法与本文提出的改进的A*热感知路由算法进行对比，仿真结果热图如图13～17所示。

图13 向下路由算法产生的四层热分布图

图14 TLAR-DLDR路由算法产生的四层热分布图

图15 TLAR-DLAR路由算法产生的四层热分布图

图16 TLAR-DLADR路由算法产生的四层热分布图

图17 改进的A*路由算法产生的四层热分布图

从图13～17可以发现，与已有的热感知路由算法相比，我们提出的改进后A*算法在降低系统温度方面处于更有利的地位，温度分布更均匀，且系统温度整体更低。

6 结论

本文提出了一种新颖的三维片上网络热感知路由算法，不仅适用于全连接的3D NoC，也适用于部分连接的3D NoC。与以往的工作相比，不会造成局部拥塞，而且不需要借助任何辅助。通过合理的算法优先选择了最短且最冷路径，使系统温度保持在最低，与此同时，也不会造成额外的系统开销。一旦系统中出现链路故障，可以避开障碍，该算法具有很强的健壮性。本文也简要地给出了解决死锁问题的方法，具有一定的创新性与研究意义。

但是在寻求最冷条件下的最短路径时，可能会增大传输延迟。后续工作将继续改进算法使得系统性能进一步提升。