The Problem: A CPU produces the following sequence of read addresses in hex.
Suppose the cache is empty to begin with and assuming an LRU replacement, determine whether each address produces a hit or miss for a) direct mapped cache b) fully associative cache c) two way set associative cache.
20 0010 0000
04 0000 0100
28 0010 1000
60 0110 0000
20 0010 0000
Here is the table of my work thus far (ones I highlighted are ones I am unsure about)
I know that because the cache is empty to begin with, the first five read addresses will produce produces because the addresses are not already in the cache.
I'am having trouble with the last address. The last address is a repeat of the first address. I know that in fully associative deals with the collision problem by allowing a memory location to go into any cache line so the first won't get overwritten and a hit will be produced.
For directly mapped, how can you tell if the first address has been overwritten or not? I know that LRU replacement is being used so if there was a collision, the first address would get overwritten. But I am not sure if there would be collision within the first five addresses(you don't have access to the number of cache lines.
For two set associative, how would you identify which sets each address belongs to? There could be different interpretations. Like you could see, reading from left to right, bits 4-5 match in addresses starting with 20, 28, 60 so 20 would get overwritten, producing a miss. At the same time, a different interpretation could lead to the conclusion that the first doesn't get replaced.