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

PEBBLING MODELS

11.3 Show that the graph of Fig. 11.2 can be completely pebbled in the three-level MHG
with resource vector p =( 2, 4 ) using only four third-level pebbles.
11.4 Consider pebbling a graph with the red-blue game. Suppose that each I/O operation
uses twice as much time as a computation step. Show by example that a red-blue
pebbling minimizing the total time to pebble a graph does not always minimize the
number of I/O operations.

I/O TIME RELATIONSHIPS

11.5 Let S min be the minimum number of pebbles needed to pebble the graph G =( V , E )
in the red pebble game. Show that if in the MHG a pebbling strategy

P

uses s k pebbles

1, then no I/O operations at level k + 1or
higher are necessary except on input and output vertices of G .
11.6 The rules of the red-blue pebble game suggest that inputs should be prefetched from
high-level memory units early enough that they arrive when needed. Devise a schedule
for delivering inputs so that the number of I/O operations for matrix multiplication is
minimized in the red-blue pebble game.

at level k or less and s k ≥

S min + k −

THE HONG-KUNG LOWER-BOUND METHOD

11.7 Derive an expression for the S -span ρ ( S , G ) of the binary tree G shown in Fig. 11.4 .
11.8 Consider the pyramid graph G on n inputs shown in Fig. 11.18 . Determine its S -span
ρ ( S , G ) as a function of S .
11.9 In Problem 2.3 it is shown that every binary tree with k leaves has k − 1 internal vertices.

1 pebbling steps are
possible on these trees from an arbitrary initial placement without re-pebbling inputs.
Hint: The vertices that can be pebbled from an initial placement of pebbles form a set
of binary trees.
11.10 An I/O operation is simple if after a pebble is placed on a vertex the pebble currently
residing on that vertex is removed. Show that at most twice as many I/O operations are
used at each level by the MHG when every I/O operation is simple.

Show that if t binary trees have a total of p pebbles, at most p −

n

Figure 11.18 The pyramid graph.