Question 53

In a virtually indexed, physically tagged (VIPT) cache, synonyms (different virtual addresses mapping to the same physical address) can map to different cache sets if the cache set index uses bits outside the page offset.

1. Cache geometry:

   • Cache size = 1 MB $= 2^{20}$ bytes.
   • 16-way set associative: Associativity $= 16 = 2^4$.
   • Block size = 64 bytes $= 2^6$ bytes. Block offset requires 6 bits (bits 0 to 5).
   • Total number of blocks in cache:
     $$\dfrac{2^{20}}{2^6} = 2^{14}\text{ blocks}$$
   • Number of sets in cache:
     $$\dfrac{2^{14}}{2^4} = 2^{10}\text{ sets}$$
   • Hence, the cache set index requires 10 bits.
   • The cache index bits are bits 6 through 15 of the address.

2. Page offset:

   • From Question 52, page size is 8 KB $= 2^{13}$ bytes.
   • The page offset consists of bits 0 to 12 (13 bits).

3. Overlapping index bits:

   • Bits 6 through 12 of the cache set index fall within the page offset and are identical between virtual and physical addresses.
   • Bits 13, 14, and 15 (3 bits) fall within the virtual page number and can differ between synonyms.
   • To ensure that synonyms always map to the same cache set, the operating system must align these 3 bits (page coloring).
   • Minimum number of page colours required:
     $$2^3 = 8\text{ colours}$$

This corresponds to option (C).