The Role of Theory in Computer Science - Models of Computation: Exploring the Power of Computing - page 25

•

A pebble can be placed on an internal vertex only if all of its predecessor vertices carry
pebbles.

• The pebble moved to a vertex can be a pebble residing on one of its immediate predecessors.

•

A pebble can be removed from a vertex at any time.

•

Every output vertex must carry a pebble at some time.

Space S in this game is the maximum number of pebbles used to play the game on a
DAG. Time T is the number of times that pebbles are placed on vertices. If enough pebbles
are available to play the game, each vertex is pebbled once and T is the number of vertices in
the graph. If, however, there are not enough pebbles, some vertices will have to be pebbled
more than once. In this case a tradeoff between space and time will be exhibited.
For a particular DAG G we may seek to determine the minimum number of pebbles, S min ,
needed to place pebbles on all output vertices at some time and for a given number of pebbles S
to determine the minimum time T needed when S pebbles are used. Methods for computing
S min and bounding S and T simultaneously have been developed. For example, the four-
point (four-input) fast Fourier transform (FFT) graph shown in Fig. 1.10 has S min = 3and
can be pebbled in the minimum number of steps with five pebbles.
Let the FFT graph of Fig. 1.10 be pebbled with the minimum number S of pebbles.
Initially no pebbles reside on the graph. Thus, there is a first point in time at which S pebbles
reside on the graph. The dark gray vertices identify one possible placement of pebbles at such
a point in time. The light gray vertices will have had pebbles placed on them prior to this time
and will have to be repebbled again later to pebble output vertices that cannot be reached from
the placement of the dark gray vertices. This demonstrates that for this graph if the minimum
number of pebbles is used, some vertices will have to be repebbled. Although the n -point
FFT graph, n a power of two, has only n log n + n vertices, we show in Section 10.5.5 that its
vertices must be repebbled enough times that S and T satisfy ( S + 1 ) T

n 2 / 16. Thus, either
S is much larger than the minimum space or T is much larger than the number of vertices
or both.

≥

7 15 8 16

3 11 6 14

1,9 2,10 4,12 5,13
Figure 1.10 A pebbling of a four-input FFT graph at the point at which the maximum num-
ber of pebbles (three) is used. Numbers specify the order in which vertices can be pebbled. A
maximum of three pebbles is used. Some vertices are pebbled twice.