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.
04-1 Multistage-Network Overview *
* 04-1
Major Types
- Banyan and Banyan-Like.
- Clos and Benes
- Batcher Sorters
- Miscellaneous
______________________________________________________________________________________________*
*_______
Banyan (Omega) Benes Ofman Gen. Con.
______________________________________________________________________________________________*
*_______
04-1 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 from *
*lsli04. 04-1
04-2 - Banyan and Banyan-Like. *
* 04-2
______________________________________________________________________________________________*
*_______
______________________________________________________________________________________________*
*_______
Includes omega network.
Provide efficient interconnections.
Easy to route.
Cannot support all connection assignments.
Most commonly used MIN type.
04-2 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 from *
*lsli04. 04-2
04-3 *
* 04-3
- Clos and Benes
______________________________________________________________________________________________*
*_______
______________________________________________________________________________________________*
*_______
Cost roughly twice as much as Banyans.
Difficult to route.
Can support all permutation connection assignments.
Used in a small number of research computers.
04-3 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 from *
*lsli04. 04-3
04-4 *
* 04-4
- Batcher Sorters
Cost roughly log N times more than N -input Banyan.
Easy to route.
Can support all permutation connection assignments.
- Miscellaneous
Fanout/Concentrate Family
Composite Networks
Of non-practical-theoretical and practical interest.
04-4 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 from *
*lsli04. 04-4
04-5 Multistage-Network Terminology *
* 04-5
A MIN consists of cells and links.
Cells arranged in stages.
Links connect cells in adjacent stages.
04-5 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 from *
*lsli04. 04-5
04-6 *
* 04-6
Multistage-Network Terminology
The following numbering will be used:
Stages, consecutively from 0 (input) to s 1 or n 1.
Cells within a stage, consecutively from 0.
Cell inputs and outputs, consecutively from 0 for each cell.
Cell inputs and outputs also given stage terminal numbers.
Terminal numbers consecutively from 0, for all cells.
04-6 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 from *
*lsli04. 04-6
04-7 *
* 04-7
Link Patterns
A link pattern is an arrangement of links that could connect adjacent stages in a MIN.
More Formally:
Let T1 and T2 be equal-cardinality sets of terminal numbers.
A link pattern is a bijection from T1 to T2.
Example:
Let T1 = f0; 1; 2g and T2 = f0; 1; 2g.
Let ss(0) = 1, ss(1) = 0, and ss(2) = 2.
Mapping ss is a bijection from T1 to T2, and therefore a link pattern.
Let ss0(0) = 1, ss0(1) = 1, and ss0(2) = 2.
Mapping ss0 is not a bijection, and so not a link pattern.
04-7 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 from *
*lsli04. 04-7
04-8 *
* 04-8
Omega Network Routing
To route request (u; v) in an n-stage 2 2 network : : :
: : :at stage i take cell output v(n1i) , for i 2 hni .
04-8 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 from *
*lsli04. 04-8
04-9 *
* 04-9
Generalization of MIN Using Shu- es
Goal: Specify a family of networks which
- consists of stages of square cells
- with shu- es between stages chosen so that:
outputs from an individual cell in one stage connect to consecutive cells in the
next stage.
Each stage can have its own cell size.
These networks called a flat square MIN in class.
04-9 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 from *
*lsli04. 04-9
04-10 Generalization of MIN Using Shu- es *
* 04-10
Notation: (s; "m; "k; l; r), where
s is the number of stages;
"m = (m0; m1; : :;:ms), mi indicates the cell size in stage i 2 hsi;
"k= _N__; _N__; : :;:_N__ ,
m0 m1 ms
Q s1
where N = i=0 mi, the number of inputs;
_N__
indicates the number of cells in stage i;
mi
and the link patterns are as follows (on next slide):
04-10 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 fro*
*m lsli04. 04-10
04-11 Generalization of MIN Using Shu- es *
* 04-11
- Stage 0:
If l = T then hI; ui connects to h0; ui for u 2 N .
That is, there is no shu- e in the first stage.
If l = S then hI; ui connects to h0; oem0;k0 (u)i for u 2 N .
That is, there is an m0; k0 shu- e in the first stage.
04-11 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 fro*
*m lsli04. 04-11
04-12 Generalization of MIN Using Shu- es *
* 04-12
- Stage i 2 f1; 2; : :;:s 1g:
Stage terminal hi 1; ui connects to hi; oemi;ki (u)i.
That is, there is an mi; ki shu- e in all but the first stage.
- Following last stage:
If r = T stage terminal hs 1; ui connects to output hO; ui .
That is, there is no shu- e following the last stage.
If r = S stage terminal hs 1; ui connects to output hO; oems;ks ui .
That is, there is a shu- e following the last stage.
(The only purpose of ms and ks is to specify this shu- e.)
04-12 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 fro*
*m lsli04. 04-12
04-13 Generalized Omega Network *
* 04-13
A generalized omega network is a type of flat square min:
N N N
(s; (m0; m1; : :;:ms) ; ( ____; ____; ; ____) ; S; T), where
m0 m1 ms
Q s1
N = i=0 mi, the number of inputs.
Path-length, d = s.
04-13 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 fro*
*m lsli04. 04-13
04-14 Generalized Omega Network *
* 04-14
Mixed Radix Numbers (used in routing)
Let "r= (rn1 ; rn2 ; : :;:r0) be a sequence of integers > 1.
To convert an integer x to radix "r:
LSD is x0 = x mod r0.
Second digit is x1 = x__rmod r1.
0
$ %
Digit xi = ___x_____Qi1mod ri.
j=0rj
Examples:
"r= (2; 3; 4): 3 = (0; 0; 3), 4 = (0; 1; 0), 20 = (1; 2; 0).
"r= (5; 4; 2): 3 = (0; 1; 1), 4 = (0; 2; 0), 20 = (2; 2; 0).
To convert x(n1) x(n2) x(0) in radix "rto decimal:
n1X i1Y
x = x0 + xi rl.
i=1 l=0
04-14 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 fro*
*m lsli04. 04-14
04-15 *
* 04-15
To route request (u; v):
- Convert u and v to radix "rnumbers, where ri = mn1i .
- At stage i take cell output vn1i .
To convert the terminal numbers in each stage to decimal:
In stage j use radix "rjwhere
rj;i= mn+jimod n .
n1X i1Y
Then x = x0 + xi rj;l.
i=1 l=0
04-15 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 fro*
*m lsli04. 04-15
04-16 Modified Omega Network *
* 04-16
Consists of stages of cells connected by shu- es.
It's not an omega network (though it does look like one).
Described by (m; k), where m > 1 and k 1.
Such a network has:
- N = mk inputs and outputs and
- s = dlog m N e stages.
Each stage consists of
- an oem;k shu- e followed by
- k cells of size m m.
Important Difference
Uses integer shu- e function, not symbol shu- e function.
Significance: structure isn't related to radix-m link numbers.1
Routing more complex.
_______________________
1 Nor any mixed-radix form, whether or not the links are numbered differently.
04-16 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 fro*
*m lsli04. 04-16
04-17 Routing Modified Omega Networks *
* 04-17
Unlike real omega, some requests have more than one path.
Will compute routing tags, denoted tp, where p is a tag number.
Routing tag used as a destination in omega.
(Or, in an omega network, the destination is the routing tag.)
To route request (i; j) in an (m; k) modified omega network:
Let: N = mk, s = dlogm N e, and M = N ms1 .
t1 = j + mM i
tp = t1 + (p 1)M , valid if tp < ms.
04-17 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 fro*
*m lsli04. 04-17
04-18 Modified Omega Network Example *
* 04-18
Network defined by m = 2, k = 9.
Then N = mk = 18 and s = dlog 218e = 5.
Constant used in routing, M = N ms1 = 18 16 = 2.
04-18 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 fro*
*m lsli04. 04-18
04-19 *
* 04-19
Modified Omega Network Example
Route for request (1; 3):
t1 = 3 + 1 2 2 = 7 = 00111, t1 can always be used.
t2 = 7 + 1 18 = 25 = 11001 < 32, can be used.
t3 = 7 + 2 18 = 43 6< 32, can not be used.
04-19 EE 7725 Lecture Transparency. Formatted 13:05, 8 October 1997 fro*
*m lsli04. 04-19
| David M. Koppelman - koppel@ee.lsu.edu | Modified 8 Oct 1997 13:06 (18:06 UTC) |