Exercise 5.8 This exercise examines the impact of different cache designs, specifi cally comparing associative caches to the direct-mapped caches from Section 5.2. For these exercises, refer to the table of address streams shown in Exercise 5.3.

5.8.1 [10] <5.3> Using the references from Exercise 5.3, show the fi nal cache contents for a three-way set-associative cache with two-word blocks and a total size of 24 words. Use LRU replacement. For each reference identify the index bits, the tag bits, the block offset bits, and if it is a hit or a miss.

5.8.2 [10] <5.3> Using the references from Exercise 5.3, show the fi nal cache contents for a fully associative cache with one-word blocks and a total size of eight words. Use LRU replacement. For each reference identify the index bits, the tag bits, and if it is a hit or a miss.

5.8.3 [15] <5.3> Using the references from Exercise 5.3, what is the miss rate for a fully associative cache with two-word blocks and a total size of eight words, using LRU replacement? What is the miss rate using MRU (most recently used)

replacement? Finally what is the best possible miss rate for this cache, given any replacement policy?

Multilevel caching is an important technique to overcome the limited amount of space that a fi rst level cache can pro vide while still maintaining its speed. Consider a processor with the following parameters:

Base CPI, no memory stalls Processor speed Main memory access time First-level cache miss rate per instruction Second-level cache, direct-mapped speed Global miss rate with second-level cache, direct-mapped Second-level cache, eight-way set associative speed Global miss rate with second-level cache, eight-way set associative

a. 2.0 3 GHz 125 ns 5% 15 cycles 3.0% 25 cycles 1.8%

b. 2.0 1 GHz 100 ns 4% 10 cycles 4.0% 20 cycles 1.6%

5.8.4 [10] <5.3> Calculate the CPI for the processor in the table using: 1) only a fi rst-level cache, 2) a second-level direct-mapped cache, and 3) a second-level eight-way set-associative cache. How do these numbers change if main memory access time is doubled? If it is cut in half ?

5.8.5 [10] <5.3> It is possible to have an even greater cache hierarchy than two levels. Given the processor above with a second-level, direct-mapped cache, a designer wants to add a third-level cache that takes 50 cycles to access and will reduce the global miss rate to 1.3%. Would this provide better performance? In general, what are the advantages and disadvantages of adding a third-level cache?
5.8.6 [20] <5.3> In older processors such as the Intel Pentium or Alpha 21264, the second level of cache was external (located on a different chip) from the main processor and the fi rst-level cache. While this allowed for large second-level caches, the latency to access the cache was much higher, and the bandwidth was typically lower because the second-level cache ran at a lower frequency. Assume a 512 KB offchip second-level cache has a global miss rate of 4%. If each additional 512 KB of cache lowered global miss rates by 0.7%, and the cache had a total access time of 50 cycles, how big would the cache have to be to match the performance of the secondlevel direct-mapped cache listed in the table? Of the eight-way set-associative cache?