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

Hint: Compare pebble placement with and without the requirement that placements
be simple, arguing that if a pebble removed by a simple I/O operation is needed later it
can be obtained by one simple I/O operation for each of the original I/O operations.

TRADEOFFS IN THE MEMORY HIERARCHIES

11.11 Using the results of Problem 11.8 , derive good upper and lower bounds on the I/O
time to pebble the pyramid graph of Fig. 11.18 in terms of n .
11.12 Under the conditions of Problem 11.4 , show that any pebbling of a DAG for convolu-
tion of n -sequences with the minimal pebbling strategy when S

S min and n is large
has much larger total cost than a strategy that treats blue pebbles as red pebbles.

≥

BLOCK I/O IN THE MHG

11.13 Determine how efficiently matrix-vector multiplication can be done in the block-I/O
model described in Section 11.6 .
11.14 Show that matrix-matrix multiplication can be done efficiently in the block-I/O model
described in Section 11.6 .

SIMULATING FAST MEMORIES

11.15 Determine conditions on a memory hierarchy under which the FFT can be executed
efficiently in the standard MHG. Discuss the extent to which these conditions are likely
to be met in practice.
11.16 Repeat the previous problem for convolution realized by the algorithm stated in the
convolution theorem.
11.17 The definition of a minimal pebbling stated in Section 11.2 assumesthatitismuch
more expensive to perform a high-level I/O operation than a low-level one. Determine
the extent to which the lower bound of Theorem 11.4.1 depends on this assumption.
Apply your insight to the problem of matrix multiplication of n × n matrices in the

three-level MHG in which s 1 < 3 n 2 and s 2 3 n 2 .(SeeTheorem 11.5.3 .) Determine

whether increasing the number of level-3 I/O operations affects the number of level-2
I/O operations.

≥

THE BLOCK-TRANSFER MODEL

11.18 Derive a lower bound on the time to realize a permutation network on n inputs in the
block-transfer model.
Hint: Count the number of orderings possible between the n inputs. Base your argu-
ment on the number of orderings within blocks and between elements in the primary
memory, and the number of ways of choosing which block from the secondary memory
to move into the primary memory.
11.19 Derive a lower bound on the time to realize the FFT graph on n inputs in the block-
transfer model.
Hint: Use the result of Section 7.8.2 to argue that an n -point FFT graph cannot have
many fewer vertices than there are switches in a permutation network.