2019, Vol. 45
随着片上知识产权(Intellectual Property, IP)核数目的急剧增加, 二维片上网络(2D Network-on-Chip, 2D NoC)的发展遇到瓶颈, 为此, 研究人员将三维集成电路(3D Integrated Circuit, 3D IC)与NoC进行结合, 提出一种3D NoC架构。3D NoC使用硅通孔(Through-Silicon-Via, TSV)技术将硅晶片的各层进行堆叠, 以缓解互连线的延迟, 方便层间节点间的通信, 从而提高网络性能[1]。但是, 目前的TSV制造工艺不够成熟, 在封装以及焊接TSV的过程中, 可能出现短路的现象, 导致TSV生产开销过大[2-3]。此外, TSV占用了大量芯片面积, 使得芯片上的IP核数量大幅减少[4-5]。因此, 拥有较少TSV数目的非全互连3D NoC架构得到了研究者的广泛关注。
为执行并行应用, 如并行搜索算法、并行图论算法等, 多播通信被广泛应用到片上多处理器系统(MPSoC)中[6-7]。相关研究表明, 在支持缓存一致性协议、令牌一致性协议和基于目录一致性协议的网络中, 多播流量占总流量的5%~10%[8]。本文对非全互连3D NoC架构进行研究, 提出一种基于区域划分的多播路由算法。
1 相关工作NoC多播路由算法主要分为基于单播、基于树结构和基于路径3类[9]。其中, 基于单播的多播路由算法将单播包复制多份, 仍采用单播算法将其发送到多个目的地址, 虽然该方法可以实现基本的传输功能, 但其性能较低。在基于树结构的多播路由算法中, 多播包依赖以源节点为根、目的节点为叶子的多播树进行路由, 在子节点实现复制, 其中, 从根到叶子的路径为最短传输路径。文献[10]通过在路由器中添加查找表来存储路由信息, 并提出虚拟电路树多播(Virtual Circuit Tree Multicast, VCTM)算法。VCTM算法首先发送建立包(setup packet)建立多播树, 然后发送真正的多播包。该算法虽然可以解决基于单播的多播路由算法存在的性能问题, 但存在3个弊端:额外存储多播树的维护信息需要更多片上面积; 在发送真正多播包前, 需要发送建立包, 增加了多播延时; 源节点一旦发生改变, 需要重新建立多播树。文献[11]提出一种广播逻辑分布路由(broadcast Logic-Based Distributed Routing, bLBDR)算法, 其通过区域划分来有效隔离有缺陷的区域, 但是, 如果目的节点被分离到不同区域, 该算法将难以定义一个包含所有目的节点的区域。为提高网络缓存资源的利用率, 文献[12]提出一种基于气泡流控的改进多播算法, 该算法通过在网络中加入气泡(空闲虚通道), 不仅释放了网络中的缓存资源, 而且避免了死锁现象。文献[13]提出延时感知的双划分多播(Latency-Aware Dual-Partition Multicast, LADPM)算法, 该算法的网络中存在2类数据包, 每类包采用不同的传输方式, 尽可能地通过最短路径传输到目的节点。但当源节点处于网络中心且多个区域同时出现目的节点时, 该算法会出现传输路径冗余问题。
在基于路径的多播算法中, 数据包根据目的节点集, 依照固定顺序进行路由, 即数据包优先传输到最近的目的节点, 然后进行复制产生复制包, 复制包传输到IP核, 原包删除当前目的地址继续传输。为提高数据包传输的自由度, 文献[14-15]分别提出自适应多路径(Adaptive Multi-Path, AMP)算法和基于汉密尔顿路径的奇偶拐弯(Hamiltonian-based OddEven, HOE)算法, 虽然上述2种算法在传输时能够给予数据包更多的方向选择, 但数据包只能在目的节点进行复制, 导致传输路径延长。文献[16]提出一种三维递归分割多播(3D Recursive Partitioning Multicast, 3D-RPM)算法, 其将所有目的节点映射到源层(源节点所在层), 然后决定在层内或者层间进行传输, 但是, 如果源层不包含目的节点或只包含很少的目的节点, 层间传输路径长度会大幅增加。为解决该问题, 文献[16]还提出三维优化递归分割多播(3D Optimized Recursive Partitioning Multicast, 3D-ORPM)算法, 该算法将所有目的节点映射到目的节点最多层。文献[17]首先递归分割网络, 直到区域内路由节点达到数量阈值k, 然后采用最小自适应路由(Minimal Adaptive Routing, MAR)算法进行传输, 当有多个方向端口可用时, 采用缓存占用最少的端口进行传输。上述基于路径的多播路由算法虽然可以减少网络中数据包的数量, 但较长的传输路径会增加其传输延时。
除上述算法外, 研究者还提出一些混合类型多播算法。文献[18]集成基于树结构和基于路径的多播优势, 提出混合多播算法, 其根据相邻节点的缓存决定传输路径。文献[19]在层内采用基于汉密尔顿路径的多播路由, 在层间以源节点为根建立多播树分支, 在提高数据传输效率的同时能够保证数据传输的可靠性。
综上, LADPM算法的传输路径存在冗余问题, 在网络中进行多包传输时易产生拥塞, HOE算法只能在目的节点实现复制, 传输路径较长。本文对非全互连3D NoC架构进行研究, 提出基于层内区域划分的多播路由算法。数据包在公共路径上采用单包传输, 在中间节点进行复制, 以增加数据包传输的自由度, 缩短传输路径长度。
2 非全互连架构与TSV表 2.1 非全互连3D NoC非全互连3D NoC层内采用2D NoC架构, 且每层规模相同, 层间通过一定数量的TSV表建立连接, 路由器通过TSV表存储TSV的位置信息。在该架构中, 存在2类路由器:含有TSV的三维路由器, 无TSV的平面路由器。其中, 三维路由器拥有7个方向端口, 分别为本地、东、西、南、北、上、下; 平面路由器拥有5个方向端口, 分别为本地、东、西、南、北。非全互连3D NoC拓扑模型如图 1所示, 每个路由器的位置由三维笛卡尔坐标表示。
|
Download:
|
| 图 1 非全互连3D NoC拓扑架构 | |
在全互连架构中, 数据包可以在任何节点通过TSV直接进行层间传输。而在非全互连架构中, 层间传输的数据包到达平面路由器后不能直接进行层间传输, 需要将三维路由器的TSV作为层间传输的通道。因此, TSV的位置成为层间传输的关键。在片上路由器中通过TSV表记录TSV的位置坐标, 可以使层间传输得到保证。TSV表建立的主要步骤为:
步骤1 在发送正式多播包之前, 三维路由器发送记录包, 记录包不仅携带TSV位置信息, 而且存储记录包在网络中已经传输的跳数。
步骤1 路由器收到记录包后与TSV表中的信息进行对比, 如果表中没有记录此方向的TSV信息, 将位置坐标和跳数写入表中, 继续传输, 重复步骤2;否则, 跳转到步骤3。
步骤3 如果表中跳数值大于记录包的跳数值, 更新TSV表中的跳数值, 继续传输, 跳转到步骤2;否则, 不进行表项更新, 传输结束。
当TSV表建立完成时, 网络中不再产生记录包。图 1中的节点(2, 2, 1)存储的TSV表信息如表 1所示。
|
下载CSV 表 1 TSV表信息 |
3D NoC多播路由算法将数据包按照一定路径从源节点准确无误地传输到多个目的节点。根据网络中目的节点的不同分布, 本文算法分为层间路由算法和层内路由算法2个部分, 其中, 数据包在层间路由时, 目的节点在同层的数据包被封装成单包进行传输。本文算法中的主要符号和含义说明如表 2所示。
|
下载CSV 表 2 符号说明 |
根据各节点的位置坐标, 在层内划分区域时的规则如下:
1) 东区域:区域中所有节点的X方向坐标大于源节点的X方向坐标。
2) 西区域:区域中所有节点的X方向坐标小于源节点的X方向坐标。
3) 南区域:区域中所有节点的X方向坐标等于源节点的X方向坐标, 但Y方向坐标小于源节点的Y方向坐标。
4) 北区域:区域中所有节点的X方向坐标等于源节点的X方向坐标, 但Y方向坐标大于源节点的Y方向坐标。
如果源节点在网络边缘, 网络被划分为3个区域; 如果源节点在网络角落, 网络被划分为2个区域; 其他情况时网络被划分为4个区域。上述3种情况的区域划分结果如图 2所示。
|
Download:
|
| 图 2 层内区域划分结果 | |
定义1(标记节点)东区域所有目的节点中X坐标最大的节点, 西区域所有目的节点中X坐标最小的节点, 南区域所有目的节点中Y坐标最小的节点, 北区域所有目的节点中Y坐标最大的节点, 定义为标记节点。
根据层内目的节点的分布, 源节点最多发送4个初始包(此时源节点在网络中心且划分的每个区域中都含有目的节点), 每个初始包携带相应区域所有目的节点的地址, 地址存放在数据包的负载中。算法将标记节点作为路由结束标记, 数据包到达标记节点说明区域中已无其他目的节点, 在此列传输结束便可完成路由。
如果目的节点和源节点在同一层, 采用层内路由算法过程具体如下:
1) 当目的节点在南(北)区域时, 南(北)初始包只在此列传输, 如果到达某一个目的节点后还未到达标记节点, 说明此区域中还有其他目的节点, 因此, 初始包在当前目的节点进行复制, 将复制包传输到IP核。初始包将当前目的节点地址从负载中删除, 然后继续向其他目的节点传输, 直至传输到标记节点。
2) 当目的节点在东(西)区域时, 东(西)初始包将源节点所在行作为公共路径, 数据包每传输到下一节点, 将该节点的X坐标和数据包负载中所有目的节点的X坐标进行对比, 目的是检查此列(南北方向)是否含有目的节点。如果该节点和数据包负载中某个或多个目的节点有相同的X坐标, 说明此列含有一个或多个目的节点, 因此, 初始包在当前节点进行复制, 复制包在此列向目的节点传输, 而初始包将当前目的节点地址从负载中删除, 然后在公共路径上继续向下一节点传输; 否则, 初始包不进行复制而继续进行正常传输。
层内路由算法伪代码描述如下:
算法1 层内路由算法
1.if (zone==0) //目的节点在东区域
2.while (XC < =XM)//当前节点坐标小于等于标记节//点坐标
3.XC=XC+1;
4.for each Xi in Payload
5.if (XC==Xi)
6.count=count+1;//当前列的目的节点计数
7.else
8.continue; //跳出此次for循环
9.end for
10.if (count==0) //此列无目的节点
11.continue; //跳出此次while循环, 继续向东传输
12.else if (YC!=YD&&count>1) //当前节点不是目的//节点, 此列还有其他目的节点
13.duplicate packet is transmitted to all destination nodes in this column;
14.else if (YC==YD&&count>1) //当前节点是目的节//点, 此列还有其他目的节点
15.duplicate packet is transmitted to all destination nodes in this column;
16.else //只有当前节点是目的节点
17.duplicate packet is transmitted to IP core;
18.end while
19.if (zone==2) //目的节点在西区域
20.the routing method is similar to (zone==0);
21.if (zone==1) //目的节点在北区域
22.while (YC < =YM)
23.YC==YC+1;
24.if (YC==YD)
25.duplicate packet is transmitted to IP core;
26.else
27.continue; //跳出此次while循环, 继续向北传输
28.end while
29.if (zone==3) //目的节点在南区域
30.the routing method is similar to (zone==1);
3.2 层间路由算法如果目的节点和源节点不在同一层, 采用层间路由算法。当源节点含有TSV时, 数据包直接传输到邻近层; 当源节点无TSV时, 数据包间接传输到邻近层, 即数据包选择当前节点TSV表中最近的TSV作为层间传输的通道, 然后在层内传输到已选择的TSV节点处, 最后通过TSV传输到邻近层。如果当前层(当前节点所在层)仍不是目的层(目的节点所在层), 根据当前节点是否含有TSV决定数据包选择直接传输还是间接传输, 直至传输到目的层, 然后将目的层当前节点作为新的源节点, 采用上述层内路由算法进行传输。层间路由算法伪代码描述如下:
算法2 层间路由算法
1.if (S has TSV) //源节点含有TSV
2.packet is transmitted to adjacent layer; //数据包直接传//输到邻近层
3.while (第1行)
4.if (adjacent layer==destination layer) //邻近层是目//的层
5.running intra-layer routing algorithm; //执行层内路由//算法
6.break; //跳出循环
7.else if (C has TSV) //邻近层不是目的层且当前节点//含有TSV
8.packet is transmitted to adjacent layer;
9.else //邻近层不是目的层且当前节点无TSV
10.packet is transmitted to adjacent layer through the nearest TSV; //选择TSV表中最近的TSV, 传输到邻近层
11.end while
12.else //源节点无TSV
13.packet is transmitted to adjacent layer through the nearest TSV;
14.execute第3行~第11行
3.3 算法示例为更清楚地说明本文算法, 用图 3展示源节点S=(1, 1, 0)和目的节点集MD={D0(4, 0, 2), D1(2, 2, 2), D2(0, 3, 2), D3(0, 4, 2)}的多播路由过程。目的节点与源节点不在同一层, 首先, 源节点S通过TSV直接将数据包传输到邻近上层, 但当前层不是目的层, 而当前节点M0无上TSV, 因此, 需要进行间接传输。根据M0的TSV表, 数据包选择最近的上TSV(中间节点M1的上TSV)进行间接传输, 当传输到中间节点M2时, 此时已经到达目的层。根据3.1.1节的规则划分层内网络区域, 节点M2作为临时源节点, 采用层内路由算法将数据包在层内传输到各目的节点。
|
Download:
|
| 图 3 多播路由过程示例 | |
根据临时源节点M2和各目的节点的分布, 分别划分网络区域为北区域(N)、西区域(W)和东区域(E)。各区域的初始包可以表示为源节点_{区域, 标记节点, (目的节点中除标记节点外的其他节点)}, 因此, 3个区域的初始包分别为M2_{N, D1, ()}、M2_{W, D3, (D2)}、M2_{E, D0, ()}。在北区域传输时, 北初始包直接向北方向传输, 到达目的节点D1后发现已经到达标记节点, 说明此列无其他目的节点, 传输结束。在西区域传输时, 首先西初始包在公共路径上传输, 当到达目的节点所在列时, 数据包在此列进行复制并向目的节点D2传输, 当到达D2后, 发现并未到达标记节点, 继续向标记节点D3传输, 数据包到达D3后传输结束。在东区域进行传输时与西区域路由动作相似, 在此不再赘述。
4 仿真结果与分析 4.1 数据包结构本文实验的网络拓扑为4×4×4的非全互连3D NoC架构, 数据以微片为单位进行传输。数据包结构如图 4所示, 头部前2 bit的Layer字段表示数据包所属层数, 2 bit的Zone字段表示数据包所属区域, 2’b00、2’b01、2’b10、2’b11表示数据包分别属于东、北、西、南区域, XS、YS、ZS分别表示源节点的X、Y、Z轴地址坐标, XM、YM、ZM分别表示此区域中标记节点的X、Y、Z轴地址坐标, 其他目的节点地址放置在Payload中。
|
Download:
|
| 图 4 数据包结构 | |
本文采用基于SystemC的Access Noxim开源仿真器进行网络性能仿真。Access Noxim集成了片上网络模拟器Noxim和热模型Hopspot, 支持网络模型、功率模型和热模型的3D NoC仿真[20]。实验将LADPM算法和HOE算法分别扩展成3D LADPM和3D HOE非全互连算法, 并与本文算法进行比较。实验参数设置如表 3所示, 其中, Random流量模型表示数据包均匀且随机选择目的节点, Hopspot流量模型表示在网络中设置热点节点。本文将第20个节点设置为热点节点, 使之多产生10%的流量。
|
下载CSV 表 3 实验参数设置 |
数据包平均传输延时是反映网络性能的重要指标, 因此, 本文分析3种算法在不同流量模型下的数据包平均传输时延情况, 结果如图 5所示。为更好地说明算法性能, 实验针对每种算法分别设置了6个目的节点和10个目的节点2种情况。从图 5可以看出, 在Random流量模型下, 当数据包注入率(表示每个节点在每个时钟周期内向网络中注入的微片数目)不超过0.03时, 无论是6个目的节点还是10个目的节点, 3种算法的平均时延没有很大差别。但随着注入率的增加, 3D HOE算法的平均时延逐渐高于其他2种算法, 原因是其数据包需要根据目的节点的顺序进行传输, 导致数据包传输路径变长。在Hopspot流量模型下, 虽然有热点节点出现, 但是在低数据包注入率下, 3种算法的平均时延都很相近。而当注入率大于0.023时, 时延均开始迅速增加, 受影响最大的是3D HOE算法, 而3D LADPM算法的平均时延增加幅度高于其在Random流量模型下的增加量, 原因是该算法采用多包传输策略, 增加了10%的流量后, 在网络未拥塞的情况下数据包将在路由器缓存中进行停留。
|
Download:
|
| 图 5 3种算法的平均传输时延对比 | |
算法的可靠性可以用丢包率进行衡量, 丢包率越小说明算法越可靠。本文分析3种算法在不同流量模型下的丢包率情况, 结果如图 6、图 7所示。从图 6、图 7可以看出, 在Random流量模型下, 3D LADPM算法的丢包率高于其他2种算法, 原因是多包传输的策略导致其数据包在缓存中等待过久, 甚至发生拥塞, 这时路由器会选择丢弃数据包。而3D HOE算法只在目的节点进行数据包复制, 丢包的情况最可能在目的节点附近发生, 因此其丢包率小于3D LADPM算法。本文算法数据包在合适的节点进行复制且尽量在公共路径传输, 因此, 丢包率小于其他2种算法。在Hopspot流量模型下, 本文算法和3D HOE算法的变化趋势与Random流量模型下基本相同, 但3D LADPM算法会随着注入率的升高而更加频繁地发生丢包。
|
Download:
|
| 图 6 设置6个目的节点时3种算法的丢包率对比 | |
|
Download:
|
| 图 7 设置10个目的节点时3种算法的丢包率对比 | |
本文提出一种基于层内区域划分的多播路由算法, 该算法在层间传输时选择最近的TSV作为传输通道, 缩短了层间传输路径的长度, 在层内通过区域划分使数据包在公共路径上单包传输, 能够在缓解网络拥塞的同时提高数据包传输的自由度。实验结果验证了该算法的高效性与可靠性。
| [1] |
NAKAHARA H, DOAN N A V, YASUDO R, et al.XYZ-randomization using TSVs for low-latency energy efficient 3D-NoCs[C]//Proceedings of International Symposium on Networks-On-Chip.Washington D.C., USA: IEEE Press, 2017: 1-8.
(  0)
|
| [2] |
欧阳一鸣, 韩倩倩, 梁国华, 等. 面向非全互连3D NoC可靠通信的分布式路由算法[J]. 计算机辅助设计与图形学学报, 2014, 26(3): 502-510. ( 0)
|
| [3] |
CHARIF A, ZERGAINOH N E, COELHO A, et al.Rout3D: a lightweight adaptive routing algorithm for tolerating faulty vertical links in 3D-NoCs[C]//Proceedings of the 22nd IEEE European Test Symposium.Washington D.C., USA: IEEE Press, 2017: 1-6.
( 0)
|
| [4] |
武畅.片上网络体系结构和关键通信技术研究[D].成都: 电子科技大学, 2008. http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y1314700
( 0)
|
| [5] |
GHOSH S, ROY S K, RAHAMAN H, et al.TSV repairing for 3D ICs using redundant TSV[C]//Proceedings of 2017 International Symposium on Embedded Computing and System Design.Washington D.C., USA: IEEE Press, 2017: 1-5.
( 0)
|
| [6] |
WANG Zheng, GU Huaxia, YANG Yintang, et al. An adaptive partition-based multicast routing scheme for Mesh-based networks-on-chip[J]. Computers and Electrical Engineering, 2016, 51: 235-251. DOI:10.1016/j.compeleceng.2016.01.021 ( 0)
|
| [7] |
RAMPAL R, CHANDEL R, DANIEL P.A network-on-chip router for deadlock-free multicast Mesh routing[C]//Proceedings of 2015 IEEE International Conference on Electronics, Computing and Communication Technologies.Washington D.C., USA: IEEE Press, 2015: 1-6. https://ieeexplore.ieee.org/document/7383882/
( 0)
|
| [8] |
PRASAD M L, DAS S, KAPOOR H K.An approach for multicast routing in networks-on-chip[C]//Proceedings of 2014 International Conference on Information Technology.Washington D.C., USA: IEEE Press, 2014: 299-304. https://ieeexplore.ieee.org/document/7033340
( 0)
|
| [9] |
NASIRI F, SARBAZI-AZAD H, KHADEMZADEH A. Reconfigurable multicast routing for Networks on Chip[J]. Microprocessors and Microsystems, 2016, 42: 180-189. DOI:10.1016/j.micpro.2016.02.009 ( 0)
|
| [10] |
JERGER N E, PEH L S, LIPASTI M.Virtual circuit tree multicasting: a case for on-chip hardware multicast support[C]//Proceedings of 2008 International Symposium on Computer Architecture.Washington D.C., USA: IEEE Press, 2008: 229-240. https://ieeexplore.ieee.org/document/4556729
( 0)
|
| [11] |
RODRIGO S, FLICH J, DUATO J, et al.Efficient unicast and multicast support for CMPs[C]//Proceedings of the 41st IEEE/ACM International Symposium on Microarchitecture.Washington D.C., USA: IEEE Press, 2008: 364-375. https://ieeexplore.ieee.org/document/4771805
( 0)
|
| [12] |
娄辉, 肖灿文, 董德尊, 等. 一种基于气泡流控的改进多播路由算法[J]. 计算机工程与科学, 2015, 37(2): 191-198. DOI:10.3969/j.issn.1007-130X.2015.02.001 ( 0)
|
| [13] |
LI Jianhua, XUE C J, XU Yinlong.LADPM: latency-aware dual-partition multicast routing for Mesh-based network-on-chips[C]//Proceedings of 2010 IEEE International Conference on Parallel and Distributed Systems.Washington D.C., USA: IEEE Press, 2010: 423-430. https://ieeexplore.ieee.org/document/5695631
( 0)
|
| [14] |
DANESHTALAB M, EBRAHIMI M, XU T C, et al. A generic adaptive path-based routing method for MPSoCs[J]. Journal of Systems Architecture, 2011, 57(1): 109-120. ( 0)
|
| [15] |
BAHREBAR P, STROOBANDT D. The Hamiltonian-based OddEven turn model for maximally adaptive routing in 2D Mesh networks-on-chip[J]. Computers and Electrical Engineering, 2015, 45(C): 386-401. ( 0)
|
| [16] |
MEENA N K, KAPOOR H K, CHAKRABORTY S.A new recursive partitioning multicast routing algorithm for 3D network-on-chip[C]//Proceedings of the 18th Inter-national Symposium on VLSI Design, Automation, and Test.Washington D.C., USA: IEEE Press, 2014: 1-6. https://ieeexplore.ieee.org/document/6881040
( 0)
|
| [17] |
EBRAHIMI M, DANESHTALAB M, LILJEBERG P, et al. Path-based partitioning methods for 3D networks-on-chip with minimal adaptive routing[J]. IEEE Transactions on Computers, 2014, 63(3): 718-733. DOI:10.1109/TC.2012.255 ( 0)
|
| [18] |
LEE K J, CHANG C Y, YANG H Y.An efficient deadlock-free multicast routing algorithm for Mesh-based networks-on-chip[C]//Proceedings of 2013 International Symposium on VLSI Design, Automation, and Test.Washington D.C., USA: IEEE Press, 2013: 1-4. https://ieeexplore.ieee.org/document/6533824
( 0)
|
| [19] |
赵俊宇, 朱珂, 侯春雨, 等. 面向非全互连3D NoC的自适应混合多播路由算法[J]. 计算机辅助设计与图形学学报, 2017, 29(3): 519-527. DOI:10.3969/j.issn.1003-9775.2017.03.015 ( 0)
|
| [20] |
JHENG K Y, CHAO C H, WANG Haoyu, et al.Traffic-thermal mutual-couping co-simulation platform for three-dimensional network-on-chip[C]//Proceedings of 2010 International Symposium on VLSI Design, Automation, and Test.Washington D.C., USA: IEEE Press, 2010: 135-138. https://ieeexplore.ieee.org/document/5496709
( 0)
|