40
Network-on-Chip
1
6
5
2
11
15
16
12
9
13
14
10
3
7
4
8
L
9
6
1 14
10 8
3
7
4
13
L
L
15
11
16
5
(a)
2
RR
CR
CR
L
RR
12
(b)
Figure 2.20
Labeling of 2 × 2 MoT (a) and its channel dependency graph (b).
of the labeling scheme, for example, labels 76–78 in Figure 2.19. Ultimately,
the packet will reach to that node where the destination core is connected.
In step 5, based on the Core-ID bit, the packet will go to the destination core.
After tracing the labels of the channels from source to destination, it can be
observed that the channel labels are always increasing, and thus the channel
dependency graph is acyclic. Therefore, this network is always deadlock free.
The labeling of the channels by applying the above-mentioned scheme in the
2 × 2 MoT and its channel dependency graph has been shown in Figure 2.20. In
the figure, the channel label is always increasing in a particular direction from
start to end and has not formed any cycle. Thus, the 2 × 2 MoT-based network
is deadlock free. Similarly, the channel dependency graph of M × N MoT by
applying the same labeling scheme will be acyclic, and hence deadlock free.
For wormhole switching, Glass and Ni (1992) proposed the turn model to
solve the routing-dependent deadlock in adaptive routing in 2D mesh. For
partially adaptive routing, west-first, north-last, and negative-first turn models were proposed by Glass and Ni (1994). In the west-first turn model, the
packet first routed toward the west, if necessary, and then adaptively south,
east, and north. The prohibited turns are the two to the west. Similarly, in
the north-last turn model, the packet first routed adaptively toward the west,
south, east, and then north. In the negative-first turn model, the packet is
routed first toward adaptively the west and south, and then adaptively the
east and north. Figure 2.21 depicts the scenarios.
Another deadlock-free turn model for partially adaptive routing, odd–
even turn model, was proposed by Chiu (2000). In the odd-even turn model,
two rules are being followed:
1. Any packet is not allowed to take an east-north or east-south turn at
any nodes located in an even column.
2. Any packet is not allowed to take an north-west or south-west turn
at any nodes located in an odd column.