EE 7725 Lecture Notes

Generated from file lsli20.dvi.

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.


14-1                                                                                               *
 *        14-1


                           All Permutations From Shu- e Stages


       Consider network composed of s shu- e stages.


       Problem:  find minimum s for which all permutations admitted.


       Two Solutions:


          1:   Transform Benes network into shu- es.


          2:   Show omega/inverse omega can admit all permutations.


               Transform omega/inverse omega into shu- es.



14-1                     EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli20*
 *.                  14-1

14-2 * * 14-2 Transformation of Benes Network Plan - Start with Benes network. - Replace parts of Benes network with functionally equivalent networks. - Stop when resulting network consists only of shu- es. Solution 1: Start with Benes network. Benes 2: Replace left n stages of the Benes with a baseline. Note that the left half of the Benes is equivalent to a baseline. 3: Replace right n 1 stages of the Benes with an inverse baseline. Baseline Baseline 1 Note that there is now an additional stage. The additional stage is redundant. 14-2 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli20* *. 14-2
14-3 * * 14-3 4: Replace the baseline with a ae link pattern followed by an omega network. ae Baseline 1 It can be shown that a baseline is terminal equivalent to ae. 5: Replace the inverse baseline with a ae link pattern followed by an omega network. aeae Recall that a baseline and inverse baseline are terminal equiva- lent. 6: Replace the middle ae with 1 AE2 ae1 AE2 where 1 AE2 = ae, 1 2 , 2 2 , and AE 2 . Since ae is a linear permutation it can be factored this way. 7: Replace 2 with . ae1 AE Recall lower-triangular permutations, , are left-invariant. 14-3 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli20* *. 14-3
14-4 * * 14-4 8: Replace 1 with . aeAE Yes, a link pattern is replaced with an entire omega network. 9: Replace AE with . ae Recall upper-triangular permutations, , are right-invariant. 10: Replace ae with . The resulting network consists of only shu- es. Using Fewer Stages It is possible to remove two or three stages. It may be possible to realize all permutations in 2n 1 stages. Use of fewer than 3n stages will not be covered. 14-4 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli20* *. 14-4
14-5 * * 14-5 Transformation of Omega/Inverse Omega Plan - Prove that omega/inverse omega can admit all permutations. - Transform omega/inverse omega to shu- es. Omega/Inverse Omega Network Constructed by cascading an omega and inverse omega network. Can realize permutations in set 1 . Theorem: 1 = . Proof: By induction on n. Let n and 1n denote n-stage omega and inverse omega networks. Basis: 1 11 = 21 . Trivially true. 14-5 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli20* *. 14-5
14-6 * * 14-6 Inductive hypothesis: If 2;n1 12;n1 = 2n1 then 2;n 12;n = 2n . Proof of IH: Draw omega/inverse omega using recursive forms. This will have four stages. The four (recursive) cells in the two inner stages form two omega/ inverse omega networks. Consider each of these omega/inverse omega networks as a unit. Then the larger omega/inverse omega network is equivalent to: a shu- e followed by a Clos network, followed by an inverse shuf- fle. It's known that the Clos network can realize all permutations. Therefore the network obtained by adding the shu- es can also realize all permutations. That is, the omega/inverse omega can realize all permutations. Next, convert 1 into shu- es. Note that 1 = aeae. Therefore, 1 = aeae. The remainder of the transformation is similar to the Benes network transformation. 14-6 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli20* *. 14-6
14-7 * * 14-7 Generalized Connectors There are several ways to construct these: - Single crossbar. (When you're rich alot of problems are easy to solve.) - Clos-type generalized connectors. - Networks called fanout/concentrators which we may not have time to cover. - Pack/Copy/Permute networks. 14-7 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli20* *. 14-7
14-8 * * 14-8 Pack/Copy/Permute Generalized Connectors. This network described by Ofman. Network is rearrangeable (for generalized connection assignments). Network has three parts: - Pack: packs those inputs having requests to consecutive links. - Copy: fans out (copies) inputs to multiple links. - Permute: routes to proper output. Construction The pack part is an inverse omega network. The copy part is an omega network. The permute part is (sometimes) a Benes network. Straightforward Construction 14-8 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli20* *. 14-8
14-9 * * 14-9 Slightly Lower-Cost Version Stages where parts meet can be removed, eliminating two stages. Cost Straightforward version: 4n2n1 cells. Lower-cost version: (4n 3)2n1 cells. 14-9 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli20* *. 14-9
14-10 * * 14-10 Routing CA - Route each input having a request from GC inputs (same as pack-part inputs) to consecutive copy-part inputs. (Using a packing CA). - Route A = (a; ff) 2 at copy-part input to jf (a; O) j (a; O) 2 g j consecutive copy-part outputs. (That is, make needed number of copies using a copy connection assignment.) - Finally, route A = (a; ff) to output ff through permute part. (Use dummy requests to create a permutation if necessary, then use looping algorithm to route Benes network.) - Done. 14-10 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli2* *0. 14-10
14-11 * * 14-11 Clos-Type Generalized Connector Described by Yang and Masson in 1991. Is a non-blocking d-limited generalized connector. Construction Topology of Clos network in which m0 > (m 1)(x + d1=x ), where 0 < x min f m 1; d g and 0 < d k. (Choice of x determines cost and performance.) 14-11 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli2* *0. 14-11
14-12 * * 14-12 Cost The minimum cost of a 2n + 1 stage Clos-type GC is bounded by n+2_ _1__ ! _1__ log N 2 n+1 C(N; 2n + 1) = O N 1+ n+1 ____________loglogN To achieve this bound choose: m0 = O m __log_k____loglogk or m0 > (m 1)(log 2 k + 2) and at level i choose _i__i+1 k = _____________N__________________i_1_: (log N= log log N ) 2 i+1 Derivation of these equations are not covered. (These equations are not easy to work with.) Routing Performance A new request can be routed in O(mk) time. A connection assignment can be routed in O(m2 k) time. (Routing for this network will not be covered.) 14-12 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli2* *0. 14-12
14-13 * * 14-13 Fanout/Concentrate Generalized Connector Described by Nassimi and Sahni in a 1982 paper. Construction: Consists of three stages: - Generalizer. Makes 2m copies of each input. - Concentrator. Multiplexes (concentrates) inputs (to outputs). - Generalized Connector. An N 2m generalized connector. Operation: Generalizer makes a copy for each of M concentrators. Concentrator routes active inputs to recursive GC. Recursive generalized connector completes routing. 14-13 EE 7725 Lecture Transparency. Formatted 13:39, 6 December 1996 from lsli2* *0. 14-13

ECE Home Page 7725 Home Page Up
David M. Koppelman - koppel@ee.lsu.edu
Modified 6 Dec 1996 13:39 (19:39 UTC)