Information Technology Reference
In-Depth Information
Proof
We apply Theorem
12.8.1
with
u
=
n
(
1
−
1
/β
)
and
v
=(
m/
4
β
)
.Because
f
is
(
α
,
n
,
m
,
p
)
independent,
w
(
u
,
v
)
>v/α
−
1for
n
−
u
+
v
≤
p
.Since
n
−
u
=
n/β
and
v
=(
m/
4
β
)
, this implies that
β
(
n
+
m/
4
)
/p
. The lower bound of Theorem
12.8.1
then is the smaller of
(
m/
2
β
)
and
(
m/
4
αβ
)
≥
1. Since we are free to choose
β
, we choose
it to make the smaller of the two as large as possible. In particular, we set
β
=(
n
+
m/
4
)
/p
,
which provides the desired result.
−
Because all of the
(
α
,
n
,
m
,
p
)
-independent functions listed in Theorem
12.7.2
have
n
,
m
,and
p
proportional to one another, each requires area
A
=Ω(
n
)
,asstatedbelow. It
follows that the lower bound
AT
2
=Ω(
n
2
)
for these problems canno
t b
e achieved to within
a constant multiplicative factor if
T
grows more rapidly with
n
than
√
n
.
COROLLARY
12.8.1
The functions
f
(
n
)
wrapped
n
,
f
(
n
)
cyclic
2
n
n
+
log
n
→B
n
,
:
R
→R
:
B
f
(
n
)
mult
2
n
2
n
,and
F
n
:
n
n
:
B
→B
R
→R
each require area
A
=Ω(
n
)
when realized by a
semellective VLSI algorithm.
A similar result applies to matrix multiplication.
THEOREM
12.8.3
The area
A
required to compute the matrix multiplication function
f
(
n
)
A×B
:
2
n
2
n
2
with a semellective VLSI algorithm satisfies
A
=Ω(
n
2
)
R
→R
Proof
We apply Theorem
12.8.1
with
n
and
m
replaced by 2
n
2
and
n
2
, respectively. Since
u
=
2
n
2
(
1
1
/β
)
and
v
=(
n
2
/
4
β
)
, the lower bound on
w
(
u
,
v
)
-flow for matrix multi-
plication function satisfies the following
−
1
4
β
−
β
2
n
2
2
1
(
2
n
2
u
)
2
/
4
n
2
)
/
2
w
(
u
,
v
)=(
v
−
−
≥
The lower bound is a positive multiple of
n
2
if
β>
4andlargestfor
β
=
8, from which
the desired conclusion follows.
.......................................
Problems
VLSI COMPUTATIONAL MODELS
12.1 Assume the I/O ports are on the periphery of a convex chip. In the speed-of-light model
show that if
p
such ports all have paths to some point on the chip, then the time for
data supplied to each port to reach that point is
Θ(
p
)
.
12.2 Under the assumptions of Problem
12.1
, derive a lower bound on the time to compute
afunction
f
on
n
inputs under the additional assumption that there is a path on the
chip from the port at which each variable arrives to the port at which
f
is produced.
Hint:
Show that the time required is at least the sum of the number of cycles needed
to read all
n
inputs and the time for data to travel across the chip. State these times in
terms of
p
and choose
p
to maximize the smaller of these two lower bounds.
Search WWH ::
Custom Search