41
Interconnection Networks in Network-on-Chip
(a)
(b)
(c)
Figure 2.21
Turn model: (a) west-first; (b) north-last; (c) negative-first.
A VC-based deadlock-free fully and partially adaptive routing in 2D mesh
was proposed by Duato (1993). When restricted to a minimal path, this routing algorithm is referred to Duato’s protocol. Ascia et al. (2008) proposed a
neighbors-on-path (NoP) congestion-aware selection in 2D mesh and used it in
the odd–even turn model-based adaptive routing. The experimental results
show that the latency of the system gets improved after adopting this selection policy with nonuniform traffic.
Deadlock recovery, however, is useful when the deadlock situation is rare.
It allows a deadlock to occur, but once the deadlock situation is detected,
it breaks at least one of the cyclic dependencies by using any of the recovery schemes, regressive (abort-and-retry) and progressive (preemptive), to
gracefully recover. Regressive recovery scheme removes a packet from a
dependency cycle by aborting and later reinjecting the packet into the network after some delay. Progressive recovery scheme removes a packet from
a dependency cycle by rerouting it onto a deadlock-free lane.
2.4.2 Avoidance of Message-Dependent Deadlock
On-chip communication, depending on the behavior of the IP modules, can
lead to four types of message dependencies—request–response, response–
request, request–request, and response–response. Message-dependent
deadlocks arise when dependency cycles on the resources (free from routingdependent deadlock) exist due to message dependencies between the NoC
and IP cores at the network end points (Song and Pinkston 2003). Figure 2.22
shows the coupling between the reception of request and the generation of
responses, which introduces a dependency between the request and response
buffers in the NI and thus causing deadlock in the network. In the figure, two
master and slave pairs communicate via two shared input-buffered routers.
The two connections between m1 and s1 are drawn with continuous lines
and the connections of m2 and s2 with dashed lines. Responses from s1
enter the network, turn the east, and end up in b2. This buffer is shared by
responses destined for m1 and requests going to s2. From b2, the dependencies continue through the slave s2, and the shared buffer b1, back to s1, closing the cycle. As a result, a deadlocked situation can occur.
In response–request dependency, the master sends a request, the slave
responds to that request, and then the master reacts on the response from
the slave by sending an additional request. Request–request dependencies
Interconnection Networks in Network-on-Chip
(a)
(b)
(c)
Figure 2.21
Turn model: (a) west-first; (b) north-last; (c) negative-first.
A VC-based deadlock-free fully and partially adaptive routing in 2D mesh
was proposed by Duato (1993). When restricted to a minimal path, this routing algorithm is referred to Duato’s protocol. Ascia et al. (2008) proposed a
neighbors-on-path (NoP) congestion-aware selection in 2D mesh and used it in
the odd–even turn model-based adaptive routing. The experimental results
show that the latency of the system gets improved after adopting this selection policy with nonuniform traffic.
Deadlock recovery, however, is useful when the deadlock situation is rare.
It allows a deadlock to occur, but once the deadlock situation is detected,
it breaks at least one of the cyclic dependencies by using any of the recovery schemes, regressive (abort-and-retry) and progressive (preemptive), to
gracefully recover. Regressive recovery scheme removes a packet from a
dependency cycle by aborting and later reinjecting the packet into the network after some delay. Progressive recovery scheme removes a packet from
a dependency cycle by rerouting it onto a deadlock-free lane.
2.4.2 Avoidance of Message-Dependent Deadlock
On-chip communication, depending on the behavior of the IP modules, can
lead to four types of message dependencies—request–response, response–
request, request–request, and response–response. Message-dependent
deadlocks arise when dependency cycles on the resources (free from routingdependent deadlock) exist due to message dependencies between the NoC
and IP cores at the network end points (Song and Pinkston 2003). Figure 2.22
shows the coupling between the reception of request and the generation of
responses, which introduces a dependency between the request and response
buffers in the NI and thus causing deadlock in the network. In the figure, two
master and slave pairs communicate via two shared input-buffered routers.
The two connections between m1 and s1 are drawn with continuous lines
and the connections of m2 and s2 with dashed lines. Responses from s1
enter the network, turn the east, and end up in b2. This buffer is shared by
responses destined for m1 and requests going to s2. From b2, the dependencies continue through the slave s2, and the shared buffer b1, back to s1, closing the cycle. As a result, a deadlocked situation can occur.
In response–request dependency, the master sends a request, the slave
responds to that request, and then the master reacts on the response from
the slave by sending an additional request. Request–request dependencies