log2 M
0
(log2 M)−1
0
S M (2
× N × 2 ) = S M (2
× N × 2 )
(11.5)
(log2 M)−1
log2 M
log2 M
+ 2
× S + (2
× N N)× ⎡
⎣ 2 log (2
)
{
b
2
⎤
⎦ }
328
Network-on-Chip
at distance 4, eight cores at distance 6, and so on as depicted in Chapter 2.
The summation of minimum distances to all the destination cores from a
specific source core in a complete binary tree, noted in Equation 2.4, is reproduced in Equation 11.2 for the sake of continuity.
S b = [4N log 2 N − 4(N − 1)]
(11.2)
A (2
1
× N × 2
0 ) 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 2
1
). Each
row tree consists of (2
1
× N) cores. Thus, the summation of minimum distances of (2
1
× N) cores lying in the second row tree from any specific core of
0
1
1
the first row tree can be written as ⎡
⎣ 2 × S b + (2 × N × 2
2
⎤
⎦
) ( log 2 ) . Hence, the
summation of minimum distances to all the destination cores from a specific
source core in a (2
1
× N × 2
0 ) MoT is
1
0
0
1
1
S M (2 × N × 2 ) =S b + 2 × S b + (2 × N) (2 log 2 2 )
(11.3)
×
2
0
1
0
In the same way, a (2 × N × 2 ) MoT consists of two (2 × N × 2 ) MoTs where
each (2
1
× N × 2
0 ) MoT contains 2
1 row-wise binary trees. The depth of each
column tree of (2
2
× N × 2
0 ) MoT is 2 (which can be written as log 2 2
2 ). Thus,
the summation of minimum distances of (2
1
× N) cores lying in the second
1
0
1
0
(2 × N × 2 ) MoT from any specific core of the first (2 × N × 2 ) MoT is equal
1
2
2
) ( log 2 ⎤
⎦ . Thus, the summation of minimum distances
to ⎡
⎣ 2 × S b + (2 × N × 2
2 )
to all the destination cores from a specific source core in (2
2
× N × 2
0 ) MoT is
as follows:
2
0
1
0
1
2
2
S M (2 × N × 2 ) = S M (2 × N × 2 ) + 2 × S + (2 × N) (2 log 2
(11.4)
b
×
2 )
2
log2 M
0
(log2 M) 1
0
In general, a (
× N × 2 ) MoT can be split into two (2
−
× N × 2 ) MoTs,
(log2 M)−1
×
0
(log2 M)−1
where each (2
N × 2 ) MoT consists of 2
row-wise binary trees.
2
log2 M
0
log2 M
The depth of each column tree of (
× N × 2 ) MoT is log (2
). Thus, the
2
(log2 M)
summation of minimum distances of ( 2
× N ) cores lying in the second
(log2 M)−1
×
0
(log2 M)−1
×
0
(2
N × 2 ) MoT from any specific core of the first (2
N × 2 )
(log2 M) 1
log2 M
log2 M
MoT is equal to {2
−
× S b + (2
× N × 2
2 2
)]}
) [ log (
. Thus for a
2
log2 M
0
(
× N × 2 ) MoT, the summation of minimum distances to all the destination cores from a specific source core can be written as
After simplification, the above equation becomes
S M (M × N × 2
0 ) = ⎡ ⎣ 4 × M × N × log 2 (M × N) − ×
8 M × N + 4(M + N)⎤ ⎦
(11.6)
While considering the third dimension, a ( M × N × 2
1 ) MoT can be split
into two (M × N × 2
0 ) MoTs, where each (M × N × 2
0 ) MoT is connected by
0
(log2 M)−1
0
S M (2
× N × 2 ) = S M (2
× N × 2 )
(11.5)
(log2 M)−1
log2 M
log2 M
+ 2
× S + (2
× N N)× ⎡
⎣ 2 log (2
)
{
b
2
⎤
⎦ }
328
Network-on-Chip
at distance 4, eight cores at distance 6, and so on as depicted in Chapter 2.
The summation of minimum distances to all the destination cores from a
specific source core in a complete binary tree, noted in Equation 2.4, is reproduced in Equation 11.2 for the sake of continuity.
S b = [4N log 2 N − 4(N − 1)]
(11.2)
A (2
1
× N × 2
0 ) 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 2
1
). Each
row tree consists of (2
1
× N) cores. Thus, the summation of minimum distances of (2
1
× N) cores lying in the second row tree from any specific core of
0
1
1
the first row tree can be written as ⎡
⎣ 2 × S b + (2 × N × 2
2
⎤
⎦
) ( log 2 ) . Hence, the
summation of minimum distances to all the destination cores from a specific
source core in a (2
1
× N × 2
0 ) MoT is
1
0
0
1
1
S M (2 × N × 2 ) =S b + 2 × S b + (2 × N) (2 log 2 2 )
(11.3)
×
2
0
1
0
In the same way, a (2 × N × 2 ) MoT consists of two (2 × N × 2 ) MoTs where
each (2
1
× N × 2
0 ) MoT contains 2
1 row-wise binary trees. The depth of each
column tree of (2
2
× N × 2
0 ) MoT is 2 (which can be written as log 2 2
2 ). Thus,
the summation of minimum distances of (2
1
× N) cores lying in the second
1
0
1
0
(2 × N × 2 ) MoT from any specific core of the first (2 × N × 2 ) MoT is equal
1
2
2
) ( log 2 ⎤
⎦ . Thus, the summation of minimum distances
to ⎡
⎣ 2 × S b + (2 × N × 2
2 )
to all the destination cores from a specific source core in (2
2
× N × 2
0 ) MoT is
as follows:
2
0
1
0
1
2
2
S M (2 × N × 2 ) = S M (2 × N × 2 ) + 2 × S + (2 × N) (2 log 2
(11.4)
b
×
2 )
2
log2 M
0
(log2 M) 1
0
In general, a (
× N × 2 ) MoT can be split into two (2
−
× N × 2 ) MoTs,
(log2 M)−1
×
0
(log2 M)−1
where each (2
N × 2 ) MoT consists of 2
row-wise binary trees.
2
log2 M
0
log2 M
The depth of each column tree of (
× N × 2 ) MoT is log (2
). Thus, the
2
(log2 M)
summation of minimum distances of ( 2
× N ) cores lying in the second
(log2 M)−1
×
0
(log2 M)−1
×
0
(2
N × 2 ) MoT from any specific core of the first (2
N × 2 )
(log2 M) 1
log2 M
log2 M
MoT is equal to {2
−
× S b + (2
× N × 2
2 2
)]}
) [ log (
. Thus for a
2
log2 M
0
(
× N × 2 ) MoT, the summation of minimum distances to all the destination cores from a specific source core can be written as
After simplification, the above equation becomes
S M (M × N × 2
0 ) = ⎡ ⎣ 4 × M × N × log 2 (M × N) − ×
8 M × N + 4(M + N)⎤ ⎦
(11.6)
While considering the third dimension, a ( M × N × 2
1 ) MoT can be split
into two (M × N × 2
0 ) MoTs, where each (M × N × 2
0 ) MoT is connected by