Information Technology Reference
In-Depth Information
The sixth and seventh rules of the new game allow the placement of level-
L
pebbles only on
output vertices. The two-level version of the I/O-limited MHG is the one-pebble game studied
in Chapter
10
. As mentioned earlier, we call the two-level I/O-limited MHG the
red pebble
game
to distinguish it from the red-blue pebble game and the MHG. Clearly the multi-level
I/O-limited MHG is a generalization of both the standard MHG and the one-pebble game.
The I/O-limited MHG models the case in which accesses to the highest level memory take
so long that it should be used only for archival storage, not intermediate storage. Today disks
are so much slower than the other memories in a hierarchy that the I/O-limited MHG is the
appropriate model when disks are used at the highest level.
The
resource vector
p
=(
p
1
,
p
2
,
...
,
p
L−
1
)
associated with a pebbling strategy
P
speci-
fies the number of
l
-level pebbles,
p
l
,usedby
P
. We say that
p
l
is the
space
used at level
l
by
P
. We assume that
p
l
≥
≤
l
≤
L
, so that swapping between levels is possible. The
1for1
and resource vector
p
,
T
(
L
)
l
I/O time
at level
l
with pebbling strategy
L
,
with both versions of the MHG is the number of inputs from and outputs to level
l
.The
com-
putation time
with pebbling strategy
P
(
p
,
G
,
P
)
,2
≤
l
≤
and resource vector
p
,
T
(
L
)
1
P
(
p
,
G
,
P
)
,intheMHG
P
is the number of times first-level pebbles are placed on vertices by
. Since there is little risk of
confusion, we use the same notation,
T
(
L
)
l
(
p
,
G
,
P
)
, in the standard and I/O-limited MHG
for the number of computation and I/O steps.
The definition of a minimal MHG pebbling is similar to that for a red-blue pebbling.
Given a resource vector
p
,
P
min
is a
minimal pebbling
for an
L
-level MHG if it minimizes
the I/O time at level
L
, after which it minimizes the I/O time at level
L
1, continuing in
this fashion down to level 2. Among these strategies it must also minimize the computation
time. This definition of minimality is used because we assume that the time needed to move
data between levels of a memory hierarchy grows rapidly enough with increasing level that it is
less costly to repebble vertices at or below a given level than to perform an I/O operation at a
higher level.
−
Figure 11.2
Pebbling an eight-input FFT graph in the three-level MHG.
Search WWH ::
Custom Search