1、1基于动态注入率的片上网络拥塞避免方法摘要：片上网络的拥塞现象极大地限制了路由器的有效性能，拥塞问题将直接影响到整个处理器芯片的性能.本文首先分析了片上网络中虚通道路由器通信流量的特性.提出设定不同的阈值将网络拥塞状态进行划分，将拥塞避免问题划分为拥塞预防和拥塞解除两个阶段.提出使用一种动态注入率策略，根据实时检测网络的拥塞状态，动态调整网络报文的注入率，将网络中的通信流量控制在一个合理水平内，减轻网络的负载压力，避免 NoC 完全陷入拥塞而出现瘫痪状态.仿真模拟结果表明，拥塞预防时 NoC 性能约在“最大负载点” ，拥塞解除时性能约在“膝点” ，注入率可以达到 0.05，在避免拥塞的同时有效
2、兼顾了网络性能. 关键词：片上网络；拥塞避免；动态注入率 中图分类号：TP391.41 文献标识码：A Dynamic Injecting Strategy for Congestion Avoidance for NoC LI Jin-wen， ZHANG Xi-min （College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China） Abstract： Network-on-chip congestion greatly limits the effective perform
3、ance of the router， and directly affects the performance of the processor chip. This paper divided the networks congestion state by using different threshold， and 2set the congestion avoidance apart into two distinct phases： congestion prevention and congestion relieving. Then a dynamic injection st
4、rategy was proposed. According to the congestion state in real-time， packet injection rate was adjusted dynamically， and communication traffic was controlled in reasonable level to decrease load press， avoiding congestion effectively. The simulation result shows that the performance of congestion pr
5、evention is almost at “Cliff“ point， while congestion relieving is almost at “Knee“ point， the injection rate can reach 0.05， and network performance is tradeoff with congestion avoidance. Key words： network-on-chip； congestion avoidance； dynamic injection rate 片上网络（Networks-on-Chip，NoC）是一种源自于并行计算机网
6、络的片上互连技术，这种网络化的互连方式不但能够有效地克服传统互连结构延迟和带宽等方面的不足，而且更加符合具有显著分布式计算特征的复杂 SoC 的需求.因此，NoC 被视为未来 SoC 中的解决互连问题的关键技术之一. 由于单芯片在功耗和面积开销方面的制约，片上网络可以利用的资源受到很大限制，而另一方面，新一代片上多核系统（MPSoC）的内核频率不断提高，对网络互连通信的高性能和低延迟需求十分迫切，因而，各种高性能的路由器体系结构和无死锁的路由算法相继被提出.然而，在3无死锁路由的前提条件下，片上网络的拥塞现象极大地限制了路由器的有效性能.为了满足片上网络内部的高速通信，缓解拥塞，提高通信的可靠
7、性，降低报文的发送和接收延迟，合理有效的拥塞缓解和避免机制尤为重要. 提高路由器的性能主要是提高其报文吞吐率和降低路由器报文延迟.提高吞吐率的必然途径是提高网络注入率，在无死锁的路由策略下，提高注入率可以适当提高网络吞吐率，但可能会带来网络的拥塞问题，有三方面的原因： 第一，路由器通道资源不足.理论上，要无限地提高网络注入率，只需要无限提高路由器的通道资源，保证注入的报文都能及时地进入通道内进行交换.但在实际应用中是不可行的. 第二，路由器的吞吐率低.不能及时地对报文进行处理交换，限制了注入率. 第三，不合理的路由器策略.主要是报文注入策略，可能出现局部注入报文过剩，导致局部拥塞，从而使整个网
8、络产生拥塞，影响网络的吞吐率. 目前，对拥塞的处理主要有如下几种方法： 1）流控技术1-2.最初采用流控技术是为了防止死锁问题，事实上对拥塞的缓解也很有帮助. 2）面向局部（Regional Congestion Awareness RCA）3和邻近（Proximity Congestion Awareness PCA）节点的拥塞控制策略4.RCA将局部范围的拥塞情况记录下来并广播出去通知整个网络，降低或避免4路由使用出现拥塞的路径；PCA 路由时，通过比较相邻节点的拥塞度来选择路由路径.两种策略均采用负载均衡技术来缓解拥塞. 3）多级拥塞控制路由算法（Multiple Level Conge
9、stion Control， MLCC）5.该算法优先选择拥塞度低的路径进行报文路由. 图 1 为网络性能与负载之间的经典关系曲线.1-2 从图 1 中可以看到，在“膝点” （Knee point）到最大负载点区间，随着注入率增加，都是负载影响占主导地位，即此时增大注入率对网络整体造成的是积极的影响.在最大负载点，两者的影响相当，一旦超过此点，延迟影响将占主导地位.用两者的斜率来表征两者影响的变化快慢可以看到，延迟影响增大的速度比负载增大的趋势要大得多，且负载增大趋势在“崖点”位置已经降为零，而延迟迅速变大. 本文选择最大负载点处为拥塞解除点，崖点处为拥塞预防点，在此基础上提出一种动态注入率策
10、略来避免片上网络拥塞，仿真结果表明了该方法的有效性. 1 拥塞率定义 虚通道是一种将物理通道进行多路复用的技术1-2，每条单向的虚通道由一对独立管理的消息缓冲器实现，并不需要添加额外的通道资源，只是需要在软件层的设计中，能够区分当前正在使用物理通道对应的虚通道.虚通道技术在解决死锁问题的同时，同样可以用来降低消息延迟，提高网络吞吐量，多路复用技术允许消息持续发送而不至于阻塞.因此虚通道路由器得到了广泛应用，本文的算法、理论分析和实验也都基于虚通道路由器. 5本文将网络的拥塞率定义为一个比值，即当前网络的拥塞节点数占网络总节点数的百分比，用 CR 来表示.公式（1）是拥塞率的表达式，其中 N 为
11、网络的总路由器节点数，由网络规模确定；NC 为出现拥塞节点数目. 拥塞节点判定方式如下：无拥塞状态下至多 3 个端口为忙状态；拥塞状态下至少 4 个端口为忙状态.路由器端口处的忙闲状态定义根据该端口的虚通道占用情况进行区分. 对路由器节点设置状态标志位（Node State） ，当路由器处于拥塞时，该路由器节点的状态标志信号为高电平，否则为低电平.这样在任意时刻都能便捷地检测网络当前的拥塞状态，有助于实时地对注入率进行调整.网络拥塞程度可通过查路由器状态表获取. 采用拥塞率（Congestion Rate）来表征当前网络拥塞状态，将网络的拥塞水平分为闲、忙、拥塞和瘫痪 4 种状态，分别对应相应
12、的拥塞水平，即当前注入率在某个范围内时对应相应的拥塞层次，具体划分如图2 示. 基于前述网络拥塞程度定义，本文实现了两种不同的动态注入率策略，并分别定义为拥塞预防（注入率不超过 0.045）和拥塞解除（注入率可以达到 0.05，但检测到网络发生拥塞时会立即发生改变）. 2 拥塞预防 拥塞预防的基本思想是在监测到网络进入拥塞状态时，通过调整注入率，实现拥塞的预防.在拥塞预防中的动态拥塞率使用“加性递增”（Additive Increasing）模型6： 6式中：T 为检测时刻；R 为拥塞率检测周期，如可取固定间隔 1 000个周期，若设定 50 个周期为一个基本窗口（W）大小，则 R=20W；
13、为注入率增大系数（下边界）.图 3 是注入率增加过程示意图. 式（2）中，R 的值取得越大，则在时间 R 内报文的注入体现的随机性越大，注入过程越接近平稳.事实上，随着注入率的不断增加，报文平均在每 50 个时钟周期内注入的报文数也随着增加，如在注入率为 0.05时，平均报文注入为每 50 个周期注入 10 个报文，而在 0.005 时只注入一个报文，因此，固定检测周期 R 对注入率小的时候有利.当注入率很大时，在检测周期内可能已经注入了很多报文，造成检测结果不准确.有效的解决办法是让检测周期可变，即拥塞率越大检测时间越短，这将在拥塞解除情况下可用到. 3 拥塞解除 拥塞预防中，报文注入率增大
14、的趋势逐渐趋于稳定，并没有充分地利用网络资源，发挥出更优的性能.以下方式能够实现注入率达到 0.05时网络性能的最大化.同样地，在拥塞解除中也认为 0.005 为注入率变化的原子单位.拥塞解除时的注入率变化公式如下所示5. 注入率增加： 式中的所有参数跟式（2）中完全一样.另外，RCD 表示注入率在0.05 下网络的拥塞检测时间，RCD 越小，则网络拥塞检测的灵敏度越高.const 是一个常数，加入 const 的目的是为了在检测到网络拥塞时注入率能够调整到原来的初始大小.注入率变化过程如图 4 所示. 图 4 中粗虚线表示没有加入 const 参量时注入率的瞬间跳变过程.如7果不加入 con
15、st 参量，随着仿真周期的增加，初始注入率会越来越接近time 坐标轴，即 Iinj_rate 无限趋于“0”.在动态的注入率过程中，注入率迅速地增大，以便在最短的时间内达到合理的网络状态，尽可能充分地利用网络资源和链路带宽.注入率越大，要求注入率的增幅越小，从而不会向网络中注入过多的报文导致拥塞甚至瘫痪.公式中的 const 参量的另外一个作用就是让注入率在跳变的时候回到的初始注入率尽量地高，从而能让注入率更快地接近跳变点. 4 实验和性能分析 在仿真实验中，采用 Verilog 中的函数实现网络动态注入率调整.拥塞预防中，动态注入率函数实现算法如下： 在上述算法中，T 为时间参量，1 00
16、0 为固定拥塞率检测周期，T%1000 即表示拥塞率检测序数.alpha 即为公式中的 ，取值为0.02.“*”在 Verilog 中表示乘方运算，该运算符左边为乘方运算的基数，右边为幂指数，上述函数能够完整实现拥塞预防中的动态注入率调整过程.函数的调用形式如下： INJECTION_RATE（timestamp-10 000） timestamp 是设置的网络时钟计数器，10 000 是网络的预热周期，预热过程会产生少量的报文，约 200 个，但是产生报文不在报文计数器内，因此预热过程对后面的报文注入过程不会产生影响. 在拥塞解除中，拥塞率的检测周期是可变的，注入率小的情况下检测周期长，注入
17、率大的情况下检测周期短.同时还要实现注入率的周期规律性变化，函数现实算法如下. 算法中 TD 为拥塞率检测间隔，呈8周期性变化，在取拥塞感知时间 TCD 为 250 cycles 时，周期 TC 为 2 500 cycles. 分析发现拥塞预防的动态注入率下的网络特点与注入率为 0.045 的静态注入模式下非常相似，同时拥塞解除时的网络特点与注入率为 0.025的静态注入模式下也很类似，如图 5 所示. 可以直观地看到，在较短的时间范围内（如 2 500 个 cycles） ，基于动态注入率的拥塞解除比拥塞预防的报文注入过程更稳定，在任意拥塞率检测间隔内注入的报文不会超过 100 个，这比拥塞
18、预防中的最高 180个报文数量少了近一半，因此导致了最终产生的报文数量约为拥塞预防的动态注入率下的 1/2. 实验是在 44 的 2D-Mesh，srandom traffic 通信流量模式下采集得到的.事实上可以证明该方法与网络规模以及网络拓扑无关，动态注入率解决拥塞问题的方法适用于任意网络规模和拓扑结构.在仿真过程的100 000 个周期内，两种动态注入率下的网络平均流量都比较稳定，但拥塞解除的注入率过程中可能出现“爆发式”的注入，使网络暂时地进入拥塞状态，这种爆发式注入持续时间很短，注入率的瞬间跳变（变小）完全可以使网络从拥塞状态中恢复过来，因此，拥塞解除过程从长的时间尺度上来说也可认为
19、是拥塞避免的. 5 结束语 NoC 在高注入率下会出现严重的拥塞现象，并且随着注入率增加而加重.在适当的报文注入策略下，可以实现将网络中的通信流量控制在一个合理水平内，从根本上减轻网络的负载压力，有效避免 NoC 完全陷入拥9塞而出现瘫痪的局面，使 NoC 通 信的安全可靠性得到保障.实验证明，动态注入率策略下，可以有效避免 NoC 拥塞，同时，在拥塞预防下的网络性能约处于“崖点”位置，注入率可以达到 0.045；拥塞解除下的网络性能约处于“膝点”位置，注入率可以达到 0.05. 参考文献 1 MARCULESCU R， OGRAS U Y， PEH L S， et al. Outstandi
20、ng research problems in NoC design： system， microarchitecture， and circuit perspectivesJ. IEEE Transaction on Computer-Aided Design of Integrated Circuit and Systems， 2009， 28（1）： 3-21. 2 DALLY W J， TOWLES B P. Principles and practices of interconnection networksM. San Francisco， California： Morgan
21、Kanfman Publishers， 2004. 3 LOTFI-KAMRAN P， DANESHTALAB M， LUCAS C， et al. BARP-A dynamic routing protocol for balanced distribution of traffic in NoCsC/Proceedings of EDAA08. New York： ACM， 2008：3-4 4 KIM J. Low-cost router microarchi-tecture for on-chip networksC/Proceedings of 42nd Annual IEEE/AC
22、M International Symposium on Microarchitecture. New York： IEEE， 2009：255-266. 5 KUMAR A， PEH L S， KUNDU P， et al. Express virtual 10channels： towards the ideal interconnection fabricC/ Proceedings of the 34th Annual International Symposium on Computer Architecture. New York： ACM， 2007：150-161. 6 NYC
23、HIS G， FALLIN C， MOSCIBRODA T， et al. Congestion control for scalability in bufferless on-chip networks（SAFARI Technical Report No.2011-003）R. Pittsburgh， Pennsylvania， United States： Carnegie Mellon University， 2011. 7 KOZIEROK C M. The TCP/IP guide： a comprehensive， illustrated internet protocols referenceM. San Francisco， California： No Starch Press， 2005.
