Information Technology Reference
In-Depth Information
Proof
Any minimal pebbling strategy for
G
1
can be used to pebble
G
0
by simulating moves
on a chain with pebble placements on the vertex to which vertices on the chain are coalesced
and by honoring the edge restrictions of
G
1
that are removed to create
G
0
. Since this strategy
for
G
1
may not be minimal for
G
0
, the inequalities follow.
11.4 The Hong-Kung Lower-Bound Method
In this section we derive lower limits on the I/O time at each level of a memory hierarchy
needed to pebble a directed acyclic graph with the MHG. These results are obtained by com-
bining the inequalities of Theorem
11.3.1
with a lower bound on the I/O and computation
time for the red-blue pebble game.
Theorem
10.4.1
provides a framework that can be used to derive lower bounds on the I/O
time in the red-blue pebble game. This follows because the lower bounds of Theorem
10.4.1
are stated in terms of
T
I
, the number of times inputs are pebbled with
S
red pebbles, which
is also the number of I/O operations on input vertices in the red-blue pebble game. It is
important to note that the lower bounds derived using this framework apply to every straight-
line program for a problem.
In some cases, for example matrix multiplication, these lower bounds are strong. However,
in other cases, notably the discrete Fourier transform, they are weak. For this reason we intro-
duce a way to derive lower bounds that applies to a particular graph of a problem. If that graph
is used for the problem, stronger lower bounds can be derived with this method than with the
techniques of Chapter
10
. We begin by introducing the
S
-span of a DAG.
DEFINITION
11.4.1
Given a DAG
G
=(
V
,
E
)
,the
S
-span of
G
,
ρ
(
S
,
G
)
, is the maximum
number of vertices of
G
that can be pebbled with
S
pebbles in the red pebble game maximized over
all initial placements of
S
red pebbles. (The initialization rule is disallowed.)
The following is a slightly weaker but simpler version of the Hong-Kung [
137
]lower
bound on I/O time for the two-level MHG. This proof divides computation time into con-
secutive intervals, just as was done for the space-time lower bounds in the proofs of Theo-
rems
10.4.1
and
10.11.1
.
THEOREM
11.4.1
For every pebbling
P
of the DAG
G
=(
V
,
E
)
inthered-bluepebblegame
with
S
red pebbles, the I/O time used,
T
(
2
)
2
(
S
,
G
,
P
)
, satisfies the following lower bound:
T
(
2
)
2
(
S
,
G
)
/S
ρ
(
2
S
,
G
)
≥|
V
|−|
In
(
G
)
|
P
{P
1
,
P
2
,
...
,
P
h
}
Proof
Divide
,whereeach
sub-pebbling has
S
I/O operations except possibly the last, which has no more such opera-
tions. Thus,
h
=
into consecutive sequential sub-pebblings
T
(
2
)
2
(
S
,
G
,
P
)
/S
.
We now develop an upper bound
Q
to the number of vertices of
G
pebbled with red
pebbles in any sub-pebbling
P
j
. This number multiplied by the number
h
of sub-pebblings
is an upper bound to the number of vertices other than inputs,
|
V
|−|
In
(
G
)
|
,thatmustbe
pebbled to pebble
G
. It follows that
Qh
≥|
V
|−|
In
(
G
)
|
The upper bound on
Q
is developed by adding
S
new red pebbles and showing that
we may use these new pebbles to move all I/O operations in a sub-pebbling
P
t
to either
Search WWH ::
Custom Search