Minimal Path and Token Based Routing Algorithm for 3D NoC

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.