O'Reilly logo

Principles and Practices of Interconnection Networks by Brian Patrick Towles, William James Dally

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

116 CHAPTER 6 Non-Blocking Networks
that contains no other system components tends to be pin limited. That is, its size
is limited by W
n
, the number of pins on the chip, rather than the area required to
implement the crossbar on the chip. In this case, the effective cost of the crossbar is
linear up to the largest crossbar that can be packaged on a single chip. If, however,
a crossbar fits on a chip but also connects together other components on that same
chip, then its quadratic area becomes important, since it might no longer be pin
limited. Once a crossbar must be implemented with multiple chips, as illustrated in
Figure 6.4, then its cost increases quadratically with size.
6.3 Clos Networks
6.3.1 Structure and Properties of Clos Networks
A Clos network is a three-stage
5
network in which each stage is composed of a num-
ber of crossbar switches. A symmetric Clos is characterized by a triple, (m, n, r) where
m is the number of middle-stage switches, n is the number of input (output) ports
on each input (output) switch, and r is the number of input and output switches.
6
In
a Clos network, each middle stage switch has one input link from every input switch
and one output link to every output switch. Thus, the r input switches are n × m
crossbars to connect n input ports to m middle switches, the m middle switches are
r × r crossbars to connect r input switches to r output switches, and the r output
switches are m × n crossbars to connect m middle switches to n output ports. For
example, a (3,3,4) Clos network is shown in Figure 6.5 and a (5,3,4) Clos network
is shown in Figure 6.6. In referring to the input and output ports of Clos networks,
we denote port p of switch s as s.p.
It is often valuable to visualize the all-to-all connection between stages of the
Clos network in three dimensions, as shown in Figure 6.7. The input and output
switches can be thought of as moving the traffic horizontally to and from the vertical
middle switches. The middle switches move the traffic vertically from a horizontal
input switch to a horizontal output switch. This crossed arrangement is also a useful
way to package small Clos networks, as it keeps all of the connections between the
stages short.
The properties of an (m, n, r) Clos network with N = rn terminals follow from
the topology. All three-stage Clos networks have H = 4. The network can be bisected
either horizontally or vertically, as drawn in Figure 6.7, giving a bisection of B
C
= mr
for the horizontal cut through the middle switches or B
C
= 2nr = 2N for the vertical
cut through the input and output switches. In practice, most networks are packaged
by co-locating the input and output switches and cutting all of the inter-switch
5. Clos networks with any odd number of stages can be derived recursively from the three-stage Clos by
replacing the switches of the middle stage with three-stage Clos networks.
6. In some situations, asymmetric Clos networks are used, in which r and n differ between the input and
output stages. Asymmetric Clos networks are described by a 5-tuple (m, n
i
,r
i
,n
o
,r
o
).
6.3 Clos Networks 117
n = 3 ports
per switch
middle
switch 1
4x4
m=3 rxr
middle switches
middle
switch 2
4x4
middle
switch 3
4x4
input
switch 1
3x3
1.1
1.2
1.3
r=4 nxm
input switches
input
switch 2
3x3
2.1
2.2
2.3
input
switch 3
3x3
3.1
3.2
3.3
input
switch 4
3x3
4.1
4.2
4.3
output
switch 1
3x3
1.1
1.2
1.3
output
switch 2
3x3
2.1
2.2
2.3
output
switch 3
3x3
3.1
3.2
3.3
output
switch 4
3x3
4.1
4.2
4.3
r=4 mxn
output switches
Figure 6.5 An (m = 3,n = 3,r = 4) symmetric Clos network has r = 4 n ×m input switches, m = 3 r ×r
middle-stage switches, and r = 4 m × n output switches. All switches are crossbars.
n = 3 ports
per switch
middle
switch 2
4x4
m=5rxr
middle switches
middle
switch 3
4x4
middle
switch 4
4x4
1.1
1.2
1.3
r =4nxm
input switches
2.1
2.2
2.3
3.1
3.2
3.3
4.1
4.2
4.3
1.1
1.2
1.3
r =4 mxn
output switches
2.1
2.2
2.3
3.1
3.2
3.3
4.1
4.2
4.3
middle
switch 1
4x4
middle
switch 5
4x4
input
switch 1
3x5
input
switch 2
3x5
input
switch 3
3x5
input
switch 4
3x5
output
switch 1
5x3
output
switch 2
5x3
output
switch 3
5x3
output
switch 4
5x3
Figure 6.6 A (5,3,4) Clos network. This network is strictly non-blocking for unicast traffic.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required