Information Technology Reference
In-Depth Information
P
is the execution of the rules of the pebble game on the vertices of
a graph. We assign a step to each placement of a pebble, ignoring steps on which pebbles are
removed, and number the steps consecutively. The
space
used by a strategy
A
pebbling strategy
P
is defined as
the maximum number of red pebbles it uses. The
I/O time
,
T
2
,of
P
on the graph
G
is the
P
.The
computation time
,
T
1
,isthenumber
number of input and output (I/O) steps used by
on
G
. Note that time in the red pebble game is the time to place red
pebbles on input and internal vertices; in this chapter the former are called
I/O operations
.
Since accesses to secondary memory are assumed to require much more time than accesses
to primary memory, a
minimal pebbling strategy
,
P
of computation steps of
P
min
, performs the minimal number of
I/O operations on a graph
G
for a given number of red pebbles and uses the smallest number
of red pebbles for a given I/O time. Furthermore, such a strategy also uses the smallest number
of computation steps among those meeting the other requirements. We denote by
T
(
2
)
1
(
S
,
G
)
and
T
(
2
2
(
S
,
G
)
the number of computation and I/O steps in a minimal pebbling of
G
in the
red-blue pebble game with
S
red pebbles.
The minimum number of red pebbles needed to play the red-blue pebble game is the
maximum number of predecessors of any vertex. This follows because blue pebbles can be used
to hold all intermediate results. Thus, in the FFT graph of Fig.
11.1
only two red pebbles are
needed, since one of them can be slid to the vertex being pebbled. However, if the minimum
number of pebbles is used, many expensive I/O operations are necessary.
In Section
11.2
we generalize the red-blue pebble game to multiple levels and consider two
variants of the model, one in which all levels including the highest can be used for intermediate
storage, and a second in which the highest level cannot be used for intermediate storage. The
second model (the
I/O-limited game
) captures aspects of the red-blue pebble game as well as
the red pebble game of Chapter
10
.
An important distinction between the pebble game results obtained in this chapter and
those in Chapter
10
is that here lower bounds are generally derived for particular graphs,
whereas in Chapter
10
they are obtained for all graphs of a problem.
Figure 11.1
An eight-input FFT graph showing three two-input FFT subgraphs.
Search WWH ::
Custom Search