Information Technology Reference
In-Depth Information
In the I/O-limited case the following lower bounds apply, where
α
is the maximum fan-in of any
vertex of
G
:
T
(
L
)
l
T
(
2
)
2
(
p
,
G
,
P
)
≥
(
s
l−
1
,
G
)
for
2
≤
l
≤
L
T
(
2
2
(
s
L−
1
,
G
)
/α
Proof
The first set of inequalities is shown by considering the red-blue game played with
S
=
s
l−
1
red pebbles and an unlimited number of blue pebbles. The
S
red pebbles and
s
L−
1
−
T
(
L
)
1
(
p
,
G
,
P
)
≥
1groupswith
p
j
pebbles in the
j
th
group, so that we can simulate the steps of an
L
-level MHG pebbling strategy
S
blue pebbles can be classified into
L
−
P
.Because
there are constraints on the use of pebbles in
,thisstrategyusesanumberoflevel-
l
I/O
operations that cannot be larger than the minimum number of such I/O operations when
pebbles at level
l
P
1 or less are treated as red pebbles and those at higher levels are treated
as blue pebbles. Thus,
T
(
L
)
l
−
T
(
2
)
2
(
p
,
G
,
P
)
≥
(
s
l−
1
,
G
)
. By similar reasoning it follows that
T
(
L
)
1
T
(
2
1
(
s
1
,
G
)
.
In the above simulation, blue pebbles simulating levels
l
and above cannot be used arbi-
trarily when the I/O-limitation is imposed. To derive lower bounds under this limitation, we
classify
S
=
s
L−
1
pebbles into
L
(
p
,
G
,
P
)
≥
1groupswith
p
j
pebbles in the
j
th group and simulate
in the red-blue pebble game the steps of an
L
-level I/O-limited MHG pebbling strategy
−
P
.
The I/O time at level
l
is no more than the I/O time in the two-level I/O-limited red-blue
pebble game in which all
S
red pebbles are used at level
l
1 or less.
Since the number of blue pebbles is unlimited, in a minimal pebbling all I/O operations
consist of placing of red pebbles on blue-pebbled vertices. It follows that if
T
I/O operations
are performed on the input vertices, then at least
T
placements of red pebbles on blue-
pebbled vertices occur. Since at least one internal vertex must be pebbled with a red pebble
in a minimal pebbling for every
α
input vertices that are red-pebbled, the computation time
is at least
T/α
. Specializing this to
T
=
T
(
2
)
2
−
(
s
L−
1
,
G
)
for the I/O-limited MHG, we have
the last result.
It is important to note that the lower bound to
T
(
2
)
1
(
S
,
G
,
P
)
for the I/O-limited case is
not stated in terms of
|
V
|
,because
|
V
|
may not be the same for each values of
S
. Consider the
multiplication of two
n
n
matrices. Every graph of the standard algorithm can be pebbled
with three red pebbles, but such graphs have about 2
n
3
vertices, a number that cannot be
reduced by more than a constant factor when a constant number of red pebbles is used. (See
Section
11.5.2
.) On the other hand, using the graph of Strassen's algorithm for this problem
requires at least
Ω(
n
.
38529
)
pebbles, since it has
O
(
n
2
.
807
)
vertices.
We close this section by giving conditions under which lower bounds for one graph can
be used for another. Let a
reduction
of DAG
G
1
=(
V
1
,
E
1
)
be a DAG
G
0
=(
V
0
,
E
0
)
,
V
0
×
E
1
, obtained by deleting edges from
E
1
and coalescing the non-terminal
vertices on a “chain” of vertices in
V
1
into the first vertex on the chain. A
chain
is a sequence
v
1
,
v
2
,
...
,
v
r
of vertices such that, for 2
⊆
V
1
and
E
0
⊆
≤
i
≤
r
−
1,
v
i
is adjacent to
v
i−
1
and
v
i
+
1
and no
other vertices.
LEMMA
11.3.2
Let
G
0
be a reduction of
G
1
. Then for any minimal pebbling
P
min
and
1
≤
l
≤
L
, the following inequalities hold:
T
(
L
)
l
T
(
L
)
l
(
p
,
G
1
,
P
min
)
≥
(
p
,
G
0
,
P
min
)
Search WWH ::
Custom Search