Article Preview
TopIntroduction
Network-on-Chip (NoC) is an emerging field for connecting, managing and manipulating the interconnection communication among different IP cores (Benini & Micheli, 2005; Hemani et al., 2000). NoC addresses the challenges of the communication and provides a promising solution for System-on-Chip (SoC) for the problem of interconnects (Forsell, 2002). Packet switched network is established in NoC in which communication is taken place by sending and receiving data in form of packets between IP cores over this network (Dally & Towles, 2001).
Need of implementation on an appropriate NoC is the selection of suitable routing algorithms, reduction of power utilization, selection of proper connections, improvement of reliability, selection of appropriate size of the core (irregular mesh) and balance the link load. Among all these factors NoC Routing is one of the most important which affect the efficiency of NoC. The routing strategy determines the path followed by each packet between a source-destination pair. Moreover, number of cores requires a communication medium that can help and motivate simultaneous high bandwidth data transfers, low power consumption with low latencies.
A number of architectures have been proposed for NoC designs which employ either regular or custom network topologies (Kumar et al., 2002). Regular topologies, such as Torus, Fat Tree and Mesh have been employed in the tile-based NoC architectures to perform appropriately because of the homogeneity. It is easy to establish a shortest path between source and destination for regular mesh. Cores may be varied in module size and shape for real life applications. So, we can say that the heterogeneity in cores makes the structure as irregular and complicated. So, we define an irregular mesh topology identical to the full mesh including the addresses used to identify various modules except some links and routers on the chip are missing as shown in Figure 1.
Figure 1. Regular vs. irregular mesh of tile-based NoC architecture
Most critical issue for routing algorithm is “how to make routing deadlock free?” There are basically two techniques which deal with deadlock: Deadlock avoidance and Deadlock recovery. In the deadlock avoidance scheme, resources are allocated in such a manner that deadlock will never occur while packets are advancing. Deadlock recovery scheme detects and resolves the deadlock. Deadlock avoidance which basically has two approaches. First, a physical communication channel can be split into several virtual channels (VCs) as per the requirement (Dally, 2002). A message is tra-versed from a given virtual channel to another virtual channel if it creates no cyclic dependencies between them. In the second approach, routing restriction is imposed in order to achieve better throughput and fault-tolerance. This is done by finding the alternative paths for traversal of the packet when network has been congested with faulty communication links.
Efficient deadlock free routing is a challenging task in case of irregular mesh topology. However, one such method is to solve it with the help of routing tables, but that is not a good approach in terms of latency, power consumption and hardware cost due to its memory requirements. Logic based distributed routing (LBDR) is the alternative suggested by Flich and Duato (2008) which remove the need of routing tables completely and used different logic for the NoC routing. Algorithm would be more adaptive by extending the logic of LBDR (chooses all possible paths and avoid deadlock problem). Furthermore, due to scaling, the number of cores increase in NoCs and the power consumption is a critical issue as power consumption is directly proportional to hardware cost. In irregular mesh the hardware cost is minimized if we omit the use of routing tables which results into reduction of power consumption. Latency is the main performance metric to evaluate on-chip networks. A routing algorithm has to be design in such a manner that it reduces the number of network hops while packet is traversed so that latency is minimized.