一种高效NOC路由选择机制的设计

摘要：NOC性能的优劣很大程度上取决与它使用的路由算法，其中包括两大块：输入选择和输出选择。先前的工作大多是研究如何改进输出选择，现论证输入选择对于路由效率的影响，并设计一种行之有效的输入选择机制―基于阻塞程度的输入选择机制。该机制工作在多个输入同时请求同一个输出时，会自动根据上流路由器的阻塞程度优先选通阻塞最严重的输入沟道，从而大大减少了网络的阻塞。实验结果证明，在不同的通信模式下，不论是与确定性输出选择还是与自适应性输出选择结合使用，该文设计的输入选择机制在性能上都优于传统的先到先得的输入选择机制。

关键词：片上网络；阻塞程度的输入选择；先到先得；阻塞程度

中图分类号：TP302文献标识码：A文章编号：1009-3044(2012)10-2232-05

An Efficient Routing Mechanism Design for NOC

WANG Yong, ZHANG Rong, PAN Pan, MENG Jian

(Institution of electronic and Information Engineering, Anhui University, Hefei 230601, China)

Abstract：The performance of Network-on-Chip largely depends on the routing techniques, which have two constituencies: output selection and input selection. Previous research on routing techniques for Network on chip has focused on the improvement of output selection. This paper investigates the impact of input selection, and presents a novel block-level input selection technique for network on chip that improves the routing efficiency. When multiple input channels competing for the same output channel, block-level input selection decides which input channel obtains the access depending on the block level of the upstream switches, which inturn removes network congestion deeply. Simulation results with different traffic patterns show that, when combined with either deterministic or adaptive output selection, block-level input selection achieves significant better performance than the traditional first-come-first-served input selection.

Key words: Network-On-Chip; Block-Level-Input-Selection; First-Come-First-Service; Block-Level

随着半导体技术的发展，集成到单个芯片上的IP核越来越多，传统的总线通信在可扩展性和高效性上已遇瓶颈。研究人员将计算机网络技术移植到芯片设计中，提出一种片上网络（Network on chip，NOC）[1-3]通信架构。相比总线结构，NOC架构在带宽、可扩展性、可靠性上都有较大的提高。

如图1（a）所示，是4X4 mesh型拓扑结构的NOC，主要由通信节点和资源节点组成。每个IP核为一个资源节点，通过网络接口与一个通信节点（switch）互联，资源节点之间通过发送和接收数据包的方式进行通信。数据包由一个个数据微片构成。每个数据包从源节点到目的节点的通信链路有很多条，数据包通过每条链路所需要的时间各不相同。特定的路由技术不仅为数据包的传送选好路径，还决定了switch的工作状态。图1（b）所示为switch的结构图，它是由n+1条输入沟道（input channel，IC）和n+1条输出沟道（output channel,OC）通过交叉开关（crossbar）连接而成。Switch中需要植入一定的路由算法，才能使数据包在网络中传输。而这个路由算法由两大部分组成：输出选择和输入选择。一个数据包从某个IC流入，可以从多个OC中流出。例如，从IC_0中流入的数据包p0可以从输出沟道OC_0，OC_1等等中流出。这时，输出选择就决定了数据包具体选择哪一条OC输出。同样的，可能有多个输入沟道IC请求通过某一条输出沟道OC进行数据包输出。例如，IC_0中数据包p0和IC_1中数据包p1同时请求从OC_0中输出。这时，输入选择就需要选出具体是哪一条输入沟道IC获得选通权。

先前的很多工作[4,5]都是研究输出选择对路由效率的影响。该文提出一种新的基于阻塞程度的输入选择机制（block-level input selection，BLIS）。该机制可以使链路通信变的流畅，提高通信效率。实验研究表明，与传统的先到先得（first come first served，FCFS）输入选择机制相比，该机制不论是与自适应性输出选择还是与确定性输出选择结合使用，都大大降低了传输延迟。

1基于阻塞程度的输入选择机制

先前已有先到先得（FCFS）[4]输入选择机制应用于NOC中，FCFS的输出沟道给了请求最早的输入沟道，因此所有输入沟道的优先级都是等同的，然而这种输入选择并没有考虑实际网络通信情况。本节提出一种不同阻塞程度下灵活选择输入沟道的输入选择机制。

图1 4X4 mesh型NOC与通信节点结构图

1.1输入选择机制

为了说明输入选择和输出选择对路由效率的影响，现在考虑如图2所示的一组通信节点网络，为了简单起见，IP核没有画出。

图2输入输出选择机制

通信节点Switch颜色的灰暗程度表示其中等待的数据包数量。随着颜色的加深，switch中等待的数据包数量逐渐增多。白色的switch中等待的数据包数量最少，灰色有比白色要多，黑色的switch如节点（2，2），表示其中等待的数据包数量最多。为了证明输出选择对路由效率的影响，现在考虑数据包p0从节点（3，0）起始，传送到节点（0，2），现有多条路径可以选择，例如path1，path2。传输延迟较少的路径需要避开阻塞区域（如图中灰色和黑色的switch区域），所以path1与path2相比，延时较少，路径较优。这就证明了输出选择对路由效率的影响，一条合适的路径可以减少链路时延。现在考虑输入选择的影响，节点（3，2）处的数据包p1和节点（4，3）处的数据包p2同时想通过节点（3，3）。在这种情况下，较好的选择是让p1通过节点（3，3），因为节点（3，2）处比节点（4，3）处等待的数据包要多，网络阻塞程度要高。这样的选择将会降低阻塞更严重区域中等待的数据包数量，降低网络阻塞，进而提高NOC的性能。由此，该文提出一种基于阻塞程度输入选择机制（block-level input selection，BLIS）。

BLIS的基本思想是赋予输入沟道不同的优先权来选通输出沟道，而输入沟道的优先级是在通信过程中基于上流switch阻塞程度动态授予的。精确的来说就是通信节点中每个输出沟道根据当前switch中输入沟道的输出请求次数，得到一个BL（block level）值，然后把得到的BL值（即为输出请求次数）传送给下路相邻switch对应的IC，再根据所得BL的值来断定下路相邻switch中对应IC的优先级别。当某个通信节点中，同时有多个IC请求同一个OC输出时，BL最大的IC优先级最高，优先被选通。

图3作出了含有BLIS的switch结构图，可以看出该switch除了含有用来传输数据的连接线，还额外包括用来传送相邻switch BL的连接线。该switch共有n+1条IC和n+1条OC，每个IC中还有一个缓存（buffer），那些即将到来的数据包微片在还没送到某个OC之前，就暂时存放在buffer中。输出选择（OS）模块根据数据包的头微片，决定整条报文从哪个OC中输出。OS模块将输出请求发送 到对应的OC。一旦某个OC空闲，OC中的BLIS模块就会检查所有的输出请求并发送一条选择信号给MUX模块，MUX模块再将获得许可的输入数据输出。如果只有一条输出请求，那么那条数据可以直接传送。如果有多条请求，则需考虑此刻具体哪个请求可以被选通。这个选择机制接下来做详细介绍。

图3含有BLIS路由器结构

2.2 BLIS算法伪代码

BLIS根据输入沟道BL的大小作出选择，输入沟道BL的取自上流相邻switch输出沟道的BL。上流switch输出沟道的BL是特定时刻收到输入沟道传送请求的次数。

图4 BLIS算法伪代码

图4为该输入机制算法的VHDL伪代码，它包括了两个并行的进程。当req_0...n变化时，进程observe_BL被激发，它根据当前第 i个输出沟道收到的请求次数，将BL值赋予out_BL_i。接着BL值被传送到下流相邻switch中对应的第i个输入沟道并用于输入选择。例如，考虑图3所示的switch，IC_0和IC_1同时请求OC_0，则out_BL_0的值就是2，下流相邻的switch的in_BL_0的值也是2。为了避免高复杂性和硬件消耗，BL值传送到下一个相邻的switch中就截止，不会继续向更远的switch传送。例如先前的例子，IC_0的in_BL_0的值为3，IC_1的in_BL_1值为4，IC_0和IC_1同时请求OC_0，OC_0中out_BL_0值不是3+4而是2。当有输出请求且输出沟道空闲时，select_input进程被激发。它比较所有的输出请求及对应的输入沟道BL的值，选择BL值最大的作为输出。

对于那些与IP核相连的输入沟道，它们没有上流switch传送BL给它们。这些输入沟道的BL值默认设置为0，因此，网络中所有正在传送的数据包优先级都高于IP核中正在等待注入网络的数据包。

2实验结果

该文设计了一系列实验来评估BLIS的性能，并与传统的FCFS输入选择做了对比。两种输入选择分别与确定性路由输出（XY路由[6]）和自适应性路由输出（OE路由[7]）结合使用，并用VHDL实现了四种路由模型：XY+FCFS，XY+BLIS，OE+FCFS，OE+BLIS，四种模型都在6X6 mesh NOC上做了仿真。由先前的工作[4,9]可知，路由算法的性能的主要是通过传输延迟来评估的。在给定的注入率（在一个周期内注入网络的数据包数）下，我们测量每个数据包的平均传输延迟。一个数据包的传输延迟时间是指从源节点数据包的第一个微片产生开始到最后个微片送进目的节点后所持续的时间。所有的仿真都是基于50，000个数据包求平均的。考虑到网络的稳定性，在头5000个周期内传输延迟不作计算。假定，数据包的固定长度是5个微片，输入沟道的buffer深度也是5个微片。将该文的路由算法应用到三种不同的通信模式上：普通（uniform）模式，对调（transpose）模式，热点（hot spot）模式[7]。在普通模式下，每个IP核随机的发送数据包去另一个IP核。在对调模式下，节点（i，j）IP核发送数据包去节点（5-i，5-j）IP核。在热点模式下，节点（3,3）IP核被设为热点，它比在普通模式下收到的数据包数量要高出10%。

图5显示了在普通模式下四种路由算法的性能。X轴代表的是每个节点的注入率，Y轴是数据包平均延迟。由图可得，在低注入率下（

图5普通模式下算法性能

图6显示了在对调模式下四种算法的性能。由图可知，在结合使用XY算法下，FCFS算法和BLIS算法性能几乎相同。在结合OE算法，FCFS算法的性能稍稍优于BLIS算法的性能。这是因为在对调通信模式下，很少出现多个输入同时请求一个输出的情况，从而输入选择对整个路由算法的性能影响很小。图7是在热点模式下四种算法的性能体现。不论是结合XY输出选择还是OE输出选择，同样可以得出BLIS算法的性能要优于FCFS算法的性能。此外，尽管在FCFS输入选择下，OE算法比XY算法性能要差。但在BLIS输入选择下，OE算法的性能却比较接近XY算法的性能。

图6对调模式下算法性能

图7热点模式下算法性能

以上实验均证明了输入选择的重要性。该文设计的BLIS输入选择很大程度上提高了NOC的路由效率。

3结论

该文证明了输入选择对于路由效率的影响，并设计了一种基于阻塞程度的输入选择算法（BLIS）。BLIS是根据上流switch的阻塞情况，赋予那些比较繁忙的输入沟道更高的优先权来输出。在高负载情况下，促使阻塞区域得以继续通信，减少了网络的阻塞。与输出选择机制结合使用，该文设计了四种路由方案。实验证明除了在对调模式下，BLIS输入选择与传统的FCFS输入选择性能相近外，其余模式下，BLIS性能均优于FCFS。在一些模式下，BLIS还能使复杂度低硬件需求少的XY路由算法在性能上接近甚至超过高复杂度硬件需求高的OE算法。

参考文献：

[1] Benini L, De Micheli works on chips: A new SoC paradigm[J].Computer, 2002,(35):70-78.

[2] Henkel J, Wolf W, Chakradhar S.On-chip networks: A scalable,communication-centric embedded system design paradigm[J]. VLSI Design, 2004(1):845-85.

[3] Dally W J , Towles B.Route packets, not wires: On-chip interconnection networks[J].DAC, 2001:684-689.

[4] Hu J , Marculescu R.DyAD Smart routing for networks-on-chip[J].DAC,2004:260-263.

[5] Nilsson E, Millberg M, Oberg J, et al.Load distribution with the proximity congestion awareness in a network on chip[C]. DATE, 2003(1): 126-7.

[6] Ni L M, McKinley P K. A survey of wormhole routing techniques in direct networks[J].Computer, 1993(26): 62-76.

[7] Chiu G M.The odd-even turn model for adaptive routing[J].IEEE Transactions on Parallel and Distributed Systems, 2000(11):729-38.