Networking Reference
In-Depth Information
Mesh and torus networks (Figure 3.1 ) provide a convenient starting point to discuss topology
tradeoffs. Starting with the observation that each router in a k -ary n -mesh, as shown in Figure
3.1 (a), requires only three ports; one port connects to its neighboring node to the left, another to its
right neighbor, and one port (not shown) connects the router to the processor. Nodes that lie along
the edge of a mesh, for example nodes 0 and 7 in Figure 3.1 (a), require one less port. The same
applies to k -ary n -cube (torus) networks. In general, the number of input and output ports, or radix
of each router is given by Equation 3.2 . The term “radix” is often used to describe both the number
of input and output ports on the router, and the size or number of nodes in each dimension of the
network.
r =
2 n +
1
(3.2)
The number of dimensions ( n ) in a mesh or torus network is limited by practical packaging
constraints with typical values of n =2 or n =3. Since n is fixed we vary the radix ( k ) to increase the
size of the network. For example, to scale the network in Figure 3.2 a from 32 nodes to 64 nodes, we
increase the radix of the y dimension from 4 to 8 as shown in Figure 3.2 b.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
0
1
2
3
4
5
6
7
32
33
34
35
36
37
38
39
8
40
9
10
11
12
13
14
15
41
42
43
44
45
46
47
16
17
18
19
20
21
22
23
48
49
50
51
52
53
54
55
24
25
26
27
28
29
30
31
56
57
58
59
60
61
62
63
(a) (8,4)-ary 2-mesh
(b) 8-ary 2-mesh.
Figure 3.2: Irregular (a) and regular (b) mesh networks.
Since a binary hypercube (Figure 3.4 ) has a fixed radix ( k =2), we scale the number of dimen-
sions ( n ) to increase its size. The number of dimensions in a system of size N is simply n = lg 2 (N)
from Equation 3.1 .
r = n + 1 = lg 2 (N) + 1
(3.3)
As a result, hypercube networks require a router with more ports (Equation 3.3 ) than a mesh or
torus. For example, a 512 node 3-D torus ( n =3) requires seven router ports, but a hypercube requires
n = lg 2 ( 512 ) +1=10ports.Itisuseful to note, an n -dimension binary hypercube is isomorphic to
Search MirCeyron ::




Custom Search