37
Interconnection Networks in Network-on-Chip
In step 5, based on the Core-ID bit, the packet gets forwarded to the
destination core. Therefore, the proposed routing algorithm always governs
the packet to reach the destination in a specified path.
2.4.1.1.3 Proof for Shortest Path
Here, a general proof has been given to show that the above algorithm will
always govern the packet to traverse in a shortest path from source to destination. From the addressing scheme of M×N MoT, the RN and CN fields are
of log 2 M and log 2 N bits. According to step 1 of the algorithm, the packet
will first follow that path leading to a node where RN of the current address
is the same as that of the destination address. That is,
if (RN of addr (curr) ≠ RN of addr (dest))
{ for (i = log 2 M; i > = 1; i–– ) {
i th
if (i th bit position of the RN of addr (curr) ≠
bit
position of the RN of addr (dest))
{k = i; break ;} }
Route upwards by k hops in column tree. }
Therefore, the packet will traverse k hops in upward direction through a
column tree and will reach to a node where RN becomes the same as the
destination. However, CL of that node is equal to k. As the cores are attached
only at the leaf level, the CL fields of the destination router are always
zero. According to step 2 of the algorithm, the packet will follow that path
where CL is gradually decreasing to zero, having RN same as destination.
Therefore, the packet will traverse k hops in downward direction through a
column tree. Thus, the packet will traverse a total of 2k hops and will reach a
node having RN and CL fields same as those of destination. Now, according
to step 3 of the algorithm, it will follow that path where CN of the current
address is the same as that of the destination address. Arguing in the same
way as above, the packet will traverse l hops in upward direction and then
in downward direction through a row tree before reaching the destination,
where l is the most significant bit position at which the column numbers of
source and destination differ. Therefore, the packet will traverse a total of
(2k + 2l) hops and will reach a node to which the destination core is attached.
We can consider this situation as if the source and the destination were the
k
l
k
l
two extreme nodes of a (2 × 2 ) MoT. In general, (2 × 2 ) MoT has the diameter of (2k + 2l). As the diameter signifies the minimum number of hops to
be traversed between two nodes that are at maximum distance, the routing algorithm always governs the packet to traverse in a shortest path from
source to destination.
2.4.1.1.4 Avoidance of Routing-Dependent Deadlock
In a multiprocessor on-chip network, communication channels and buffers
constitute the set of permanent reusable resources. The processors that send or