Memory-Hierarchy Tradeoffs - Models of Computation: Exploring the Power of Computing - page 538

the beginning or the end of the sub-pebbling without changing the number of computation
steps or I/O operations. Thus, without changing them, we move all computation steps to a
middle interval of

P t , between the higher-level I/O operations.
We now show how this may be done. Consider a vertex v carrying a red pebble at some
time during

P t (vertex 7 at
step 11 in Fig. 11.3 ). Instead of pebbling v with a blue pebble, use a new red pebble to
keep a red pebble on v . (This is equivalent to swapping the new and old red pebbles on v .)
This frees up the original red pebble to be used later in the sub-pebbling. Because we attach
a red pebble to v for the entire pebbling

P t that is pebbled for the first time with a blue pebble during

P t can
be deleted except for the last such operation, if any, which can be moved to the end of the
interval. Note that if after v is given a blue pebble in

P t , all later output operations from v in

P

, it is later given a red pebble, this red
pebbling step and all subsequent blue pebbling steps except the last, if any, can be deleted.
These changes do not affect any computation step in

P t .
Consider a vertex v carrying a blue pebble at the start of

P t is given a
red pebble (see vertex 4 at step 12 in Fig. 11.3 ). Consider the first pebbling of this kind.
The red pebble assigned to v may have been in use prior to its placement on v .Ifanew
red pebble is used for v , the first pebbling of v with a red pebble can be moved toward
the beginning of

P t that later in

P t so that, without violating the precedence conditions of G ,itprecedes
all placements of red pebbles on vertices without pebbles. Attach this new red pebble to v
during

P t . Subsequent placements of red pebbles on v when it carries a blue pebble during
P t , if any, are thereby eliminated.

9 10 11 12

5 6 7 8

1 2 3 4

P t

tep12345678910 11 12 13

Pebble R1 R2 R2 B R2 R2 R1 B R2 R2 B R2 R2

↓ ↓ ↑ ↓ ↓ ↑ ↓ ↑ ↓

Ve r t e x 1 25 5 26 3 6 4 7 7 48

Step 14 15 16 17 18 19 20 21 22 23

Pebble R1 R2 R2 R2 R2 R1 R2 R2 R2 R2

Ve r t e x ↓ 5 ↓ 79 ↓ 7 1 ↓ 6 ↓ 8 0 ↓ 8 2

Figure 11.3 The vertices of an FFT graph are numbered and a pebbling schedule is given in
which the two numbered red pebbles are used. Up (down) arrows identify steps in which an
output (input) occurs; other steps are computation steps. Steps 10 through 13 of the schedule

P t
contain two I/O operations. With two new red pebbles, the input at step 12 can be moved to the
beginning of the interval and the output at step 11 can be moved after step 13.