Given the following stream of accesses to a 4-block fully associative cache with LRU replacement, determine whether the access is a hit or a miss. If it is a hit, write "hit". If it is a compulsory miss, write "compulsory", and similarly for conflict and capacity misses. Assume the cache is initially empty and all addresses are block addresses (that is, the offset is omitted). 0x1111 0x1000 0x1234 0x0000 0xab23 0x1234 0x0000 0x1111 0x1000 0x1234

The number of memory miss cycles for instructions in terms of the Instruction count (I) is

image

As the frequency of all loads and stores is 36%, we can find the number of memory miss cycles for data references:

image

The total number of memory-stall cycles is 2.00 I+1.44 I=3.44 I. This is more than three cycles of memory stall per instruction. Accordingly, the total CPI including memory stalls is 2+3.44=5.44. Since there is no change in instruction count or clock rate, the ratio of the CPU execution times is

image

The performance with the perfect cache is better byimage.

What happens if the processor is made faster, but the memory system is not? The amount of time spent on memory stalls will take up an increasing fraction of the execution time; Amdahl’s Law, which we examined in Chapter 1, reminds us of this fact. A few simple examples show how serious this problem can be. Suppose we speed-up the computer in the previous example by reducing its CPI from 2 to 1 without changing the clock rate, which might be done with an improved pipeline. The system with cache misses would then have a CPI of 1+3.44=4.44, and the system with the perfect cache would be

image

The amount of execution time spent on memory stalls would have risen from

image

to

image

Similarly, increasing the clock rate without changing the memory system also increases the performance lost due to cache misses.