GATE CS 2013 Q53 — Memory Management and Virtual Memory

To find the minimum number of page colors, we first need to determine the page size and then analyze the cache indexing structure.

Step 1: Determine the Page Size

Let the page size be $2^p$ bytes, so the page offset is $p$ bits. Since the physical address is $32$ bits, a page table entry (PTE) of $32$ bits ($4$ bytes) is sufficient to store a physical page frame address.

• The number of entries per page of a page table is $\frac{2^p}{2^2} = 2^{p-2}$.
• Thus, each level of the page table index ($d_1, d_2, d_3$) requires $p-2$ bits.

The virtual address is split as follows:

So, the page offset is $13$ bits, and the page size is $2^{13} = 8\text{ KB}$.

Step 2: Determine Cache Parameters

• Cache Size = $1\text{ MB} = 2^{20}$ bytes
• Block Size = $64\text{ bytes} = 2^6$ bytes
• Associativity = $16 = 2^4$
• Number of Sets = $\frac{\text{Cache Size}}{\text{Block Size} \times \text{Associativity}} = \frac{2^{20}}{2^6 \times 2^4} = 2^{10}$ sets

To index the cache, we need:

• Block offset = $6$ bits
• Set index = $10$ bits
• Total bits for cache indexing = $6 + 10 = 16$ bits

Step 3: Calculate Page Colors

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 virtual address bits used for cache indexing overlap with the virtual page number (VPN) bits.

• Bits used for cache indexing = $16$ bits
• Bits in page offset = $13$ bits
• Overlapping bits = $16 - 13 = 3$ bits

The minimum number of page colors required to prevent synonym conflicts is: