广东工业大学学报  2017, Vol. 34Issue (4): 97-101.  DOI: 10.12052/gdutxb.160020.
0

引用本文 

张坤, 刘怡俊. 一种提高无缓存片上网络性能的方法[J]. 广东工业大学学报, 2017, 34(4): 97-101. DOI: 10.12052/gdutxb.160020.
Zhang Kun, Liu Yi-jun. A Method of Raising Bufferless Network-on-Chip Performance[J]. JOURNAL OF GUANGDONG UNIVERSITY OF TECHNOLOGY, 2017, 34(4): 97-101. DOI: 10.12052/gdutxb.160020.

基金项目:

广东省科技计划项目(2015B090908001，2013A090100005，2014B090901061，2015B090903080)；广州市科技计划项目(2014Y2-00211)

作者简介:

张坤(1993–)，男，硕士研究生，主要研究方向为片上网络。

通信作者

刘怡俊(1977–)，男，教授，博士，主要研究方向为计算机体系结构、集成电路设计. E-mail： yjliu@gdut.edu.cn

文章历史

收稿日期：2016-02-29
Contents              Abstract              Full text              Figures/Tables              PDF
一种提高无缓存片上网络性能的方法
张坤, 刘怡俊     
广东工业大学　计算机学院， 广东　广州  510006
收稿日期：2016-02-29
基金项目：广东省科技计划项目(2015B090908001，2013A090100005，2014B090901061，2015B090903080)；广州市科技计划项目(2014Y2-00211)
作者简介：张坤(1993–)，男，硕士研究生，主要研究方向为片上网络。
通信作者：刘怡俊(1977–)，男，教授，博士，主要研究方向为计算机体系结构、集成电路设计. E-mail： yjliu@gdut.edu.cn
摘要: 无缓存片上网络路由在低负荷时表现较有缓存路由有能耗低、延迟低的优势, 而在较高负荷情况下由于竞争的增加和较多的微片偏转的出现降低了无缓存路由的性能, 使得延迟增加、能耗升高. 本文从拥塞控制出发, 提出了一种新的流控方式降低在高负荷情况下因为过多的微片偏转对无缓存片上网络产生的影响. 该方法是通过基于对优先级控制算法的改进可以实现拥塞控制, 降低在拥塞发生时微片的偏转次数. 通过模拟仿真, 该方法可以有效降低在高负荷情况微片的偏转次数和平均延迟.
关键词: 无缓存    片上网络    低延迟    低功耗    
A Method of Raising Bufferless Network-on-Chip Performance
Zhang Kun, Liu Yi-jun     
School of Computes, Guangdong University of Technology, Guangzhou 510006, China
In low load, bufferless Network-on-Chip (NoC) routing performance is better than buffered routing, and has the advantage of low-power dissipation and low latency. But in the condition of high load due to increased competition and the emergence of deflection decrease bufferless NoC routing causes more time-delay and energy consumption. Based on congestion control, a new way is proposed to reduce packet deflection on bufferless NoC in high load condition. The competition frequency of each output link of the router in the congestion register is recorded. When competition occurs on one output port, a count is increased in the corresponding register. According to the priority policies, while winning the route calculation flits through the effective output port, the other flits are deflected to an inactive output port of low congestion degree. This method, based on improvement of the priority control algorithm, can effectively reduce the number of flits deflection when the congestion occurs. Through the simulation, this method can effectively reduce the deflection and average delay of a flit in high load condition.
Key words: bufferless    NoC    low-latency    low-power dissipation    

近年来，在计算机体系结构中单芯片集成多CPU核已经成为一个重要的发展趋势，片上网络(Network-on-Chip)被认为是解决多核间通信问题的重要途径[1]. 随着片上网络核心数量的增加，性能和成本越来越成为片上网络设计的关键因素. 理想的片上网络需要具备低延迟、高吞吐、低功耗[2]性能.

由于片上网络的功耗和芯片面积限制，当前的片上网络路由设计多是基于有缓存的虚通道路由. 缓存增加了芯片的成本、功耗和延迟，并降低了系统的时钟频率[3]，同时缓存占用了较大部分的芯片面积[4]. 在TRIPS原型的芯片中，路由缓冲区占据了片上网络面积的75%. 因此，研究人员提出了基于无缓存NoC的路由设计[5]. 无缓存NoC路由设计是通过移除路由节点缓存来实现的. 在无缓存NoC路由中，当多个微片同时竞争同一个输出端口时，将其中一个正确转发，其他微片则偏转到其他方向或者丢包重传. 在低负载情况下，竞争较小，微片出现偏转或丢包情况较少，其性能表现较有缓存路由好. 但在较高负载时，无缓存路由就会因竞争加大出现偏转过多引发拥塞[6]，导致延迟过高，其性能表现较有缓存路由低.

因此，目前针对无缓存NoC的研究主要是在高负载下如何通过减少偏转控制拥塞的发生来提高性能. 文献[7]使用FLIT-BLESS的偏转路由算法，该算法递增偏转微片的年龄使其在下次竞争中有较高的优先级，但缺少相应的拥塞控制. 文献[8]在FLIT-BLESS的基础上研究了通过添加自环回道的方式减少偏转次数的发生，但当某些节点通信量较大时，容易形成多点拥塞. 文献[9]提出了一种基于信约方式的拥塞控制，其中每个节点通过隐式反馈存储了其他节点的可用缓冲空间，但当节点数量较多时，增加了维护缓存空间的复杂性.

综上所述，本文以FLIT-BLESS为基础从拥塞控制出发提出了一种适应性优先策略算法提高无缓存NoC的平均性能，并以FLIT-BLSS作对比，模拟结果显示，本文提出的路由算法的性能要比FLIT-BLESS性能优越.

1 无缓存片上网络 1.1 NoC约束

拓扑结构是影响NoC性能的重要因素[10]，拓扑结构直接影响了网络直径、吞吐率和路由方式. 在无缓存路由中，由于没有缓存，输入的数据微片经过路由计算后必须及时地通过输出端口转发出去. 为了正确路由每个数据数据包，要求每个路由器的输出端口数量至少等于其输入端口数量，且任意两个路由器之间是可达的[11].

本文所提出的算法是基于2D-mesh[12]拓扑结构实现的. 2D-mesh拓扑结构简单且易于实现，因此该拓扑结构在NoC研究中比较常见，其拓扑结构如图1所示.

在偏转路由中，数据包是以数据微片的方式传输的. 当一个数据包注入网络时，首先要被分割成多个数据微片，文献[13]研究了两种微片的传输方式FLIT-BLESS和WORM-BLESS，实验表明，FLIT-BLESS要比WORM-BLESS传输效率高. 在FLIT-BLESS中，同一数据包的微片可以独立传输，每个数据微片都包含了完整的路由信息.

图 1 2D-mesh拓扑结构 Figure 1 2D-mesh NoC
1.2 拥塞控制策略

拥塞的发生增加了数据微片传输的平均延迟. 在有缓存的路由中，文献[14]提出基于拥塞的DyXY的路由算法. 该算法依据每个路由器瞬时缓冲区可用量来衡量其拥塞程度，在所申请的缓冲区不可用时，动态将数据包路由到拥塞度较低的节点. 无缓存NoC由于没有缓存，因此无法使用缓冲区的可用量作为衡量拥塞程度的标准.

为了表示每条链路的拥塞程度，本文使用每条链路出现竞争的频数衡量链路的拥塞程度. 在路由器中添加一个路由拥塞寄存器，记录每个输出端口出现竞争的频度，且每个路由器只需要维护本地路由节点的拥塞信息. 容易发生竞争的输出链路称为“热点区”，反之则为“非热点区”.

数据微片发生竞争时，通过优先级仲裁获胜的微片将通过有效的输出端口输出，而竞争失败的微片则被偏转到一个拥塞度最低的非有效输出端口. 有效的输出端口是指当一个数据微片被传输到一个路由从输出端口输出后，能够缩短到达目的节点的距离. 反之，则为非有效的输出端口. 被偏转的数据微片通过拥塞度低的端口输出，拥塞度低的输出端口由于出现竞争的概率小，因此数据微片有较多的机会从有效输出端口传出，从而避免了热点区，降低了微片传输的平均延迟.

本文在链路拥塞寄存器中记录该路由器中每条输出链路发生竞争的频度Fi. 当输出端口出现竞争时，在相应的寄存器中增加一个计数，表示为

$\left( {{F_i}{\rm{ = }}{F_i}{\rm{ + 1}}} \right) \leqslant {\rm{ }}T.$ (1)

其中，T表示设定的阈值. Fi的值越大说明该端口出现竞争的概率越大，由于寄存器计数大小和阈值T的限制，Fi不能无限增大. 在每个时钟周期检测Fi的值，每当其中一个或多个Fi的值等于阈值T时，则将所有的Fi的计数值右移一位表示为

${F_i}{\rm{ = }}{F_i} > > 1.$ (2)
2 AOC-BLESS路由算法 2.1 相关介绍

路由算法决定了数据微片从源节点到目的节点的传输路径. 良好的路由算法要求数据微片传输路径尽可能短，且没有死锁活锁发生. 在没有竞争的情况下的，数据微片通过路由计算沿着最短路径传输. 当出现多个数据微片竞争同一个输出端口时，路由算法需要合理地分配通道，使得每个数据微片在一定的时间内均能到达目的节点.

由于无缓存路由不存在缓存，在数据微片发生竞争时，需要通过优先仲裁决定哪些数据微片可以通过有效的输出端口. 因此优先策略对数据微片的传输有重要影响. FLIT-BLESS采用了基于当前经历跳数OF(Oldest-First)的优先级策略，其中数据微片中记录了当前数据微片的已经经历的跳数，其数值越大则优先级越高，可以优先通过有效输出端口. 虽然该策略可以有效地避免活锁的发生，但不能准确反映偏转的次数，因此该策略不能有效减少偏转的发生.

根据图1所示的2D-mesh结构说明在路由发生竞争时OF-BLESS路由算法以及本文对其所做的相应改进，如图2所示.

图 2 发生偏转时的数据传输 Figure 2 Data transmission when the deflection occurs

定义1　剩余维度：指在2D-mesh结构中不同方向分别代表不同的维，数据微片在没有竞争时要到达目的节点时需要通过的维数.

图2中某一时刻ID为5的IP核通过路径(5→6→7→8→1)发送一个FLIT1. 一个周期后，ID为2的IP核通过路径(2→7→8)发送一个FLIT2. 在第二个周期时发生竞争，在OF-BLESSS算法中，FLIT1先于FLIT2传输，因此优先级高于FLIT2，由于竞争失败FLIT2被偏转到ID为10的路由器，最终传输路径如图2(a)所示. 在发生竞争时，FLIT1在X维和Y维都存在剩余步，而FLIT2只在X维存在剩余步. 本文优先安排剩余维度少的FLIT2进行路由，将FLIT1偏转到Y维进行路由，如果同时竞争的FLIT较多，再以跳数多优先的原则进行路由. 在该策略传输生成的路径如图2(b)所示.

分析图2得出，发生竞争的两个FLIT在图2(b)中的平均传输路径要小于在图2(a)中的平均传输路径，并且随着网络注入率的增加，该策略较OF-BLESS更加高效.

2.2 AOC-BLESS算法设计

本文基于第二节所提出的拥塞控制对OF-BLESS算法进行改进，提出AOF-BLESS(Adaptive-Oldest-First-BLESS)算法. 该算法有以下优点：(1) 改进了OF-BLESS算法的适应性；(2) 降低了数据微片发生竞争时的偏转平均次数；(3) 增加了相应的拥塞控制.

数据微片传输发生竞争时，首先根据不同数据微片传输剩余维度的不同分配输出端口. 在2D-mesh拓扑结构中如果数据微片传输剩余维度为一维，优先获得竞争端口，剩余维度为二维时被偏转到另一维路由，此后如果竞争没有解决时，采用OF-BLESS算法进行路由，竞争获胜的数据微片通过有效输出端口输出，竞争失败的数据微片被偏转到拥塞度低的无效输出端口.

依据以上原则，通过算法1描述了AOC-BLESS算法的实现.

算法1　AOC-BLESS路由算法描述

(1) 依据当前坐标(xS，yS)和目的坐标(xD，yD)计算所有FLIT的有效输出端口和剩余维度.

(2) 根据FLIT所请求的输出端口按照剩余维度的不同分配输出端口，剩余维度最小的优先级最高，分配剩余维度高于1的数据微片在另一维路由.

(3) 检查各端口是否还存在竞争，如果存在剩余相同维度的竞争，根据OF-BLESS算法进行优先仲裁. 获胜的FLIT通过有效端口输出，竞争失败的FLIT，根据拥塞寄存器，选择偏转到拥塞度低的无效输出端口.

(4) 分配完毕，进行传输.

2.3 无死锁活锁证明

本文提出的AOC-BLESS路由算法以无缓存偏转路由为基础，输入的数据微片总可以通过输出端口输出且不会在节点处停留，到达目的节点则被该节点接收. 数据微片剩余维度越小时其优先级越高，其可以准确路由到目的节点. 而发生偏转的数据微片随着被偏转的次数增多优先级升高，则可以获得有效输出端口，同样可以路由到目的节点，因此可以有效避免了活锁的出现.

3 仿真实验

为了评估本文所提出的算法，采用基于SystemC[15]的NoC仿真工具NNSE，该工具允许用户根据拓扑结构、流控策略和路由算法配置一个网络，评估不同配置NoC的延迟和吞吐率.

本文选择2D-mesh作为仿真NoC的拓扑结构. 采用均匀随机流量模式在不同注入率的情况下对3种不同的路由算法进行了模拟并对其进行性能分析，即基于有缓存的XY路由算法、基于跳数的优先级算法OF-BLESS和本文改进的适应性AOC-BLESS算法.

从图3中看出3种不同的注入率情况下的网络延迟，在注入率较低时，AOC-BLESS比另外两种算法表现出更低的延迟，XY路由方式由于存在缓存，所以带来了一定的时间延迟. OF-BLESS和AOC-BLESS在低注入率的情况下比较接近. 随着注入率的增加，由于XY路由缓存了较多的FLIT，因此可以得到缓冲，而OF-BLESS和AOC-BLESS由于不存在缓存，大量的FLIT偏转造成网络快速达到饱和状态，因此延迟也很快达到饱和状态. 然而AOC-BLESS采用了“避开热点”的处理方法，使得更多的FLIT可以均匀地分布在网络中，同时又降低转发次数，因此本文提出的方法能够比OF-BLESS获得更好的效果.

图 3 注入率对平均延迟影响 Figure 3 Injection rate influence on the average delay

图4中，可以看出在网络注入率低的情况下3种不同的网络的吞吐量几乎相同，因为网络未发生拥塞. 随着网络注入率的增加，网络开始发生拥塞，基于缓存的XY路由，能够获得较高的吞吐量，而不存在缓存的OF-BLESS和AOC-BLESS由于较多的FLIT偏转，所以吞吐量遇到瓶颈，但是AOC-BLESS能够在网络拥塞情况下，有效地避开“热点”，因而获得了比OF-BLESS更高的吞吐量，从而提高了网络利用率.

图 4 注入率对吞吐量的影响 Figure 4 Injection rate influence on throughput
4 结语

本文在OF-BLESS的基础上加以改进，通过多方面策略来降低无缓存NoC系统在较高负载时的平均延迟，并达到了预期的效果. 本文提出的AOC-BLESS算法，在网络注入率较低的时候时间延迟较低，在网络注入率高的时候通过策略算法后可以获得比OF-BLESS更好的性能提升，同时比XY路由性能损失小. 由于其本身没有缓存，减少了芯片的设计面积和功耗，因此在对延时敏感的系统可以获得较好的效果.

参考文献
[1] LEE K, LEE S J, YOO H J. Low-power network-on-chip for high-performance SoC design[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2006, 14(2): 148-160. DOI: 10.1109/TVLSI.2005.863753.
[2] ZHANG N, GU H, YANG Y, et al. QBNoC: QoS-aware bufferless NoC architecture[J]. Microelectronics Journal, 2014, 45(6): 751-758. DOI: 10.1016/j.mejo.2014.04.015.
[3] CRISPÍN G, GÓMEZ M E, PEDRO L, et al. How to reduce packet dropping in a bufferless NoC[J]. Concurrency & Computation Practice & Experience, 2011, 23(1): 86-99.
[4] FALLIN C, CRAIK C, MUTLU O. CHIPPER: A low-complexity bufferless deflectionrouter [C]// IEEE International Symposium on High Performance Computer Architecture. USA, Washington, D C: IEEE Computer Society, 2011: 144-155.
[5] CHRYSOSTOMOU C, TATAS K, RUNCAN A R. A Dynamic fuzzy logic based routing scheme for bufferless NoCs [C]// IEEE International Conference on Computational Science and Engineering. USA, Washington, D C: IEEE Computer Society, 2012: 295-302.
[6] 苑召国, 郭大昌. 超立方体中基于极大安全链路矩阵的容错路由[J]. 广东工业大学学报, 2008, 25(1): 33-37.
YUAN Zhao-guo, GUO Da-chang. Fault-tolerant routing based on maximum safety-link matrices in hypercube[J]. Journal of Guangdong University of Technology, 2008, 25(1): 33-37.
[7] MOSCIBRODA T, MUTLU O. A case for bufferless routing in on-chip networks [C]//Proceedings of the 36th Annual International Symposium on Computer architecture. New York, NY, USA: ACM Press, 2009: 196-207.
[8] 刘亮亮, 韩国栋, 张帆, 等. 一种无缓存片上网络交叉开关调度机制[J]. 小型微型计算机系统, 2013, 34(7): 1579-1584.
LIU L L, HAN G D, ZHANG F, et al. Crossbar scheduling mechanism for bufferless network-on-chip[J]. Journal of Chinese Computer Systems, 2013, 34(7): 1579-1584.
[9] KIM H, KIM Y, KIM J H. Clumsy flow control for high-throughput bufferless on-chip networks[J]. Computer Architecture Letters, 2013, 12(2): 47-50. DOI: 10.1109/L-CA.2012.22.
[10] CAMACHO J, FLICH J, DUATO J, et al. Towards an efficient NoC topology through multiple injection ports[C]// Proceedings of the 14th Euro micro Conference on Digital System Design. USA, Washington, D C: IEEE Computer Society, 2011: 165-172.
[11] STENSGAARD M B, SPARSO J. Renoc: A network-on-chip architecture with reconfigurable topology[C]// Proceedings of the Second ACM/IEEE International Symposium on Networks-on-Chip. USA, Washington, D C: IEEE Computer Society, 2008: 55-64.
[12] 胥大成, 樊建席, 张书奎. 基于2D-Mesh的容错路由算法[J]. Computer Science, 2012, 39(3): 113-117.
XU D C, FAN J X, ZHANG S K. Fault-tolerant routing algorithm in 2D-mesh[J]. Computer Science, 2012, 39(3): 113-117.
[13] LU Z, ZHONG M, JANTSCH A. Evaluation of on-chip networks using deflection routing[C]// Proceedings of the 16th ACM Great Lakes symposium on VLSI. USA, New York: ACM Press, 2006: 296-301.
[14] LI M, ZENG Q A, JONE W B. DyXY - A proximity congestion-aware deadlock-freedynamic routing method for network on chip[C]// Proceedings of the 43rd annual Design Automation Conference. USA, New York: ACM Press, 2006: 849-852.
[15] XIE Y, YAO L I. NoC system-level modeling based on De Bruijn graph and systemC[J]. Journal of University of Science & Technology of China, 2011, 41(2): 183-188.
[16] YAO C, FENG C, ZHANG M, et al. Low latency multicasting scheme for bufferlesshybrid NoC-bus 3D on-chip networks[J]. Communications in Computer & Information Science, 2015, 491: 36-47.