A computer uses 46-bit virtual address, 32-bit physical address, and a…

20132013

A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table (T1), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (T2). Each entry of T2 stores the base address of a page of the third-level table (T3). Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16-way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes.

What is the minimum number of page colours needed to guarantee that no two synonyms map to different sets in the processor cache of this computer?

  1. A.

    2

  2. B.

    4

  3. C.

    8

  4. D.

    16

Attempted by 44 students.

Show answer & explanation

Correct answer: C

Concept. In a virtually-indexed cache, two virtual addresses that map to the same physical frame (synonyms) must land in the same cache set, otherwise the same data is cached twice and can become inconsistent. The set-index field of the cache spans some address bits above the page offset; the count of those overlapping bits decides how many distinct “colours” a page can have. Number of page colours = cache size ÷ (associativity × page size) = 2(set-index bits + block-offset bits − page-offset bits).

  1. Step 1 — page size. Each table entry stores a base address / PTE of 32 bits = 4 bytes = 22 bytes. A page of size 2p bytes therefore holds 2p−2 entries, so each of the three levels consumes (p − 2) index bits. The virtual address splits as 46 = p + 3(p − 2) = 4p − 6, giving 4p = 52, p = 13. Page size = 213 = 8 KB; page-offset = 13 bits.

  2. Step 2 — cache geometry. Cache = 1 MB = 220 B, 16-way, block = 64 B = 26 B. Number of sets = 220 ÷ (16 × 26) = 220 ÷ 210 = 1024, so the set-index is 10 bits. The cache index field (set-index + block-offset) spans the low 10 + 6 = 16 address bits.

  3. Step 3 — overlapping bits → colours. The page offset occupies bits 0–12 (13 bits) and is identical for synonyms; the cache-index field occupies bits 0–15. The overlap that comes from the physical-page part is bits 13, 14, 15 — that is 16 − 13 = 3 bits a synonym could vary. Distinct page colours = 23 = 8. Equivalently, cache size ÷ (associativity × page size) = 220 ÷ (16 × 213) = 8.

Cross-check. 8 × page size = 8 × 8 KB = 64 KB = cache size ÷ associativity = 1 MB ÷ 16. The per-way capacity equals 8 pages, so colouring across 8 colours fixes the set index regardless of the physical frame — consistent with the result.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Niacl Ao It Specialist