Research On High-Performance And Deadlock-Free Routing Algorithms In Mesh-Based Networks-on-chip

NetworksonChips(No Cs)is one of key components of the current SystemonChip(So C),due to its high scalability and flexibility,and it can provide highspeed and reliable data communication between cores.The research of No Cs mainly focuses on the topology,switching technology,and routing algorithm.The routing algorithm determines the appropriate transmission path for a message and is a key factor affecting the system performance.Therefore,it is very important to study the routing algorithm of the No C.This paper analyzes problems existing in the routing algorithm of No Cs indepth,and launches a series of studies.The main contributions of this paper are as follows:· To solve the problem that the routing algorithms could not provide full routing adaptiveness with fairly utilized virtual channels in 2D meshes,this paper proposes a new fully adaptive routing algorithm based on a new virtual network scheme.The major contribution of the proposed routing algorithm is that some common virtual channels can be shared by separate virtual networks to reduce the required number of virtual channels and improve performance.Prevented turns and special turns are set for a small portion of messages to avoid deadlocks,that is the lightweight constraint and cannot affect the adaptiveness of the routing algorithm.Through simulation experiments,the results show the effectiveness of the routing algorithm.· With the increase in the number of integrated cores on chip,2D No Cs have shown some shortcomings such as longer links and higher power consumption.To solve this problem,This paper studies the routing algorithm of 3D stacked No Cs with full vertical connections.This paper analyzes and explores the routing pressure of various routing algorithms based on the concept of repetitive turns,and finds the routing algorithm with the minimum routing pressure,which guarantees that the obtained routing algorithm has the ability to balance the network load theoretically.Moreover,strict deadlockfree proof is performed on the proposed routing algorithm.Simulation results show that the proposed routing algorithm can improve the performance compared with other routing algorithms without virtual channels,which is consistent with the theoretical analysis.· Due to the manufacturing complexity and the area cost of TSVs,this paper takes the virtual network scheme in the 2D mesh as an inspiration point,proposes a new virtual network scheme suitable for 3D No Cs with partial vertical connections(PVCs)between two dies,and designs the corresponding highperformance routing algorithm.Based on the new virtual network scheme,two virtual networks can be assigned some common virtual channels,which is completely different from the original virtual network scheme proposed by Linder and Harden.Any message can traverse inside multiple virtual networks.Simulation results show that the new method outperforms two previous methods,which can provide higher throughput and lower average latency.