34
Network-on-Chip
2.4.1.1.1 Addressing Scheme

The address of each node in an M × N MoT network consists of four fields:
(1) row number (RN), (2) column level (CL), (3) column number (CN), and (4) row
level (RL). For each row tree, RN is fixed; thus, for a 4 × 4 MoT, RNs are 00,
01, 10, and 11. RLs are gradually increased by 1 from leaf level to root level of
the row tree. In a row tree, CL is 00 for all the nodes. CN is assigned taking
parent–child relationship as shown in Figure 2.18. For example, 00–00–10–00
and 00–00–11–00 are the children and 00–00–1X–01 is the row parent where
X denotes “don’t care.” Similarly, for each column tree, CN is fixed. For a
4 × 4 MoT, CNs are 00, 01, 10, and 11. CLs are gradually increased by 1 from
leaf level to root level of each column tree. In a column tree, RL is 00 for all
the nodes and RNs are assigned taking parent–child relationship as shown
in Figure 2.18. For example, 00–00–00–00 and 01–00–00–00 are the children
and 0X–01–00–00 is the column parent where X denotes “don’t care.” A core
has the same RN, CL, CN, and RL similar to its associated router node.
A  core has only one additional Core-ID bit. For example, the addresses of
Core1 and Core2 attached to the leaf node 11–00–11–00 are 0–11–00–11–00 and
1–11–00–11–00, respectively.
In the above addressing scheme, Xs (don’t cares) are used in the addresses
of stem and root nodes. As all the nodes have different addresses, the RN and
CN are represented using 4-bit numbers (0 = 01; 1 = 10; X = 11). Therefore, each
node has 12-bit address; for example, node address 10–00–XX–10 becomes
1001–00–1111–10. Therefore, in 4 × 4 MoT, each core has a 13-bit address. The
bit size required for addressing a core in M × N MoT is given below:
Core-ID = 1 bit
Row number = 2log 2 M bit
Column level = log 2 (log 2 2M ) bit
Column number = 2log 2 N bit
Row level = log 2 (log 2 2N ) bit
2.4.1.1.2 Routing Algorithm
The routing algorithm follows the deterministic approach. The algorithm
ensures that the packet will reach its destination always through a specified
shortest path. Thus, the proposed network is always livelock free. The following abbreviations have been used to describe the algorithm:
• addr (curr) denotes the address of the current node.
• addr (dest) denotes the address of the destination node.
Each leaf and stem router executes the same algorithm as proposed below.
In root routers, no routing is performed and routers are replaced by first-in
first-out (FIFOs).