31
Interconnection Networks in Network-on-Chip
routing, precomputed routing table is stored in the network interface (NI).
Æthereal uses source routing (Goossens et al. 2005). In distributed routing,
each packet carries the source and destination addresses. The routing decision is implemented in each router either by a routing table or by executing
a finite-state machine. SoCIN is an example of distributed routing (Zeferino
and Susin 2003). Depending on the adaptability, both source and distributed routing can further be classified as deterministic, oblivious, and adaptive
(Duato et al. 2003). In deterministic (or static) routing, packets always follow
a specific path from source to destination. This assures in-order delivery of
packets. Oblivious routing, however, selects the path randomly or cyclically.
Both deterministic and oblivious routing do not consider the current state
of the network. In adaptive (or dynamic) routing, the routing decisions are
made according to the current state of the network (congestion, available
links, etc.) and alternative paths are chosen dynamically to avoid congested
or faulty regions of the network. Therefore, in-order delivery is not guaranteed and reordering of packets at destination NI is a necessity. Adaptive
routing can be classified as progressive and backtracking. Progressive routing
moves the header forward, reserving a new channel at each routing operation. Backtracking routing allows the header to backtrack as well, releasing
previously reserved channels. Backtracking algorithms are mainly used for
fault-tolerant routing. Both deterministic and adaptive routing can be minimal and non-minimal, based on the number of hops traversed from source to
destination. Delay and power consumption in communication are higher in
non-minimal routing than in minimal routing as it traverses more number
of hops. Adaptive routing that follows a minimal path from source to destination is further classified as minimal fully adaptive and partially adaptive. The
challenges of any routing scheme are that the routing should be livelock and
deadlock free.
Livelock arises when packets travel around their destination node, but
unable to reach it because the channels to do so are occupied by other packets. It can only occur in adaptive routing when packets are allowed to follow non-minimal paths. Deadlock occurs when a set of messages is blocked
forever because each message in the set holds one or more resources needed
by another message in the set. There are two ways in which a deadlock can
occur in a network—routing-dependent deadlock and message-dependent
deadlock.
2.4.1 routing-Dependent Deadlock
Depending on the routing information, a deadlock situation will arise if
there exists any cycle in its channel dependency graph (Dally and Seitz 1987).
A channel dependency graph is a directed graph whose vertices are the
channels of the interconnection network, whereas edges show the dependency between any pair of channels. Figure 2.15 shows a scenario of routingdependent deadlock in a mesh network. Figure 2.15a depicts that s1, s2, s3,
Interconnection Networks in Network-on-Chip
routing, precomputed routing table is stored in the network interface (NI).
Æthereal uses source routing (Goossens et al. 2005). In distributed routing,
each packet carries the source and destination addresses. The routing decision is implemented in each router either by a routing table or by executing
a finite-state machine. SoCIN is an example of distributed routing (Zeferino
and Susin 2003). Depending on the adaptability, both source and distributed routing can further be classified as deterministic, oblivious, and adaptive
(Duato et al. 2003). In deterministic (or static) routing, packets always follow
a specific path from source to destination. This assures in-order delivery of
packets. Oblivious routing, however, selects the path randomly or cyclically.
Both deterministic and oblivious routing do not consider the current state
of the network. In adaptive (or dynamic) routing, the routing decisions are
made according to the current state of the network (congestion, available
links, etc.) and alternative paths are chosen dynamically to avoid congested
or faulty regions of the network. Therefore, in-order delivery is not guaranteed and reordering of packets at destination NI is a necessity. Adaptive
routing can be classified as progressive and backtracking. Progressive routing
moves the header forward, reserving a new channel at each routing operation. Backtracking routing allows the header to backtrack as well, releasing
previously reserved channels. Backtracking algorithms are mainly used for
fault-tolerant routing. Both deterministic and adaptive routing can be minimal and non-minimal, based on the number of hops traversed from source to
destination. Delay and power consumption in communication are higher in
non-minimal routing than in minimal routing as it traverses more number
of hops. Adaptive routing that follows a minimal path from source to destination is further classified as minimal fully adaptive and partially adaptive. The
challenges of any routing scheme are that the routing should be livelock and
deadlock free.
Livelock arises when packets travel around their destination node, but
unable to reach it because the channels to do so are occupied by other packets. It can only occur in adaptive routing when packets are allowed to follow non-minimal paths. Deadlock occurs when a set of messages is blocked
forever because each message in the set holds one or more resources needed
by another message in the set. There are two ways in which a deadlock can
occur in a network—routing-dependent deadlock and message-dependent
deadlock.
2.4.1 routing-Dependent Deadlock
Depending on the routing information, a deadlock situation will arise if
there exists any cycle in its channel dependency graph (Dally and Seitz 1987).
A channel dependency graph is a directed graph whose vertices are the
channels of the interconnection network, whereas edges show the dependency between any pair of channels. Figure 2.15 shows a scenario of routingdependent deadlock in a mesh network. Figure 2.15a depicts that s1, s2, s3,