Minimum Distance
Number of Cores
0
2 0
2
2 1
4
2 2
6
2 3
. . .
. . .
. . .
. . .
. . .
. . .
(log N )
2log 2 N
2
2
25
Interconnection Networks in Network-on-Chip
latency of a network is proportional to the average distance of the network.
Thus, for any topology, knowledge of the number of directed edges (E) and
the average distance (D) are equally important as its diameter and bisection
width. Kundu et al. (2012) presented a general formulation to find both of these
parameters for an M × N MoT structure having two cores connected to each
leaf level node, where each row tree and column tree is a complete binary tree.
This formulation has been presented in Sections 2.2.1 and 2.2.2.
2.2.1 Number of edges
The number of edges in each complete binary tree having k number of leaf
nodes is (2k − 2) (West 2002). In an M × N MoT topology, each row tree and
column tree is a complete binary tree having N and M leaf nodes, respectively. Thus, the number of edges É of an undirected MoT graph can be formulated as follows:
É = [M(2N − 2) + N(2M − 2)] = 4MN − 2(M + N)
(2.2)
As in the MoT structure, adjacent routers are connected by two unidirectional opposite edges, the number of directed edges will be
E MoT (M × N) = 2É = 8MN – 4(M + N)
(2.3)
2.2.2 Average Distance
The average distance of a network is the average of the minimum distances
(in hop count) between all pairs of IP cores. In a complete binary tree having
N number of leaf nodes with two cores connected to each router, the distribution of destination cores from a specific source core is shown in Table 2.1.
Thus, the summation of minimum distances to all the destination cores from
TABLe 2.1
Distribution of Destination Cores from a Specific Core
in a Complete Binary Tree