Research On Routing Algorithms For 3-D Network On Chip Based-on Virtual Channels

As the number of transistors integrated on a single chip grows rapidly in accordance with Moore's Law, the traditional single-chip system with bus architecture is restricted by the complicated bus architecture, low efficiency in communication and so on. The Network-on-Chip, which draws on the design of network protocol based on packets switching and separates the function of cores from that of communication interfaces, has become a hotspot on the design of complex System-on-Chip. The two-dimensional Network-on-Chip has longer connection distance between cores, smaller capacity and larger radius of network,which limit its performance. When the perforated silicon technology and the on-chip wireless communication technology were proposed and applied, the three-dimensional Network-on-Chip gets more attention of researchers. For the routing problem of the three-dimensional Network-on-Chip, we propose a modified virtual channel allocation strategy, a new three-dimensional topology and the corresponding routing algorithm, which improve the average latency and network throughput rate effectively.At first, in order to solve the problem that the global cache utilization rate of the existing virtual channel allocation strategies on the three-dimensional topology is low, this paper improves the SVC virtual channel allocation strategy and presents the LPVC virtual channel strategy. We utilize the linear programming idea and use adaptive factors to manage buffers in the strategy, which achieves a high utilization rate of buffers while the average latency of the network reduces. Then, for the problem that the pillar nodes overload at high injection rate on the three-dimensional topology, we present the AXNoTs topology which draws on the idea of aspect topology. Using hierarchical interconnection topology as the aspect topology of AXNoTs alleviates the pressure of the pillar nodes effectively and improves the throughput rate of the Network-on-Chip. Finally, for the characteristics of AXNoTs topology, we propose the PFBR routing algorithm. It fully utilizes the aspect topology and determines the routing path by the probability of direction, which gets the average latency of the network reduced.In order to evaluate the three-dimensional virtual channel allocation strategies and routing algorithms, we have developed a simulator of the three-dimensional Network-on-chip.The simulator uses the self-similar business model to improve the reliability of the simulation results on the three traffic patterns with random, replacement and hotspot. In these traffic patterns, the simulation results based on the AXNoTs topology indicates the average delay of the virtual channel allocation strategy LPVC is lower than the virtual channel allocation strategy GVC, and the throughput rate of the routing algorithm is higher than the current ones of HamFA and PPROM, while on the pattern of replacement, the throughput rate is as high as 0.43flit/cycle.