Information Technology Reference
In-Depth Information
bounds exist on the semellective planar circuit size of the characteristic predicates of the con-
volution, cyclic shift, integer multiplication, discrete Fourier transform, matrix multiplication
functions, and many others.
12.8 Area Bounds
We now derive lower bounds on the area used by semellective VLSI chip algorithms for a
variety of functions. For the functions considered here, these bounds are linear in their number
of variables. As explained in the Chapter Notes, not all functions are amenable to the type of
analysis presented in this section.
The technique used to derive area lower bounds is similar to that used in Section
10.4.2
to derive lower bounds on the exchange of space for time in the pebble game. If a chip has
many I/O ports, it has large area. On the other hand, if it has a small number of ports, the
inputs to the function computed are received over many cycles. If the function has a large
w
(
u
,
v
)
-flow, by direct analogy with the pebble game, the area must be large to insure that
enough information be stored between cycles.
THEOREM
12.8.1
Let
β ≥
1
.If
f
:
X
n
X
m
has a
w
(
u
,
v
)
-flow, every chip computing
f
requires area
A
= Ω(min((
m/
2
β
)
,
w
(
u
,
v
)))
,where
u
=
n
(
1
→
1
/β
)
and
v
=(
m/
4
β
)
.
Proof
If the chip has
π
I/O pads or can store
S
values over the alphabet
X
, it has area
A
−
≥
λ
2
min(
π
,
S
)
.Fix
β
≥
1. Its value is chosen later to provide a strong lower bound. If
π
≥
w
(
u
,
v
)
when
π<m/
2
β
.
Let the VLSI algorithm have
T
time steps and let
h
i
≤
m/
2
β
, we are done. Thus, we show that
S
≥
π
outputs be generated on the
i
th time step, 1
T
.Create
q
intervals of consecutive time steps as follows: The first
interval contains the first
k
1
time steps, where
k
1
is such that the total number of outputs
produced during the first
k
1
steps is as large as possible without exceeding
m/β
. Successive
intervals are created in the same way, namely by grouping consecutive later time steps to
satisfy the same requirement on the number of outputs produced. For all intervals except
possibly the last, the number of outputs produced is at least
(
m/β
)
≤
i
≤
π
+
1
>
(
m/
2
β
)
.
If the last interval contains fewer than
(
m/
2
β
)
outputs, redistribute the elements in the last
two intervals, of which there are at least
(
m/β
)
−
(
m/
2
β
)+
2, so that each has at
least
(
m/
4
β
)+
1 outputs. It follows that the number of intervals,
q
, satisfies
β
−
π
+
2
≥
4
β
.
We now examine the inputs read during intervals. Since there are
n
inputs to be read
and each is read once, the average number read per interval is
n/q
which is at most
n/β
.It
follows that there is some interval
I
in which at least
(
m/
4
β
)+
1 outputs are pebbled and
at most
n/β
inputs are read.
Fix the inputs that are read during
I
. The remaining inputs, of which there are at least
u
=
n
(
1
≤
q
≤
1
/β
)
, are free to vary. The number of outputs produced during
I
is at least
v
=(
m/
4
β
)
.Since
f
has a
w
(
u
,
v
)
-flow, if
S<w
(
u
,
v
)
,the
v
outputs, whose values are
determined by the values stored on the chip at the beginning of
I
, cannot assume all their
values. It follows that
S
−
≥
w
(
u
,
v
)
, which is the desired conclusion.
We now apply this bound to
(
α
,
n
,
m
,
p
)
-independent functions. Later we apply it to the
matrix multiplication function.
THEOREM
12.8.2
Let
f
:
X
n
X
m
be
(
α
,
n
,
m
,
p
)
-independent. It requires area
A
=
→
λ
2
((
mp/
(
n
+
m/
4
)
α
)
−
1
)
when realized by a semellective VLSI algorithm.
Search WWH ::
Custom Search