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

134 CHAPTER 6 Non-Blocking Networks
routing problems for each of the n three-stage Clos networks used as middle switches.
We then move inward and apply the same procedure to each of the Clos networks
used as a middle switch. For each of the n middle switches, we route the calls assigned
to this (n, n, n) Clos middle switch using the algorithm of Figure 6.11. This assigns
each call to one of the n crossbars in this Clos (one of n
2
middle-stage crossbars
overall).
The five-stage Clos network of Figure 6.17 is rearrangeably non-blocking for
unicast traffic. The outer (2,2,4) network is rearrangeable and thus can assign each
call to one of the two middle stage switches. Also, each of the (2,2,2) middle stage
networks are rearrangeable, and thus can route all of the calls assigned to them.
For a five-stage Clos network to be strictly non-blocking for unicast traffic, ex-
pansion is required in each input stage. For example, a strictly non-blocking network
comparable to the network of Figure 6.17 would require a (3,2,4) outer network
with four 2 × 3 switches in the input stage, four 3 × 2 switches in the output stage,
and three 4 × 4 middle stage subnetworks. To be strictly non-blocking, each of the
four middle stage subnetworks must be realized as (3,2,2) Clos networks with two
2×3 input switches, two 3×2 output switches, and three 2×2 middle switches. The
five-stage strictly non-blocking network has nine 2 × 2 switches down its midpoint,
as opposed to four 2 × 2 switches for the five-stage rearrangeable network. This is
because expansion is needed in both the first and second stages. If we use a factor
of two expansion in each input stage,
10
a2n + 1-stage strictly non-blocking Clos
network requires a total expansion of 2
n
.
To route multicast traffic in a Clos network that has more than three stages, one
must decide where to perform the fanout. Fanout can be performed at any stage
of the network. A complete discussion of this problem is beyond the scope of this
book. However, when routing a fanout of f multicast call on a 2n + 1-stage Clos
network, a good heuristic is to perform a fanout of f
1
n+1
on each of the first n + 1
stages.
6.4 Beneˇs Networks
A Clos network constructed from 2 × 2 switches —for example, the network of
Figure 6.17 is also called a Beneˇs network. These networks are notable because
they require the minimum number of crosspoints to connect N = 2
i
ports in a
rearrangeably non-blocking manner. As discussed above, to connect N = 2
i
ports
with 2 × 2 switches requires 2i 1 stages of 2
i1
2 × 2 switches. This gives a total
of (2i 1)2
i1
switches. With 4 crosspoints per 2 × 2 switch, the total number of
crosspoints is (2i 1)2
i+1
.
The astute reader will have noticed that a 2i1 stage Beneˇs network is equivalent
to two 2-ary i-fly networks back-to-back with the abutting stages fused. Very often,
Beneˇs networks and other multistage Clos networks are implemented by folding the
10. Strictly speaking, the expansion required in each stage is
2n1
n
, which is slightly less than 2.
6.5 Sorting Networks 135
network along this middle stage of switches. In a 2i 1-stage folded Clos network,
stages j and 2i j are co-located and share common packaging. This arrangement
takes advantage of the symmetry of the network to reduce wiring complexity.
6.5 Sorting Networks
An N -input sorting network accepts a set of N records tagged with unique sorting
keys on its N input terminals and outputs these records with the keys in sorted order
on its N output terminals. A sorting network can be used as a non-blocking network
1 3 4 5
(a) Batcher bitonic sort
(b) Bitonic sorting network
26
Figure 6.18 Batcher bitonic sorting network. (a) Batcher bitonic sort operates by treating two sorted se-
quences of length 2
i
as a bitonic sequence of length 2
i+1
and then merging this into a sorted
sequence of length 2
i+1
. (b) A sorting network that realizes this sort is constructed from 2 ×2
switches that route based on the relative values of the sorting keys.

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