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 fully associative cache

20 0010 0000
04 0000 0100
28 0010 1000
4C 0100 1100

Here is the format that we use for the address enter image description here

I am not quite sure what the addr field is for but I am assuming its the actual address in RAM.(Please correct me if this is wrong)

I know that it can't be apart of the TAG because the TAG portion is made up of bits and C in one of the example addresses above is not a bit(it's a hex digit)

Here is the table I made thus far to store my results.

enter image description here

The red entry I highlighted was the entry I am not sure about. I know that with 3 index bits, the cache will have 8 cache lines. When the CPU goes to the cache for the third address, will it be a hit because the tag already exists(1st cache line) and not add that data or will be a miss and the data will be added because the cache isn't full yet?

  • $\begingroup$ I'm not sure, but I think it's a miss. In full associative cache every tag can appear only once, as this is the identification of the data. Thus, for 20H, the "TAG" must be 001000, while for 28H, the tag is 001010 which is different. The splitting these 6 bits to tag+index makes sense when you have smaller associativity or direct map. I may be wrong on this, but maybe the "format" you use as given needs more thought. $\endgroup$
    – Ran G.
    Jun 4, 2015 at 22:52
  • 2
    $\begingroup$ Furthermore, I recommend merging this question with cs.stackexchange.com/questions/43131 into a single question that asks how associativity works. Please don't spray us with multiple small or similar questions - take the time to ask about the concept you don't understand, that will solve the questions in all these posts.. $\endgroup$
    – Ran G.
    Jun 4, 2015 at 22:55
  • $\begingroup$ You're right about the miss. I just realized that the tag would include the index as well. That questions about direct mapped cache and n way set cache. This one's just about fully associative. I don't think they should be combined. $\endgroup$ Jun 4, 2015 at 23:09