Space–Time Tradeoffs - Models of Computation: Exploring the Power of Computing - page 462

10.1 The Pebble Game
The pebble game is a game played on directed acyclic graphs (DAGs), which capture the
dependencies of straight-line programs studied in Chapters 2 and 6 . Algorithms for many
important problems, such as the FFT and matrix multiplication, are naturally computed by
straight-line programs. In the pebble game pebbles are placed on vertices of a DAG to indicate
that the value associated with a vertex resides in a register. Pebbles are placed on vertices in a
data-independent order.
In this game a pebble can be placed on an input vertex at any time and on any non-input
vertex whose immediate predecessor vertices carry pebbles. The goal of the game is to place
pebbles on each output vertex. A pebble can be removed from a vertex, including an output
vertex, at any time after it has been pebbled. These rules are summarized below.

The rules of the pebble game are the following:

•

(Initialization) A pebble can be placed on an input vertex at any time.

•

(Computation Step) A pebble can be placed on (or moved to) any non-input vertex only
if all its immediate predecessors carry pebbles.

• (Pebble Deletion) A pebble can be removed at any time.

• (Goal) Each output vertex must be pebbled at least once.

Placement of a pebble on an input vertex models the reading of input data. Placement of
a pebble on a non-input vertex corresponds to computing the value associated with the vertex.
The removal of a pebble models the erasure or overwriting of the value associated with the
vertex on which the pebble resides.
Allowing pebbles to be placed on input vertices at any time reflects the assumption that
inputs are readily available. (The multi-level pebble game introduced in the next chapter
models the case in which each access to secondary storage is expensive.) The condition that
all predecessor vertices carry pebbles when a pebble is placed on a vertex models the natural
requirement that an operation can be performed only after all arguments of the operation
are located in main memory. Moving (or sliding ) a pebble to a vertex from an immediate
predecessor reflects the design of CPUs that allow the result of a computation to be placed in
a memory location holding an operand.
A pebbling strategy 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 from 1 to T ,the time or number of steps in
the strategy. The space , S , used by a pebbling strategy is the maximum number of pebbles
it uses. The goal of the pebble game is to pebble a graph with values of space and time that
are minimal; that is, the space cannot be reduced for the given value of time and vice versa.
In general, it is not possible to minimize space and time simultaneously. We derive upper and
lower bounds on the possible exchanges of space for time.

10.1.1 The Pebble Game Versus the Branching Program
As stated above, the branching program model introduced in Section 10.9 handles data-
dependent computation, and is thus a more general model than the pebble game. However,
there are three reasons to study the pebble game. First, the branching program assumes that