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.
9-1 *
* 9-1
Omega-Network Connection Assignments
A connection assignment that a network can satisfy is an admissible
permutation.
The set of all permutations admissible by an mn -input omega network
is denoted m;n .
The set of all permutations admissible by an mn -input inverse omega
network is denoted 1m;n .
Simple lemma: If P 2 m;n then P 1 2 1m;n .
The contents of m;n is of interest to those:
- writing parallel algorithms and
- designing networks.
Two families of admissible permutations will be studied:
- Shift and
- Bitonic
9-1 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15. *
* 9-1
9-2 *
* 9-2
Shift Permutations
Used to connect input i to output pi + c, where
i; c 2 h2n i and p mod 2 = 1 (p is odd).
A permutation is a p, c shift permutation of size 2n , denoted Sp;c, if
for all x 2 h2n i
Sp;c(x) j xp + c (mod 2n );
where c is a nonnegative integer and p is a nonnegative odd
integer.
Examples:
S1;2 = 02 13 24 35 46 57 60 71
S3;2 = 02 15 20 33 46 51 64 77
Examples, illustrated:
9-2 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15. *
* 9-2
9-3 *
* 9-3
The set of all shift permutations of size 2n is given by
[
S(2n ) = fS2x+1;c g:
x;c2h1i
Assertion: Any shift permutation can be satisfied by an omega net-
work, that is, S (2n ) 2;n :
Proof Outline
Consider A = (a; ff) 2 Sp;c for an N = 2n -input omega network.
By definition, ff = pa + c.
Consider a second request B = (b; fi) 2 Sp;c, b 6= a.
First prove ff 6= fi for all a; b 2 hN i .
Find the stage terminal needed by requests A and B at cell outputs
in stage i 2 hni .
Request (a; ff) uses
ff
i; a(n2i) a(n3i) : : :a(0) ff(n1) ff(n2) : : :ff(n1i) :
Request (b; fi) uses
ff
i; b(n2i) b(n3i) : : :b(0) fi(n1) fi(n2) : : :fi(n1i) :
ff
Show that: i; a(n2i) a(n3i) : : :a(0) ff(n1) ff(n2) : : :ff(n1i)ff *
*6=
i; b(n2i) b(n3i) : : :b(0) fi(n1) fi(n2) : : :fi(n1i) .
for all i 2 hni , A = (a; ff) 2 Sp;c, B = (b; fi) 2 Sp;c, a 6= *
* b,
p; c 2 hN i .
This proof is simple when p is limited to 1.
9-3 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15. *
* 9-3
9-4 *
* 9-4
Admissibility Proof for Shift Permutations, p = 1
Since a 6= b (be definition) they differ in 1 digit.
Let x + 1 be the lowest-numbered differing digit.
That is, a(0:x) = b(0:x) and a(x+1) 6= b(x+1) .
Lemma: ff(x+1) 6= fi(x+1) .
Proof:
Consider addition of ff = a + c and fi = b + c by bits.
Let r(x+1) be carry to be added to digit x + 1.
Since c and digits up to x in A and B are identical: : :
: : :the carry r(x+1) must also be identical.
Bitwise addition:
ff(x+1) = a(x+1) c(x+1) r(x+1)
and fi(x+1) = b(x+1) c(x+1) r(x+1) .
Since only difference is a(x+1) 6= b(x+1) , then ff(x+1) 6= fi(x + 1) .
Back to admissibility proof:
In stage i,: : :
: : :either a(0:n2i) 6= b(0:n2i) or ff(n1i:n1) 6= fi(n1i:n1) : *
*: :
: :e:ither way there is no contention.
9-4 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15. *
* 9-4
9-5 *
* 9-5
Admissibility Proof for Shift Permutations, p Odd
Similar to proof above:
Let x + 1 be the lowest-numbered differing digit:
a(0:x) = b(0:x) and a(x+1) 6= b(x+1) .
Lemma: ff(x+1) 6= fi(x+1) .
Proof:
Need to compare (ap)(x+1) and (bp)(x+1) .
x+1 !
X
(ap)(x+1) = p(z) a(xz+1) + Rx+1 mod 2,
z=0
where Rx+1 is the carry.
Splitting the sum yields:
x+1 !
X
(ap)(x+1) = p(0) a(x+1) + p(z) a(xz+1) + Rx+1 mod 2,
z=1
Since a(0:x) = b(0:x) expressions for (ap)(x+1) and (bp)(x+1) differ : : :
: : :only in p(0) a(x+1) and p(0) b(x+1) : : :
: : :(noting that since p is odd, p(0) = 1): : :
: : :and so (ap)(x+1) 6= (bp)(x+1) : : :
: : :and therefore ff(x+1) 6= fi(x+1) .
9-5 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15. *
* 9-5
9-6 *
* 9-6
Remainder of proof is the same:
In stage i,: : :
: : :either a(0:n2i) 6= b(0:n2i) or ff(n1i:n1) 6= fi(n1i:n1) : *
*: :
: :e:ither way there is no contention.
9-6 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15. *
* 9-6
9-7 *
* 9-7
Bitonic Permutations
A sequence of numbers is bitonic if the magnitude of the numbers first
increases then decreases, or if the magnitude of the numbers first
decreases then increases.
Examples:
1,1,2,5,5,4,0
1,2,1
5,3,0,8
Not bitonic: 1,2,0,3 and 1,2,3,4.
The definition of a bitonic permutation will have a slight difference:
The sequence is a sequence of integers,
the integers are a permutation of hmn i , and
the sequence when shifted is bitonic.
9-7 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15. *
* 9-7
9-8 *
* 9-8
A permutation for which the sequence P (c), P (c + 1), P (c + 2); : : :;
P (c + mn 1) is bitonic is called a bitonic permutation, where
P is a permutation of hmi n , c is an integer, and arithmetic is
modulo mn .
Examples:
P1 = 02 13 25 37 46 54 61 70 P2 = 05 17 26 34 41 50 62 73
9-8 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15. *
* 9-8
9-9 *
* 9-9
Theorem: Let symbol B(mn ) denote the set of all bitonic permuta-
tions of h mn i . Then B(mn ) m;n .
Proof Introduction:
Let P 2 B and (a; ff) 2 P and (b; fi) 2 P , (a 6= b).
Link used by (a; ff) at cell output in stage x is: : :
: : :a(nx2) a(nx3) a(0) ff(n1) ff(n2) ff(nx1) .
Similarly (b; fi) uses b(nx2) b(nx3) b(0) fi(n1) fi(n2) fi(nx1) *
* .
To prove (a; ff) and (b; fi) don't share a link: : :
: :s:ufficient to show that: : :
: :i:f ff(n1) ff(nx1) = fi(n1) fi(nx1)
: :t:hen a(nx2) a(nx3) a(0) 6= b(nx2) b(nx3) b(0) .
Proof Introduction In words:
Call a(nx2) a(nx3) a(0) and b(nx2) b(nx3) b(0) the (input)
LSDs.
Call ff(n1) ff(nx1) and fi(n1) fi(nx1) the (output) MSDs.
Need to prove: if the MSDs of two requests match,: : :
: :t:he LSDs must be different.
For rest of proof consider only requests with
ff(n1) ff(nx1) = fi(n1) fi(nx1)
9-9 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15. *
* 9-9
9-10 *
* 9-10
Proof Observation:
Because P is a permutation: : :
: :f:or each choice of ff(n1) ff(nx1) : : :
: :t:here are mnx1 requests in P .
If the LSDs of the inputs of those mnx1 requests are distinct: : :
: :(:e.g., a(nx2) a(nx3) a(0) 6= a(nx2) a(nx3) a(0) )
: :t:hen (a; ff) and (b; fi) won't share a link.
So, that's what will be proven.
Proof Outline:
Show that for a given ff(n1) ff(nx1) : : :
: :t:he possible input numbers form up to 3 runs of consecutive num-
bers.
(By property of bitonic sequences.)
Show that gaps between runs contain a multiple of mnx1 inputs.
(Show directly for ff(n1) ff(nx1) = mx+1 2, proceed with
induction on ff(n1) ff(nx1) .)
Show a bijection between mnx1 consecutive integers: : :
: :a:nd the inputs.
9-10 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15*
*. 9-10
9-11 *
* 9-11
For example consider P = 01 13 27 36 45 54 62 70 for 2;3 .
In stage 0 let ff(2) = 1.
Then inputs form one run: 2,3,4,5 and there is no gap.
In stage 0 let ff(2) = 0.
Then inputs form two runs: 0,1 and 6,7 with a gap of 4.
Note that LSDs of inputs are 0,1,2,3. (LSDs might need to be
sorted.)
In stage 1 let ff(2:1) = 112 = 3.
Then inputs form one run: 2,3.
LSDs form sequence 0,1.
In stage 1 let ff(2:1) = 102 = 2.
Then inputs form one run: 4,5.
In stage 1 let ff(2:1) = 012 = 1.
Then inputs form two (single-digit) runs: 1 and 6 with a gap of
4.
9-11 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15*
*. 9-11
9-12 *
* 9-12
Application: Spreading, Copying, and Packing
The bitonic permutations are related to three useful families of con-
nection assignments:
Spreading Connection Assignment: A 1-limited GCA (general-
ized connection assignment) in which consecutive inputs
are routed to outputs, preserving order.
Copy Connection Assignment: An N -limited GCA in which con-
secutive inputs are routed (multicast) to outputs, preserv-
ing order.
Packing Connection Assignment: A 1-limited GCA in which a
subset of inputs is connected to consecutive outputs, pre-
serving order.
9-12 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15*
*. 9-12
9-13 *
* 9-13
Spreading Connection Assignments
Examples:
f(0; 2); (1; 5); (2; 7)g is a spreading CA.
f(0; 2); (2; 5); (3; 7)g is not a spreading CA. (Input 1 is skipped.)
f(0; 2); (1; 7); (2; 5)g is not. (The requests do not appear in the
same order when sorted by outputs.)
Assertion: An omega network can satisfy all spreading connection
assignments.
Proof outline:
It is known that an omega network can realize all bitonic per-
mutations.
It will be shown that a bitonic permutation can be constructed
from any spreading CA.
Consider f(0; 2); (1; 5); (2; 7)g:
P = 02 15 27 3 4 5 6 7
Construct a bitonic permutation by adding (3; 6), (4; 4), etc.
It can easily be shown that this procedure will work in all cases.
9-13 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15*
*. 9-13
9-14 *
* 9-14
Copy Connection Assignments
Examples:
f(0; 2); (0; 3); (1; 5); (2; 6); (2; 7)g
In the CA above, two "copies" made of data at inputs 0 and 2.
One copy made of data at 1.
These can be realized in omega networks with broadcast capability.
In such networks a single cell input must be able to connect to
both outputs.
9-14 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15*
*. 9-14
9-15 *
* 9-15
Assertion: All copy CAs can be satisfied by an omega network.
Proof outline:
Proof is by contradiction.
Suppose there is a copy CA that cannot be realized.
Let X be such a CA.
For at least one cell, two requests in X from different inputs
must need the same cell output.
Call the requests A = (a; ff) and B = (b; fi).
By definition of A and B, a 6= b.
Construct a spreading CA, X0 in the following way:
Put A and B in X0.
Add one request for each of the other inputs in X to X0.
The result is a spreading CA, which can be satisfied by an
omega network.
Since paths in an omega network are unique, if A and B do not
conflict in X0 they cannot conflict in X.
9-15 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15*
*. 9-15
9-16 *
* 9-16
Packing Connection Assignments
These are the mirror image (inverse) of spreading CAs.
Examples:
f(3; 0); (7; 1); (9; 2)g is a packing CA.
f(4; 2); (7; 3); (11; 4)g is a packing CA.
Assertion: An inverse omega network can satisfy all packing connec-
tion assignments.
Proof outline:
Show that packing CA is mirror image of spreading CA.
If P 2 then P 1 2 1 .
9-16 EE 7725 Lecture Transparency. Formatted 8:23, 20 November 1996 from lsli15*
*. 9-16
| David M. Koppelman - koppel@ee.lsu.edu | Modified 20 Nov 1996 8:26 (14:26 UTC) |