广东工业大学学报  2017, Vol. 34Issue (5): 60-64.  DOI: 10.12052/gdutxb.160047.
0

引用本文 

孙锋, 刘怡俊. 一种片上网络路由算法的分析与优化设计[J]. 广东工业大学学报, 2017, 34(5): 60-64. DOI: 10.12052/gdutxb.160047.
Sun Feng, Liu Yi-jun. Analysis and Optimization Design of Network-on-Chip Routing Algorithm[J]. JOURNAL OF GUANGDONG UNIVERSITY OF TECHNOLOGY, 2017, 34(5): 60-64. DOI: 10.12052/gdutxb.160047.

基金项目:

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

作者简介:

孙锋(1989–)，男，硕士研究生，主要研究方向为片上网络。

文章历史

收稿日期：2016-03-16
Contents              Abstract              Full text              Figures/Tables              PDF
一种片上网络路由算法的分析与优化设计
孙锋, 刘怡俊     
广东工业大学　计算机学院，广东　广州  510006
收稿日期：2016-03-16
基金项目：广东省科技计划项目(2015B090908001, 2013A090100005, 2014B090901061, 2015B090903080); 广州市科技计划项目(2014Y2-00211)
作者简介：孙锋(1989–)，男，硕士研究生，主要研究方向为片上网络。
摘要: 针对XY-YX算法局部路径选择单一、较容易出现拥塞热点区域、不能很好适应高速的网络数据传输等问题, 提出一种无死锁路由算法(dead-lock free XY-YX). 该算法通过改进XY-YX路由算法, 达到了减轻局部链路负载过重导致的热点问题的目的; 此外, 为了适应改进的路由算法, 设计了一种无死锁结构的路由, 避免了死锁的出现. 在本文设计的无死锁路由架构上仿真后, 结果表明, 改进的路由算法, 相比于XY路由算法和XY-YX路由算法, 其网络平均延时与吞吐量均有所提升.
关键词: 路由算法    无死锁路由    片上网络    
Analysis and Optimization Design of Network-on-Chip Routing Algorithm
Sun Feng, Liu Yi-jun     
School of Computers Science, Guangdong University of Technology, Guangzhou 510006, China
Abstract: To solve XY-YX routing algorithm’s problem of choosing a single key path, liable to fall into hot spot region and cannot adapt to high speed network data transmission, a modified XY-YX routing algorithm with dead-lock free XY-YX routing is set up. The modified algorithm can release the burden of link circuit. What’s more, in order to adapt to the modified algorithm, a dead-lock free route is put forward to avoid the dead-lock. Simulation result shows that the modified routing algorithm, experimented on dead-lock free route, can keep lower level latency and achieve higher network throughput than XY routing algorithm and XY-YX routing algorithm.
Key words: routing algorithm    dead-lock free route    network on chip    

随着片上系统(System on Chip, SoC)的制造工艺趋于亚深微米尺寸越来越小，严重约束了片上资源的可重用性，以及设计中出现的制约延时和功耗也很严重. 片上网络(Networks on Chip, NoC)以其良好的资源可扩展性突破了IP核个数的限制，同时以局部同步、全局异步的方式解决了存在于SoC中的时钟难以同步问题，并且能很好地控制传送延时和设计功耗[1].

在NoC设计中，路由算法决定了数据包从源节点怎么达到目的节点的路径. 网络根据路由算法确定的关系给数据包分配路由，路由信息会被数据包的头部，即头微片占据. 数据包的目的节点以及路由关系，共同指定一个可以路由数据包的通道集[2]. 在特定的网络拓扑结构下，每个通道不定向地从源节点向目的节点传输数据.

XY路由算法是比较简单、常用且较重要的一种确定性维序路由算法，适用于数据注入率较低的网络. 它只专注源节点与目的节点的地址，而与网络的拓扑结构和状态无关. 该算法首先选定X维方向传输数据包，到达目的节点同一行后再转向Y方向，直到目的节点. 但由于其确定路径单一，容易出现链路过载，产生热点区域，同时也容易出现拥塞，缺乏自适应性. 在此基础上联合XY算法与YX算法，出现了XY-YX[3]联合算法，通过Y方向上的分流，在一定程度上减轻了X方向上的通讯压力.

而后针对XY算法的不足，继续做了一系列的改进. 文献[4]中提出了一种伪自适应XY路由算法，它能根据网络数据包负载量决定用XY路由算法还是AXY(Adapting XY)路由算法，负载量高用AXY，而负载量不高则用XY；在源节点和目的节点之间存在多条最短路径时，DXY[5](Dynamic XY)路由算法能根据每条路径的拥塞值，选择一条值最小的路径进行数据包传输；EDXY[6](Enhanced-Dynamic XY)在DXY的基础上，进一步降低了拥塞成本；还有降低通讯延时的路由算法OE-XY[7](Odd-Even XY)，它通过TurnModel选择仅有的NE、ES、WS、NW 4个路由方向，选择哪一个方向依赖于被路由的数据包所在位置的纵列是偶数还是奇数，这样既能控制流速和拥塞，也能降低延时；而LA-XYZ[8](Look-Ahead XYZ)路由算法，更是将应用从二维状态推向了三维应用.

本文通过进一步改进XY-YX路由算法，让该算法具有更好的均衡负载效果. 同时提出无死锁要求，设计出无死锁路由架构，最终将这种设计应用于无虚拟通道路由设计或者是非均匀虚拟通道分配的路由设计中.

1 改进的XY-YX路由算法

其实XY-YX算法已经具有一定的伪自适应性，该算法通过数据包当前所在节点与目的节点位置的Y值共同决定路由的方向. 当目的节点的Y值小于当前节点的Y值时, 即目的节点在当前节点的北边, 选择先Y后X ;当目的节点的Y值大于当前节点对应的值时, 即目的节点在当前节点的南边, 选择先X后Y, 从而减轻XY路由算法在X方向产生的负载压力[9]. 缺点是当前节点与目的节点的相对位置具有局部性，导致选择的XY路由算法或YX路由算法比较集中，所以网络负载均衡的效果不明显[10].

为此，本文提出一种改进的XY-YX路由算法. 针对每一次路由过程，目的节点位置是固定的. 如果按照目的节点列坐标的奇偶性确定数据包下一跳路由的算法是XY还是YX，容易出现X或者Y链路负载过重，因此本文选定不固定的当前节点的列坐标的奇偶性作为评判依据，通过列坐标的变换，随时均衡X或Y链路的负载. 该算法的主要思想是，当前的节点位于偶数列且目的节点在当前路由节点的右边时，采用XY路由算法；当前节点位于奇数列且目的节点在当前路由节点的右边时，则采用YX路由算法. 相比于XY-YX路由算法，改进的XY-YX算法避免了因局部选择导致的链路负载失衡问题.

改进的XY-YX路由算法描述如下.

(1) 当前节点与目的节点为同一个节点，将数据发向本地节点；

(2) 当前节点与目的节点处在同一列，用YX路由算法；

(3) 当前节点与目的节点处在同一行，用XY路由算法；

(4) 当前节点与目的节点既不出在同一行，也不在同一列，如果当前节点的Y值为偶数用YX路由算法，否则用XY路由算法.

destAddr为目的节点地址，destX表示目的节点的行坐标，destY为目的节点的纵坐标；switchAddr为当前节点地址，switchX表示目的节点的行坐标，switchY为目的节点的纵坐标. 算法伪代码如下所示.

2 无死锁路由设计实现

片上路由器是NoC通讯的核心构件，主要负责通讯数据的发送与存储，其性能的好坏直接影响整个片上系统通讯效率的高低. 为了缓解通讯竞争问题，典型的片上路由器在每一个输入端口或者输出端口都配有一定容量的缓存，用于临时存储被阻塞的数据包. 除了缓存外，一个典型的路由器还包含输入输出(Input and output)、交叉开关(Crossbar)、仲裁调度(Arbiter)、路由计算(Route computing)等模块，路由器的类型有很多，最常见的便是XY路由.

传统的XY路由，经常用于torus或者mesh拓扑结构，其设计简单，实现容易，在低数据包注入率的前提下，能避免死锁和活锁，较其他的路由设计有很大的优势. 为了进一步适应较高的数据包注入率，通过改进XY路由，形成XY-YX联合路由[11]. 相比于XY路由，XY-YX联合路由能通过提前预测数据包被路由的通路来消除唤起延时，由于避免了局部单一链路确定性选择，也缓解了链路的拥塞问题. 在XY-YX联合路由设计中，由于要兼顾XY算法与YX算法路由的数据包，同时在联合XY与YX两种路由结构时，也要避免死锁的发生，因此本文提出了一种无死锁路由设计. 为了平衡XY算法和YX算法两个方向上的数据流，避免拥塞，每个组至少有两条通道，否则XY-YX通讯链路很容易出现死锁[12].

本文设计的路由结构中，添加了4条额外的物理通道，这样既降低了路由算法的复杂度，也省去了虚拟通道的设计所需的缓存资源与控制逻辑. 每条额外的物理通道用于XY算法或者YX算法的数据包传输. 设输入通道条数为M，输出通道条数为N，单条通道数据包输入平均流速Vm，单条通道数据包输出平均流速Vn，那么

${V_m}M \leqslant {V_n}N,M \geqslant 0.$ (1)

理论出现的输出端数据平均流速应该大于或者等于输入端平均流速的M/N倍，才能确保不出现拥塞. 为了进一步节约资源和降低功耗，交叉开关的输入端通道的条数可以大于等于输出端通道的条数的，这种设计对路由的性能影响很小，多数交叉开关是通过数字逻辑实现的，例如三态门[13]. 如图1 为本文设计的路由架构.

图 1 无死锁XY-YX路由架构 Figure 1 The structure of dead-lock free XY-YX route

图1中路由节点有9条输入通道，4条输出通道，即M=9，N=4. 每个输入方向都添加了一条物理通道，用于防止死锁. 在输入通道与交叉开关之间，有专门用于控制每个方向上的X通路与Y通路的选择逻辑，数据包进入节点之前，首选X通道，如果X通道被占用，那么选择逻辑置为1，后续通过该方向上的数据包会选择Y通道传输，直到占有X通道的数据包释放该通道的资源，则选择逻辑置为0，如此反复. 该架构支持虫洞交换机制，并能很好地应用于mesh拓扑结构中，所有注入路由节点的数据包都会根据自适应路由算法的决定来选择是利用XY链路还是YX链路.

3 仿真实现

本文采用BookSim2.0仿真器，它可以对多种拓扑结构以及多种路由架构进行仿真. 仿真器通过配置NoC的某些参数，实现对NoC的性能评估. 可设置的参数有路由器类型、数据包长度、数据包注入率、缓存单元大小、虚拟通道长度等[14]. 该仿真器各个功能模块是相对独立的，设计者也可以根据自己的需求添加新的功能模块.

本次功能仿真主要集中在网络平均延时和吞吐率上. 为了衡量吞吐率和随时调整数据包注入率，假设数据包不断地注入路由节点，并且每次仿真运行的周期也是固定的，其中前期少部分时间片用于唤起延时. 此处设数据包的长度为9个flit长度，其中开头的一个是头flit，最后的一个是尾flit，中间的是体flits，头flit占有所有的路由信息，尾微片负责数据包离开占有通道时的通道资源释放.

图2和图3是在8×8 mesh结构下针对路由算法给出的平均延时与吞吐量的仿真结果. 本文算法在无死锁路由架构下获得的平均延时与吞吐量均优于XY路由算法和XY-YX联合路由算法. 从图2中得知，当数据包注入率低于0.3时，3种算法的平均延时基本上相似且处于较低的状态. 这说明在低注入率的状态下，3种算法性能都比较好，但XY算法由于实现较另外两者简单，因此XY算法更适合在数据包低注入率状态下的网络. 数据包注入率超过0.3以后，本文算法较另外两种算法有明显的延时优势. 图3中的吞吐量比较，在注入率大于0.3以后，也出现了明显的分界，注入率到达0.34后基本上三者均达到了稳定，稳定后的吞吐量中本文算法是最高的，分别大于XY算法和XY-YX算法14.2%与4.6%.

图 2 不同算法实现的网络平均延时 Figure 2 The network latency in different routing algorithm
图 3 不同算法实现的网络吞吐量 Figure 3 The network throughput in different routing algorithms

图4给出的是不同路由架构实现的自适应XY-YX算法的网络平均延时. 以数据包注入率0.2为分界点，0.2以前都表现出较低的延时，0.2以后出现了明显的异化，本文路由架构优势较明显. 相比于XY路由与XY-YX联合路由，本文路由多增加了4条额外的物理通道，平衡了X方向与Y方向上的数据包流量，减少了网络拥塞的发生，因此在平均延时上有较大的优势. 但也因此出现在较低数据包注入率时，路由缓存利用率较低的缺点. 并且在路由的每个节点上，同时控制X方向与Y方向的数据包传输，新增了必要的控制逻辑.

图 4 不同路由架构实现的网络平均延时 Figure 4 The network latency in different route structures
4 结束语

除了某些专用的芯片，比如说对实时、能耗、硬件面积等有特殊的要求，通常在NoC的设计中，很多时候都是取一种折衷的结果，经过各个性能之间的平衡，以最少的资源，获得最大的作用效果[15]. 本文从网络延时和网络吞吐率两个方面对本文设计的算法进行了性能评估，得到了一个NoC整体性能较优的结果. 针对XY-YX算法的局限性，改进了XY-YX算法，同时提出了一种无死锁路由设计架构. 改进的XY-YX算法根据当前节点所在列的奇偶性，选择XY路由方式还是YX路由方式. 无死锁路由结构在XY-YX路由的基础上添加了4条额外的物理通道，用于X与Y方向上的数据包传输平衡，有效地降低了拥塞的发生率.

参考文献
[1] 李超. 异步片上网络自动生成及模拟方法的研究[D]. 广州: 广东工业大学计算机学院, 2014.
[2] DALLY W J. Virtual-channel flow control[J]. IEEE Transactions on Parallel & Distributed Systems, 1992, 3(2): 60-68.
[3] 欧阳一鸣, 董少周, 梁华国. 基于2D Mesh的NoC路由算法设计与仿真[J]. 计算机工程, 2009, 35(22): 227-229, 235.
OUYANG Y M, DONG S Z, LIANG H G. Design and simulation of NoC routing algorithm based on 2D Mesh[J]. Computer Engineering, 2009, 35(22): 227-229, 235. DOI: 10.3969/j.issn.1000-3428.2009.22.078.
[4] DEHYADGARI M, NICKRAY M. Evaluation of pseudo adaptive XY routing using an object-oriented model for NOC [C]//The 17th International Conference on Microelectronics. Islamabad: IEEE, 2005: 5pp, doi: 10.1109/icm.2005.1590068.
[5] YANG S, LI L, XU Y, et al. A power-aware adaptive routing scheme for network on a chip [C]//IEEE 2007 7th International Conference on ASIC. Guilin: Curran Associates, 2007: 1301-1304.
[6] LOTFI-KAMRAN P, RAHMANI A M, DANESHTALAB M, et al. EDXY-A low cost congestion-aware routing algorithm for network-on-chips[J]. Journal of Systems Architecture, 2010, 56(7): 256-264. DOI: 10.1016/j.sysarc.2010.05.002.
[7] JIANG S Y, CHEN L, LU Z, et al. Low latency routing algorithm simulation and hardware verification of NoC [C]//Electronic Engineering and Information Science: Proceedings of the International Conference of Electronic Engineering and Information Science 2015 (ICEEIS 2015). Harbin: CRC Press, 2015: 251-254.
[8] AHMED A B, ABDALLAH A B. LA-XYZ: low latency, high throughput look-ahead routing algorithm for 3D network-on-chip (3D-NoC) architecture [C]//The 6th IEEE international symposium on embedded multicore SoCs. Aizu-Wakamatsu: IEEE,2012: 167-174.
[9] 王芳丽, 杜慧敏. 片上网络路由算法综述[J]. 西安邮电学院学报, 2007, 16(1): 72-77.
WANG F L, DU H M. The summary of network-on-chip routing algorithm[J]. Journal of Xi’an Institute of Posts and Telecommunications, 2007, 16(1): 72-77.
[10] 郭林林, 李光顺, 吴俊华. 基于虚拟通道非均匀分布的路由算法[J]. 计算机科学, 2014, 41(8): 164-168, 177.
GUO L L, LI G S, WU J H. Routing algorithm based on non-uniform distribution of virtual channel[J]. Computer Science, 2014, 41(8): 164-168, 177. DOI: 10.11896/j.issn.1002-137X.2014.08.036.
[11] SHIM K S, CHO M H, KINSY M, et al. Static virtual channel allocation in oblivious routing [C]//Proceedings of the 2009 3rd ACM/IEEE International Symposium on Networks-on-Chip. Washington D C: IEEE Computer Society, 2009: 38-43.
[12] JEONG Y S, LEE S E. Deadlock-free XY-YX router for on-chip interconnection network[J]. IEICE Electronics Express, 2013, 10(20): 699-704.
[13] MULLINS R, WEST A, MOORE S. Low-latency virtual-channel routers for on-chip networks [C]//2014 ACM/IEEE 41st International Symposium on Computer Architecture (ISCA). Washington D C: IEEE Computer Society, 2004: 188-197.
[14] LI M, ZENG Q A, JONE W B. DyXY-A proximity congestion-aware deadlock-free dynamic routing method for network on chip [C]//Proceedings of the 43rd annual Design Automation Conference. New York: ACM Press, 2006: 849-852.
[15] NICOPOULOS C A, PARK D, KIM J, et al. ViChaR: a dynamic virtual channel regulator for network-on-chip routers[C]//IEEE/ACM International Symposium on Microarchitecture. Orlando: IEEE, 2006: 333-346.