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