Research On 3D NoC Routing Algorithm Based On Mesh Topology

Three-Dimensional Network on Chip(3D NoC)has the advantages of short physical connection length,low data transmission delay and high chip integration density.It completely breaks through the bottleneck of 2D NoC and has attracted extensive attention from academia and industry.While 3D NoC plays an important role,it is also facing more and more serious challenges.It is a key issue that how to reliably transmit data in the network.The routing algorithm is responsible for calculating the transmission path of the packet and transmitting the packet from the source node to the destination node accurately,which is of great significance and status in the 3D NoC.The research on routing algorithms has achieved a lot of results,however there are still some problems:(1)The priority failure of packet in the transmission process leads to the deflection transmission of packet;(2)When the network scale is expanded,the overhead of on-chip storage increases dramatically;(3)In the scenario of multicast transmission,the network is prone to congestion and the packet transmission delay is high,which is not conducive to the real-time processing and service of each program.In view of the above problems,based on the national science and technology major project,this dissertation aims to improve the transmission performance of 3D NoC.The deflection routing algorithm,the unicast routing algorithm and the multicast routing algorithm are studied based on two topologies of vertically fully connected 3D Mesh and vertically partially connected 3D Mesh.The specific contents of this dissertation are as follows:1.Aiming at the problems that the priority allocation mechanism of packet is invalid and the local packet is not ejected timely in the deflection routing algorithm,a recalculation deflection routing algorithm based on the minimally buffered router is proposed.First,the algorithm determines which packet preferentially selects the output port according to the priority of the packet,and then selects the optimal output port based on the direction of the destination node.In order to ensure that the priority of packet is still valid in the downstream router,when the packet is about to be transmitted to the downstream router,the priority recalculation is performed according to the direction of the current node relative to the destination node.In addition,an ejection buffer is introduced in the ejection unit of the router to solve the problem that the local packet is not ejected in time.Finally,the simulation results show that compared with the reference algorithm,the transmission delay and deflection times of the proposed algorithm are reduced by 14.8% and 15.4% respectively.2.For unicast routing algorithm in the vertically partially connected 3D Mesh NoC,it has a large storage overhead and lacks scalability.The multi-dimensional information record table structure is proposed.The record table only stores the nearest 4 TSV location information from the current node,the network fault state and output port buffer occupancy.In addition,an adaptive unicast routing algorithm based on multi-dimensional information mixing is designed in combination with the proposed record table.The algorithm can calculate the optimal transmission path by combining multi-dimensional information.The results of the theoretical calculation show that the proposed record table can greatly reduce the hardware resource overhead in a large-scale network.Simulation results show that the proposed algorithm can improve the throughput by at least 8.5% and reduce the transmission delay by 11.6% compared with the algorithms that only consider the fault information.3.In order to solve the problems that multicast routing algorithm in the vertically partially connected 3D Mesh NoC has high transmission delay and is prone to congestion,a multicast routing algorithm based on intra-layer network zone partition is proposed.In the case of inter-layer transmission,the packet selects the TSV closest to the current node as the channel for inter-layer transmission,which can shorten the length of the inter-layer transmission path.In the case of intra-layer transmission,the network zone is partitioned according to the location relation between source node and destination nodes,and then the packets are transmitted on the public path in a single packet and are not forced to copy on the destination node,which can reduce the possibility of network congestion.At the same time,the zone partition strategy can avoid the occurrence of deadlock in the layer.Experimental results show that the proposed algorithm has higher reliability than the existing multicast routing algorithms,and averagely improves the network transmission performance by 7.1% and 12.5% respectively based on Random and Hotspot traffic models.