周文强, 张金艺, 周多, 刘江. 三维片上网络最短路径令牌式路由算法[J]. 微电子学与计算机, 2015, 32(5): 84-90. DOI: 10.19304/j.cnki.issn1000-7180.2015.05.018
引用本文: 周文强, 张金艺, 周多, 刘江. 三维片上网络最短路径令牌式路由算法[J]. 微电子学与计算机, 2015, 32(5): 84-90. DOI: 10.19304/j.cnki.issn1000-7180.2015.05.018
ZHOU Wen-qiang, ZHANG Jin-yi, ZHOU Duo, LIU Jiang. Minimal Path and Token Based Routing Algorithm for 3D NoC[J]. Microelectronics & Computer, 2015, 32(5): 84-90. DOI: 10.19304/j.cnki.issn1000-7180.2015.05.018
Citation: ZHOU Wen-qiang, ZHANG Jin-yi, ZHOU Duo, LIU Jiang. Minimal Path and Token Based Routing Algorithm for 3D NoC[J]. Microelectronics & Computer, 2015, 32(5): 84-90. DOI: 10.19304/j.cnki.issn1000-7180.2015.05.018

三维片上网络最短路径令牌式路由算法

Minimal Path and Token Based Routing Algorithm for 3D NoC

  • 摘要: 目前,常用的一些三维片上网络(3D NoC)路由算法在路由路径最短和路由路径多样性两方面只能保证其一个,二者不能很好地兼顾.针对这些不足,设计了两种既能保证路由路径最短,同时也能保证路由路径多样性的三维片上网络最短路径令牌式路由算法,分别是适用于3D Mesh结构的3D-Mesh-MPT路由算法和适用于3D Torus结构的3D-Torus-MPT路由算法.两种算法在路由过程中总是选择最短的路径进行路由,同时路由器输出端口的选择由算法中令牌的分配情况而定,保证了路径的多样性.采用Verilog HDL实现了这两种三维片上网络路由算法,同时,为了提高算法的灵活性,设计时采用了参数化设计.实验结果表明,设计的两种算法具有较低的资源利用率,在FPGA主要资源Slice Registers、Slice LUTs以及Occupied slices等方面的利用率分别均不到0.3‰、1.4‰、3.5‰.在延时方面,两种算法的最大输出延时均在7.3~7.6 ns之间.另外,两种算法的功耗随频率变化的趋势和理论分析一致,呈现低功耗的特点.

     

    Abstract: At present, considering the two aspects which are the minimal path and the path diversity for routing algorithm of 3D NoC(3D Network on Chip), some 3D NoC routing algorithms which are commonly used can only guarantee one of these two aspects. To overcome these disadvantages, two minimal path and token based routing algorithms for 3D NoC are designed in this paper, these two routing algorithms not only can ensure the routing paths are minimal, but also have the characteristics of path diversity. They are 3D-Mesh-MPT routing algorithm which is used for 3D Mesh topology and 3D-Torus-MPT routing algorithm which is used for 3D Torus topology. They always choose the minimal path to route, in addition, in order to guarantee the diversity of the path, the routers' output ports are chosen by tokens. Verilog HDL is used to implement these two algorithms. Furthermore, to improve the flexibility, the algorithms adopt the method of parametric design. The results show that these two algorithms have low resource utilizations. The utilization of Slice Registers, Slice LUTs and Occupied slices on FPGA are less than 0.3‰, 1.4‰, 3.5‰, respectively. The maximum output delay of these two algorithms are between 7.3~7.6 ns. Moreover, the two algorithms' trends of power consumption with frequency are consistent with theoretical analysis and they have the characteristics of low power consumption.

     

/

返回文章
返回