混合无线三维片网中无线路由节点分布研究*

丁盼盼，宋国治+，赵成龙，周一杰

1.天津工业大学 计算机科学与技术学院，天津 300387

2.史蒂文斯理工学院 计算机科学学院，美国 霍博肯07030

1 引言

目前，科学技术的发展非常迅速，芯片的集成度越来越高，片上系统（system-on-chip，SoC）中的功能单元数量越来越多，如何在这些功能单元之间进行通信已经成为一个重要的课题。传统的共享总线体系结构[1]由于其固有的可扩展性和较低的通信效率已经不能满足当前SoC设计的需要。而片上网络[2-4]（network-on-chip，NoC）作为替代结构出现。

片上网络作为复杂SoC 的一种新的互联与通信架构[5]，当规模越来越复杂时，其自身所存在的功耗和延时问题严重限制了SoC 性能的进一步提升。传统片上网络中远距离传输会带来高延迟高能耗等问题，扩展性、空间等问题也是巨大的挑战。为了缓和NoC 中复杂的通信问题，人们提出了一些新的互连结构，如3D片上网络[6]、片上光网络[7]、无线片上网络[8]（wireless network-on-chip，WNoC）。

因为片上微型无线天线技术的实现，使得片上网络的内部可以实现无线通信。混合无线片上网络正是基于这一技术和为解决高集成度带来的高功耗和高延迟难题而提出的新型的技术[9]。无线片上网络作为其中一种新型的互连结构己经受到了广泛的关注，已经有很多人提出了各种类型的WNoC 并进行研究。研究界提出无线片上网络WNoC，希望用无线连接代替有线连接，在NoC节点间插入某种更快的传输信道，增加NoC节点的传输范围，减小多核系统中信息传输路径的跳数，达到减小系统延时和能耗，增加系统吞吐率的目的，进一步提高系统整体性能。

本文提出了一种正六面体的混合无线片上网络架构。在这个正六面体的结构中，将无线节点放置在正六面体的顶点上。在本文提出的正六面体的拓扑结构中，存在无线节点的层间消息传送就可以依靠无线路由器进行快速的数据包的传输。同时，对传统的XYZ 路由算法进行了改进，使改进后的路由算法适应于此正六面体无线片上网络架构。

2 拓扑结构

NoC 的拓扑结构决定了网络的物理布局及节点和通道之间的连接。拓扑结构的设计对WNoC的网络延迟、功耗、吞吐能力等性能指标均有直接的、重要的影响。无线NoC的拓扑中除了有线节点、链路的布局和互连方式外，其无线节点的数目、链路的放置以及信道的分配[10]对无线NoC的性能影响也至关重要。

文献[11]中，Zhao 等人提出了一个基于Mesh 结构的纯无线WNoC。在该结构中，所有的节点均为无线节点，任意两个相邻节点均通过无线链路通信，从而形成了一个无线的二维Mesh 结构。由于该WNoC是一个纯无线网络，因此节点之间的通信采用无线多跳的方式，从而导致整个网络的面积开销和功耗大大增加。文献[12]为了解决在不同模块之间进行芯片互联信号的传输问题，提出了一个混合无线片上网络结构。该结构是将二维片上网络结构分成四个子网，并在每个子网的中心位置放置无线节点。该结构随着网络规模的逐渐增大，子网内部通信的路由距离也随之增大，因此会造成一定程度的延时。哈尔滨工业大学吕鹏提出了一种2-Level Hybrid Mesh结构[13]，其是将整个有线Mesh 划分成3×3 的子网，并将每个子网中心位置的节点换成无线节点。因此，它包含了一个下层有线Mesh和一个上层无线Mesh。虽然该结构降低了网络延时和拥塞水平，但会造成一定的面积开销。文献[14]介绍了一种多级网状拓扑结构，称为MLM（multi-level mesh）的NoC 拓扑结构。如果令最下层的Mesh为有线Mesh结构，而其余的上层Mesh为无线Mesh结构，就可以得到一个基于MLM结构的混合WNoC。该结构中虽然无线节点分布比较均衡，能够缩短节点间数据包传输的距离，但当该结构中无线Mesh 的层数过多时，无线节点数量的增长会导致网络的功耗增加。在该拓扑结构的基础上，提出将有线Mesh层和无线Mesh层交替形成一个4层的混合无线拓扑结构，对每一层进行子网的划分，并在无线Mesh 层的各个子网的中心放置一个无线路由节点。通过改变无线路由节点的位置（无线节点的摆放位置有6种情况，分别为第0层和第1层、第0层和第2层、第0层和第3层、第1层和第2层、第1层和第3层、第2层和第3层）进行仿真实验，结果表明在4层的混合无线NoC结构中，将无线节点均匀地放置在第0层和第3层的性能最优，此时无线路由节点的摆放位置恰好构成了正六面体的8 个顶点。在整个网络中，无线节点的数量处于较低的水平，因此网络的面积开销和功耗可以得到有效的控制，使其保持在合理的范围之内。

本文提出的是一个含有无线路由节点的8×8×4的混合无线片上网络结构。在Noxim仿真器中现有的拓扑结构基础上增加无线路由节点和无线连接构成正六面体结构，使其可以应用到混合无线片上网络中。NoC的互联结构如图1所示。从中可以看出一个NoC系统由处理单元（processing element）、网络接口（network interface，NI）、路由器（router）和数据通道组成，其中含有无线路由节点的Mesh结构如图2所示。

Fig.1 Composition of NoC interconnection architecture图1 片上网络互联结构的组成

Fig.2 Mesh structure with wireless routing nodes图2 含有无线路由节点的Mesh结构

定义节点坐标为N（x,y,z）。其中第0 层和第3 层的节点坐标分别为（2,2,0）、（5,2,0)、（2,5,0）、（5,5,0）、（2,2,3）、（5,2,3）、（2,5,3）、（5,5,3），这8 个节点均为无线节点，分别记为WR0～WR7。该混合结构的中间两层不存在无线节点，拓扑结构如图3所示。

3 路由算法

Fig.3 Topology of 4 layer hybrid wireless NoC图3 4层混合无线片上网络的拓扑结构

目前，对于三维片上网络的研究[15]主要集中在底层元器件、拓扑结构和路由算法三方面，其中以拓扑结构与路由算法的关系最为密切。一个优秀的路由算法可以充分发挥出拓扑结构的性能，而一个优秀的拓扑结构也可以使路由算法设计更加简单有效。在片上网络和无线片上网络中，路由算法根据不同的分类标准分成不同的类别[16]。

在确定了WNoC 拓扑结构后，路由算法决定一个消息或者一个数据包从源节点传输到目标节点的路径。路由算法应该基于网络的拓扑结构，以合适的方式分布数据流，使得网络中的数据流能很好地得到平衡，同时使网络的延迟和吞吐量得到改善。

基于本文所提出的混合无线片上网络拓扑结构，传统的XYZ 路由算法显然不适合该架构下的节点之间的数据包的传递[17]。因此给出了一种由维序XYZ 路由算法改进而来的，可以和本文提出的混合无线片上网络架构相匹配的新型路由算法：WXYZ算法。在本文提出的WXYZ路由算法中，结合正六面立体结构的对称性[18]，设立规则：无线路由节点之间只能在Z轴方向进行数据传输，算法流程如图4所示。

WXYZ路由算法将有线传输与无线传输结合起来，实现了无线的高带宽通信和无线传输的单跳低延迟特性[19]。这对降低功耗，提高片上网路的整体性能具有至关重要的作用。

算法具体描述如下：

Fig.4 Flow chart of WXYZ routing algorithm图4 WXYZ路由算法流程图

（1）判断初始节点（S）和目的节点（D）是否在同一子网Mesh 中。如果在同一子网中，则用传统的维序XY 路由算法，将初始节点的信息传递到目标节点。XY 路由算法的具体过程是：先沿X方向将数据发送至目标节点所在的列；再沿Y方向将数据发送至目标节点所在的行。这种算法很简单地解决了不同维度上的死锁。若不在，执行（2）。

（2）假设S和D不在同一个子网中，计算初始节点与目标节点之间的Z轴坐标之差是否大于1，即通过初始节点和目标节点的Z轴坐标之差得到。若层数之差大于1 执行第（3）步，若层数之差等于1，则通过传统的维序XYZ路由算法将初始节点的信息传递至目标节点。子网内部的通信通过有线链路来完成。XYZ 路由算法是在XY 路由算法的基础上增加了Z轴方向的数据传输，属于静态路由选择策略，实现简单且开销较小。

（3）对于初始节点和目标节点层数之差大于1的情况，先找到距离初始节点最近的无线路由节点，然后将初始节点的信息转发到该无线节点中，通过无线节点进行传递，传输至目标节点。此时，源节点和目的节点通过无线链路进行跨子网通信。无线节点之间的消息传输采用了单跳的模式，缩短了子网之间数据包的传输距离。由于无线节点在网络中分布较为均衡，降低了网络拥塞[20]的可能性。

节点之间的信息传输方式根据源节点与目的节点Z轴坐标之差可分为三种方式，一一举例来说明。

对于实例1（即源节点和目的节点所在子网都存在无线路由节点的情况下），如图5 所示。假设源节点坐标为A（2，1，0），目的节点坐标是B（1，1，3），那么信息传输的路径就为A—WR0—WR4—B。其中节点WR0（2，2，0）到WR4（2，2，3）通过无线进行传输，节省了从第0 层慢慢地通过一个一个节点传输到第3层这个步骤，实现了无线网络的单跳传输。当片上网络规模较大的时候，会有效地降低延迟。

Fig.5 Example 1 transmission path图5 实例1传输路径

对于源节点和目的节点相隔一层的信息传输，使用传统的XYZ路由算法。

对于实例2（即源节点和目的节点层数差为2），如图6所示。从源节点M（1，1，1）要发送信息到N（2，0，3），根据文中提出的路由算法来计算|Mz-Nz|=2，此时Z轴的坐标差等于2，此时应该将源节点M的数据包首先传输到距离M较近的拥有无线节点的第0层，然后通过第0层的无线路由节点将数据信息传输到目的节点。传输路径如下：M-WR0-WR2-WR6-WR4-N。

4 仿真实验

Fig.6 Example 2 transmission path图6 实例2传输路径

本文给出的拓扑结构是在8×8×4 的混合无线片上网络架构，有256个节点。仿真实验是在Access Noxim v2.0 仿真器上实现的，运行于Ubuntu13 操作系统。该仿真器的默认架构是同构的3D-mesh架构，将其改成基于正六面体的混合无线的三维片上网络结构。通过仿真实验证明了本文提出的混合无线三维片上网络拓扑架构在功耗和延迟方面与传统的有线片上网络架构相比有了显著的性能改善。仿真实验的参数设计上参考文献[21-22]，具体实验参数配置如表1所示。

Table 1 Parameters for simulation experiments表1 仿真实验固定参数配置

4.1 网络平均路由跳数

与传统的有线三维片上网络相比，平均路由跳数最能直观地反映出无线节点在网络中传输的优势，同时还对比了将无线节点放置于其他层间的情况。通过仿真得出6 种不同拓扑结构的平均路由跳数，如图7 所示。其中Average_hopcount表示平均路由跳数，N01表示将无线路由节点放置在第0层和第1层，其他同理，Wired NoC表示传统有线片上网络。

Fig.7 Average routing hop count图7 平均路由跳数

由于本文采用的算法在一定通信量之内，可以避免网络拥塞。平均路由跳数直接反映了片上网络的性能。通过仿真数据可以看出将无线节点放置在相邻的两层几乎和有线片上网络的跳数相差不大，而将无线路由节点放置在第0层和第3层，平均路由跳数最低，性能最好。

4.2 网络平均延迟

在片上网络中，网络延迟表示的是数据包从注入网络开始，到成功送达目的节点结束，中间所经历的总时间。网络延迟包括了发送延迟、传输延迟和接收延迟。由于网络中数据包源节点和目的节点的不同，经过的路径不同，路由节点的阻塞状况不同，导致每个数据包的网络延迟也不尽相同。因此，一般采用平均延迟来衡量片上网络的性能，如式（1）所示。

其中，Daverage表示网络平均延迟，n表示网络在一定时间内传输的数据包的个数，Di表示第i个数据包的延迟。在其他条件相同的情况下，平均延迟越小的网络，其性能则越好。

在仿真实验中，由于将无线节点放置在相邻层的性能与有线片上网络相差不大，因此只对比了将无线节点放置在第0层和第3层、第0层和第2层、第1层和第3 层的平均延时。通过改变无线节点的摆放位置，得出了在不同注入率条件下的混合无线片上网络的平均时延，仿真结果如图8 所示。此外，还将本文提出的混合无线三维片上网络架构与有线三维片上网络架构的平均延迟进行了对比，实验结果如图9所示。

Fig.8 Relation of packet injection rate and average delay for wireless node distribution图8 不同无线节点分布，注入率与平均延迟关系图

Fig.9 Average delay of NoC with uniform random distribution of packet injection rate图9 注入率均匀随机分布下的网络平均延迟

从图8 中可以看出，在注入率较低的情况下，即注入率在0.01～0.03 的范围内，延迟变化不明显。但随着逐渐加大注入率，在注入率大于0.03 后无线拓扑结构N03的延时略优于无线拓扑结构N02和N13，大约有10%的性能提升，而在注入率加大到0.07 后，无线拓扑结构N03 的延时与无线拓扑结构N02 和N13 逐渐拉大，约有12%的性能提升。由此可以看出，三维无线片网中无线节点分布对于片网性能是有较大的影响。在原有的拓扑结构中加入无线路由器节点和无线通信信道，整个无线信道构成正六面体结构使得数据包在整个拓扑结构中的传输延迟有较明显的降低。

图9中，Hybrid NoC表示本文所提出的混合无线片上网络结构，Wired NoC表示传统的有线三维片上网络。仿真实验的结果表明，在注入率较低的情况下，性能并没有显著提升，但随着注入率的逐渐增大，有线片上网络的时延和无线片上网络的时延差距越来越明显，尤其是在注入率大于0.03后，改进后的混合无线片上网络架构在延迟方面的性能表现明显优于传统的有线三维片上网络拓扑结构。

4.3 网络总功耗

NoC 系统功耗指的是在单位时间内网络中处理数据和传输数据所引起的功率消耗。仿真实验是在Ubuntu13 下进行的，其总功耗主要来自于处理机产生的功耗和片上网路中数据通信产生的功耗，如式（2）所示。

其中，P为总功耗值，PN为片上网络中数据通信产生的耗能值，PPE为处理器产生的耗能值。

图10的实验结果表明，随着注入率的逐渐增大，两种结构的总功耗呈线性增加，且有线片上网络架构的总功耗增加的幅度较大。当注入率在0.13 时，两种结构的总功耗开始趋于稳定状态，此时，混合无线片上网络架构的网络总功耗要远小于有线片上网络。

Fig.10 Total power consumption of NoC with uniform random distribution of packet injection rate图10 注入率均匀随机分布下的网络总功耗

5 结束语

本文提出了一种混合无线片上网络架构以及适应于该架构的路由算法，最后通过仿真实验分别得出网络平均延迟和网络总功耗等性能参数。一方面，在8×8×4 的混合无线片上网络的基础上，改变无线路由节点的位置，探讨了无线路由位置对于片网的性能的影响。另一方面，将该架构与传统的有线三维片上网络的性能进行了对比。实验结果表明，本文所提出的混合无线片上网络架构在平均延迟以及功耗方面有了很大改善。由于该架构中的无线节点占节点总数的比例较小，在大规模通信时，无线节点所承担的通信量较大，在一定程度上会产生拥塞问题，接下来的工作将会重点集中在此。