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.
10-1 *
* 10-1
J-Partitioning of Omega Networks
Idea:
Divide Omega network into independent parts.
Each part can be treated as a complete network.
Simple Example:
Upper illustration is user's view.
Lower illustration shows network routing.
Network divided into 4 parts by all setting cells in first 2 stages to
identity.
10-1 EE 7725 Lecture Transparency. Formatted 8:24, 20 November 1996 from lsli16*
*. 10-1
10-2 *
* 10-2
Motivation:
Divide system so each user has own partition.
Benefit: Users get predictable performance.
Create "new" connection assignments.
Each partition realizes CA from familiar family.
Whole network realizes "new" connection assignment.
10-2 EE 7725 Lecture Transparency. Formatted 8:24, 20 November 1996 from lsli16*
*. 10-2
10-3 *
* 10-3
Partitioning
Requirement:
Requests in different partitions cannot share a link.
Requirements met if:
Requests entering a cell either: : :
: :a:ll belong to the same partition: : :
: :o:r all belong to different partitions.
When requests for different partitions use same cell: : :
: :c:ell output is a function only of partition: : :
: :a:nd no two cell inputs use same cell output.
Realization
Choose digit positions to specify partition number.
In Omega network, digit positions are same in input and output.
10-3 EE 7725 Lecture Transparency. Formatted 8:24, 20 November 1996 from lsli16*
*. 10-3
10-4 *
* 10-4
Functions used for J-Partitioning
Functions extract digits from radix-m representation.
Let x 2 hmn i and let J hni .
The block function BL J (x) returns digits from x specified in J .
More formally, let J hni , r = n jJ j, and x 2 hmn i . Then the block
function is given by
BL J (x) = x(jnr1 )x(jnr2 ) : : :x(j0) ;
where the ji are elements of J , j0 is the smallest element in J
and ji > ji1 for all 0 < i < n r.
Examples:
If J = f2; 0g then BL J (13) = BL J (11012 ) = 112 = 3 and
BL J (9) = BL J (10012 ) = 012 = 1.
The offset function OF J(x) removes digits in x specified in J .
More formally, let J and x be defined as above. Then the offset
function is given by:
OF J (x) = x(j0r1 )x(j0r2 ) : : :x(j00);
where the j0iare elements of hni nJ (the set of elements in hni not
in J ) and j00 is the smallest of the elements and j0i> j0i1
for all 0 < i < r.
Examples:
If J = f2; 0g then OF J(13) = 102 = 2. OF J (5) = 002 = 0.
10-4 EE 7725 Lecture Transparency. Formatted 8:24, 20 November 1996 from lsli16*
*. 10-4
10-5 *
* 10-5
J-Partition Definition
Overview
Call network to be partitioned the host network.
Let J hni and r = n jJ j.
J specifies "fixed" stages which aren't part of partitions.
Using J host network partitioned: : :
: :i:nto mjJj partitions (smaller networks).
- Each partition has mr inputs and outputs.
- Each partition is topologically equivalent to an mr -input omega
network.
Input x 2 hmn i belongs to partition BL J (x).
Input x in the host network: : :
: :i:s input OF J(x) in its partition.
Yi 2 m;r will denote the permutation used for partition i.
The partitions themselves can be permuted.
That is:
Input x belongs to partition BL J (x).
Input x connects to partition BL J (x)X.
Interestingly, X 2 m;jJj .
10-5 EE 7725 Lecture Transparency. Formatted 8:24, 20 November 1996 from lsli16*
*. 10-5
10-6 *
* 10-6
Formal J -Partition Definition
Given some nonempty J ae hni : : :
: : :and permutations X 2 m;nr and Yi 2 m;r : : :
: : :for all i 2 hmnr i : : :
: : :there exists P 2 m;n : : :
: : :such that for all (s; d) 2 P : : :
BL J(s)X = BL J (d) and
OF J(s)YBL J (s) = OF J (d)
where r = n jJ j.
10-6 EE 7725 Lecture Transparency. Formatted 8:24, 20 November 1996 from lsli16*
*. 10-6
10-7 *
* 10-7
How a J -Partition is Specified
Determine the number of partitions.
Must be a power of m.
Let mz be the number of partitions.
Determine how inputs connect to partitions.
This is done by choosing J .
To obtain the correct number of partitions:
jJ j = z:
For a given J , input i is a member of partition BL J (i).
Choose J for desired connections.
For example, suppose J = f n 1; n 2; n 3 g.
Then there are eight partitions.
Consecutive numbered inputs member of same partition (except
for last).
For example, suppose J = f 0; 1; 2; 3 g.
Then there are 16 partitions in a 2 2 omega network.
Consecutive numbered inputs connected to different partitions.
10-7 EE 7725 Lecture Transparency. Formatted 8:24, 20 November 1996 from lsli16*
*. 10-7
10-8 *
* 10-8
Determine how partitions connect to outputs.
This is done by choosing X 2 m;z .
For a given X and J :
Input s (in partition BL J(s)) will connect to an output d for
which BL J (d) = BL J (s)X.
This might be used, for example, to have partition 0 use the top half
inputs and the bottom half outputs.
Determine a permutation for each partition.
This is done by choosing mjJj permutations Yk 2 m;nz .
Permutation Yk is the permutation realized by partition k.
10-8 EE 7725 Lecture Transparency. Formatted 8:24, 20 November 1996 from lsli16*
*. 10-8
10-9 *
* 10-9
Example
Goals:
Divide 8-input network into four partitions, A, B, C, and D.
Inputs for each partition consecutive.
Permute partitions using shift.
Each partition also realizes its own permutation.
Solution:
Permutation for partitions:
X = AD BA CB DC = 0011 0100 1001 1110
Permutation for each partition:
Y0 = 00 11 Y1 = 01 10 Y2 = 00 11 Y3 = 01 10
To divide network this way, J = f1; 2g.
The permutation realized by the entire network:
P = 06 17 21 30 42 53 65 74
10-9 EE 7725 Lecture Transparency. Formatted 8:24, 20 November 1996 from lsli16*
*. 10-9
10-10 *
* 10-10
Example, continued.
Blocks in permutation:
P =
BL J (0) BL J (1) BL J(2) BL J (3) BL J (4) BL J (5) BL J (6) *
* BL J(7)
BL J (6) BL J (7) BL J(1) BL J (0) BL J (2) BL J (3) BL J (5) *
* BL J(4)
= 0011 0011 0100 0100 1001 1001 1110 1110
Offsets in permutation:
P =
OF J (0) OF J(1) OF J(2) OF J(3) OF J(4) OF J (5) OF J (6*
*) OF J (7)
OF J (6) OF J(7) OF J(1) OF J(0) OF J(2) OF J (3) OF J (5*
*) OF J (4)
= 00 11 01 10 00 11 01 10
10-10 EE 7725 Lecture Transparency. Formatted 8:24, 20 November 1996 from lsli1*
*6. 10-10
| David M. Koppelman - koppel@ee.lsu.edu | Modified 20 Nov 1996 8:27 (14:27 UTC) |