In a set associative cache (in this case 4-way) what happens when you try to read an entry with e.g. the tag 0x3B and this tag appears two times within the same set. Given the first is invalid, would you search on for the second (which is valid) or simply get a miss? And why do would there be a duplicate line at all?

enter image description here


2 Answers 2


The CPU tests all caches ways and selects the one that is both valid and have a matching tag address. It may occur concurrently on all ways or be sequential (with a preferred way, depending on the address)

When invalidating cache lines, only the valid bit needs to be cleared, the tag address value do not need to be modified, so it may contain stray values.

(Cache lines may be invalidated by the operating system for coherency with some DMA peripherals, because of self-modifying code, by hardware cache coherency algorithms like MEI/MESI, etc. Depends on the architecture.)

You cannot have several lines that are simultaneously valid and with the same tag address [and different data].

It may occur at power-up, if registers are not automatically reinitialized, and the boot sequence may have to manually clear the cache before enabling it using special accesses and/or instructions.

  • $\begingroup$ The CPU tests the cache? $\endgroup$
    – Ran G.
    Jul 22, 2015 at 0:51
  • $\begingroup$ Well, test is not a good term. The cache controller compares the address of the current address with the address field of the tags and, if it matches and if the corresponding valid bit is set, then it is a hit and the read or write operation can be completed. $\endgroup$
    – Grabul
    Jul 22, 2015 at 19:27

The cache usually performs the tag comparison in parallel, and the same tag is not supposed to be in two different locations. However, since the valid bit is off at one place, it may be the case that the same tag appears more than one, where only one of the places is valid.

In fact, if the valid bit is off there is no reason to even compare that tag—even if it matches, the result will be a miss, similar to the case the tag was not found). So the most rational behavior here, is that the "valid" bit enables the selection of that cell, and cells with valid=0 are excluded form the tag comparison circuit.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.