基于3D NoC 架构上的自适应路由算法设计与仿真

苏 新，程 军，刘 俞

（1. 马鞍山职业技术学院 电子信息系，安徽 马鞍山 243011；2. 巢湖学院 信息工程学院，安徽 合肥 238000）

0 引言

在电子通讯、多媒体处理等许多领域，片上系统（system-on-chip，SoC）将运算、存储、通信、输入输出等功能集成在一起，提供了一种有效的解决方案。伴随着半导体工艺的进步，集成度和复杂度不断提升，数以百计的处理器被集成到单个芯片上，而对于基于共享总线通信架构的SoC，地址资源限制了功能模块的扩展、线上延迟增加了全局时钟树的设计难度、共享总线通信机制降低了通信效率，SoC 的发展遇到了瓶颈。于是业界提出了一种新的通信架构：片上网络（network-on-chip，NoC）［1］，它借鉴了计算机网络互联的思想，引入了分布式处理和并发通信技术，可有效提高通信效率，近年来成为研究热点。

NoC 拓扑结构主要有二维拓扑结构（2D NoC）和三维拓扑结构（3D NoC），3D NoC 将不同电路单元制作在多个平面晶片上，通过硅通孔层间垂直互连技术（through-silicon-via，TSV）实现层间垂直堆叠互连，可以有效降低功耗、提高带宽、增加集成度，因此3D NoC 将成为未来的发展趋势。目前主流的3D NoC 拓扑包括3D Mesh、堆叠3D Mesh 和纤毛3D Mesh［2］。

路由算法是NoC 研究的关键技术之一，其设计依赖于网络的拓扑结构。NoC 路由器运行路由算法，做路由决策，通过多个路由器可将数据包从源节点传送到目标节点。路由算法的设计，对优化网络性能、提高系统吞吐量、降低功耗开销都是非常有效的。DOR 算法［3］是传统确定性路由算法的代表，数据包依次沿X轴、Y轴、Z轴到达目标节点所在的维度。DOR 算法思想简单，当网络负载较低时，使用该算法非常有效，但在网络负载较高时，网络的吞吐率低，传输时延长。Wang 等［4］提出了一种3D 轮转路由算法，数据包先沿着Z轴的TSV 链路路由到目标节点所在层，在层内传输时，通过路由器内设置的翻转标志的修改，平均分配X轴和Y轴的流量，在一定程度上可实现网络流量分流，提高网络吞吐量。RPM 算法［5］在Mesh 网络阶数为偶数时实现了最优的最坏情况网络吞吐率，且具有良好的平均网络吞吐率。USM 路由算法［6］在Mesh 网络阶数为奇数时实现了最优的最坏情况下的网络吞吐率，但传输延时较高。

本文提出了一种3D Mesh 结构上的输出输入自适应路由算法（output input adaptive routing algorichm，OIARA）。本算法在当前节点全局上，根据7 个输入端口内待处理数据包对输出端口的需求程度作为优先级参数，优先选择需求程度最少的输出端口，再在竞争该输出端口的数据包集合内授权总跳数最小的数据包。

1 相关工作

1.1 3D Mesh 拓扑结构

3D Mesh 拓扑结构是三维片上网络最基本、最简单的拓扑结构，其在2D Mesh 结构基础上将各层之间通过TSV 链路连接拓展而形成3D Mesh 结构，图1 为一个3 × 4 × 4 的3D Mesh 结构。3D Mesh 结构由于其具有扩展性好、结构简单以及易实现等优点而被广泛使用。

1.2 路由器体系结构

路由器是片上网络非常重要的组成部分（见图2），路由器内部通常包括路由逻辑模块Routing Compute（RC）、仲 裁模块Arbiter、交叉开关CrossBar、输 入 端口Input Ports、输出 端 口Output Ports 和寄存器等。路由器配置7 个输入端口和7 个输出端口，每个输入端口配置2 个虚拟通道VC，以避免死锁，每个虚拟通道容量等于整数个微片尺寸；7 × 7 交叉开关在输入端口和输出端口之间建立通信链路；RC 模块收集信息，执行路由算法，做路由决策；仲裁模块功能包括虚拟通道仲裁VA 和交叉开关仲裁CA，VA 阶段负责授权一个输入端口，传输该端口上VC 内的数据包，被选中的VC 优先传输数据，同时，多个输入端口选出的虚拟通道也存在对同一输出端口的竞争，输出端口的选择在仲裁器的CA 阶段完成。

图1 3×4×4 3D Mesh 拓扑结构Fig.1 3×4×4 3D Mesh topology

图2 路由器体系结构Fig.2 The architecture of the router

1.3 坐标系统与方位

图1 所示的3D Mesh 结构中，示意了本文算法所依据的坐标系统。同时路由器体系结构中，数据包可被路由方位包括东、南、西、北、上、下以及本地7 个方向，坐标系统与方位的映射关系如表1 所示。

表1 坐标系统与方位映射关系Tab.1 The mapping relationship between coordinate system and position

1.4 相关定义

结合本文所提路由算法，对算法中涉及的相关概念、引用作以下规定：

定义13D NoC 中每个节点地址用三元组（Z，X，Y）标记，其中Z表示节点所在的层，X、Y表示层内二维坐标。

定义2输入端口内数据包的目标节点（Zd，Xd，Yd）相对于当前节点（Zc，Xc，Yc）的曼哈顿距离称为总跳数top，记为

这里，规定如果某个输入端口没有接收到任何数据包，则将对应的目标地址用(∞,∞,∞)表示，那么7 个输入端口待处理数据包的总跳数可以构成一个长度为7 的一维数组top［7］。

定义3用一个7 × 6 的矩阵表示7 个输入端口内待处理数据包，按照靠近目标节点的原则，所可能走的6 个方向称之为方向矩阵Direct。

说明：对于Direct［i］［j］元素，i表示输入端口，j表示可选方向。若元素值为1，表示数据包从第i个输入端口，可以走j方向靠近目标；若元素值为0，表示数据包从第i个输入端口，不可以走j方向靠近目标；若元素值为-1，表示第i个输入端口没有待处理数据。表2 所示为数组的行坐标与输入端口映射关系，表3 所示为列坐标与方向的映射关系。

表2 行坐标与输入端口映射关系Tab.2 The mapping relationship between row coordinates and input port

表3 列坐标与方向的映射关系Tab.3 Teh mapping relationship between column coordinates and output port

例如，图3 所示的案例中，第4 行表示West 输入端口，其列坐标0，1，4 上元素值为1，表示该数据包可以被路由到Up、Down、North 3 个方向；第7 行元素值全为-1，表示Local 端口上没有待处理的数据包。

图3 Direct数组案例Fig.3 Directarray case

2 OIARA 算法设计

2.1 算法总体思路

路由器在做路由决策前，路由节点的仲裁模块需要授权输入端口，并选择输出端口，对于输入端口的授权，DOR 算法以及大部分算法采用了时间片轮转［7］的方法，输出端口选择有维序法［3］（如DOR 算法）、随机法（如DPT 算法［7］）等。

本文算法从当前路由节点全局考虑，在仲裁模块授权输入端口和选择输出端口时，都采用优先级确定。根据当前节点所有端口内数据包对输出端口的需求程度情况，需求越高表示该端口竞争越大，在选择输出端口时，优先选择需求程度低的端口输出；然后在竞争选中的输出端口数据包集合内，授权总跳数最小的数据包来传输，如此可以在交叉开关内为授权的输入端口和选择的输出端口建立链路，传输数据，总跳数用定义2 中的曼哈顿距离来表示。算法在对输入端口授权以及输出端口选择时，采用贪心算法思想，每次选出的都是需求程度最不迫切的输出端口和总跳数最小的数据包，可以尽快处理网络内积压的数据包，提高网络整体吞吐量。

2.2 算法实现

本算法分为两个阶段，第一个阶段是对数据结构初始化，主要包括总跳数数组top和方向矩阵Direct；第二个阶段负责在7 个输入端口中授权其中一个端口并匹配一个输出端口。如此可以在路由器交叉开关内建立传输链路，将授权的输入端口内数据包传送到输出端口。算法的主要伪代码如下：

2.3 举例

假设在一个4 × 4 × 4 的3D Mesh 结构中，当前路由节点的坐标是（2，1，2），路由器的上、下、东、西、北、南以及本地7 个输入端口中的数据包目标地址分别是（0，1，3），（∞，∞，∞），（3，2，1），（1，2，3），（2，1，2），（2，2，3），（0，2，0），即下方输入端口没有数据包，北方输入端口和本地端口地址相同，表示当前节点就是目标节点，不考虑算法执行过程中有新数据包到达，那么根据本算法思路，在对top数组和Direct数组初始化后，其中top［4］= 0，即北输入端口输入的数据包目标节点是本地，优先路由到本地节点处理，此时output = 6，input = 4；第二个数据包处理时，根据Direct数组统计得到的count数组中，count［0］= 1 最小（不含等于0），因此output = 0，选择Up 输出端口，而竞争Up 输出端口的数据包只有一个，即East 输入端口，因此input = 2，依次类推，可得当前路由节点处理数据包的顺序见表4。

表4 案例处理结果Tab.4 The result of case processing

2.4 死锁避免

自适应路由算法容易造成死锁，当多个数据包在网络中传输时，可能因为包的传输路径形成环，彼此等待对方释放资源却又各自占有资源从而导致死锁［8］。文献［9］使用了在双虚拟通道中添加不同的传输方向限制避免死锁，本文算法基于双虚拟通道路由器，引入双虚拟通道技术解决死锁。如图4 所示，在一个平面上，数据包A 的两个微片A1、A2 分别占用了路由器R1 的南输入端口和东输出端口的其中一个虚拟通道缓存，数据包B 的两个微片B1、B2 分别占用了路由器R2的西输入端口和南输出端口的其中一个虚拟通道缓存，数据包C 和数据包D 也是类似的情况，但此时由于引入了虚拟通道技术，一条物理通道被划分成两条逻辑通道，数据包分时复用物理通道，在每一个端口还有一个虚拟通道缓存可以使用，从而使4 个数据包都可以继续传送。

图4 双虚拟通道技术解决死锁Fig.4 Double virtual channel for solving the deadlock

3 仿真结果与分析

3.1 仿真环境

本文算法模拟实验采用了基于System C 语言开发的仿真器Nirgam［10］。从芯片面积和死锁两方面综合考虑，实验中路由器使用双虚拟通道路由器，每个虚拟通道的深度是8，宽度为32 bits，即1 个微片的尺寸，每个数据包划分成8 个微片，实验模型为4 × 4 × 4 3D Mesh 结构，分别在两种不同的流量模式下：热点注入模式和均匀注入模式，调节数据包的注入率。通过OIARA 算法与DOR算法、文献［4］的3D 轮转算法相比对，以平均时延和吞吐率两个片上网络的重要指标作分析。

3.2 数据包结构

实验使用虫孔交换机制，每个数据包分成8 个微片，每个微片尺寸为32 bits，微片包括头微片Head、体微片Body 和尾微片Tail，头尾片中由微片类型、数据包id、微片id，到目标节点的距离Top，目标节点的坐标等字段组成，如图5 所示，路由算法只根据头微片的信息计算路由，体微片和尾微片沿着相同的路径传输。

图5 数据包格式Fig.5 Format of the data packet

3.3 平均时延

一个数据包的时延是指数据包从注入到源节点开始到被目标节点接收所经历的时间T，主要由数据包在链路上的传输时间Ttransport、数据包在节点内排队时间Twait和数据包的发送时间Tsend组成，即T=Ttransport+Twait+Tsend，其中Tsend忽略不计。仿真时间内所有数据包时延的平均值为整个网络的平均时延［11］，平均时延越小，表明网络性能越好，平均时延大，表示数据包等待时间长，网络可能产生拥堵。

图6 所示在均匀流量注入模式下，在注入率较低时，本算法和DOR 算法及3D 轮转算法平均时延相差不大，当注入率达到0.012，网络内微片数量增多，DOR 算法先沿某个方向走完再转向，处理数据微片开始显得乏力，在注入率超过0.016 后，由于本算法和3D 轮转算法基于了分流的思想，平均时延明显低于DOR 算法。图7 显示了在热点模式下的仿真结果，在网络中随机选择8个节点作为热点注入数据包，由于网络内在局部迅速产生大量微片，DOR 算法难以快速解决，本算法能够从多个方向分流，也略优于3D 轮转算法，最好情况下可以从7 个不同的方向输出，减少了排队等待的时间，平均时延更低，但是因为网络局部范围内迅速出现大量数据，造成拥堵的触发点提前了。

图6 均匀流量模式下平均时延对比Fig.6 Comparison of average delay in uniform traffic mode

图7 热点流量模式下平均时延对比Fig.7 Comparison of average delay in hot traffic mode

3.4 网络吞吐率

网络吞吐率体现了网络承载数据的能力［11］，用每个节点在每个时钟周期内传输微片的数量来度量［9］，公式为其中Li表示第i个数据包的长度，N为网络的总节点数，T是仿真时间，单位是时钟周期。网络吞吐率的单位是flit/cycle/node。

图8和图9分别是均匀模式和热点模式下吞吐率的对比，可以看到，本算法可以从7 个方向分流，3D 轮转算法则是在层内传输时轮转，因此本算法吞吐率略高，当注入率达到一定值后，本文方法的吞吐率明显高于DOR 算法

图8 均匀模式下吞吐率对比Fig.8 Comparison of throughput in uniform traffic mode

图9 热点模式下吞吐率对比Fig.9 Comparison of throughput in hot traffic mode

4 结语

本文针对3D Mesh 结构，不考虑节点故障和链路故障，提出了一种自适应的路由算法OIARA，算法在处理数据包时可以从多个方向分流，同时每一步路由决策基于贪心算法思想保持当前节点状态下最优。仿真结果可以看到，OIARA 算法在网络平均时延和网络吞吐率两个重要的NoC 评价指标方面，都优于传统的维序算法。