V22.0436 - Prof. Grishman

Assignment 8 - Caches


1.  (From Patterson and Hennessy, chapter 7) Consider a processor with a one-level cache with a total cache size of 16 words, making memory references to the following series of word addresses:  1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, and 17.  Label each reference as a cache hit or cache miss, and show the final contents of the cache, assuming

(a) a direct-mapped cache with 16 one-word blocks

(b) a direct-mapped cache with four-word blocks

(c)  a two-way set associative cache with one-word blocks and  LRU replacement.

(d)  a fully-associative cache with one-word blocks and LRU replacement.

2. Suppose that we have a processor where the CPI without cache misses is 1.2, that the instruction miss rate is 2%, the data fetch miss rate is 4%, and one half of the instructions contain a data fetch. Suppose the cache miss penalty is 15 cycles. What is the CPI if cache misses are taken into account?

For extra credit:  Look up the (L2) cache size of your own CPU.  Confirm that information by running the 'timer' program (Lecture 23) for array sizes slightly smaller and larger than the cache size and recording the increase in running time.  (Report in a small table the values of ARRAYSIZE, ITERATIONS, and the running time.)  For best effect, run the program with maximum optimization (gcc -O2)

Due December 11th (either by email or by hard copy in class).