V22.0436 - Prof. Grishman

Assignment 8 - Caches

1.  (From Patterson and Hennessy, chapter 5) 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 (assuming the ache is initially empty), 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 40% of the instructions contain a data fetch. Suppose the cache miss penalty is 25 cycles. What is the CPI if cache misses are taken into account?

3. Consider the following C code.  Approximately how many cache misses would occur running this program on a machine with a

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

(b) a direct-mapped 4K word (16KB) cache with 4-word (16B) blocks

(c) a direct-mapped 8K word (16KB) cache with 4-word (16B) blocks

(where K = 1024).

#define ARRAYSIZE 8192
#define ITERATIONS 10

int ray[ARRAYSIZE];
int sum;

main() {
    int iter, i;
    for (iter=0; iter<ITERATIONS; iter++)
        for (i=0; i<ARRAYSIZE; i++)
            sum += ray[i];

Due December 8th.

Submit your homework in class or mail it (plain text or Word file) to  grishman@cs.nyu.edu and mark the mail CompArch -- Asgn 8.