S
S
S
S
S
R
R
R
R
S
S
S
S
S
S
S
S
R
R
R
R
S
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
S
S
26
Network-on-Chip
a specific source core in a complete binary tree having two cores in each leaf
level router can be written as
0
2 N )
S ⎡
1
2
3
(log
⎤
b = 0.2 + 2.2 + 4.2 + 6. 2 + + ( 2 log 2 N × 2
⎣
)
⎦
(2.4)
= ⎡ ⎣ 4N log 2 N N − 4(N − 1)⎤ ⎦
A (2
1
× N) MoT consists of two row-wise binary trees of depth log 2 N and N
column-wise binary trees of depth 1 (which can be written as log 2
1
2
. Each
row tree consists of (2
1
× N) cores. Thus, the summation of distances of
(2
1
× N) cores lying in the second row tree from any specific core of the first
row tree is [2
0
× S b + (2
1
× N ) × ( 2 log
1
2 2 )]. Hence, the summation of minimum
distances to all the destination cores from a specific source core in a (2
1
× N)
MoT can be written as
S
1
0
MoT ( 2 × N ) = S b + ⎡ 2 × S
⎣
b + ( 2
1
× N ) × ( 2 log 2
1
) ⎤
(2.5)
2
⎦
In the same way, a (2
2
× N) MoT can be split into two (2
1
× N) MoTs (as shown
in Figure 2.14) where each (2
1
× N) MoT consists of 2
1 row-wise binary trees.
The depth of each column tree of (2
2
× N) MoT is 2 (which can be written as log 2
2
2
. Thus, the summation of distances of (2
2
× N) cores lying
in the second (2
1
× N) MoT (shown as dotted box in the figure) from any
specific core of the first (2
1
× N) MoT (shown as firm box in the figure) is
Figure 2.14
Splitting of a (2
2 × 2
2 ) MoT into two (2
1 × 2
2 ) MoTs.