28
Network-on-Chip
⎛
⎡ C
⎤ ⎞
⎡ C
⎤
⎛
⎡ C
⎤ ⎞
E MoT ⎜ M
×
⎢
⎟ =
8
⎥
M
×
− 4
⎢
⎜ M
⎥
+
⎢
⎥ ⎟
⎝
⎢ 2
M
⎥ ⎠
⎢ 2
M
⎥
⎝
⎢ 2
M
⎥ ⎠
⎡ 4M × ⎡ ⎢ C/2M⎤ ⎥ × log 2 ( M × ⎡ ⎢ C/2M ⎥ ⎤) − ⎤
⎢
⎥
⎢
⎥
⎛
M
⎡ C ⎤ ⎞ ⎢ 8 × ⎡ ⎡ ⎢ C/2M⎤
⎣
⎥ + 4 ( M + ⎡ ⎢ C/2M⎤ ⎥ ) ⎥ ⎦
D MoT ⎜ M × ⎢
⎟ =
⎥
⎝
⎢ 2M ⎥ ⎠
(C − 1)
Theoretically, E/D is a good indicator for the throughput of a network, without considering contention among packets (Decina et al. 1991). It can be
shown that the value of (E MoT D MoT ) reaches its maximum and D MoT reaches
its minimum when the condition M = ⌈C/2M⌉ holds. This implies that the
MoT network will show maximum throughput and minimum latency in a
congestion-free environment when the number of row trees and that of column trees are same.
Similarly, for an M = ⌈C/M⌉ mesh network (where M is the number of
nodes in each row and C is the total number of cores attached in the network), the average distance (D) and the number of directed edges (E), respectively, can be written as follows (Pavlidis and Friedman 2007):
( M + ⎡ ⎢ C M⎤ ⎥ )
D =
(2.12)
3
⎪ ⎧
⎛ ⎡ C
⎤ ⎞ ⎡ C
⎤
⎫ ⎪
E
=
2
×
⎨ M
×
⎜
− 1
⎟ +
× M
⎥ ( −
1)
⎢ ⎥
⎬
(2.13)
⎢
⎩
⎪
⎝
⎢ M
⎥ ⎠
⎢ M
⎥
⎪ ⎭
⎛ E ⎞
⎛
6C
⎞
⎜ ⎟ = 2 × ⎜
− 3 ⎟
(2.14)
D
⎜
⎝ ⎠
M
⎝ + ⎡C M ⎥ ⎤
⎟
⎢
⎠
It can be shown that for a mesh network having a single core connected
to each router, the value of (E/D) reaches its maximum and the value of D
reaches its minimum when the condition M = ⌈C/M⌉ holds. This signifies
that a square mesh network with an equal number of row and column trees
is expected to show the best performance. The performance will degrade as
the network becomes more and more rectangular in nature. Thus, to connect
2 n cores, where n is odd, a mesh network that connects a single core to each
router may not be the ideal choice to the NoC designers due to its rectangular
shape. This statement is also true for a mesh network connecting two cores
to each router for 2 n cores, where n is even.
Pande et al. (2005) compared a set of network topologies with 256 cores
in terms of throughput, latency, energy consumption, and area overhead.
They have reported that SPIN and octagon networks have very high
Network-on-Chip
⎛
⎡ C
⎤ ⎞
⎡ C
⎤
⎛
⎡ C
⎤ ⎞
E MoT ⎜ M
×
⎢
⎟ =
8
⎥
M
×
− 4
⎢
⎜ M
⎥
+
⎢
⎥ ⎟
⎝
⎢ 2
M
⎥ ⎠
⎢ 2
M
⎥
⎝
⎢ 2
M
⎥ ⎠
⎡ 4M × ⎡ ⎢ C/2M⎤ ⎥ × log 2 ( M × ⎡ ⎢ C/2M ⎥ ⎤) − ⎤
⎢
⎥
⎢
⎥
⎛
M
⎡ C ⎤ ⎞ ⎢ 8 × ⎡ ⎡ ⎢ C/2M⎤
⎣
⎥ + 4 ( M + ⎡ ⎢ C/2M⎤ ⎥ ) ⎥ ⎦
D MoT ⎜ M × ⎢
⎟ =
⎥
⎝
⎢ 2M ⎥ ⎠
(C − 1)
Theoretically, E/D is a good indicator for the throughput of a network, without considering contention among packets (Decina et al. 1991). It can be
shown that the value of (E MoT D MoT ) reaches its maximum and D MoT reaches
its minimum when the condition M = ⌈C/2M⌉ holds. This implies that the
MoT network will show maximum throughput and minimum latency in a
congestion-free environment when the number of row trees and that of column trees are same.
Similarly, for an M = ⌈C/M⌉ mesh network (where M is the number of
nodes in each row and C is the total number of cores attached in the network), the average distance (D) and the number of directed edges (E), respectively, can be written as follows (Pavlidis and Friedman 2007):
( M + ⎡ ⎢ C M⎤ ⎥ )
D =
(2.12)
3
⎪ ⎧
⎛ ⎡ C
⎤ ⎞ ⎡ C
⎤
⎫ ⎪
E
=
2
×
⎨ M
×
⎜
− 1
⎟ +
× M
⎥ ( −
1)
⎢ ⎥
⎬
(2.13)
⎢
⎩
⎪
⎝
⎢ M
⎥ ⎠
⎢ M
⎥
⎪ ⎭
⎛ E ⎞
⎛
6C
⎞
⎜ ⎟ = 2 × ⎜
− 3 ⎟
(2.14)
D
⎜
⎝ ⎠
M
⎝ + ⎡C M ⎥ ⎤
⎟
⎢
⎠
It can be shown that for a mesh network having a single core connected
to each router, the value of (E/D) reaches its maximum and the value of D
reaches its minimum when the condition M = ⌈C/M⌉ holds. This signifies
that a square mesh network with an equal number of row and column trees
is expected to show the best performance. The performance will degrade as
the network becomes more and more rectangular in nature. Thus, to connect
2 n cores, where n is odd, a mesh network that connects a single core to each
router may not be the ideal choice to the NoC designers due to its rectangular
shape. This statement is also true for a mesh network connecting two cores
to each router for 2 n cores, where n is even.
Pande et al. (2005) compared a set of network topologies with 256 cores
in terms of throughput, latency, energy consumption, and area overhead.
They have reported that SPIN and octagon networks have very high