采用双层子网动态虚通道的片上网络

凌 翔，沈 慧，汪 凡，胡剑浩

(电子科技大学通信抗干扰技术国家级重点实验室 成都 611731)

深亚微米工艺水平在不断地提高，特征尺寸逐渐减小，片上资源之间的互连通信成为片上系统(SoC)设计中制约时延与功耗的关键因素，因此片上网络(NoC)的概念应运而生，成为提高片上系统通信效率的解决方案。传统的宏观网络通信技术被借鉴到芯片内部设计中，在芯片上构建分组交换的微网络，实现多处理器片上系统(MPSoC)中大量处理器、存储单元之间的高效率通信，从体系架构上彻底解决总线结构所引发的问题。

芯片上的处理器之间可能传输不同类型的业务流量，而这些流量有各种各样的特性与需求，因此需要根据数据包的不同应用及性能需求，为它们分配不同的服务等级与服务质量保证(QoS)。由于片上网络与宏观网络的巨大差异，NoC中的QoS保障面临许多新问题。

NoC 提供的服务分为两种基本类型：尽力而为服务(best effort，BE)和有保障服务(guaranteed，GT)[1]。在NoC中，BE服务只需实现数据正确传输，不必完全满足某些通信性能的要求。然而，NoC在业务流量比较重的情况下可能会发生拥塞，因此，在对延迟和吞吐率等有特殊要求的实时信号处理系统中，BE服务可能会无法适用。这就导致GT服务的出现，GT服务要求满足数据包传输的正确性和成功率。GT服务又可细分为硬GT服务和软GT服务两种。硬GT服务主要通过预留存储资源实现，属于面向连接的方式。MANGO、AETHEREAL等NoC仿真系统就采用面向连接的方式，通过预留带宽资源，实现服务质量的硬保障[2-3]。软GT服务系统通常是动态分配虚通道(VC)[4]，将数据包划分为多个服务等级来保障其服务性能[5]，具有统计特性的保障，如QNoC、AdNoC等[6-9]。在设计软GT服务前，需知道注入的流量模型，根据仿真结果，研究者需要了解应该给各节点分配多少带宽以保证达到确定的性能要求。而QoS中的BE服务不提供承诺，在某些情况下也可以归到低优先级的软GT服务中。

本文在设计提供GT服务的NoC路由器时采用硬GT保障技术，即在传输数据业务流量之前为其分配VC资源用于建链，使不同等级的GT数据业务流量与NoC中的其他数据流量实现逻辑上的隔离，避免了该GT业务流在网络中被堵塞，以对其实现服务质量保障。提供硬保障服务对资源的需求比较高，因为必须考虑最坏情形，可能会过度分配资源，从而导致浪费。在宏观网络中可以大量使用存储资源，而NoC中若增加缓存资源，其面积和功耗会急剧增加，而大大影响NoC的系统性能。芯片面积、功耗的要求限制了缓存资源的数目[10]。针对这种情况，本文在不增加缓存资源(即VC资源)的基础上，对NoC网络接口(NI)模块和路由器模块的结构做改进，利用双层子网技术和动态虚通道分配技术来增加建链成功率，降低服务连接建立的等待时间，提高NoC的数据包传输速度，最终提高NoC的整体传输性能。

1 片上网络结构

一个4´4 mesh 片上网络结构如图1所示，它主要由路由器(R)、链路、网络接口(NI)和本地子系统组成。本地子系统包括处理单元(PE)与私有存储器，PE通过局部总线访问私有存储器，通过NI连接NoC网络，经NoC网络与其他PE传输数据。

图1 4´4 mesh NoC网络结构

一具有QoS保障的路由器结构如图2所示，数据微片(flits)由输入端口进入，在输入端口控制逻辑下，将数据信息解复用到对应的VC。路由器根据输入端口调度规则，将选定VC的数据微片依据数据格式，传入相应的BE路由交换模块或GT路由交换模块。NoC系统网络层依靠路由器主要完成了存储转发和路由计算等功能。路由器的结构主要由输入端口控制器、输入虚通道、输入仲裁器、BE路由交换单元、GT路由交换单元、输出控制器构成。

图2 传统的QoS路由器结构图

2 动态虚通道技术

通常，片上网络路由器中的虚通道采用静态分配方式，且给每个路由节点的每个端口分配相同数目的VC，称之为静态均衡分配VC。然而实际中，路由器各个端口发送或接收的包流量并不均衡，某些端口的流量负载可能重一些，而某些端口则没有数据流通，从而导致某些端口的VC资源紧张，而某些端口的VC被闲置，在这种情况下，如果每个端口分配同等数目的VC就会造成比较严重的资源浪费。传统的VC静态分配技术对非平衡的业务负荷不具有很好的适应性，可能会使某些节点中某些方向上的VC资源不够用，建链失败，导致建链成功率很低。因此，在QoS路由器中采用动态虚通道技术以提高建链成功率。

本文在虚通道静态分配的基础上，将一部分VC资源统一管理，根据各端口的需求情况进行动态分配，提出了动态VC分配的QoS路由器结构(Dyn-VCQoS-NoC)。对于BE数据包，动态VC管理模块实时监测节点各端口的数据包传递的方向，若产生一个新的方向，则给该数据包分配新的静态VC资源，如果静态VC用尽，则分配新的动态VC。当检测到一段时间该端口的数据包投递的方向个数小于给该端口分配的动态VC资源的数目，则可以释放掉动态VC，这样，网络能够很好地适应非平衡的业务流量波动变化。预留的动态VC资源被路由器的所有端口间共享，根据通信业务需求进行动态调度。对于GT建链包，已有的建链包占用完该端口的所有静态VC资源后，若该端口又收到新的GT建链请求，则为该端口分配一个动态VC用于虚链路的搭建，在该GT数据服务传递期间，该动态分配的VC一直被占用，直至收到最尾一个数据包或源拆链包之后才释放VC资源。因此，在QoS路由器中采用动态分配虚通道技术不仅能够很好地提升建链成功率，还极大程度地节约了存储器资源，有效减小芯片面积。

对BE包而言，这不仅保证了VC分配的实时性，而且提高了缓存资源利用率；而对GT包而言，提高了GT建链的成功率。

动态VC分配比静态VC分配复杂。在保留原有的路由计算模块、VC分配单元和交换开关等部件外，还需要增加动态VC控制单元，用来实现动态VC的分配、建立、拆除过程。动态分配虚通道的QoS路由器结构如图3所示。

图3 动态VC分配的QoS路由器结构

路由器的每一个输入端口各有k个静态分配的虚通道，所有端口共有n个用于动态分配的虚通道资源。路由器的每个输入端口都会有一份传递方向记录表，记载动态VC所提供服务的源节点编号、目的节点编号和服务等级标识。当输入端口检测到新的数据包建链请求时，如果端口的静态VC全部被占用，而有空闲的动态VC时，此时才给该新的建链包请求分配动态资源，提供建链所必须的资源。输入端的VC仲裁对该端口的静态VC和选定的动态VC进行仲裁，选择出一路向输出端口发出申请。若动态资源分配给端口建立连接，则其具体后续操作和普通静态VC类似。不同的是，若建链失败，则收到反馈信号后，释放的预留动态VC资源仍可以被任意路由端口使用。对GT建链包而言，当该建链包传递经过，则节点一直预留某一VC资源用于GT业务数据的传输，直至源端最尾一个数据包释放该虚链路，被该服务占用的动态虚通道才会被释放，从而可以再次用于其他端口的新的服务。

Dyn-VC-QoS-NoC优点在于它可以在虚通道数目不变或减少的情况下，适应不均衡的业务流模型，极大地提高建链成功率和VC利用率，这对各种优先级服务的性能改善是非常明显的。然而，Dyn-VC-QoS-NoC结构可能导致在一段时间内某段链路上同时提供的业务数目过多，从而使得该段物理链路上的竞争过于激烈，导致数据包的平均传输时延升高、性能降低。为此，进一步提出了双层子网技术，通过将网络划分成两层，分散业务流，减小拥塞，降低数据包平均传输时延。

3 双层子网技术

常规的XY路由算法一般是先X方向，再Y方向路由，它是无死锁的，但易造成阻塞。对于GT服务的数据包，利用这种常规的XY路由算法会导致GT建链成功率比较低，低优先级的GT数据包很有可能没办法获资源，使得建链失败。

为了提升GT数据业务建链成功的概率，提高各等级数据业务的服务质量，本文提出双层子网(dualnet)结构[11]，按照源节点和目的节点的位置关系对数据包分别在子网中进行XY或者YX路由方式。XY-YX混合路由优先选择方式的伪代码如下：

当选定的优先路由方式建链失败时，源节点则选择另一个子层路由建链。

按照上述基于源/目的地址关系对路由优先选择方式，图4b中将图4a中比较拥塞的节点6至节点7之间链路上的数据流分散开，从而避免了链路竞争，提高数据包的传输效率。

图4 双层子网基于固定源/目的地址对路由优先选择方式

在NoC上同时执行XY和YX路由方式很容易导致死锁的发生，而本文提出的双层子网的网络结构则能够避免这种问题。

建立双层子网的mesh网络要增加路由器之间的物理链路，如图5所示；还需对路由器内部结构做一些相应的设计，如图6所示。当新的数据包由输入端口传入路由器时，首先要判断它是经过XY子网还是YX子网传入的，然后其相应的子网控制器会对数据做出处理。

双层子网在本质上是通过增加链路资源提高传输吞吐率，由于存储资源(即VC资源)不变，因此芯片面积开销增加不多。

图5 4´4 mesh双层子网示意

图6 双层子网的QoS路由器结构

4 结合动态VC分配与双层子网的Dyn-dualnet-QoS-NoC

双层子网可以分散数据流，减小网络的拥塞程度，降低平均数据包传递时延；动态分配VC策略则能提高VC利用率，节省面积，同时提升建链成功率。本文最终结合两者的优点设计提高QoS保障的NoC路由器，设计的Dyn-dualnet-QoS-NoC结构如图7所示。普通的静态VC分为两组，分别用来进行XY子网和YX子网的数据包投递；动态VC也分为两组，分别分配给XY子网及YX子网的数据包路由传输过程。因此，从整体结构看，所有的VC通道仍是分布在两张独立的网络上的，两个子网上均不会出现环路状态，从而有效避免死锁的发生。各子网的待分配的动态VC根据各输入端口的请求由它们的分配控制单元分别分配给各端口。图8b中将图8a中拥塞的节点1至2、节点1至5、节点6至7之间链路上的数据流分摊到两个子网，从而避免了链路竞争。

Dyn-dualnet-QoS-NoC既可以在节约VC资源的基础上适应各端口流量不均衡的情况，缩短平均建链时间，又可以利用双层子网的特性，分散业务流，提高链路的传输效率。

图7 Dyn-dualnet-QoS-NoC结构

图8 Dyn-dualnet-QoS-NoC结构对3类QoS等级业务的建链情况的优化

表1 QoS-NoC、Dyn-VC-QoS-NoC和Dyn-dualnet-QoS-NoC资源耗费对比表

由于Dyn-dualnet-QoS-NoC结构中采用了动态分配VC的策略，因此，在路由器中使用较少的VC资源即可满足业务需求。对于4´4的mesh NoC网络，其相比于普通QoS-NoC节约了16.7%的虚通道资源。

4 仿真结果

在MSNS仿真器[12]上进行仿真，采用泊松注入模式。数据包根据泊松分布的流量模型由PE层产生，注入到NI层的缓存资源中；数据包以flit的形式注入NoC网络。

GT业务分3个等级：等级1为低优先权业务；等级2为中优先权业务；等级3为高优先权业务。BE业务与GT1、GT2、GT3业务各具有相同的注入强度。

图9 3种QoS机制下各等级数据包平均建链成功延时

图10 3种QoS机制下各等级数据包平均传输延时

图11 3种QoS机制下各等级数据包吞吐量

GT1、GT2、GT3的数据包的平均建链延时如图9所示，动态虚通道机制、双层子网动态虚通道机制都比普通QoS策略降低了平均建链时延。在传统QoS-NoC中，低优先权业务的建链请求会被滞后响应。而在Dyn-dualnet-QoS-NoC中，低优先权业务GT1的建链时延减少了44%，GT2的建链时延减少了42%，从而证明了Dyn-dualnet-QoS-NoC结构可以提高各等级业务的建链性能。

各等级数据包平均传输延时的比较如图10所示。传输延时是指从数据包请求发送到最后一个微片到达目的节点的时间。从图10中可以清晰地观察到，改进后的Dyn-dualnet-QoS机制系统各等级数据包的平均传输延时都比普通QoS机制大幅降低了；从低优先权GT1、GT2到高优先权GT3业务的平均传输延时分别降低53%、44%和28%。Dyn-VC-QoS机制下的平均传输延时比普通QoS机制略高，是因为Dyn-VC-QoS机制使用的虚通道数量少，对性能略有影响。

而Dyn-dualnet-QoS机制相应的其各GT等级的数据包平均吞吐量都增加，如图11所示。在饱和状态下，Dyn-dualnet-QoS机制从低优先权GT1、GT2到高优先权GT3业务的平均吞吐率比普通QoS机制分别提高了118%、83%和46%；比Dyn-VC-QoS机制分别提高了77%、89%和60%。

图10和图11中性能的提高是因为本结构中采用了双层子网结构，将数据流分散到XY层和YX层中，避免了部分X路径或Y路径上过于拥塞。

5 结 论

本文主要通过对NoC路由器结构做改进来提高保障服务的建链效率，提高整个NoC网络的传输性能。结合动态虚通道分配技术和双层子网结构，提出了一种Dyn-dualnet-QoS-NoC策略。动态虚通道分配技术提高了建链成功率，双层子网结构则较好地分散了数据流，避免数据包拥塞，降低了数据包的传输延时。Dyn-dualnet-QoS-NoC达到面积和传输效率上的平衡，在保证提高建链成功率的基础上，既提升各个等级服务数据传输的吞吐率，又可以有效减小虚通道资源开销。

[1] RIJPKEMA E, GOOSSENS K, RADULESCU A, et al.Trade offs in the design of a router with both guaranteed and best-effort services for networks on chip[C]//Proceedings Computers and Digital Techniques. [S.l.]: IEE, 2003.

[2] BJERREGAARD T, SPARS J. A router architecture for connection-oriented service guarantees in the MANGO clockless network-on-chip[C]//Proceedings of the Design,Automation and Test in Europe Conference. Munich: IEEE,2005: 1226-1231.

[3] GOOSSENS K, DIELISSEN J, RADULESCU A. The Aethereal network on chip: concepts, architectures, and implementations[J]. IEEE Design and Test of Computers,2005, 22(5): 414-421.

[4] WINTER M, FETTWEIS G P. Guaranteed service virtual channel allocation in NoC for run-time task scheduling[C]//Proceedings of the Design, Automation and Test in Europe Conference. Grenoble: IEEE, 2011: 419-424.

[5] WISSEM C, BRAHIM A, ABID N, et al. A quality of service network on chip based on a new priority arbitration mechanism[C]//Proceedings of the International Conference on Microelectronics. Hammamet: IEEE, 2011.

[6] BOLOTIN E, CIDON I, GINOSAR R, et al. QNoC: QoS architecture and design process for network on chip[J].Journal of Systems Architecture, 2004, 50(2-3): 105-128.

[7] MOHAMMAD A A F, THOMAS E, JORG H. AdNoC:runtime adaptive network-on-chip architecture[J]. IEEE Trans on Very Large Scale Integration Systems, 2012, 20(2):257-269.

[8] PHAM P H, PARK J, MAU P, et al. Design and implementation of backtracking wave-pipeline switch to support guaranteed throughput in network-on-chip[J]. IEEE Trans on Very Large Scale Integration Systems, 2012, 20(2):270-283.

[9] WU X W, WU Y L, WANG L, et al. QoS router with both soft and hard guarantee for network-on-chip[C]//NORCHIP.Trondheim: IEEE, 2009: 1-6.

[10] WANG L W. A virtual channel calculation algorithm for application specific on-chip networks[C]//Proceedings of the 3rd International Conference on Intelligent Networks and Intelligent Systems. Shenyang: IEEE, 2010: 541-544.

[11] SHEN H, LING X. The routing strategy of network-onchip with dual subnets infrastructure[C]// Proceedings of the 3rd International Conference on Computer and Electrical Engineering. Chengdu: IEEE, 2010.

[12] LI Z Q, LING X, HU J H. MSNS: A top-down MPI-style hierarchical simulation framework[C]//Proceedings of 2009 WRI International Conference on Communications and Mobile Computing. Kunming: IEEE, 2009: 609-614.