Information Technology Reference
In-Depth Information
also applies for this game. The computation time in the I/O-limited red-blue pebble game satisfies
the following bound:
)=Ω
n
3
T
(
2
)
1
(
S
,
G
,
P
√
S
Proof
For the standard MHG, the lower bound to
T
(
2
)
1
(
S
,
G
,
P
)
follows from the fact that
F
n
has
Θ(
n
3
)
vertices and Lemma
11.3.1
.Thelowerboundto
T
(
2
)
every graph in
(
S
,
G
)
2
follows from Corollary
11.4.1
and Lemma
11.5.1
and the lower bound to
T
(
2
)
1
(
S
,
G
,
P
)
for the I/O-limited MHG follows from Theorem
11.3.1
.
We now describe a pebbling strategy that has the I/O time stated above and
uses
the
obvious algorithm suggested by Fig.
11.6
.If
S
red pebbles are available, let
r
=
S/
3
be
an integer that divides
n
.(If
r
does not divide
n
,embed
A
,
B
and
C
in larger matrices for
which
r
does divide
n
. This requires at most doubling
n
.) Let the
n
×
n
matrices
A
,
B
and
C
be partitioned into
n/r
×
n/r
matrices; that is,
A
=[
a
i
,
j
]
,
B
=[
b
i
,
j
]
,and
C
=[
c
i
,
j
]
,
whose entries are
r
×
r
matrices. We form the
r
×
r
submatrix
c
i
,
j
of
C
as the inner product
of a row of
r
×
r
submatrices of
A
with a column of such submatrices of
B
:
r
c
i
,
j
=
a
i
,
q
×
b
q
,
j
q
=
1
We begin by placing blue pebbles on each entry in matrices
A
and
B
.Compute
c
i
,
j
by
computing
a
i
,
q
×
b
q
,
j
for
q
=
1, 2,
...
,
r
and adding successive products to the running
sum. Keep
r
2
red pebbles on the running sum. Compute
a
i
,
q
×
b
q
,
j
by placing and holding
r
2
red pebbles on the entries in
a
i
,
q
and
r
red pebbles on one column of
b
q
,
j
at a time. Use
two additional red pebbles to compute the
r
2
inner products associated with entries of
c
i
,
j
in the fashion suggested by Fig.
11.4
if
r
2 and one additional pebble if
r
=
1. The
maximum number of red pebbles in use is 3 if
r
=
1andatmost2
r
2
+
r
+
2if
r
≥
≥
2.
Since 2
r
2
+
r
+
2
2, in both cases at most 3
r
2
re
d pe
bbles are needed. Thus,
there are enough red pebbles to play this game because
r
=
3
r
2
for
r
≤
≥
S/
3
implies that 3
r
2
≤
S
,
the number of red pebbles. Since
r
≥
1, this requires that
S
≥
3.
n
n
×
n
C
=
A
B
Figure 11.6
A pebbling schema for matrix multiplication based on the representation of a
matrix in terms of block submatrices. A submatrix of
C
is computed as the inner product of a
row of blocks of
A
with a column of blocks of
B
.
Search WWH ::
Custom Search