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 *
* 7-1
Recursive Decomposition
A technique used to describe networks.
Analogous to recursion in computer programs.
Need a scalable network description to do this.
Scalable Network Description
A scalable network description is a one-to-one mapping from the pos-
itive integers to network descriptions.
In words: an infinite family of networks, each assigned an integer,
starting with one.
Any kind of network description will do, for example, five-tuples and
LGMs.
Example, the 2 2-cell omega networks:
(n; 2; 2n1 ; S; T )n :
To Describe a Network Using Recursive Decomposition
- Start with a scalable network description.
- Mark certain cells as recursive, the rest are atomic as follows:
A cell may (or may not) be marked recursive if the cell has a
inputs and b outputs and their exists a scalable network with a
inputs and b outputs.
Otherwise, mark the cell atomic.
7-1 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli13.*
* 7-1
7-2 *
* 7-2
Recursive Decomposition Example, Recursive Omega Redux
Scalable network:
ae
(2; (m; mn1 ); (mn1 ; m); S; T )n if n > 1;
(1; m; 1; T; T ) if n = 1.
After replacing recursive cells by smaller networks
7-2 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli13.*
* 7-2
7-3 *
* 7-3
The completed network of size n = 4:
When the link patterns are redrawn, this network appears as the re-
cursive omega presented earlier.
7-3 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli13.*
* 7-3
7-4 *
* 7-4
Introducing Butterfly Networks
Structure of an n-stage m m-cell butterfly network:
- Each stage has mn1 cells.
- Network inputs connect to like-numbered stage-0 cell in-
puts.
- Stage-x cell outputs connect to stage-(x + 1) cell inputs
with a n x 1 butterfly, for 0 x < n 1.
- Stage-(n1) cell outputs connect to like-numbered network
outputs.
Routing in butterfly networks:
At stage x request (a; ff) uses cell-output ff(n1x) .
A 16-input butterfly network:
Inverse Butterfly Network
An inverse butterfly network is the mirror image of the butterfly.
7-4 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli13.*
* 7-4
7-5 *
* 7-5
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, and
oe10;103 (12345) = 13452.
Formally:
Let m, k, and i be positive integers. The extended shu- e func-
tion oem;k j Z ! Z is defined to be
i
oem;k (i) = i(H) + m i(L) + _(L)_k mod 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-5 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli13.*
* 7-5
7-6 *
* 7-6
Introducing Baseline Networks
Structure of an n-stage m m-cell baseline network:
- Each stage has mn1 cells.
- Network inputs connect to like-numbered stage-0 cell in-
puts.
- Stage-x cell outputs connect to stage-(x + 1) cell inputs
with a mnx1 ; m extended shu- e, for 0 x < n 1.
- Stage-(n1) cell outputs connect to like-numbered network
outputs.
Routing in baseline networks:
At stage x request (a; ff) uses cell-output ff(n1x) .
A 16-input baseline network:
7-6 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli13.*
* 7-6
7-7 *
* 7-7
Baseline, Butterfly, and Omega Comparison
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-7 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli13.*
* 7-7
7-8 *
* 7-8
Banyan Network Family
A multistage network is a banyan network if: : :
: : :there exists exactly one path between: : :
: : :each input/output pair.
Banyan Network Examples
Omega, butterfly, inverse omega.
Not Banyan Networks
Modified omega network
7-8 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli13.*
* 7-8
7-9 *
* 7-9
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: : :
: :b:y definition, deltas have paths between all inputs and outputs: : :
: :":unique" cell output equivalent to unique path.
7-9 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli13.*
* 7-9
7-10 *
* 7-10
A Non-Delta Network
A modified omega network is not a delta network because: : :
: :f:or requests with multiple routing tags: : :
: :a:ny 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-10 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli1*
*3. 7-10
7-11 *
* 7-11
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-11 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli1*
*3. 7-11
7-12 *
* 7-12
Recursive Decomposability of Delta Networks
Theorem 2: All delta networks are recursively decomposable.
Proof outline:
Consider the second stage of cells.
Partition the cells into subsets: : :
: :b:ased 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-12 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli1*
*3. 7-12
7-13 *
* 7-13
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 net-
works.
The following is a delta network but not a bidelta network:
Definition: A bidelta network cell's dual path descriptor is the se-
quence obtained by joining its path descriptor with the path
descriptor of the corresponding cell in the network's inverse.
7-13 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli1*
*3. 7-13
7-14 *
* 7-14
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-14 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli1*
*3. 7-14
7-15 *
* 7-15
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 digit.
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 compar-
ing labels of adjacent cells.
7-15 EE 7725 Lecture Transparency. Formatted 18:46, 22 October 1996 from lsli1*
*3. 7-15
| David M. Koppelman - koppel@ee.lsu.edu | Modified 22 Oct 1996 18:47 (23:47 UTC) |