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:
- 00010001
- 01101011
- 00111111
- 01001000
- 00011001
- 01000010
- 10001001
- 00000000
- 01001000
- 00011100
- 00110000
- 11111100
- 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:
- Miss, stored in set 4, block 0
- Miss, stored in set 2, block 0
- Miss, stored in set 7, block 0
- Miss, stored in set 2, block 1
- Miss, stored in set 6, block 0
- Miss, stored in set 0, block 0
- Miss, stored in set 2, block 0 (block 0 was LRU, now block 1 becomes LRU)
- Miss, stored in set 0, block 1
- Hits on set 2, block 1
- Miss, stored in set 7, block 1
- Miss, stored in set 6, block 1
- Miss, stored in set 7, block 0 (block 0 was LRU, now block 1 becomes LRU)
- 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.
- 000_100_01
- 000_010_01
- 000_001_10
- 000_001_01
- 001_010_11
- 000_001_00
- 000_010_11
- 000_010_01
- 001_110_00
- 000_100_11
- 000_000_01
- 000_101_11
- 011_010_11
Which should like:
- Miss, stored in set 4 block 0
- Miss, stored in set 2 block 0
- Miss, stored in set 1 block 0
- Miss, stored in set 1 block 1, block 0 becomes LRU
- Miss, stored in set 2 block 1, block 0 becomes LRU
- Miss, stored in set 1 block 0, block 1 becomes LRU
- Miss, stored in set 2 block 0, block 1 becomes LRU
- Hit, set 2 block 0 becomes LRU
- Miss, stored in set 6 block 0
- Miss, stored in set 4 block 1
- Miss, stored in set 0 block 0
- Miss, stored in set 5 block 0
- Miss, stored in set 2 block 0, block 1 becomes LRU