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

11.2.1 Playing the MHG
Figure 11.2 shows the FFT graph on eight inputs being pebbled in a three-level MHG with
resource vector p =( 2, 4 ) . Here black circles denote first-level pebbles, shaded circles denote
second-level pebbles and striped circles denote third-level pebbles. Four striped, three shaded
and two black pebbles reside on vertices in the second row of the FFT. One of these shaded
second-level pebbles shares a vertex with a black first-level pebble, so that this black pebble can
be moved to the vertex covered by the open circle without deleting all pebbles on the doubly
covered vertex.
To pebble the vertex under the open square with a black pebble, we reuse the black pebble
on the open circle by swapping it with a fourth shaded pebble, after which we place the black
pebble on the vertex that was doubly covered and then slide it to the vertex covered by the
open box. This graph can be completely pebbled with the resource vector p =( 2, 4 ) using
only four third-level pebbles, as the reader is asked to show. (See Problem 11.3 .) Thus, it can
also be pebbled in the four-level I/O-limited MHG using resource vector p = ( 2, 4, 4 ) .

11.3 I/O-Time Relationships
The following simple relationships follow from two observations. First, each input and output
vertex must receive a pebble at each level, since every input must be read from level L and
every output must be written to level L . Second, at least one computation step is needed for
each non-input vertex of the graph. Here we assume that every vertex in V must be pebbled
to pebble the output vertices.

LEMMA 11.3.1 Let α be the maximum in-degree of any vertex in G =( V , E ) and let In ( G )
and Out ( G ) be the sets of input and output vertices of G , respectively. Then any pebbling

P

of G

≤ l ≤ L :

with the MHG, whether standard or I/O-limited, satisfies the following conditions for 2

T ( L )
l

( p , G , P ) ≥| In ( G ) | + | Out ( G ) |

T ( L )
1

( p , G , P ) ≥| V |−| In ( G ) |

The following theorem relates the number of moves in an L -level game to the number in
a two-level game and allows us to use prior results. The lower bound on the level- l I/O time
is stated in terms of s l− 1 because pebbles at levels 1, 2, ... , l

−

1 are treated collectively as red
pebbles to derive a lower bound; pebbles at level l and above are treated as blue pebbles.
THEOREM 11.3.1 Let s l = l− 1

j = 1 p j . Then the following inequalities hold for every L -level

and T ( 2 )

1 ( S , G )
and T ( 2 2 ( S , G ) are the number of computation and I/O operations used by a minimal pebbling in
thered-bluepebblegameplayedon G with S red pebbles:

P

for G ,where p istheresourcevectorusedby

P

standard MHG pebbling strategy

T ( L )
l

T ( 2 )
2

( p , G , P ) ≥ ( s l− 1 , G ) for 2 ≤ l ≤ L

P

Also, the following lower bound on computation time holds for all pebbling strategies in the

standard MHG:

T ( L )
1

T ( 2 )
1

( p , G , P ) ≥ ( s 1 , G ) ,