33
Interconnection Networks in Network-on-Chip
c 0
c 0
s 1
s 4
s 3
s 2
s 5
d 4
d 3
d 2
d 5
d 1
c 1
c 1
c 16
c 16
c 5
c 5
c 4
c 4
c 2
c 2
c 17
c 17
c 6
c 6
c 11
c 11
c 10
c 10
c 7
c 7
c 18
c 18
c 15
c 15
c 14
c 14
c 3
c 3
c 9
c 9
c 8
c 8
c 19
c 19
c 13
c 13
c 12
c 12
(a)
(b)
Figure 2.16
XY routing in 2D mesh topology (a) and its channel dependency graph (b).
For ring, torus, and folded torus, Dally and Seitz (1987) proposed a
deadlock avoidance technique by splitting each physical channel into
a group of VCs. For a ring network, Figure 2.17 shows that the packets at
a node numbered less than their destination node are routed on the firm
channels (C 00 , C 01 , and C 02 ), whereas the packets at a node numbered greater
than their destination node are routed on the dotted channels (C 11 , C 12 , and
C 13 ). For example, if a packet originated from n3 and destined for n2, it traversed through the following channels: C 13 –C 00 –C 01 .
For routing in BFT, a least common ancestor (LCA) algorithm was proposed
by Pande et al. (2003a). For deadlock free routing in any irregular topology
or faulty regular topology, instead of using VC, up*/down* routing is used
(Schroeder et al. 1991). A deterministic routing in an M × N MoT network
was proposed by Kundu and Chattopadhyay (2008a, 2008b) and presented
here in detail.
2.4.1.1 Deterministic Routing in M × N MoT Network
To propose a routing algorithm for any network, the following steps are
required: (1) addressing of each node, (2) proof of livelock free, and (3) proof
of deadlock free routing.
C 00
C 01
C 02
C 12
n2
n3
n1
n0
C 11
C 13
Figure 2.17
Routing-dependent deadlock avoidance in ring network using VC.