Virtually indexed physically tagged cache Multi-level page tables - hierarchical paging

Question

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.

Q.What is the size of a page in KB in this computer?

(A) 2 (B) 4 (C) 8 (D) 16

Q.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?

(A) 2 (B) 4 (C) 8 (D) 16

A question from last Gate exam . how do I solve this kind of question?

Answer 1

All the page table reside in the physical memory(RAM) since the physical address is 32 bit addressable each level table holds a 32 bit (4 byte)address of the RAM

Assume the size of a page is x bytes. (which we need to find)

As the size of level 1 table is also x (as given in the question that level 1 table accommodate exactly a page)it can hold x/4 base addresses of x/4 level 2 tables (which also accommodate exactly a page) and each level 2 table hold base addresses of x/4 level 3 tables.

the level 3 table has entities equal to 2^46/x

ie. (x/4)(x/4)(x/4) = 2^46/x

on solving x=8192 which is in bytes so 8192/1024 = 8 K bytes

Answer 2

answer to 2nd part .... as its virtually indexed and physically tagged so for caches L group bits and B byte bits can accommodate a Full page of Ram for the efficient use so for efficient use we have cache size /2^A = 2^l+b =page size ................http://cseweb.ucsd.edu/classes/fa10/cse240a/pdf/08/CSE240A-MBT-L18-VirtualMemory.ppt.pdf Page size = 1 MB /16 = 64 KB ......... so cache will have 8 different pages copied on same l+b bits so we will color 8 Pages to differentiate between them.