Information Technology Reference
In-Depth Information
12.7.1 The Performance of VLSI Algorithms on Functions
The
w
(
u
,
v
)
-flow property of functions is introduced in Section
10.4.1
andappliedtothe
study of space-time tradeoffs in the pebble game. In this section we use this property to derive
lower bounds on the semellective planar circuit size of multi-output functions.
DEFINITION
12.7.1
Afunction
f
:
X
n
X
m
has a
w
→
(
u
,
v
)
-flow
if for all subsets
U
1
and
V
1
of its
n
input and
m
output variables with
v
there is some assignment
to variables not in
U
1
(variables in
U
0
) such that the resulting subfunction
h
of
f
that maps input
variables in
U
1
to output variables in
V
1
(the other outputs are discarded) has at least
|
U
1
|≥
u
and
|
V
1
|≥
w
(
u
,
v
)
|
X
|
points in the image of its domain. (Note that
w
(
u
,
v
)
≥
0
.)
A lower bound on planar circuit size of a function
f
is now derived from its
w
(
u
,
v
)
-flow
property. For some functions the parameter
P
will need to be large for
w
(
u
,
v
)
>
0, as is seen
Lemma
12.7.1
.
THEOREM
12.7.1
Let
f
:
X
n
X
m
have a
w
(
u
,
v
)
-flow. Then its semellective planar circuit
size must satisfy th
e fol
lowing lower b
ound
for
u
→
≥
n
(
1
−
3
/
2
P
)
,
v
≥
m/
(
3
P
)
,and
P
≥
2
,
where
K
2
=
4
(
2
/
3
+
1
)
/
(
1
−
5
/
6
)
.
w
2
(
u
,
v
)
4
K
2
Proof
Consider a minimal semellective planar circuit for
f
:
X
n
C
p
,
Ω
(
f
)
≥
X
m
on
n
inputs con-
taining
N
=
C
p
,
Ω
(
f
)
inputs, gates, and crossings. We apply the version of the planar sepa-
ratortheoremgiveninLemma
12.6.4
to this circuit by assigning unit weight to each input
vertex and zero weight to all other vertices. For any integer
P
→
≤|
V
|
we conclude that the
inputs, gates, and crossings of this circuit can be partitioned into
q
sets
{
A
1
,
A
2
,
...
,
A
q
}
,
for 2
P/
3
3
P
,suchthateachsethasatleast
n/
(
3
P
)
and at most 3
n/
(
2
P
)
input
vertices. Since the average number of output vertices in these sets is
m/q
, at least one set,
call it
A
1
, has at least the average of output vertices or at least
m/
3
P
vertices. Let
U
0
and
V
1
be the sets of inputs and outputs in
A
1
, respectively. Then,
n/
(
3
P
)
≤
q
≤
≤|
U
0
|≤
3
n/
(
2
P
)
and
m/
3
P
.
For some assignment of values to variables in
U
0
,thereareatleast
|
V
1
|≥
w
(
u
,
v
)
values for
|
X
|
the outputs in
V
1
when
u
=
n
m/
(
3
P
)
.But
all of the values assumed by the outputs in
V
1
must be assumed by the inputs, gates, and
crossing wires of the separator. Since at most two wires cross, a separator
C
of size
−|
U
0
|≥
n
(
1
−
3
/
2
P
)
and
v
=
|
V
1
|≥
|
C
|
has
|
C
|
|
X
|
at most 2
inputs, gates, and wires each of which can have at most
values. Thus,
if
C
1
,theseparatorfor
A
1
, has a size satisfying 2
|
C
1
|
<w
(
u
,
v
)
, a contradiction results
and the output variables in
V
1
ca
nnot assume
|
X
|
w
(
u
,
v
)
|
C
1
|≥
values.
It follows that
K
2
√
N
, this implies that
N
w
(
u
,
v
)
/
2. Since
C
1
≤
≥
w
2
(
u
,
v
)
/
(
2
K
2
)
2
, the desired
conclusion.
We apply this general result to
(
α
,
n
,
m
,
p
)
-independent functions and matrix multiplica-
tion. A function is
(
α
,
n
,
m
,
p
)
-independent (see Definition
10.4.2
)ifithasa
w
(
u
,
v
)
-flow
satisfying
w
(
u
,
v
)
>
(
v/α
)
−
1for
n
−
u
+
v
≤
p
,where
n
−
u
≥
0.
Search WWH ::
Custom Search