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

Minimal Path and Token Based Routing Algorithm for 3D NoC

作　　者：周文强[1] 张金艺[1,2,3] 周多[2] 刘江[1] 

机构地区：[1]上海大学微电子研究与开发中心,上海200072 [2]上海大学特种光纤与光接入网省部共建教育部重点实验室,上海200072 [3]上海大学教育部新型显示与系统应用重点实验室,上海200072

出　　处：《微电子学与计算机》2015年第5期84-90,共7页Microelectronics & Computer

基　　金：国家"八六三"计划项目(2013AA03A1121;2013AA03A1122);上海市教委重点学科资助项目(J50104)

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

关 键 词：3D NOC 最短路径 多样性 令牌式 参数化设计 

分 类 号：TN47[电子电信—微电子学与固体电子学]