Due to the shrinking transistor sizes, the density of ICs roughly doubles every year as predicted by Moore's law. These advancements in the VLSI integration densities towards the nano scale era, witnessed a paradigm shift from computation centric designs to communication centric designs incorporating very large number of simple cores. Plenty of traditional interconnect schemes like point to point, buses and crossbars are available to interconnect small number of cores. While achieving fast and efficient communication with point to point communication schemes, wire density is a barrier for adapting them to many core architectures. Moreover, buses are simpler in design, they suffer from the scalability and arbitration issues along with bandwidth bottleneck as the number of cores increases. Similarly area and power requirements of a crossbar limits its applicability. Hence, in many core architectures like Chip Multiprocessors (CMP) and Multi processor System-on-Chip (MPSoCs), emerge the need of an efficient communication infrastructure as traditional solutions fails to handle the communication challenges. Network-on-Chip (NoC), a scalable and modular design approach, has been proposed as a promising alternative to traditional bus based architectures for inter-core communication. NoC has also been accepted in industy (Tilera's TILE-Gx72, TILE64TM [1] processors and Intel's terascale processor [2]. NoCs are an attractive alternative for the traditional shared-buses or dedicated wires due to many reasons. First, NoCs represent a scalable solution to on-chip communication paradigm, because they provide scalable bandwidth at low power and area overheads. Second, NoCs are very efficient in terms of use of wiring and multiplexing many traffic flows on the same channels providing quality of service and higher bandwidth. Finally, on-chip networks with regular topologies have short interconnects that can be optimized and reused using regular iterative blocks, thus making the- verification process easy. For on-chip networks, two-dimensional (2D) mesh is the most preferred topology choice due to its regularity, scalability, and perfect physical layout on an actual chip. This tutorial shall focus on NoC routing algorithms, their implementations and issues. The main parameters of the network which are affected by the routing algorithm include fault-tolerance, quality of service, communication performance (throughput and latency) and power consumption. The following are the main objective of this tutorial ; Introduction to NoC [3]: In this part, we briefly discuss about various design parameters of NoC such as topology, switching, flow control, routing and comparison with existing mechanisms. : Routing Taxonomy [4]: In this part, we present classification of various routing algorithms. : Deadlock and Livelock freedom in Routing: One of current issue in NoC routing is the use of acyclic channel dependency graph (ACDG) for deadlock freedom prohibiting certain routing turns. Thus, ACDG reduces the degree of adaptiveness. In this section, we discuss various turn models [5] and how these turn model can be improved to increase adaptivity while maintaining deadlock freedom. : Routing Implementations for NoC: Denser integration advancements make the chip more prone to failures (deep sub-micron effects, manufacturing effects etc). Furthermore these failures may disrupt the regularity of 2D meshes, leading to an irregular set of topologies generated from regular 2D meshes. Under this condition, solutions of regular 2D meshes may no longer work due to irregular topology. In this section, we discuss state-of-art routing implementation techniques [6]-[8] used for irregular 2D mesh under different failures. : Learning methods to handle congestion in Routing: Reinforcement Learning (RL) is a machine learning paradigm that has been widely applied in many areas. The Q-Learning has been used in NOC to learn the network traffic and make the routing decisions a
展开▼
