38
Network-on-Chip
receive messages compete for these resources. 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. A practical routing algorithm
must be deadlock free. The sufficient condition to avoid deadlock in a network
is that there should not be any cycle in the channel dependency graph.
Here, a general proof has been given to show that the proposed routing algorithm is deadlock free. Two opposite unidirectional links are used between two
adjacent routers as shown in Figure 2.19. All the channels in the M × N MoT
are labeled as shown in the figure (considering M = 4, N = 4) in different steps.
Each channel has a unique label. The labeling scheme is mentioned as follows:
1. Label those channels in ascending order which are directed from
the leaf levels to the root of the column trees, for example, labels 1–24
as shown in Figure 2.19.
2. Label those channels in ascending order which are directed from
the root of the column trees to the leaf levels, for example, labels
25–48 as shown in Figure 2.19.
3. Label those channels in ascending order which are directed from
the leaf levels to the root of the row trees, for example, labels 49–72
as shown in Figure 2.19.
4. Label those channels in ascending order which are directed from
the root of the row trees to the leaf levels, for example, labels 73–96
as shown in Figure 2.19.
In step 1 of the routing algorithm, if RN of the source address is different
from that of the destination address, the packet will be directed from the
leaf level to the root of the column tree until the RN becomes the same as
destination. Therefore, the packet will traverse from a lower labeled channel
to a higher labeled channel as mentioned in step 1 of the labeling scheme, for
example, labels 1–3 in Figure 2.19.
In step 2, if CL of the current node is different from that of the destination
node, the packet will be directed from the root of the column tree to the leaf
level where RN is same as destination. Therefore, the packet will traverse
from a lower labeled channel to a higher labeled channel as mentioned in
step 2 of the labeling scheme, for example, labels 28–30 in Figure 2.19.
In step 3, if CN of the current node is different from that of the destination
node, the packet will be directed from the leaf level to the root of the row tree
until CN becomes the same as destination. Therefore, the packet will again traverse from a lower labeled channel to a higher labeled channel as mentioned
in step 3 of the labeling scheme, for example, labels 49–51 in Figure 2.19.
In step 4, if RL of the current node is different from that of the destination
node, the packet will be directed from the root of the row tree to the leaf level
where RN is same as destination. Therefore, the packet will traverse from
a lower labeled channel to a higher labeled channel as mentioned in step 4