Can there be a cache block with the same Tag-ID in different Sets?

Question

I am currently investigating some previous exams for my CA course.

There is one question which i found really confusing, here is the the data to work with:

Considering a 32-bit address (tag 20bits, index 7 bits, byte offset 5bits) with a 4 way set associative cache. The two least significant address bits are always zero.

Cache is initially empty and when fetching it always hits. Its a write back cache which always transfers complete blocks with an allocate on write miss policy.

There is the trace to work with in hex:

Read 0770 3718 – write 0770 3704 – read 0770 3768 - [...]

Now to my question:

When looking at the first 3 statements only:

Trace	Tag	Set	Offset
07703718	0000 0111 0111 0000 0011	0111 000	1 1000
07703704	0000 0111 0111 0000 0011	0111 000	0 0100
07703768	0000 0111 0111 0000 0011	0111 011	0 1000

I am likely doing something wrong., but i thought that there cant be the same tag within different / multiple sets.

I looked at Computer Architecture: A quantitative approach but all there all the examples match.

Answer 1

There is nothing wrong in this case.

Tags could be the same in the different sets, actually that is one of the reasons for seperating address as Tag-Set-Offset in caches.

Storing of the first X bit as tags and AddressWidth-X-OffsetWidth bits as set index, so you can place the consecutive addresses without making any placement issue.

Think about an uint32 type array with 128 depth. (uint32_t array[256] in C) And assume that array[0] is addressed as 0x30 00 00 00.

So: array[1] is 0x30 00 00 04. array[2] is 0x30 00 00 08. array[3] is 0x30 00 00 0c. array[4] is 0x30 00 00 10. array[5] is 0x30 00 00 14.

In my example, the least significant hexadecimal number is the offset, and 2 hexadecimal number left of this are the set. Assume the cacheline width is 128 bit (4 Words).

So the first 4 word of array will be placed in set 0x00 in cache. The second 4 word will be placed in set 0x01 in cache. By that way, we use depth of the case as an advantage.

If you choose to place the second 4 on the same set and modify them in time, when another consecutive read/write operations comes to different tags with the same index (as starting with 0x80 00 00 00), you should evict all of the cache lines in that set.

Generally cache depths are 128-256 lines. If you did place the as i said, 256 sets for array[255] and array_next[255], you won't evict the first array[255] and the other array.

It would be easier to reach the first array again.

Also bus won't be busy for that 256 evictions. Win & Win.

Answer 2

I think you're doing it right.

Remember that the index is part of the address, so cache lines can represent different addresses even with the same tag.  Tag + index portions together identify a 32-byte range of main memory, while the offset says which starting byte in the 32-byte range.

In your example, the first two addresses are in the same 32-byte range of main memory, so the 2nd access is a hit.  That 32-byte block is caching main memory address range 0x07703700 through 0x0770371F.

The third address is in a wholly different main memory address range (it doesn't fall in the range for the prior two accesses) so that maps to a different index, the tag being the same is irrelevant.  That 32-byte block is caching main memory address range 0x07703760 to 0x0770377F.

The 4-way cache mechanism will always look for addresses 0x07703718 & 0x07703704 at index position 0x38, and, for address 0x07703768 at index position 0x3b.  So, there's no conflict with having the same tags at those two separate index positions.