Information Technology Reference
In-Depth Information
11.1 The Red-Blue Pebble Game
The red-blue pebble game models data movement between adjacent levels of a two-level mem-
ory hierarchy. We begin with this model to fix ideas and then introduce the more general
memory-hierarchy game. Both games are played on a directed acyclic graph, the graph of a
straight-line program. We describe the game and then give its rules.
In the red-blue game, (hot) red pebbles identify values held in a fast primary memory
whereas (cold) blue pebbles identify values held in a secondary memory. The values identified
with the pebbles can be words or blocks of words, such as the pages used by an operating
system. Since the red-blue pebble game is used to study the number of I/O operations necessary
for a problem, the number of red pebbles is assumed limited and the number of blue pebbles is
assumed unlimited. Before the game starts, blue pebbles reside on all input vertices. The goal
is to place a blue pebble on each output vertex, that is, to compute the values associated with
these vertices and place them in long-term storage. These assumptions capture the idea that
data resides initially in the most remote memory unit and the results must be deposited there.
RED-BLUE PEBBLE GAME
•
(Initialization) A blue pebble can be placed on an input vertex at any time.
•
(Computation Step) A red pebble can be placed on (or moved to) a vertex if all its imme-
diate predecessors carry red pebbles.
•
(Pebble Deletion) A pebble can be deleted from any vertex at any time.
•
(Goal) A blue pebble must reside on each output vertex at the end of the game.
•
(Input from Blue Level) A red pebble can be placed on any vertex carrying a blue pebble.
•
(Output to Blue Level) A blue pebble can be placed on any vertex carrying a red pebble.
The first rule (
initialization
) models the retrieval of input data from the secondary mem-
ory. The second rule (a
computation step
) is equivalent to requiring that all the arguments
on which a function depends reside in primary memory before the function can be computed.
This rule also allows a pebble to move (or
slide
) to a vertex from one of its predecessors, mod-
eling the use of a register as both the source and target of an operation. The third rule allows
pebble deletion
: if a red pebble is removed from a vertex that later needs a red pebble, it must
be repebbled.
The fourth rule (the
goal
) models the placement of output data in the secondary memory
at the end of a computation. The fifth rule allows data held in the secondary memory to be
moved back to the primary memory (an
input operation
). The sixth rule allows a result to
be copied to a secondary memory of unlimited capacity (an
output operation
). Note that a
result may be in both memories at the same time.
The red-blue pebble game is a direct generalization of the pebble game of Section
10.1
(which we call the
red pebble game
), as can be seen by restricting the sixth rule to allow
the placement of blue pebbles only on vertices that are output vertices of the DAG. Under
this restriction the blue level cannot be used for intermediate results and the goal of the game
becomes to minimize the number of times vertices are pebbled with red pebbles, since the
optimal strategy pebbles each output vertex once.
Search WWH ::
Custom Search