36
Network-on-Chip
Algorithm
If (RN of addr (curr) ≠ RN of addr (dest)) // Step1
      Route to Column Parent;
      Else If (CL of addr (curr) ≠ CL of addr (dest)) // Step2
             Route to Column Child having equal RN as addr (dest);
           Else If (CN of addr (curr) ≠ CN of addr (dest)) // Step3
                  Route to Row Parent;
                Else If (RL of addr (curr) ≠ RL of addr (dest)) // Step4
                         Route to Row Child having equal CN as addr (dest);
                         Else If (Destination Core-ID field = 0) // Step5
                                 Route to Core1;
                                 Else Route to Core2;
In step 1, a difference in RN of current and destination addresses signifies
that current and destination routers are at different row trees. Therefore,
the packet needs to be routed toward the root of the column tree until RN
of the current router becomes equal to that of the destination router. For
example, if router addresses associated with source and destination cores
are 00–00–00–00 and 11–00–11–00, respectively, the path traversed by the
packet is 00–00–00–00 → 0X–01–00–00 → XX–10–00–00. Therefore, after
step 1, the packet will reach a node whose RN of the current router is the
same as that of the destination router.
In step 2, a difference in CL of current and destination addresses signifies
that the current router is not at the leaf level as all destination routers are.
Therefore, the packet needs to traverse toward the leaf level of the column
tree for which RN is equal to the destination. For the above example, the
path traversed by the packet is XX–10–00–00 → 1X–01–00–00 → 11–00–00–
00. Therefore, after step 2, the packet reaches a node whose RN and CL are
same as those of destination, that is, the packet has arrived at a node which
is on the same row tree as the destination.
In step 3, the difference in CN of current and destination addresses signifies that current and destination routers are at different column trees.
Therefore, the packet should be routed toward the root of the row tree until
CN of the current router becomes equal to that of the destination router. For
the above example, the path traversed by the packet is 11–00–00–00 → 11–00–
0X–01 → 11–00–XX–10. Therefore, after step 3, the packet will reach a node
whose first three fields are same as destination.
In step 4, a difference in RL of current and destination addresses signifies
that the current router is not at leaf level. Therefore, the packet should traverse
toward the leaf level of the row tree, where CN is same as destination. For the
above example, the path traversed by the packet is 11–00–XX–10 → 11–00–1X–
01 → 11–00–11–00. Therefore, after step 4, the packet reaches a router whose
all four fields are same as destination; in other words, the packet reaches a
router to which the destination core is attached.