Virtually indexed physically tagged cache Synonym

Question

I am not able to entirely grasp the concept of synonyms or aliasing in VIPT caches.

Consider the address split as:-

Here, suppose we have 2 pages with different VA's mapped to same physical address(or frame no).

The pageno part of VA (bits 13-39) which are different gets translated to PFN of PA(bits 12-35) and the PFN remains same for both the VA's as they are mapped to same physical frame.

Now the pageoffset part(bits 0-13) of both the VA's are same as the data which they want to access from a particular frame no is same.

As the pageoffset part of both VA's are same, bits (5-13) will also be same, so the index or set no is the same and hence there should be no aliasing as only single set or index no is mapped to a physical frame no.

How is bit 12 as shown in the diagram, responsible for aliasing ? I am not able to understand that.

It would be great if someone could give an example with the help of addresses.

---

Note: this diagram has a minor error that doesn't affect the question: 36 - 12 = 24-bit tags for 36-bit physical addresses, not 28. MIPS64 R4x00 CPUs do in fact have 40-bit virtual, 36-bit physical addresses, and 24-bit tags, according to chapters 4 and 11 of the manual.

This diagram is from http://www.cse.unsw.edu.au/~cs9242/02/lectures/03-cache/node8.html which does label it as being for MIPS R4x00.

Pentamerous

Answer 1

The page offset is bits 0-11, not 0-13. Look at your bottom diagram: the page offset is the low 12 bits, so you have 4k pages (like x86 and other common architectures).

If any of the index bits come from above the page offset, VIPT no longer behaves like a PIPT with free translation for the index bits. That's the case here.

A process can have the same physical page (frame) mapped to 2 different virtual pages.

Your claim that The pageno part of VA (bits 13-39) which are different gets translated to PFN of PA(bits 12-35) and the PFN remains same for both the VA's is totally bogus. Translation can change bit #12. So one of the index bits really is virtual and not also physical, so two entries for the same physical line can go in different sets.

---

I think my main confusion is regarding the page offset range. Is it the same for both PA and VA (that is 0-11) or is it 0-12 for VA and 0-11 for PA? Will they always be same?

It's always the same for PA and VA. The page offset isn't marked on the VA part of your diagram, only the range of bits used as the index.

It wouldn't make sense for it to be any different: virtual and physical memory are both byte-addressable (or word-addressable). And of course a page frame (physical page) is the same size as a virtual page. Right or left shifting an address during translation from virtual to physical would make no sense.

---

As discussed in comments:

I did eventually find http://www.cse.unsw.edu.au/~cs9242/02/lectures/03-cache/node8.html (which includes the diagram in the question!). It says the same thing: physical tagging does solve the cache homonym problem as an alternative to flushing on context switch.

But not the synonym problem. For that, you can have the OS ensure that bit 12 of every VA = bit 12 of every PA. This is called page coloring.

Page coloring would also solve the homonym problem without the hardware doing overlapping tag bits, because it gives 1 more bit that's the same between physical and virtual address. phys idx = virt idx. (But then the HW would be relying on software to be correct, if it wanted to depend on this invariant.)

---

Another reason for having the tag overlap the index is write-back during eviction:

Outer caches are almost always PIPT, and memory itself obviously needs the physical address. So you need the physical address of a line when you send it out the memory hierarchy.

A write-back cache needs to be able to evict dirty lines (send them to L2 or to physical RAM) long after the TLB check for the store was done. Unlike a load, you don't still have the TLB result floating around unless you stored it somewhere. How does the VIPT to PIPT conversion work on L1->L2 eviction

Having the tag include all the physical address bits above the page offset solves this problem: given the page-offset index bits and the tag, you can construct the full physical address.

(Another solution would be a write-through cache, so you do always have the physical address from the TLB to send with the data, even if it's not reconstructable from the cache tag+index. Or for read-only caches, e.g. instruction caches, there is no write-back; eviction = drop.)

Coalition

Maybe your explanation is obvious but still I didn't get you. Can you please explain with an example (With 2 different VA addresses)? Also, in VA, we divide the address into 2 parts pageno and pageoffset, as 14-39 is pageno, 0-13 should be pageoffset right ? – Pentamerous

@Zephyr: I think you're misreading your diagram. Your lower diagram shows the divide between pageno and offset is between bit 11 and bit 12. So the low 12 bits (0-11) of physical/virtual addresses are the offset, and the 13th bit (bits #12) and higher are the page number. The pageno part of VA is 12-38 (the 13th to 39th bit). This is what you got wrong. One of the pageno bits is part of the index. – Coalition

It appears the tag and index overlap, though. I haven't thought much about how you'd actually design a VIPT cache that isn't also a PIPT with free translation (and thus avoids all aliasing), by having cache size <= associativity * page size so the index bits all come from page offset bits of addresses. – Coalition

Yeah, I was misreading the diagram. Actually my doubt is how is the bit between the dotted lines responsible for aliasing. Because the page offset bits for VA and PA are not exactly same. – Pentamerous

@Zephyr: Because it has to be translated. So your claim that The pageno part of VA (bits 13-39) which are different gets translated to PFN of PA(bits 12-35) and the PFN remains same for both the VA's is totally bogus. Translation can change bit #12. So one of the index bits really is virtual and not also physical, so two entries for the same physical line can go in different sets. – Coalition

Actually I saw Udacity video from Georgia tech which says that 2 or more VA's having different page no's may map to same PFN and that causes the problem. – Pentamerous

@Zephyr: That's exactly what I just said. Two mappings (VAs) for the same physical page (PFN) will go to different sets. So a store to one page might not affect the data read later by a load from the other page. – Coalition

I don't understand how will they go to different sets. Both VA's have different pageno but map to same PFN and read the same data from the same offset inside the frame. So both VA's will have exactly same page offset even though their pageno's are different and hence set index number is also same. – Pentamerous

@Zephyr: The problem is that one of the index bits comes from the pageno bits, not the offset. This is what the dotted line is showing you: that the range of index bits extends past the page offset. – Coalition

I think my main confusion is regarding the page offset range. Is it the same for both PA and VA (that is 0-11) or is it 0-12 for VA and 0-11 for PA ? Will they always be same ? – Pentamerous

@Zephyr: It's the same for PA and VA. The page offset isn't marked on the VA part of your diagram, only the index. It wouldn't make sense for it to be any different: virtual and physical memory are both byte-addressable (or word-addressable). – Coalition

I appreciate your patience in replying to my comments. One last question, is frameno in PA = TAG always or is it just for these caches and we generally have frameno = TAG + indexno. – Pentamerous

@Zephyr: You always need the tag to include all bits above the index to correctly detect hits, regardless of where the page split is or VIVT / PIPT. I'm not sure why this cache is using a tag that overlaps with the index. Maybe that lets them detect some kinds of aliasing? VIPT caches often have size and associativity that puts the top of the index right at the page split (cache size = associativity * page size, e.g. the 32kiB 8-way L1D/L1I in Intel CPUs for many years, and in AMD Ryzen. x86 uses 4k pages). But if you had a smaller L1, the tag would include some page-offset bits. – Coalition

Thanks ! This picture is just an example of aliasing and so they have purposely overlapped the index and tag bits. Otherwise, if they are different then VIPT caches work fine. Till now I was repeatedly asking you questions thinking that pageoffset bits for both VA and PA are different :P – Pentamerous

@Zephyr: tag/index overlap is not what causes aliasing! It's caused by having the index include bits above the page offset. (And yeah, I was about to start ignoring any more comments since I didn't know what else to say besides tell you that the index included a non-offset bit. Glad you finally clued in and figured out what you were missing.) – Coalition

@Zephyr: I was curious so I googled for index tag overlap (no luck) then just thought about the implications: Using the whole pageno as the tag (even if the index also includes some of those bits) avoids the need for cache invalidation after changing a mapping in the page tables. (Same virtual address now points to a different physical address). Same virt addr goes to the same set, but tag won't match it's a different phys page (frame). This wouldn't be reliable if the tag didn't include all the frameno bits. – Coalition

I did eventually find cse.unsw.edu.au/~cs9242/02/lectures/03-cache/node8.html (which includes the diagram in the question!). It says the same thing: physical tagging does solve the cache homonym problem as an alternative to flushing on context switch. But not the synonym problem. For that, you can have the OS ensure that bit 12 of every VA = bit 12 of every PA. This is called page coloring. It would also solve the homonym problem without the hardware doing overlapping tag bits, because it gives 1 more bit that's the same between physical and virtual address. phys idx = v idx. – Coalition