32
Network-on-Chip
(a)
(b)
s 1
s 2
C0
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
P1
P1
P1
P2
P2
P3
P3
P4
P4
P5
P2
P3
c 3
c 5
c 8
c 11
c 12
c 7
c 6
s 3
c 4
c 2
c 0
c 1
c 9
c 10
d 2
d 3
d 5
s 4
d 4
d 1
s 5
P4
Figure 2.15
Routing-dependent deadlock in mesh network: (a) packet traversal path; (b) channel dependency graph.
s4, and s5 are the sources of packets, whereas d1, d2, d3, d4, and d5 are their
respective destinations. Packet P1 originated from s1 traversed through the
channels c0–c1–c2 and blocked by the packet P2 originated from s2. Packet
P2 originated from s2 traversed through the channels c3–c4–c5 and blocked
by the packet P3 originated from s3. Packet P3 originated from s3 traversed
through the channels c6–c7–c8 and blocked by the packet P4 originated from
s4. Similarly, the packet P4 originated from s4 traversed through the channels c9–c10–c11 and blocked by the packet P1 originated from s1. Figure 2.15b
shows the formation of a cycle (c2–c5–c8–c11–c2) in the channel dependency
graph of the above communication. Due to this routing-dependent deadlock,
none of the packet can reach to its destination.
For handling routing-dependent deadlock, any of the two techniques—
deadlock avoidance and deadlock recovery—can be adopted. In order to
avoid routing-dependent deadlock in a network, the sufficient condition is to
show the nonexistence of a cycle in the channel dependency graph.
Dimension-ordered routing is the most simplistic approach to avoid deadlock in deterministic routing. In a 2D mesh, this routing is known as XY
routing where a packet is forwarded first in X-dimension until it reaches the
X-coordinate of the destination and then it is forwarded in Y-dimension until
it reaches the destination. Figure 2.16a depicts the scenario and Figure 2.16b
shows its channel dependency graph where no cycle exists, and hence this
routing can avoid deadlock in the network. Like XY routing, YX routing is
also deadlock free.
For SAF and VCT switching, as the buffer has the capacity to store the
entire packet, it is much simpler to avoid deadlock. Deflection routing or
hot potato routing (Greenberg and Hajek 1992) is used for these switching
techniques.
Network-on-Chip
(a)
(b)
s 1
s 2
C0
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
P1
P1
P1
P2
P2
P3
P3
P4
P4
P5
P2
P3
c 3
c 5
c 8
c 11
c 12
c 7
c 6
s 3
c 4
c 2
c 0
c 1
c 9
c 10
d 2
d 3
d 5
s 4
d 4
d 1
s 5
P4
Figure 2.15
Routing-dependent deadlock in mesh network: (a) packet traversal path; (b) channel dependency graph.
s4, and s5 are the sources of packets, whereas d1, d2, d3, d4, and d5 are their
respective destinations. Packet P1 originated from s1 traversed through the
channels c0–c1–c2 and blocked by the packet P2 originated from s2. Packet
P2 originated from s2 traversed through the channels c3–c4–c5 and blocked
by the packet P3 originated from s3. Packet P3 originated from s3 traversed
through the channels c6–c7–c8 and blocked by the packet P4 originated from
s4. Similarly, the packet P4 originated from s4 traversed through the channels c9–c10–c11 and blocked by the packet P1 originated from s1. Figure 2.15b
shows the formation of a cycle (c2–c5–c8–c11–c2) in the channel dependency
graph of the above communication. Due to this routing-dependent deadlock,
none of the packet can reach to its destination.
For handling routing-dependent deadlock, any of the two techniques—
deadlock avoidance and deadlock recovery—can be adopted. In order to
avoid routing-dependent deadlock in a network, the sufficient condition is to
show the nonexistence of a cycle in the channel dependency graph.
Dimension-ordered routing is the most simplistic approach to avoid deadlock in deterministic routing. In a 2D mesh, this routing is known as XY
routing where a packet is forwarded first in X-dimension until it reaches the
X-coordinate of the destination and then it is forwarded in Y-dimension until
it reaches the destination. Figure 2.16a depicts the scenario and Figure 2.16b
shows its channel dependency graph where no cycle exists, and hence this
routing can avoid deadlock in the network. Like XY routing, YX routing is
also deadlock free.
For SAF and VCT switching, as the buffer has the capacity to store the
entire packet, it is much simpler to avoid deadlock. Deflection routing or
hot potato routing (Greenberg and Hajek 1992) is used for these switching
techniques.