, 王爱侠, 张壬申东北大学 信息科学与工程学院, 辽宁 沈阳 110819
收稿日期：2016-04-22
基金项目：国家自然科学基金资助项目(51607029)。
作者简介：李贞妮(1982-), 女, 辽宁沈阳人, 东北大学讲师, 博士研究生;
李贞妮(1982-), 女, 辽宁沈阳人, 东北大学讲师, 博士研究生。
摘要：由于片上网络的拓扑结构和路由算法直接影响片上网络的传输延迟和传输效率, 提出了一种新的片上网络拓扑结构——半环形网格结构(H-annular Mesh).它以2D-Mesh拓扑结构为基础, 由顶角节点向中心节点引入连线构成半环形的网格结构, 充分结合了2D-Torus拓扑结构的优点.并针对H-annular Mesh拓扑结构, 提出了HAA-XY自适应路由算法.仿真结果表明, 基于H-annular Mesh拓扑结构和HAA-XY路由算法的片上网络, 能够有效地减少网络传输延迟, 并可实现多方向及多节点的数据并行通信.
关键词：半环形网格片上网络拓扑结构自适应路由算法
A New Network-on-Chip Topology and Its Adaptive Routing Algorithm
LI Zhen-ni, LI Jing-jiao
, WANG Ai-xia, ZHANG Ren-shenSchool of Information Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: LI Jing-jiao, E-mail: lijingjiao@ise.neu.edu.cn
Abstract: The topology and routing algorithm of network-on-chip (NoC) directly influence the transmission delay and transmission efficiency of the network. A new topology of NoC— H-annular Mesh was proposed based on the 2D-Mesh topology. The lines introduced from the vertex nodes to the center nodes constituted a half annular Mesh (H-annular Mesh), which could fully take the advantage of 2D-Torus topology. An adaptive routing algorithm HAA-XY was proposed for H-annular Mesh topology. The simulation results indicate that based on the H-annular Mesh topology and the HAA-XY routing algorithm, the NoC can effectively reduce the network transmission delay, and can realize the multi-directional and multi-node data parallel communication.
Key Words: H-annular Meshnetwork-on-chip(NoC)topologyadaptiverouting algorithm
随着集成电路技术的飞速发展, 在芯片上集成的IP核数目越来越多, 时钟频率越来越高[1].片上网络(network-on-chip, NoC)的出现, 可以很好地解决传统总线在时钟和功耗方面的问题, 并具有更低的通信功耗, 因此逐渐成为片上多核系统的标准通信架构[2].
片上网络拓扑结构对片上多处理器性能和功耗的影响非常重要[3].目前, 大多数片上网络采用最典型的2D-Mesh(二维网格)[4-5]或者2D-Torus(二维环状)[6-7]结构.2D-Mesh拓扑结构, 其节点之间的连线方式比较简单, 路由算法和物理实现难度相对较低, 占用的片上资源比较少; 然而网络直径的增加会降低2D-Mesh结构的性能和功耗水平, 致使其不适用于规模较大的片上网络[8-9].2D-Torus拓扑结构的每一个路由节点都与4个方向的路由节点相连接, 每个节点的结构相同, 使得其具有很好的可扩展性, 且其路由路径的多样性有效降低了阻塞的发生, 提高了网络的传输效率[10].但是, 基于2D-Torus拓扑结构的片上网络, 由于增加了首尾节点的长连线, 会增加传输延迟, 带来路由死锁的问题; 若采用虚拟通道的方法来解决这个问题, 会占据大量的片上资源, 并不利于硬件实现, 从而无法充分体现出片上网络的优越性[11].
此外, 片上网络路由算法的设计对于片上网络的性能也是至关重要的.路由算法的设计目标在于是否能够有效地避免阻塞的发生, 充分利用片上网络的空闲资源, 以此来改善片上网络的延迟和吞吐率; 同时路由算法设计还要尽可能少地占用片上资源, 减小片上网络功耗.现在, 大多数片上网络采用确定性路由算法[12], 当源节点和目的节点确定后, 传输路径也就确定了, 当该路径上某一节点发生阻塞时, 数据包会停止路由进行等待; 因此, 这种路由算法增加了网络传输的延迟, 导致整个网络负载的不平衡.
针对现有技术的不足, 本文提出一种片上网络拓扑结构, 半环形网格结构(H-annular mesh)及其自适应路由算法HAA-XY(H-annular Mesh adaptive XY routing algorithm), 以达到减小路由平均跳数和网络直径, 实现根据阻塞情况自主调整, 减小路由延迟, 提高数据传输效率的目的.
1 H-annular Mesh拓扑结构描述1.1 H-annular Mesh拓扑结构设计对于N×N的H-annular Mesh片上网络可以将其分为两种情况:当N为偶数时, 将片上网络中每一行中间的2个节点与该行的首尾节点相连接, 将片上网络中每一列中间的2个节点与该列的首尾节点相连接; 当N为奇数时, 将每一行中间节点左右两侧的节点与首尾节点相连接, 将每一列中间节点上下两侧的节点与首尾节点相连接.针对该网络拓扑结构的特点, N＜6时其还原为2D-Mesh, 在网络规模较小时具有2D-Mesh型片上网络的所有优点.该拓扑结构如图 1所示(以网络规模6×6为例), 并做出如下定义:
图 1(Fig. 1)
 | 图 1 6×6的H-annular Mesh片上网络拓扑结构Fig.1 Topology of the 6×6 H-annular Mesh NoC |
定义1?? N×N的H-annular Mesh拓扑结构节点为(x, y), 其中0≤x≤N-1, 0≤y≤N-1.
定义2??＜(x2, y2), (x1, y1)＞表示由路由节点(x2, y2) 指向路由节点(x1, y1) 的单向数据链路.
定义3??坐标为(x, 0) 的节点为横向头节点, 坐标为(x, N-1) 的节点为横向尾节点; 坐标为(0, y)的节点为纵向头节点, 坐标为(N-1, y)的节点为纵向尾节点.
定义4??定义x方向上新增连接线的方向为Tx方向, y方向上新增连接线的方向为Ty方向.
如图 1所示, 6×6的H-annular Mesh片上网络每一行上共有6个路由节点, 每一列上也共有6个路由节点; 其中左下角为(0, 0) 节点, 右上角为(5, 5) 节点, x和y坐标分别沿着右侧和上侧方向依次递增.例如:在第一行中, (0, 0) 节点与(2, 0) 节点和(0, 2) 节点相连接, 那么当(0, 0) 节点访问在水平方向上距离大于或等于2的节点时, 或者在竖直方向上访问节点距离大于或等于2的节点时, 则不必像2D-Mesh拓扑结构依次对节点进行路由, 而可以直接访问中间节点再继续路由过程, 缩短了路由路径的长度, 减小了片上网络的网络延迟.与2D-Torus拓扑结构相比, H-annular Mesh结构采用折半的连线, 避免了长连线在网络结构较大时带来的延迟问题, 而且其访问路由节点的速度不亚于2D-Torus拓扑结构, 并没有为了提升访问速度而消耗更多的资源和空间, 且其硬件实现复杂度也相对较低.
1.2 H-annular Mesh网络直径在片上网络中, 任意2个路由节点间距离的最大值被称为网络直径, 其大小是影响网络传输和路由延迟的关键因素之一.因此，如果能够减小网络直径则能够改变网络传输的速度.对于N×N的2D-Mesh结构网络, 其网络直径为2N-2；而对于N×N的2D-Torus结构网络, 当N为偶数时, 其网络直径为N, 当N为奇数时, 其网络直径为N-1；对于N×N的H-annular Mesh网络, 分为4种情况讨论:N=4k, 4k+1, 4k+2, 4k+3.具体情况如表 1所示.
表 1(Table 1)
 表 1 H-annular Mesh的网络直径Table 1 Network diameter of the H-annular Mesh
| 表 1 H-annular Mesh的网络直径 Table 1 Network diameter of the H-annular Mesh |
可以看出, H-annular Mesh拓扑结构在网络直径方面优于2D-Mesh型片上网络.与2D-Torus型片上网络比较, 其网络直径等于或略高于Torus型片上网络, 但它采用折半的连线, 避免了长连线在网络结构较大时带来的延迟问题.
1.3 H-annular Mesh路由平均跳数片上网络路由平均跳数, 即为片上网络中数据包到达目的节点的跳数的平均值.片上网络路由平均跳数是影响片上网络吞吐量与网络延迟的重要因素.路由平均跳数越少, 路由延迟越小.以网络规模为6×6的片上网络为例, 计算结果如表 2所示.
表 2(Table 2)
表 2 三类拓扑结构的路由平均跳数Table 2 Average routing hops of the three topologies
| 表 2 三类拓扑结构的路由平均跳数 Table 2 Average routing hops of the three topologies |
可以看出, H-annular Mesh拓扑结构的路由平均跳数小于2D-Mesh, 与2D-Torus的相同.
2 HAA-XY路由算法设计为解释算法, 将片上网络的路由节点分成三类:既有Tx方向连线又有Ty方向连线的路由节点, 只有Tx方向或Ty方向连线的路由节点和其他路由节点, 采用分类路由策略.
设定源节点为S(x_s, y_s), 目的节点为D(x_dst, y_dst), 当前节点为C(x, y).路由开始时, 当前节点即为源节点, 即C(x, y)=S(x_s, y_s); 同时每个路由节点具有9个方位, 分别为E(东)、S(南)、W(西)、N(北)、NE(东北)、SE(东南)、NW(西北)、SW(西南)和O(本地); 每个路由节点具有5个端口, 即本地端口、东向端口、西向端口、南向端口、北向端口, 部分节点还具有Tx端口或Ty端口.
采用pend信号作为传输方向上的局部阻塞信号, 该信号为0时代表路由节点某一路由方向不阻塞, 为1时代表路由节点的某一路由方向阻塞, 例如pend_E信号代表东向输出路径的阻塞状态.
对于N×N的H-annular Mesh片上网络, 路由算法执行过程如下.
2.1 目的节点在东、南、西、北4个方向如果目的节点在当前节点的东、南、西、北4个方向, 则不需要对数据输出路径的阻塞情况进行判断, 包括如下几种情况:
1) 目的节点为当前节点, 则当前节点将数据发送到其本地端口;
2) 若目的节点在当前节点的东、西向.当N为偶数时, 令T=N, Q=0;当N为奇数时, 令T=N-1, Q=1, 则可以分为五种情况讨论:
① 若x=0, 说明当前节点具有Tx方向的连线, 目的节点在当前节点的东向, 则是否x_dst=x+i, 其中i=1, 2, …, t, t为整数, 且t＜T/2-1, 是, 则当前节点将数据发送到东向端口输出; 否, 则当前节点将数据发送到Tx方向端口输出.
② 若x=N-1, 说明当前节点具有Tx方向的连线, 目的节点在当前节点的西向, 则是否x_dst=x-i, 其中i=1, 2, …, t, t为整数, 且t＜T/2-1, 是, 则当前节点将数据发送到西向端口输出; 否, 则当前节点将数据发送到Tx方向端口输出.
③ 若x=T/2-1, 说明当前节点具有Tx方向的连线, 则
Ⅰ若x_dst=x-i, 其中i=1, 2, …, t, t为整数, 且t＜T/2-1, 即目的节点在当前节点的西向, 则当前节点将数据发送到西向端口输出;
Ⅱ若x_dst=x-(T/2-1), 即目的节点在当前节点的西向, 且目的节点与当前节点之间有Tx方向的连线, 则当前节点将数据发送到Tx方向端口输出;
Ⅲ若x_dst =x+i, 其中i=1, 2, …, t, t为整数, 且t＜T/2+1, 即目的节点在当前节点的东向, 则当前节点将数据发送到东向端口输出.
④ 若x=T/2+Q, 说明当前节点具有Tx方向的连线，则
Ⅰ若x_dst=x-i, 其中i=1, 2, …, t, t为整数, 且t＜T/2+1, 即目的节点在当前节点的西向, 则当前节点将数据发送到西向端口输出;
Ⅱ若x_dst=x+(T/2-1), 即目的节点在当前节点的东向, 且目的节点与当前节点之间有Tx方向的连线, 则当前节点将数据发送到Tx方向端口输出;
Ⅲ若x_dst =x+i, 其中i=1, 2, …, t, t为整数, 且t＜T/2-1, 即目的节点在当前节点的东向, 则当前节点将数据发送到东向端口输出.
⑤ 若x≠T/2+Q且x≠T/2-1, 说明当前节点不具有Tx方向的连线, 则判断是否x_dst=x-i, 其中i=1, 2, …, t, t为整数, 且t≤x, 是, 即目的节点在当前节点的西向, 则当前节点将数据发送到西向端口输出; 否, 即目的节点在当前节点的东向, 则当前节点将数据发送到东向端口输出.
3) 若目的节点在当前节点的南、北向, 算法分析过程与2) 相似, 不再赘述.
2.2 目的节点东北、东南、西北和西南4个方向如果目的节点在当前节点的东北、东南、西北和西南4个方向, 则需要对数据输出路径的阻塞情况进行判断.包括如下几种情况:1) 若当前节点任意方向的数据输出路径均为无阻塞, 则结合该当前节点上一时刻路由的输出情况, 采取轮转策略, 决定下一跳路由节点；2) 若当前节点的任意方向均存在阻塞, 此时无法进行数据帧传输, 数据保存在当前路由节点的缓存中并等待, 直至网络阻塞情况发生变化; 3) 若当前节点的任一方向出现阻塞, 该节点立即可以通过阻塞信号得到反馈, 进而调整数据帧的路由方向, 选择畅通的路径进行路由, 可有效规避故障节点, 降低数据包的路由延迟, 提高片上网络的吞吐量.
3 系统测试及结果分析基于H-annular Mesh拓扑结构并采用HAA-XY路由算法的6×6片上网络采用System Verilog语言, 在Xilinx ISE 14.4上实现并仿真测试.系统性能测试使用的硬件平台为Xilinx Virtex-5系列的FPGA, 下载工具为DIGILENT的Adept.
3.1 单个节点传输测试分析这里以＜(0, 5), (5, 2)＞为例分析.数据传输仿真图如图 2所示.
图 2(Fig. 2)
 | 图 2 ＜(0, 5), (5, 2)＞数据传输仿真图Fig.2 Simulation diagram of ＜ (0, 5), (5, 2)＞ |
在路由的过程中, H-annular Mesh型网络共消耗了大约65个时钟周期, 而对于6×6结构的2D-Mesh型网络, ＜(0, 5), (5, 2)＞共消耗了大约98个时钟周期.对比分析可知, 当传输的节点间距离较长时, 该文提出的H-annular Mesh拓扑结构相对于2D-Mesh拓扑结构, 能够大大缩减路由过程消耗的时间, 减少网络延迟, 提高数据的传输速率.
3.2 多节点并行传输测试分析测试中, 分别从(5, 1), (0, 5), (5, 5) 节点向(0, 5), (5, 2), (0, 2) 节点传输数据, 那么从三个源节点的本地端口分别输入数据0x116a00a, 0x1a4500a, 0x1b4200a.通过仿真结果可知, 多组数据在6×6的H-annular Mesh网络中能够进行正确的传输, 没有发生阻塞的情况, 并且目的节点输出数据也与源节点输入数据保持一致, 说明HAA-XY自适应路由算法保证了并行传输的准确率.
3.3 片上网络系统性能测试在Genesys Vertex-5 FPGA上实现了本文提出的规模为6×6的片上网络.以节点调用IP核后的测试结果为例, 片上网络系统实物图如图 3所示.结果表明, 系统实物测试与仿真结果一致.
图 3(Fig. 3)
 | 图 3 片上网络系统实物图Fig.3 Photo of the NoC system |
4 结论本文提出了一种H-annular Mesh拓扑结构, 该拓扑结构在网络直径和路由平均跳数方面, 均优于2D-Mesh型片上网络, 能够减小远距离节点间的访问时间.与2D-Torus型片上网络相比, 长连线的减少有效地避免了时钟偏移等问题, 且不需要为了防止死锁或活锁消耗过多的资源, 降低了设计难度.针对该拓扑结构, 该文提出了HAA-XY自适应路由算法.实验结果表明, HAA-XY算法可以有效规避阻塞严重或出现故障的路由节点, 减小路由延迟.基于H-annular Mesh拓扑结构和HAA-XY路由算法的片上网络, 能够实现多方向以及多节点的并行通信.片上网络是新一代片上多核系统的标准通信架构, 因此基于本文提出的H-annular Mesh拓扑结构和HAA-XY自适应路由算法的片上网络具有较好的应用前景.
参考文献
| [1] | 李贞妮, 李晶皎, 方志强, 等. 异步2D-Torus片上网络自适应路由算法[J].东北大学学报(自然科学版), 2015, 36(9): 1217–1221. ( Li Zhen-ni, Li Jing-jiao, Fang Zhi-qiang, et al. Adaptive routing algorithm of asynchronous 2D-Torus network-on-chip[J].Journal of Northeastern University (Natural Science), 2015, 36(9): 1217–1221.) |
| [2] | 王新玉, 向东, 虞志刚. TM:一种新的片上网络拓扑结构[J].计算机学报, 2014, 37(11): 2327–2341. ( Wang Xin-yu, Xiang Dong, Yu Zhi-gang. TM:a new topology for networks-on-chip[J].Chinese Journal of Computers, 2014, 37(11): 2327–2341.) |
| [3] | Xu Y, Zhao B, Zhou X, et a1.A low-radix and low-diameter 3D interconnection network design [C]// Proceedings of the International Symposium on High Performance Computer Architecture.Raleigh, 2009:30-42. |
| [4] | Taylor M B, Lee W, Miller J, et al.Evaluation of the raw microprocessor:an exposed-wire-delay architecture for ILP and streams [C]// Proceedings of the 31st Annual International Symposium on Computer Architecture.Munich, 2004:2-13. |
| [5] | Moraes F, Calazans N, Mello A, et al. Hermes:an infrastructure for low area overhead packet-switching networks on chip[J].Integration, the VLSI Journal, 2004, 38(1): 69–93.DOI:10.1016/j.vlsi.2004.03.003 |
| [6] | Dally W J, Towles B.Route packets, not wires:on-chip interconnection networks [C]//Proceedings of the 38th Design Automation Conference.New York, 2001:684-689. |
| [7] | Gul K S, Hamza M M, Khan S A, et al. Designing area optimized application-specific network-on-chip architectures while providing hard QoS guarantees[J].PLoS One, 2015, 10(4): 1–17. |
| [8] | Feero B, Pande P.Performance evaluation for three-dimensional networks-on-chip [C]//IEEE Computer Society Annual Symposium on VLSI.Porto Alegre, 2007:305-310. |
| [9] | Chiu G M. The odd-even turn model for adaptive routing[J].IEEE Transactions on Parallel and Distributed Systems, 2000, 11(7): 729–738.DOI:10.1109/71.877831 |
| [10] | Touzene A, Day K. All-to-all broadcasting in torus network on chip[J].The Journal of Supercomputing, 2015, 71(7): 2585–2596.DOI:10.1007/s11227-015-1406-z |
| [11] | Ren P J, Kinsy M A, Zheng N N. Fault-aware load-balancing routing for 2D-Mesh and torus on-chip network topologies[J].IEEE Transactions on Computers, 2016, 65(3): 873–887.DOI:10.1109/TC.2015.2439276 |
| [12] | 周磊, 吴宁, 李云. 一种基于2D-Mesh的片上网络无死锁容错路由算法[J].上海交通大学学报, 2013, 47(1): 18–22. ( Zhou Lei, Wu Ning, Li Yun. A fault-tolerant and deadlock-free routing algorithm in 2D-Mesh for network on chip[J].Journal of Shanghai Jiao Tong University, 2013, 47(1): 18–22.) |
