, 王骄, 杨丹 东北大学 信息科学与工程学院，辽宁 沈阳 110819
收稿日期：2019-11-28
基金项目：国家自然科学基金资助项目(61836011);中央高校基本科研业务费专项资金资助项目(2020GFYD011，2020GFZD008)。
作者简介：李贞妮(1982-), 女, 辽宁沈阳人, 东北大学讲师, 博士;
李晶皎(1964-), 女, 辽宁沈阳人, 东北大学教授, 博士生导师;
王骄(1978-), 男, 辽宁沈阳人, 东北大学教授, 博士生导师。
摘要：片上网络的拓扑结构和路由算法直接影响片上网络的传输延迟和传输效率.基于2D-Torus拓扑结构，提出了一种新的片上网络无死锁路由算法.通过改变数据包在片上网络路由过程中受限制转弯的位置，保证片上网络的自适应路由条件，从而有效降低片上网络的延迟.在FPGA硬件平台上，设计并实现了基于该路由算法的2D-Torus片上网络，并对其进行测试.实验结果表明，基于该路由算法的片上网络，可以满足片上网络多方向数据通信及多路数据并行通信等性能要求.
关键词：2D-Torus片上网络无死锁路由算法FPGA
Deadlock-Free Routing Algorithm of 2D-Torus Network-on-Chip Based on FPGA
LI Zhen-ni, LI Jing-jiao
, WANG Jiao, YANG Dan School of Information Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: LI Jing-jiao, E-mail: lijingjiao@ise.neu.edu.cn.
Abstract: The topology and routing algorithm of network on chip (NoC) directly influence the transmission delay and the transmission efficiency of the network-on-chip. A new deadlock-free routing algorithm for NoC was proposed based on 2D-Torus topology. By changing the position of packets that are restricted to turn during NoC routing, the adaptive routing condition of network-on-chip was guaranteed, and the delay of network-on-chip was reduced. The 2D-Torus NoC based on this routing algorithm was designed and implemented on FPGA hardware platform, and then was tested. The experimental results indicated that the NoC based on this routing algorithm can meet the performance requirements of network-on-chip data communication for multi-direction and multi-channel.
Key words: 2D-TorusNoC(network-on-chip)deadlock-freerouting algorithmFPGA
随着面向智能信息处理的嵌入式系统的发展和半导体工艺技术的进步，片上系统(system on chip, SoC)能够集成的处理器和IP核越来越多，使基于总线结构的设计复杂度呈指数增长，片上多核间的复杂通信也使得基于总线的通信结构成为限制芯片速度、功耗、面积和数据吞吐量的瓶颈[1-3].ITRS预测，到2020年，单芯片上可集成的晶体管数目将达到千亿级的规模[4].片上网络(network-on-chip，NoC)的出现解决了基于总线的系统不可伸缩等问题，通过借鉴计算机网络技术，在芯片内部各个模块之间采用路由和数据包分组交换的方式进行通信，为SoC中处理器和IP核之间的通信提供灵活、高效、可靠的解决方案[5].
目前，大多数片上网络采用最典型的二维网格(2D-Mesh)[6-7]结构.2D-Mesh拓扑结构是一种网格结构，每个路由节点连接一个计算节点IP核，并与其上、下、左、右4个方向的相邻路由节点连接(边界节点除外)；然而在Mesh拓扑结构中，边界路由节点之间不存在直接的路由连接，因此当数据包在边界节点之间传输时，可能需要沿横向或纵向穿过整个片上网络，导致数据包在片上网络中的传输延迟增加[8-9].与之相比，2D-Torus拓扑结构在Mesh拓扑结构的基础上，增加了行和列首尾路由节点的长连线，以达到缩短网络平均直径和提升片上网络通信性能的目的[10-12]，每个路由节点具有相同的结构，因此可扩展性强，易于在硬件上实现，且其路由路径的多样性有效降低了阻塞的发生，提高了网络的传输效率[1, 13].因此，本文主要针对2D-Torus拓扑结构，对片上网络的路由算法进行研究.
片上网络的路由算法决定了消息从源节点到目的节点要经过的通道序列[14-16].随着片上系统集成的处理器核数的不断增加，由生产缺陷、工艺偏差和芯片老化等引发的故障导致NoC出现故障的概率不断提高.路由算法主要解决路由路径的选择问题，一个好的路由算法必须考虑其是否能够充分利用片上网络的空闲资源来改善片上网络的延迟和吞吐率；是否能够尽可能减小片上网络的功耗.Torus拓扑结构中的环路增加了路由路径的多样性，但同时也带来了许多问题，例如死锁问题，这就进一步要求面向Torus结构的路由算法能够解决环路带来的死锁等问题.因此，本文针对2D-Torus拓扑结构，提出了一种基于列分转弯[5]的Torus无死锁(Torus deadlock-free, TDF)路由算法，通过改变数据包在片上网络路由过程中受限制转弯的位置，保证片上网络的自适应路由条件，从而降低片上网络的延迟.并通过理论分析、仿真实验和实物测试来证明该算法是无死锁的.
1 TDF路由算法描述为解释TDF路由算法，假设目的节点坐标为D(xd, yd)，源节点坐标为S(xs, ys)，当前节点坐标为C(x, y)；路由开始时，源节点坐标等于当前节点坐标.每个路由节点中，数据包可能的传输方向有9个，分别为O(本地)，E(东)，W(西)，S(南)，N(北)，SE(东南)，SW(西南)，NE(东北)，NW (西北)，具体如图 1所示.
图 1(Fig. 1)
 | 图 1 路由节点的可能传输方向Fig.1 The possible transmission direction of routing node |
2D-Torus片上网络由于增加了首尾节点的连线，因此每一行及每一列都存在环路.路由方向也不再是简单的东、西、南、北4个方向，传统的禁止转向技术不再适用.对于一个4×4的2D-Torus片上网络，假定(0, 0)节点在片上网络的左下角，(3, 3)节点在片上网络的右上角.其拓扑结构如图 2所示.
图 2(Fig. 2)
 | 图 2 4×4的2D-Torus片上网络拓扑结构Fig.2 The topology of 4×4 2D-Torus network-on-chip |
设片上网络系统中0维上的坐标为x，k代表每个维度上节点的数目，例如一个4×4的2D-Torus片上网络，k=4，则x坐标的取值范围是0≤x＜k.
定义TDF算法的规则如下：当节点的x＜[k/2]时，数据禁止NW转向和SW转向；当节点的x≥[k/2]时，数据禁止NE转向和SE转向.数据在0列、k-1列、0行、k-1行这4条边缘信道时，若数据由0列向k-1列路由，下一跳应向西(W)转弯；若数据由0行向k-1行路由，当前节点为(0, 0)，目的节点为(k-1, k-1)时，下一跳应向西(W)转弯，其余情况下一跳应向南(S)转弯；若数据由k-1列向0列路由，当前节点为(k-1, 0)，目的节点为(0, k-1)，下一跳应向南(S)转弯，当前节点为(k-1, k-1)，目的节点为(0, 0)，下一跳应向北(N)转弯，其余情况下一跳向东(E)转弯；若数据由k-1行向0行路由，当前节点为(0, k-1)，目的节点为(k-1, 0)时，下一跳应向西(W)转弯，其余情况下一跳向北(N)转弯.
以4×4的2D-Torus片上网络为例，TDF路由算法的具体执行过程如下：
1) 若xd=x，yd=y，说明数据已经传输到目的节点，当前路由节点会将数据发送到其本地端口.
2) 若xd=x，yd＜y，当y=3，yd=0，则数据应向北方向(N)路由，其余情况数据应该向南方向(S)路由，当前节点也会随即将数据传输到南向输出端口.
3) 若xd=x，yd＞y，当y=0，yd=3，则数据应向南方向(S)路由，其余情况数据应该向北方向(N)路由，当前节点也会随即将数据传输到北向输出端口.
4) 若xd＞x，y=yd，当x=0，xd=3，则数据应向西方向(W)路由，其余情况数据应该向东方向(E)路由，当前节点也会随即将数据传输到东向输出端口.
5) 若xd＜x，y=yd，当x=3，xd=0，则数据应向东方向(E)路由，其余情况数据应该向西方向(W)路由，当前节点也会随即将数据传输到西向输出端口.
6) 若xd＞x，yd＞y，当x≥[k/2]-1时，若y=0，yd=3, 则数据应该向南方向(S)路由，若y≠0或yd≠3，则数据应该向北方向(N)路由；当x＜[k/2]-1时, 若y=0，yd=3，如果xd=3，则数据应该向西方向(W)路由，其余情况数据应该向南方向(S)路由，若y≠0或yd≠3，如果xd=3，数据应向西(W)路由，如果xd≠3，则数据应该向东方向(E)路由.
7) 若xd＞x，yd＜y，当x≥[k/2]-1时，若y=3，yd=0, 则数据应该向北方向(N)路由，若y≠0或yd≠3，数据应该向南方向(S)路由；当x＜[k/2]-1时, 若y=3，yd=0，如果xd=3，则数据应该向西(W)路由，其余情况数据应该向北(N)路由，若y≠3或yd≠0，如果xd=3，数据应向西(W)路由，如果xd≠3，数据应该向东(E)路由.
8) 若xd＜x，x≥[k/2]，yd＞y，当y=0，yd=3时，数据应向南(S)路由，当y≠0或yd≠3时，如果x=3，xd=0, 则数据应向东(E)路由，其余情况数据应向北(N)路由.
9) 若xd＜x，x≥[k/2]，yd＜y，当y=3，yd=0时，数据应向北(N)路由，当y≠3或yd≠0时，如果x=3，xd=0, 则数据应向东(E)路由，其余情况数据应向南(S)路由.
10) 若xd＜x，x＜[k/2]，yd＞y，如果y=0，yd=3，数据应向南(S)路由，如果y≠0或yd≠3，则数据应该向西(W)路由.
11) 若xd＜x，x＜[k/2]，yd＜y，如果y=3，yd=0，数据应向北(N)路由，如果y≠3或yd≠0，则数据应该向西(W)路由.
2 TDF路由算法无死锁证明由于面向片上网络的Torus拓扑结构在网络中存在多个环路，因此当数据包在路由节点间传输时容易产生死锁.当相邻的路由节点彼此请求对方进行数据转发时，若数据包进入循环等待状态，就会发生死锁.例如，当某一路由节点接收到数据包，并将其存储在缓存区中，数据包将根据路由算法请求下一跳的路由节点并申请缓存.若下一跳路由节点的接收通道被占据了，而占据该通道的数据包也正在等待被传输，并形成一个环路循环状态.那么，这些数据包都会因为无法请求到下一跳路由节点而无法释放当前路由节点的缓存，从而造成死锁现象.分析可知，产生死锁的根本原因在于数据包在路由传输过程中存在具有依赖性的环路.通常采用3种方法来避免死锁：①通过设计路由算法来控制数据包的传输，限制路由方向，破除依赖性环路，从而避免死锁现象.②通过使用虚通道来避免死锁的发生.③通过检测死锁现象，强制破坏依赖性环路，从而限制死锁的发生.本文提出的TDF算法就是通过设计路由算法来避免死锁.
本文结合Dally[17]提出的通道依赖图和Duato等[18]提出的无死锁充分必要条件来证明本文提出的Torus片上网络TDF路由算法的无死锁特性.基于上述方法，对4×4的2D-Torus拓扑结构中各个路由节点的出入通路进行编码标记，标记方案如图 3所示.该方案中将每条路由通道分成两个方向，即路由节点的输出通道与输入通道.每一行的每一个方向上通道的x坐标都相同，每一列的每一个方向上通道的y坐标都相同.
图 3(Fig. 3)
 | 图 3 路由路径编码Fig.3 The routing path coding |
编码完成后的2D-Torus片上网络路由路径编码如图 4所示.
图 4(Fig. 4)
 | 图 4 2D-Torus片上网络路由路径编码Fig.4 The routing path encode of route in 2D-Torus NoC |
例如，(1, 1)节点上方输出通道编码为(5, 1)，输入通道编码为(7, 2).假设有两组路由数据A和B，数据A从路由节点(1, 1)传输至路由节点(3, 3)，数据B从路由节点(3, 3)传输至路由节点(1, 1).根据本文设计的路由算法规则，数据A的路由路径为〈(1, 1)(1, 2)(1, 3)(2, 3)(3, 3)〉，数据B的路由路径为〈(3, 3)(3, 2)(3, 1)(2, 1)(1, 1)〉，根据编码规则可知数据A所经过的通道依次为〈(5, 1)(5, 2)(1, 9)(2, 9)〉，数据B所经过的通道依次为〈(9, 3)(9, 2)(3, 5)(2, 5)〉.由路由路径可见，数据A所经过的路由通道在不同维度均严格递增，数据B所经过的路由通道在不同维度均严格递减，又根据编码规则可知，该路由算法下数据在任意节点间传输所经路径均为单调增或单调减，且不存在路径交叉的情况，所以TDF路由算法是无死锁的.
3 系统测试及结果分析在Xilinx ISE 14.4开发环境下，基于System Verilog语言，设计并实现了4×4的基于2D-Torus拓扑结构，采用TDF路由算法的片上网络，并对该片上网络进行仿真测试与功能验证.在FPGA的Xilinx Virtex-5硬件平台上对系统性能进行测试.
在测试中，对路由节点进行编号，net_gen[i]表示坐标为(i%4, i/4)的路由节点，这里i为整数，则仿真中的net_gen[i]/…./output_port_(x)代表坐标为(i%4, i/4)的节点将数据从x端口输出，net_gen[i]/…./input_port_(x)代表坐标为(i%4, i/4)的节点将数据从x端口输入，x可以为O，W，S，E和N，其中O代表本地端口，W为西端口，S为南端口，E为东端口，N为北端口.例如b00net_gen[0]/…./output_port_(E)代表(0, 0)节点将数据从东端口输出，b32net_gen[11]/…./input_port_(S)代表(3, 2)节点将数据从南端口输入.
3.1 单个节点传输测试分析这里以数据从(0, 1)节点向(3, 3)节点的传输为例进行分析.单个节点传输波形如图 5所示.根据仿真波形图中的信息，可以列出该过程的路由信息表如表 1所示.
图 5(Fig. 5)
 | 图 5 单个节点传输波形图Fig.5 Transmission waveform of a routing node |
表 1(Table 1)
 表 1 〈(0, 1), (3, 3)〉路由信息表Table 1 The routing information table of 〈(0, 1), (3, 3)〉
| 表 1 〈(0, 1), (3, 3)〉路由信息表 Table 1 The routing information table of 〈(0, 1), (3, 3)〉 |
数据从(0, 1)节点的本地端口输入，接着从(0, 1)节点即net_gen[4]的西端口输出，从(3, 1)节点即net_gen[7]的东端口输入，然后从net_gen[7]的北端口输出，从节点(3, 2)即net_gen[11]的南端口输入，接着从net_gen[11]的北端口输出，从节点(3, 3)即net_gen[15]的南端口输入，最后从net_gen[15]的本地端口输出.在路由的过程中，基于TDF路由算法的2D-Torus片上网络共消耗了大约48个时钟周期，而同样结构的奇偶转弯(odd-even)[9]片上网络共消耗了大约55个时钟周期.可知，TDF路由算法可以有效减少路由延迟时间.
3.2 多节点并行传输测试分析测试中，分别从(3, 3)，(2, 1)，(0, 3)节点向(0, 1)，(0, 3)，(3, 1)节点传输数据，那么输入数据的标志位应该分别为111110001, 110010011和100111101.仿真结果如图 6所示.通过仿真结果可知，多组数据在4×4的2D-Torus片上网络中能够进行有效的传输，没有产生死锁现象.且目的节点的输出数据与源节点的输入数据相同，验证了片上网络在该路由算法作用下并行传输的准确率.
图 6(Fig. 6)
 | 图 6 多节点并行传输测试仿真图Fig.6 The test simulation diagram of multi-node parallel transmission |
3.3 基于FPGA的片上网络性能测试以Genesys Vertex-5系列的FPGA作为硬件平台，设计并实现了本文提出的4×4的无死锁2D-Torus片上网络.无死锁Torus片上网络的硬件实物如图 7所示，源节点为(0, 0)，目的节点为(3, 3).测试结果表明，系统实物测试与仿真结果一致.
图 7(Fig. 7)
 | 图 7 无死锁片上网络FPGA硬件实物Fig.7 The deadlock-free NoC system based on FPGA |
4 结论本文针对2D-Torus拓扑结构，提出了一种基于列分转弯模型的TDF路由算法，保证了数据包在片上网络中的自适应路由条件.并对TDF路由算法的无死锁性进行了理论证明.设计并实现了基于TDF路由算法的2D-Torus片上网络系统，并在FPGA硬件平台上对其进行了测试.实验结果表明，基于TDF路由算法的片上网络，路由算法无死锁，且能够实现多方向以及多节点的并行通信.片上网络是未来片上多核系统的主流通信架构，因此基于2D-Torus拓扑结构及TDF路由算法的片上网络具有较好的应用前景.
参考文献
| [1] | 李贞妮, 李晶皎, 方志强, 等. 异步2D-Torus片上网络自适应路由算法[J]. 东北大学学报(自然科学版), 2015, 36(9): 1217-1221. (Li Zhen-ni, Li Jing-jiao, Fang Zhi-qiang, et al. Adaptive routing algorithm of asynchronous 2D-Torus network-on-chip[J]. Journal of Northeastern University(Natural Science), 2015, 36(9): 1217-1221. DOI:10.3969/j.issn.1005-3026.2015.09.001) |
| [2] | Wang L, Ma S, Li C, et al. A high performance reliable NoC router[J]. Integration, 2017, 58: 583-592. DOI:10.1016/j.vlsi.2016.10.016 |
| [3] | Daneshtalab M, Palesi M, Mak T. Introduction to the special issue on NoC-based many-core architectures[J]. Computers & Electrical Engineering, 2015, 45(1): 359-361. |
| [4] | Hoefflinger B.The International technology roadmap for semiconductors[EB/OL].(2013-06-26)[2018-04-01].http://www.itrs.net/Links/2010ITRS/Home2010.htm. |
| [5] | 蔡源, 罗伟, 向东. 基于列分转弯模型的片上网络路由算法[J]. 清华大学学报(自然科学版), 2018, 58(12): 1051-1058. (Cai Yuan, Luo Wei, Xiang Dong. Routing algorithm based on a column-partition turn model for a network-on-chip[J]. Journal of Tsinghua University(Natural Science), 2018, 58(12): 1051-1058.) |
| [6] | He A P, Feng G B, Zhang J L, et al. An asynchronous mesh NoC based booth multiplication[J]. IET Circuits, Devices & Systems, 2019, 13(1): 73-78. |
| [7] | Wang L, Wang X H, Leung H F, et al. A non-minimal routing algorithm for aging mitigation in 2D-Mesh NoCs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems, 2019, 38(7): 1373-1377. |
| [8] | Feero B, Pande P.Performance evaluation for three-dimensional networks-on-chip[C]//IEEE Computer Society Annual Symposium on VLSI.Porto Alegre, 2007: 305-310. |
| [9] | Chiu G M. The odd-even turn model for adaptive routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(7): 729-738. DOI:10.1109/71.877831 |
| [10] | Khawaja S G, Mushtaq M H, Khan S A, et al. Designing area optimized application-specific network-on-chip architectures while providing hard QoS guarantees[J]. PLoS One, 2015, 10(4): 1-17. |
| [11] | Dally W J, Seitz G L. Deadlock-free message routing in multiprocessor interconnection networks[J]. IEEE Transactions on Computers, 1987, 36(5): 547-553. |
| [12] | Rahmati D, Sarbazi-Azad H, Hessabi S, et al. Power-efficient deterministic and adaptive routing in Torus networks-on-chip[J]. Microprocessors and Microsystems, 2012, 36(7): 571-585. DOI:10.1016/j.micpro.2011.05.009 |
| [13] | Touzene A, Day K. All-to-all broadcasting in Torus network on chip[J]. The Journal of Supercomputing, 2015, 71(7): 2585-2596. DOI:10.1007/s11227-015-1406-z |
| [14] | Ezz-Eldin R, El-Moursy M A, Hamed H F A, et al. Process variation delay and congestion aware routing algorithm for asynchronous NoC design[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(3): 909-919. DOI:10.1109/TVLSI.2015.2434853 |
| [15] | 周磊, 吴宁, 李云. 一种基于2D-Mesh的片上网络无死锁容错路由算法[J]. 上海交通大学学报, 2013, 47(1): 18-22. (Zhou Lei, Wu Ning, Li Yun. A fault-tolerant and deadlock-free routing algorithm in 2D-Mesh for network on chip[J]. Journal of Shanghai Jiaotong University, 2013, 47(1): 18-22. DOI:10.3969/J.ISSN.1671-9964.2013.01.004) |
| [16] | Ren P J, Kinsy M A, Zheng N N. Fault-aware load-balancing routing for 2D-Mesh and Torus on-chip network topologies[J]. IEEE Transactions on Computers, 2016, 65(3): 873-887. DOI:10.1109/TC.2015.2439276 |
| [17] | Dally W J. Virtual-channel flow control[J]. IEEE Transactions on Parallel and Distributed Systems, 1992, 3(2): 194-205. DOI:10.1109/71.127260 |
| [18] | Duato J, Yalamanchili S. Interconnection networks:an engineering approach[M]. San Francisco: Morgan Kaufmann, 2002. |
