Information Technology Reference
In-Depth Information
LEMMA
12.7.1
Let
f
:
X
n
→
X
m
be
(
α
,
n
,
m
,
p
)
-independent. Then for
P
≥
(
m/
3
+
3
n/
2
)
/p
and
m
≥
2
α
,
f
has semellective planar circuit size satisfying the following lower bound:
m
2
144
(
αP
)
2
K
2
Proof
f
has a
w
(
u
,
v
)
-flow satisfying
w
(
u
,
v
)
>
(
v/α
)
C
p
,
Ω
(
f
)
≥
−
1for
n
−
u
+
v
≤
p
.When
u
≥
n
(
1
−
3
/
2
P
)
,
n
−
u
+
v
≤
p
is satisfied if
v
≤
p
−
3
n/
(
2
P
)
. Since we also require
that
v
≥
m/
(
3
P
)
, this implies that
P
≥
(
m/
3
+
3
n/
2
)
/p
.Also,
v/α
−
≥
v/
2
α
if
1
v
≥
2
α
. Substituting
m/
3
P
for
v
, we have the desired conclusion.
In Section
10.5
we have shown that many functions are
(
α
,
n
,
m
,
p
)
-independent. We
summarize these results below.
Name
Function
Independence Property
f
(
n
)
2
n
n
Wrapped convolution
wrapped
:
R
→R
(
2, 2
n
,
n
,
n/
2
)
f
(
n
)
n
+
log
n
n
Cyclic shift
cyclic
:
B
→B
(
2,
n
+
log
n
,
n
,
n/
2
)
f
(
n
)
2
n
2
n
Integer multiplication
mult
:
B
→B
(
2, 2
n
,
n
,
n/
2
)
n
n
n
-point DFT
F
n
:
R
→R
(
2,
n
,
n
,
n/
2
)
m/
(
6
α
)
.Thus,eachofthe
(
α
,
n
,
m
,
p
)
-independent function has a planar circuit size that is quadratic in
n
,itsnumber
of inputs. The following theorem results from this observation and Theorem
12.6.1
.
It follows that for each case Lemma
12.7.1
holds when
P
≤
THEOREM
12.7.2
The area
A
and time
T
required to compute
f
(
n
)
wrapped
2
n
n
,
:
R
→R
f
(
n
)
cyclic
n
,
f
(
n
)
mult
n
+
log
n
→B
2
n
2
n
,and
F
n
:
n
n
:
B
:
B
→B
R
→R
on a semellec-
tive VLSI chip satisfy the following bounds:
AT
2
,
A
2
T
=Ω(
n
2
)
The
AT
2
lower bound can be a
ch
ieved up to a constant multiplicative factor for each of these
functions for
Ω(log
n
)
≤
√
n
.
Proof
From Theorem
12.5.1
we know t
ha
t any fully normal algorithm can achieve the
AT
2
=
O
(
n
2
)
for
Ω(log
n
)=
T
=
O
(
√
n
)
on an embedded CCC network. Since cyclic
shift and FFT are shown to be fully normal (see Section
7.7
), we have matching upper and
lower bounds for them. From Problem
12.13
we have that the wrapped convolution can
be realized with matching bounds on
AT
2
overthesamerangeofvaluesfor
T
.Thesame
statement applies to integer multiplication (see Problem
12.16
).
≤
T
In Section
12.6.1
we said that we would exhibit a function whose planar circuit size is
nearly quadratic in its standard circuit size. This property holds for the cyclic shifting function
because, as shown in Section
2.5.2
,
f
(
n
)
n
has circuit size no larger than
O
(
n
log
n
)
, whereas from the above its planar circuit size is
Θ(
n
2
)
.
The cyclic shift function is also a
n exampl
e of a function for which most of the chip area
n
+
log
n
→B
cyclic
:
B
is occupied by wires when
T
=
O
(
n/
log
n
)
, because in this case the area is
Ω(
n
log
n
)
but
the number of gates needed to realize it is
O
(
n
log
n
)
.
Search WWH ::
Custom Search