This page was generated using an imperfect translator. Text may be poorly positioned and mathematics will be barely readable. Illustrations will not show at all. If possible, view the PostScript versions of these notes.
13-1 *
* 13-1
Recursive Decomposition of The Clos Network
Result is a much-lower-cost rearrangeable network.
In contrast, the network obtained when recursive decomposition
was applied to the Omega network had the same properties.
First, a scalable Clos network:
ae
(3; (m; mn1 ; m); (mn1 ; m; mn1 ); T; T )n ; if n > 1;
(1; m; 1; T; T )1 ; if n = 1.
For scalable Clos networks with n > 1:
Center-stage cells are recursive.
Other cells are atomic.
13-1 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli1*
*9. 13-1
13-2 *
* 13-2
Two Methods To Compute Cost
The powerful way: write recurrence equations:
Let C(n; m) be cost of network of size n using m m cells.
C(1; m) = m2 xp
C(n; m) = m2 mn1 xp +mC(n 1; m) + m2 mn1 xp
= 2mn+1 xp +mC(n 1; m)
Equations like this can easily (more or less) be solved in closed
form.
The easy? clever? way:
Observation: every stage consists of mn1 cells.
Number of stages: 2n 1.
C(n; m) = m2 mn1 (2n 1) xp
= mn+1 (2n 1) xp
Substituting N = mn and n = log m N :
C(N; m) = mN (2 log m N 1) xp
Cost is almost twice the cost of an omega network.
But, it is much less than non-recursive Clos network.
And it's still a permutation network.
13-2 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli1*
*9. 13-2
13-3 *
* 13-3
The Benes Network
Named after V. Benes, described in a 1962 BSTJ paper.
It is a recursively decomposed (3; (2; 2n1 ; 2); (2n1 ; 2; 2n1 ); T; T ) Clos
network.
Routing:
Use looping algorithm several times:
- We're finished if network consists of a single 2 2 crossbar.
- Otherwise, use looping algorithm, remembering that this
is a recursive network.
Result is settings for first and last stages, and
permutations for two center-stage recursive cells.
- Route each center-stage recursive cell using this procedure.
13-3 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli1*
*9. 13-3
13-4 *
* 13-4
Routing Example
P = 05 115 213 37 43 50 68 171 89 96 1012 111 1210 132 1414 1*
*54
Routing Example, Continued
13-4 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli1*
*9. 13-4
13-5 *
* 13-5
P = 05 115 213 37 43 50 68 171 89 96 1012 111 1210 132 1414 1*
*54
13-5 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli1*
*9. 13-5
13-6 *
* 13-6
Routing Example, Continued.
P1 = 02 16 21 34 43 50 65 77
P2 = 185 191 108 1113 1212 1314 149 1510
13-6 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli1*
*9. 13-6
13-7 *
* 13-7
Routing Example, Finished.
P = 05 115 213 37 43 50 68 171 89 96 1012 111 1210 132 1414 1*
*54
13-7 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli1*
*9. 13-7
13-8 *
* 13-8
Minimum Cost Permutation Networks
Lower Bound on Permutation Network Cost
Result due to Shannon, BSTJ 1950.
This is similar to proof that Omega networks are not permuta-
tion networks.
Idea: Compare amount of information to code a permutation to amount
of information in Benes network state.
This is sort of log 2 [ what we did with the omega network].
Amount of information can be measured in number of bits.
Amount of information to code a permutation I(N ) = log 2 N !.
Using Sterling's approximation:
I(N ) = log 2 N !
p _______ N
= log 2 2ssN N_____eN
= 1_2log2 2ssN + log 2 N N log 2 eN
n ) (2n )
= 1_2log2 2ss2n + log 2(2n )(2 log 2 e
= 1_2log2 ss + n_+_1___2log2 2 + n2n log 2 2 2n log 2 e
= 1_2log2 ss + n_+_1___2+ n2n 2n log 2 e
= n2n 2n log 2 e + n_+_1___2+ 1_2log 2 ss
13-8 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli1*
*9. 13-8
13-9 *
* 13-9
The number of bits to code a Benes network state.
(When routing permutations) each cell can be in two states:
Identity and transpose.
So state of each cell can be coded with one bit.
The number of bits then is equal to the number of cells:
I(Benes ) = 2n1 (2n 1) = n2n 2n1
I(N ) = n2n 2n log 2 e + n_+_1___2+ 1_2log 2 ss
The highest order terms of the two expressions are equal.
Therefore, the Benes network is asymptotically optimal.
(Which is not quite as good as being optimal.)
13-9 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli1*
*9. 13-9
13-10 *
* 13-10
Correspondence Between Clos and Benes Networks
Cells in Benes network can be mapped to Clos in a many-to-one fash-
ion.
This mapping reveals important properties.
Used as basis for routing algorithm.
Used to determine which connection assignments the input- and
output-stage cells need to realize.
13-10 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli*
*19. 13-10
13-11 *
* 13-11
Example: Using Correspondence For Routing
Problem: How to route a (3; (2 ; 2 ; 2 ); (2 ; 2 ; 2 ); T; T ) Clos net-
work, > 1?
Solution: Route a ( + ; 2; 2+1 ; T; T ) Benes network: : :
: :f:ind Clos-network cell settings based on Benes-network cell settings.
P = 05 115 213 37 43 50 68 171 89 96 1012 111 1210 132 1414 *
*154
ssh0; 0i = 0 1 2 3 ssh0; 1i = 0 1 2 3 ssh0; 2i = 0 1 2 *
* 3
ssh0; 3i = 0 1 2 3 ssh1; 0i = 0 1 2 3 ssh1; 1i = 0 1 2 *
* 3
ssh1; 2i = 0 1 2 3 ssh1; 3i = 0 1 2 3 ssh2; 0i = 0 1 2 *
* 3
ssh2; 1i = 0 1 2 3 ssh2; 2i = 0 1 2 3 ssh2; 3i = 0 1 2 *
* 3
13-11 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli*
*19. 13-11
13-12 *
* 13-12
Correspondence Between Benes and Clos, Formally
First, Models of Benes and Clos Networks
Benes Network LGM
I = f hI; ji j j 2 h2n i g O = f hO; ii j i 2 h2n i g
n1 ff
V = I [ O [ f hx; ii j x 2 h2n 1i ; i 2 2 g
ae oe
E = (hI; ii ; h0; i0i) j i 2 h2n i ; i0 = i_2 [
n1 ff
f (hx; ii ; hx + 1; i0i ) j x 2 hn 1i ; i 2 2 ; d 2 f0; 1g;
i0 = i(n2:n1x) d i(n2x:1) *
* g[
n1 ff
f(hx; ii ; hx + 1; i0i ) j x0 2 hn 1i ; x = x0 + n 1; i 2 2 ;
d 2 f0; 1g; i0 = i(n2:xn+2) i(xn:0) *
* d g[
n1 ff 0
f (h2n 2; ii ; hO; i0i ) j i 2 2 ; d 2 f0; 1g; i = 2i + d g
Clos Network LGM
I = f hI; ji j j 2 hmki g O = f hO; ii j i 2 hmki g
V = I [ O [ f hx; ii j x 2 f0; 2g; i 2 hki g [ f h1; ii j i 2 hmi g
ae oe
E = (hI; ii ; h0; i0i) j i 2 hmki ; i0 = _i_m [
f (h0; ii ; h1; i0i) j i 2 hki ; i0 2 hmi g[
f (h1; ii ; h2; i0i) j i 2 hmi ; i0 2 hki g[
f (h2; ii ; hO; i0i ) j i 2 hki ; d 2 hmi ; i0 = im + d g
13-12 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli*
*19. 13-12
13-13 *
* 13-13
Mapping Function
This will not be a bijective map (as was used for equivalence).
Instead, several Benes-network nodes (cells) will be mapped to a single
Clos-network cell.
Input and output labels do not change:
f (hI; ii ) = hI; ii ; f (hO; ii ) = hO; ii
For cells, consider a path in the Benes and Clos networks.
Let all the cells in both networks be set to the identity state.
Consider stage 0 in the Clos network.
Consider stages 0 to 1 in the Benes network.
Consider a path from the same input through these stages in
both networks.
The cells on this path in the Benes network are mapped to the
cell on this path in the Clos network.
13-13 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli*
*19. 13-13
13-14 *
* 13-14
The equivalent mapping, mathematically:
Consider the first stage of both networks:
1 ff
f (h0; ii ) = 0; bi2 c
Consider the second stage of the Benes network:
2 n ff
f (h1; ii ) = 0; bi2 c mod 2
For stages 0 to 1:
1+x n ff
f (hx; ii ) = 0; bi2 c mod 2
for 0 x < .
A similar procedure is followed for the last stages:
1 ff
f (h2n 2; ii ) = 2; bi2 c
2 ff
f (h2n 3; ii ) = 2; bi2 mod 2 c
2n1x ff
f (hx; ii ) = 2; bi2 mod 2 c
for 2n 1 x < 2n 1.
The center-stages case is straightforward:
1n+ ff
f (hx; ii ) = 1; bi2 c
for x < 2n 1 .
13-14 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli*
*19. 13-14
13-15 *
* 13-15
Proof that the Mapped Benes Network is a Clos Network
Use the mapping function on the set of edges (from the Benes) network
LGM definition.
Eliminate self edges. (E.g., (hx; ii ; hx; ii )).
Compare the mapped-Benes edges to the Clos edges.
If they are equal, then the mapped Benes is a Clos network.
13-15 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli*
*19. 13-15
13-16 *
* 13-16
Let EY (x) denote the stage-x to stage-(x + 1) links in the Y 2 fB,C g
network, where I + 1 = 0 and the B and C networks are just
what you'd think they would be.
The input-to-first-stage edges obviously correspond:
ae oe
EB (I) = (hI; ii ; h0; i0i) j i 2 h2n i ; i0 = i_2
ff n ff
I; i(n1:0) ; 0; i(n1:1) j i 2 h2 i 2*
* EB (I)
ff ff n
f I; i(n1:0) ; f 0; i(n1:1) j i 2 h2 i 2 f (E*
*B (I))
ff ff n
= I; i(n1:0) ; 0; i(n1:) j i 2 h2 i 2*
* EC (I)
Benes-network links "inside" Clos network cells form self loops.
ff ff
x; i(n2:0) ; x + 1; i(n2:n1x) d i(n2x:1) 2 *
*EB (x)
ff ff
f x; i(n2:0) ; f x + 1; i(n2:n1x) d i(n2x:1)
2 f (EB*
* (x))
ff ff
= 0; i(nx2:x1) ; 0; i(nx2:x1)
ff
for 0 x < 1, where i 2 2n1 and d 2 h2i .
13-16 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli*
*19. 13-16
13-17 *
* 13-17
The stage- 1 to stage- edges in the two networks should corre-
spond:
ff ff
1; i(n2:0) ; ; i(n2:n) d i(n1:1)
2 EB ( *
* 1)
ff ff
f 1; i(n2:0) ; f ; i(n2:n) d i(n1:1)
2 f (EB ( 1*
*))
ff ff
= 0; i(n1:0) ; 1; i(n2:n) d 2 *
*EC (0)
ff
where i 2 2n1 and d 2 h2i .
Note that there is a one-to-one correspondence despite the fact that
edges for Clos network are specified differently.
Proof for the other network half is similar.
Use of Map for Routing
Start with connection assignment meant for Clos network.
Route this connection assignment on the Benes network.
Let (a; ff0)x be the stage-x link to which input a is routed.
Set input-stage crossbars using requests (a; ff00) where f (h; ff0i ) =<
1; ff00 >.
13-17 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli*
*19. 13-17
13-18 *
* 13-18
Clos-Network Input and Output Stage Cells.
We have seen the correspondence between Clos and Benes network
cells.
Only stages of Benes-network cells are mapped to a Clos network
input- or output-stage cell.
This means the Clos network input- and output-stage cells do not have
to be crossbars.
In fact, they are terminal equivalent to inverse baseline and baseline
networks.
These are omega networks with the input- or output-stage shu- e re-
moved.
13-18 EE 7725 Lecture Transparency. Formatted 15:28, 26 November 1996 from lsli*
*19. 13-18
| David M. Koppelman - koppel@ee.lsu.edu | Modified 26 Nov 1996 15:29 (21:29 UTC) |