Information Technology Reference
In-Depth Information
shows a graph
G
for a 2
×
2 matrix multiplication algorithm in which the product vertices
are those just below the output vertices. The black vertices carry pebbles. In this example
r
=
2and
p
=
1. While
p
+
r
−
1
=
2, only one pebble placement is possible on addition
trees in this example.)
Given the dependencies of graphs in
F
n
, there is no loss in generality in assuming that
product vertices are pebbled before pebbles are advanced in addition trees. It follows that at
most
p
+
r
addition-tree vertices carry pebbles before pebbles are advanced in addition trees.
These pebbled vertices define subtrees of vertices that can be pebbled from the
p
+
r
initial
pebble placements. Since a binary tree with
n
leaves has
n
−
1 non-leaf nodes, it follows
that if there are
t
such trees, at most
p
+
r
t
pebble placements will be made, not counting
the original placement of pebbles. This number is maximized at
t
=
1. (See Problem
11.9
.)
We now complete the proof by deriving an upper bound on
p
.Let
−
n
matrix whose
(
i
,
j
)
entry is 1 if the variable in the
(
i
,
j
)
position of the matrix
A
carries a
pebble initially and 0 otherwise. Let
A
−
1
n
×
be the 0
B
be similarly defined for
B
. It follows that the
(
i
,
j
)
entry,
δ
i
,
j
, of the matrix product
, where addition and multiplication are over
the integers, is equal to the number of products that can be formed that contrib
u
te to the
C
=
A×B
√
S
(
S
(
i
,
j
)
entry of the result matrix
C
.Thus
p
=
i
,
j
δ
i
,
j
. We now show that
p
≤
−
r
)
.
Let
A
and
B
have
a
and
b
1's, respectively, where
a
+
b
=
S
−
r
.Thereareatmost
a/α
rows of
containing at least
α
1's. The maximum number of products that can be formed
from such rows is
ab/α
because each 1 in
A
B
combine with a 1 in each of these rows. Now
consider the product of other rows of
.Atmost
S
such row-column
inner products are formed since at most
S
outputs can be pebbled. Since each of them
involves a row with at most
α
1's, at most
αS
products of pairs of variables can be formed.
Thus, a total of at most
p
=
ab/
α
+
α
S
products can be formed. We are free to choose
A
with columns of
B
α
to minimize this sum (
α
=
ab/S
does this) but must choose
a
and
b
to maximize it
(
a
=(
S
√
S
(
S
−
r
)
/
2 satisfies this requirement). The res
ult
is that
p
≤
−
r
)
.Wecomplete
2
√
SS
for
r
the proof by observing that
π
=
2
p
+
r
−
1
≤
≥
0.
Theorem
11.5.2
states bounds that apply to the computation and I/O time in the red-blue
pebble game for matrix multiplication.
THEOREM
11.5.2
For every graph
G
in the family
F
n
of inner product graphs for multiplying
two
n
×
n
matrices and for every pebbling strategy
P
for
G
in the
red-blue pebble game
that
uses
S
≥
3
red pebbles, the computation and I/O-time satisfy the following lower bounds:
T
(
2
)
1
)=Ω(
n
3
)
(
S
,
G
,
P
)=Ω
n
3
T
(
2
)
2
(
S
,
G
,
P
√
S
Furthermore, there is a pebbling strategy
P
for
G
with
S
≥
3
red pebbles such that the following
upper bounds hold simultaneously:
T
(
2
)
1
)=
O
(
n
3
)
(
S
,
G
,
P
)=
O
n
3
T
(
2
)
2
(
S
,
G
,
P
√
S
The lower bound on I/O time stated above applies for
every graph
of a straight-line program for
matrix multiplication in the
I/O-limited red-blue pebble game
. The upper bound on I/O time
Search WWH ::
Custom Search