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 Generalized Connectors *
* 14-1
There are several ways to construct these:
- Single crossbar.
- Clos-type generalized connectors.
- Networks called fanout/concentrators.
- Pack/Copy/Permute networks.
14-1 EE 7725 Lecture Transparency. Formatted 14:19, 24 November 1997 from lsli2*
*0. 14-1
14-2 *
* 14-2
Pack/Copy/Permute Generalized Connectors.
This network described by Ofman1 and a generalized version described
by Thompson2 .
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, with cells that can broadcast.
The permute part is (sometimes) a Benes network.
Straightforward Construction
_______________________________
1 Ju. P. Ofman, "A universal automaton," Transactions of the Moscow Math Society,
pp. 200-215, 1965.
2 Clark D. Thompson, "Generalized connection networks for parallel processor intercom-
munication," IEEE Transactions on Computers, vol. 27, no. 12, pp. 1119-1125, Decem-
ber 1978.
14-2 EE 7725 Lecture Transparency. Formatted 14:19, 24 November 1997 from lsli2*
*0. 14-2
14-3 *
* 14-3
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-3 EE 7725 Lecture Transparency. Formatted 14:19, 24 November 1997 from lsli2*
*0. 14-3
14-4 *
* 14-4
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-4 EE 7725 Lecture Transparency. Formatted 14:19, 24 November 1997 from lsli2*
*0. 14-4
14-5 Clos-Type Generalized Connector *
* 14-5
Described by Yang and Masson3 .
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.)
_______________________________
3 Yuanyuan Yang and Gerald M. Masson, "Nonblocking broadcast switching networks,"
IEEE Transactions on Computers, vol. 40, no. 9, pp. 1005-1015, September 1991.
14-5 EE 7725 Lecture Transparency. Formatted 14:19, 24 November 1997 from lsli2*
*0. 14-5
14-6 *
* 14-6
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-6 EE 7725 Lecture Transparency. Formatted 14:19, 24 November 1997 from lsli2*
*0. 14-6
14-7 Fanout/Concentrate Generalized Connector *
* 14-7
Described by Nassimi and Sahni4
Construction:
Consists of three stages:
- Generalizer. Makes 2m copies of each input.
- Concentrator. Multiplexes (concentrates) inputs (to outputs).
- Generalized Connector. An N___2mgeneralized connector.
Operation:
Generalizer makes a copy for each of 2m concentrators.
Concentrator routes active inputs to recursive GC.
Recursive generalized connector completes routing.
_______________________________
4 David Nassimi and Sartaj Sahni, "Parallel permutation and sorting algorithms and a new
generalized connection network," Journal of the Association for Computing Machinery,
vol. 29, no. 3, pp. 642-667, July 1982.
14-7 EE 7725 Lecture Transparency. Formatted 14:19, 24 November 1997 from lsli2*
*0. 14-7
| David M. Koppelman - koppel@ee.lsu.edu | Modified 24 Nov 1997 14:21 (20:21 UTC) |