Information Technology Reference
In-Depth Information
Lower bounds on
AT
2
and
A
2
T
also exist for matrix multiplication. From Lemma
10.5.3
we know that the matrix multiplication function
f
(
n
)
A
2
n
2
n
2
R
→R
has a
w
(
u
,
v
)
-flow,
B
:
×
where
w
(
u
,
v
)
u
)
2
/
4
n
2
)
/
2. Using this we have the following lower bound on
the planar circuit size of this function.
≥
(
v
−
(
2
n
2
−
THEOREM
12.7.3
The area
A
and time
T
required to compute the matrix multiplication function
f
(
n
)
2
n
2
n
2
A×B
:
R
→R
with a semellective VLSI algorithm satisfies the following lower bound:
AT
2
,
A
2
T
=Ω(
n
4
)
The
AT
2
lower bound can be met to within a constant multiplicative factor.
Proof
Apply Theorem
12.7.1
to matrix multiplication by replacing the number of input
variables
n
by 2
n
2
and the number of output variables
m
by
n
2
.The
w
(
u
,
v
)
-flow function
has value
1
3
P
−
2
3
2
P
n
2
2
(
2
n
2
u
)
2
/
4
n
2
)
/
2
w
(
u
,
v
)=(
v
−
−
≥
The right-hand side is maximized when
P
=
14 and has value greater than
n
2
/
163, from
which the conclusion follows.
AsshowninSection
7.5.3
,two
n
n
matrix can be multiplied with area
A
=
O
(
n
2
)
and
time
T
=
n
, which meets the lower bound up to a multiplicative factor. Other near-optimal
solutions also exist. (See Problem
12.15
.)
×
12.7.2 The Performance of VLSI Algorithms on Predicates
The approach taken above can be extended to predicates, functions whose range is
B
.Again
we derive lower bounds on the size of the smallest planar circuit for a function. However, since
the flow of information from inputs to outputs is at most one bit, we must find some other
way to measure the amount of information that must be exchanged between the two halves
of a planar circuit. An extension of the communication complexity measure introduced in
Section
9.7.1
serves this purpose.
The communication complexity measure of Section
9.7.1
assumes that two players ex-
change bits to compute the value of a Boolean function
f
:
n
B
→B
. The input variables
of
f
are partitioned into two sets
U
and
V
and assigned to two players. Given this partition,
the players choose a protocol (a scheme for alternating the transmission of bits from one to
the other) by which to decide the value of
f
for every input
n
-tuple of
f
.Thebitsofeach
n
-tuple are partitioned between the two players according to the division of the
n
input vari-
ables between the sets
U
and
V
. The players then use their protocol to determine the value of
f
.The
communication complexity
C
(
U
,
V
)
of this game is the minimum over protocols of
the maximum over input
n
-tuples of the number of bits exchanged by the players to compute
f
given the partition of the input variables into sets
U
and
V
. This measure and its associated
game are naturally extended to predicates
f
:
X
n
, whose variables assume values over
the set
X
. Players now exchange values drawn from the set
X
.
We can derive a lower bound on planar circuit size by applying the planar separator theo-
rem. Since this theorem partitions the input variables into three sets,
A
,
B
, and a separator
C
,
where
A
and
B
contain at most two-thirds of the total number of input vertices, it is natural
→B
Search WWH ::
Custom Search