two way set associative cache referencing using lru

basil picture basil · Nov 5, 2013 · Viewed 8.1k times · Source

I am trying to understand how caching works. I am working on a problem to better understand this concept:

Given a 2 way set associative cache with blocks 1 word in length, with the total size being 16 words of length 32-bits, is initially empty, and uses the least recently used replacement strategy. Show whether the following addresses hit or miss and list the final contents of the cache.

Addresses:

  1. 00010001
  2. 01101011
  3. 00111111
  4. 01001000
  5. 00011001
  6. 01000010
  7. 10001001
  8. 00000000
  9. 01001000
  10. 00011100
  11. 00110000
  12. 11111100
  13. 00111010

First off, with the given information, it seems to me that there will be 2 offset bits, 3 set bits, and 3 tag bits in the following order (T=tag,S=set,O=offset): TTTSSSOO

Example (address 1):

Tag=000 (0), Set = 100 (4), Offset = 01 (1)

Now, assuming this is correct, the following should happen when the above addresses are looked up:

  1. Miss, stored in set 4, block 0
  2. Miss, stored in set 2, block 0
  3. Miss, stored in set 7, block 0
  4. Miss, stored in set 2, block 1
  5. Miss, stored in set 6, block 0
  6. Miss, stored in set 0, block 0
  7. Miss, stored in set 2, block 0 (block 0 was LRU, now block 1 becomes LRU)
  8. Miss, stored in set 0, block 1
  9. Hits on set 2, block 1
  10. Miss, stored in set 7, block 1
  11. Miss, stored in set 6, block 1
  12. Miss, stored in set 7, block 0 (block 0 was LRU, now block 1 becomes LRU)
  13. Miss, stored in set 6, block 0 (block 0 was LRU, now block 1 becomes LRU)

And the final contents of the cache should look like the following:

Set 0: 01000010, 00000000

Set 1: empty, empty

Set 2: 10001001, 01001000

Set 3: empty, empty

Set 4: 00010001, empty

Set 5: empty, empty

Set 6: 00111010, 00110000

Set 7: 11111100, 00011100

I am having a very difficult time with this so hopefully someone can let me know if I am on the right track or not. If these look ok, I want to try the same exercise but with different addresses for further practice, to make sure that I've got it.

EDIT1: New addresses.

  1. 000_100_01
  2. 000_010_01
  3. 000_001_10
  4. 000_001_01
  5. 001_010_11
  6. 000_001_00
  7. 000_010_11
  8. 000_010_01
  9. 001_110_00
  10. 000_100_11
  11. 000_000_01
  12. 000_101_11
  13. 011_010_11

Which should like:

  1. Miss, stored in set 4 block 0
  2. Miss, stored in set 2 block 0
  3. Miss, stored in set 1 block 0
  4. Miss, stored in set 1 block 1, block 0 becomes LRU
  5. Miss, stored in set 2 block 1, block 0 becomes LRU
  6. Miss, stored in set 1 block 0, block 1 becomes LRU
  7. Miss, stored in set 2 block 0, block 1 becomes LRU
  8. Hit, set 2 block 0 becomes LRU
  9. Miss, stored in set 6 block 0
  10. Miss, stored in set 4 block 1
  11. Miss, stored in set 0 block 0
  12. Miss, stored in set 5 block 0
  13. Miss, stored in set 2 block 0, block 1 becomes LRU

Answer