CSE 141 Ungraded Homework # 4

Recommended "due date" - March 1.

Consider the following sequence of memory references: 16, 4, 40, 32, 0, 8, 44, 16. Each reference is the byte address for a 4-Byte word. There is a 32 Byte cache and the line length is 8 Bytes. Simulate this cache (by hand) to determine which memory references are hits and misses, and the final contents of cache, under the following assumptions:
- The cache is direct mapped.
- The cache is 2-way set associative with LRU replacement.
- The cache is fully associative with LRU replacement.
In general, having higher associativity leads to fewer cache misses. However, this general rule doesn't always hold true. Consider the following code:
```
   for (i=0; i<10; i++)
      for (j=0; j<600; j++)
         sum += a[i]*b[j];
```
Suppose all data items are 4 Bytes long, and there is a 2KB cache with a line size of 16 Bytes.
- Suppose the cache is fully-associative with LRU replacement. Approximately how many cache misses will there be? (Don't bother counting misses associated with the "a" array or the scalars i, j, and sum. Assume the cache is initially empty.)
- Now suppose the cache is direct mapped. Approximately how many cache misses will there be?