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.
7-1 Recursive Decomposition *
* 7-1
A technique used to describe networks.
Analogous to recursion in computer programs.
Need a scalable network description to do this.
Scalable Network Description
A network description with an integer size parameter; : : :
: : :a distinct network is defined for every positive size.
Any kind of network description will do, for example:
Omega: (m; n). (An n-stage network.)
Generalized omega: (m; mn1 ). (A 2-stage network.)
7-1 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from *
*lsli13. 7-1
7-2 *
* 7-2
To Describe a Network Using Recursive Decomposition
- Start with a scalable network description.
- Mark certain cells as recursive, the rest are atomic.
A cell can be recursive : : :
: : :only if there exists a smaller network with the same number of inputs.
7-2 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from *
*lsli13. 7-2
7-3 *
* 7-3
Recursive Decomposition Example, Recursive Omega
ae n1
Scalable network based on generalized omega: (m;(mm) ) ifinf>n1;= 1.
(Note, (m) is a single m m crossbar.)
Left network shows single level, right network shows two levels.
7-3 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from *
*lsli13. 7-3
7-4 *
* 7-4
The completed network of size n = 4 with (right) and without (left) links straightened.
7-4 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from *
*lsli13. 7-4
7-5 *
* 7-5
Introducing Butterfly Networks
Structure of an n-stage mm-cell butterfly
network:
- Each stage has mn1 cells.
- Network inputs connect to stage-0 cell
inputs with same number.
- Stage-x cell outputs connect to stage-
(x + 1) cell inputs with a n x 1
butterfly, for 0 x < n 1.
- Stage-(n 1) cell outputs connect to like-numbered network outputs.
Routing in butterfly networks:
At stage x request (a; ff) uses cell-output ff(n1x) .
Inverse Butterfly Network
An inverse butterfly network is the mirror image of the butterfly.
7-5 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from *
*lsli13. 7-5
7-6 *
* 7-6
Extended Shu- e Function
The extended shu- e function, oe j Z ! Z, is similar to the shu- e function, except
that it can operate on any non-negative integer.
(Notation Z is the set of all non-negative integers.)
Used to shu- e least significant digits of a number.
For example:
oe2;22 (11001) = 11010, oe22;2 (11001) = 11100
oe2;23 (11001) = 10011, oe10;103 (12345) = 13452.
Formally: let m, k, and i be positive integers. The extended shu- e function oem;k j
Z ! Z is defined as
i
oem;k (i) = i(H) + m i(L) + _(L)_kmod mk ;
where i(L) = i mod mk and i(H) = _i__mkmk.
The extended shu- e function can also be defined for sequences of symbols.
7-6 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from *
*lsli13. 7-6
7-7 *
* 7-7
Introducing Baseline Networks
Structure of an n-stage m m-cell baseline
network:
- Each stage has mn1 cells.
- Network inputs connect to stage-0 cell
inputs of the same number.
- Stage-x cell outputs connect to stage-
(x + 1) cell inputs with a mnx1 ; m
extended shu- e, for 0 x < n 1.
- Stage-(n 1) cell outputs connect to network outputs with the same number.
Routing in baseline networks:
At stage x request (a; ff) uses cell-output ff(n1x) .
7-7 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from *
*lsli13. 7-7
7-8 Baseline, Butterfly, and Omega Comparison *
* 7-8
Similarity:
Routing from MSD to LSD of
destination number.
Difference:
Not TE to each other.
Significance of Difference
A connection assignment on one
may not be realized by the other.
7-8 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from *
*lsli13. 7-8
7-9 *
* 7-9
Banyan Network Family
A multistage network is a banyan network if : : :
: : :there exists exactly one path between each input/output pair : : :
: : :and all outputs are reachable.
Banyan Network Examples
Omega, butterfly, inverse omega.
Not Banyan Networks
Modified omega network
7-9 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from *
*lsli13. 7-9
7-10 *
* 7-10
Delta Network Family
A multistage network is a delta network if
- There is a path between every input/output pair.
- The cell output needed by request (a; ff) : : :
: : :is uniquely determined only by : : :
: : :the cell stage : : :
: : :and ff.
In other words, the one-and-only routing tag : : :
: : :is determined by the output only.
Delta Network Property
Lemma: All delta networks are banyan networks.
Proof: directly from the definition : : :
: : :by definition, deltas have paths between all inputs and outputs : : :
: : :"unique" cell output equivalent to unique path.
7-10 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from*
* lsli13. 7-10
7-11 *
* 7-11
Delta Network Output Names
Since the paths from all inputs to a particular output are all identical : : :
: : :the path can be used to name the output.
In an omega network the path (cell outputs) form the digits of the output's radix-m
representation.
7-11 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from*
* lsli13. 7-11
7-12 *
* 7-12
A Non-Delta Network
A modified omega network is not a delta network because : : :
: : :for requests with multiple routing tags : : :
: : :any of several cell outputs could be used.
Delta Network Examples
The following are delta networks: omega, inverse omega, butterfly, inverse butterfly.
The network below is not a delta network, but is a banyan network:
7-12 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from*
* lsli13. 7-12
7-13 *
* 7-13
Definition: The part of the routing tag used to reach a cell is called the path descriptor.
Theorem 1: The path descriptors for all requests passing through a cell in a delta network
are identical.
Proof: (By contradiction.)
Consider requests, (a; ff) and (b; fi).
Suppose these pass through the same cell, u.
Suppose they have different path descriptors.
Construct a request that starts at a, passes through u and goes to fi.
If it's impossible to construct such a request, the network is not a delta network.
If it is possible to construct such a request there are two different routing tags*
* to
fi, so the network is not a delta network.
7-13 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from*
* lsli13. 7-13
7-14 *
* 7-14
Recursive Decomposability of Delta Networks
Theorem 2: All scalable delta networks are recursively decomposable.
Proof outline:
Consider the second stage of cells.
Partition the cells into subsets : : :
: : :based on the output number of cells in the previous stage to which they connect.
All cells in each subset will have the same path descriptor.
Expand the subsets by including cells in the following stages to which they connect.
Since each output can be reached using one tag, the subsets remain disjoint.
7-14 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from*
* lsli13. 7-14
7-15 *
* 7-15
Bidelta Networks
A network is a bidelta network if it is a delta network and its inverse is a delta network.
The omega, baseline, butterfly, and their inverses are all bidelta networks.
The following is a delta network but not a bidelta network:
Definition: A bidelta network cell's dual path descriptor is the sequence obtained by
joining its path descriptor with the path descriptor of the corresponding cell in
the network's inverse.
7-15 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from*
* lsli13. 7-15
7-16 *
* 7-16
Theorem 3: The dual path descriptor for a cell in a stage of a bidelta network is unique.
Proof:
Choose two requests, (a; ff) and (b; fi), so they pass through stage-x cells with the
same dual path descriptor.
Call the stage-x cell that (a; ff) passes through u.
Call the stage-x cell that (b; fi) passes through v.
Call the dual path descriptor l r.
Next, consider request (a; fi).
The path must pass through u since l is part of the routing tag to fi.
Consider the reverse path from fi to a.
The routing tag will start with r, since that's on the path to a.
This leads to cell v, so u and v must be the same cells since these are bidelta networks.
7-16 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from*
* lsli13. 7-16
7-17 *
* 7-17
Bidelta Network Properties
Theorem 4: All bidelta networks are topologically equivalent.
Proof outline:
Consider network X.
Will map node labels so that network mapped to baseline.
Step 1: Create new labels for each output in X using the routing tags needed to reach
the outputs.
For example, in an omega network
Output 7 in an 4-stage omega is labeled 0 1 1 1.
Output i in an n-stage omega is i(n1) i(n2) : :i:(0).
A new output number is created by treating routing tag as an n-digit, mixed radix
number, with the radices determined by the cell size.
The element used for routing in the first stage is used as the most-significant di*
*git.
7-17 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from*
* lsli13. 7-17
7-18 *
* 7-18
Step 2: Similarly, create new labels for each input in X using the routing tags needed to
reach the inputs.
Create an input number by treating the routing tag as a mixed radix number.
The element used for routing in the first stage is the least-significant digit.
Label the cells using the dual path descriptor.
The networks can be shown to be identical to the baseline by comparing labels of adjacent
cells.
7-18 EE 7725 Lecture Transparency. Formatted 14:55, 17 October 1997 from*
* lsli13. 7-18
| David M. Koppelman - koppel@ee.lsu.edu | Modified 17 Oct 1997 14:56 (19:56 UTC) |