Caches can be indexed and tagged in either address space. The choice decides whether a lookup waits for translation.
Arrangement | Index from | Tag from | Cost |
|---|---|---|---|
VIVT | Virtual address | Virtual address | No translation wait, but aliases and flushes on context switch. |
VIPT | Virtual address | Physical address | Index starts at once; tag compare waits for the TLB. |
PIPT | Physical address | Physical address | No aliasing, but every access waits for translation. |
VIPT works like PIPT when the index bits all sit inside the page offset. Those bits are identical in both addresses, so the set is selected before translation finishes.
That gives the size rule: cache size may not exceed associativity times page size. Larger caches must raise associativity, use larger pages, or go PIPT.
example: 32 KiB cache, 8-way, 64 B lines, 4 KiB pages
sets = 32768 / (8 x 64) = 32768 / 512 = 64
index bits = log2(64) = 6, block offset = log2(64) = 6
index + offset = 6 + 6 = 12 bits = page offset -> set needs no translation
rule: size <= associativity x page size = 8 x 4 KiB = 32 KiB -> holds exactly
counter-example: 64 KiB, 4-way, 64 B lines
sets = 65536 / (4 x 64) = 65536 / 256 = 256
index 8 bits + offset 6 bits = 14 bits > 12 -> 2 index bits need translationWhen index bits cross into the VPN, two virtual addresses can place one physical line in two sets. That synonym problem needs extra handling.
Systems answer with PIPT caches, higher associativity, page coloring by the OS, or hardware alias checks. Small L1 caches usually just obey the size rule.
Index plus offset is 12 bits, exactly the page offset. The set index never depends on translation.
Two. Index plus offset is 14 bits against a 12-bit page offset, so the top 2 index bits come from the VPN.