Question

Given the following word addresses: 3, 180, 43, 2,191, 88, 190, 14, 181, 44, 186, 253

a. Show the final 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.
b. Show the final cache contents for a fully associative cache with one-word blocks and a total size of 8 words. Use LRU replacement. For each reference identify the index bits, the tag bits, and if it is a hit or a miss.
c. What is the miss rate for a fully associative cache with two-word blocks and a total size of 8 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?

Answer 1

A. index bits = 2, tag bits = 2, block offset bits = 1, it is a miss.

B. index bits = 2, tag bits = 1, block offset bits = 0, it is a hit

C. the miss rate is 0

Step-by-step explanation:

a. number of blocks = 12

number of blocks per set = 3

number of set = number of blocks / number of blocks per set = 12/3 = 4

word size = 24

block size = 2

the block offset =
`log_(2)` block size

=
`log_(2)` 2 = 1

the index bits =
`log_(2)` number of set =
`log_(2)` 4 = 2

the tag bits = (
`log_(2)` word size) - offset - index = (
`log_(2)` 24) -2 - 1 = 5 -2 - 1 = 2

b. word size = 8

block size = 1

the block offset =
`log_(2)` block size

=
`log_(2)` 1 = 0

the index bits =
`log_(2)` number of set =
`log_(2)` 4 = 2

the tag bits = (
`log_(2)` word size) - offset - index = (
`log_(2)` 8) -2 - 1 = 3 - 0- 2= 1