Interconnection Networks in Network-on-Chip
27
[2
1
× S
2
2
b + ( × N ) × ( 2 log
2
2 2 )]. The following equation shows the summation
of minimum distances to all the destination cores from a specific source core
in a (2
2
× N) MoT:
S
( 2
2
MoT
× N ) = S MoT ( 2
1
× N ) + ⎡ 2
1
× S b + 2
2
× ( 2 log 2
2
) × N ⎤ (2.6)
⎣
2
⎦
Similarly, Equations 2.7 and 2.8 show the summation of minimum distances
to all the destination cores from a specific source core in (2
3
× N) and (2
4
× N)
MoTs, respectively:
S MoT ( 2
3
× N ) = S MoT ( 2
2
× N ) + ⎡ 2
2
× S + 2
3
b
× ( 2 log
3
2 2 ) N ⎤
(2.7)
⎣
⎦
S
4
3
3
MoT ( 2 × N ) = S MoT ( 2 × N ) + ⎡ 2 × S b + 2
4
× ( 2 log 2
4
) N ⎤
(2.8)
⎣
2
⎦
In general, a ( 2
log2 M
× N) MoT can be split into two [2
(log2 M)−1
× N] MoTs where
each [2
(log2 M) −1
× N] MoT consists of 2
(log2 M )−1 row-wise binary trees. The
depth of each column tree of the ( 2
log2 M
× N) MoT is log 2 (2
log2 M ). Thus, the
summation of minimum distances of (2
log2 M
× N) cores lying in the second
[2
(log2 M) −1
× N] MoT from any specific core of the first [2
(log2 M)−1
× N] MoT is
[2
(log2 M)−1
× S + (2
log2 M
× N)]×[2 log (2
log2 M )]. For a ( 2
log2 M
b
2
× N) MoT, the summation of minimum distances to all the destination cores from a specific
source core can be written as
S
log2 M
MoT ( 2 × N ) = S
(
o ⎡
1
M T 2
log
× N ⎤ +
⎣
2 M)−
⎦
{
(2.9)
(
2
log2 M)−1 × S + ( 2
log2 M
× N N ) × ⎡
b
2 log
⎣
( 2
log2 M
) ⎤
2
⎦ }
After simplification, the above equation becomes
log2 M
S
2
× N = S (M × N)= 4MN × log (MN)− 8MN + 4(M + N)⎤ ⎦ (2.10)
MoT (
) MoT
⎡ ⎣
2
It is noticeable that due to the symmetrical structure of MoT topology, the
summation of minimum distances to all the destination cores from any
source core is always the same. Hence, the average distance of M × N MoT
network connecting C number of cores can be written as
⎡ ⎣ 4MN × log 2 (MN) − 8MN + 4(M + N)⎤ ⎦
D MoT (M × N ) =
(2.11)
C − 1
In general, for an M × (C/2M) MoT network (where M is the number of row
trees and C is the total number of cores attached) having two cores connected to each leaf node, the number of directed edges (Equation 2.4) and the
average distance (Equation 2.11), respectively, can be written as