25,597 views

A computer uses $46\text{-bit}$ virtual address, $32\text{-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 $\text{(T1)},$ which occupies exactly one page. Each entry of $\text{T1}$ stores the base address of a page of the second-level table $\text{(T2)}.$ Each entry of $\text{T2}$ stores the base address of a page of the third-level table $\text{(T3)}.$ Each entry of $\text{T3}$ stores a page table entry $\text{(PTE)}.$ The $\text{PTE}$ is $32\;\text{bits}$ in size. The processor used in the computer has a $1\;\textsf{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. $2$
2. $4$
3. $8$
4. $16$

@   The video from udacity which you have shared (Georgia Tech) says only about the  problems, but does not deal with the solution using page coloring ( checked the entire playlist 4 of the High performance Computer Architecture Georgia Tech)

edited by

Let the page size be $x$.

Since virtual address is $46$ bits, we have total number of pages $= \frac{2^{46}}{x}$

We should have an entry for each page in last level page table which here is $T3$. So,

Number of entries in $T3$ (sum of entries across all possible $T3$ tables) $= \frac{2^{46}}{x}$

Each entry takes $32$ bits $= 4$ bytes. So, total size of $T3$ tables $= \frac{2^{46}}{x} \times 4 = \frac{2^{48}}{x}$ bytes

Now, no. of $T3$ tables will be Total size of $T3$ tables/page table size  and for each of these page tables, we must have a $T2$ entry. Taking $T3$ size as page size, no. of entries across all $T2$ tables
$= \frac{\frac{2^{48}}{x}}{x} = \frac{2^{48}}{x^2}$

Now, no. of $T2$ tables (assuming $T2$ size as pagesize) $= \frac{2^{48}}{x^2} \times 4$ bytes = $\frac{\frac{2^{50}}{x^2}} {x} = \frac{2^{50}}{x^3}$.

Now, for each of these page table, we must have an entry in $T1$. So, number of entries in $T1$

$=\frac{2^{50}}{x^3}$

And size of $T1 =\frac{2^{50}}{x^3} \times 4 =\frac{2^{52}}{x^3}$

Given in question, size of $T1$ is page size which we took as $x$. So,

$x = \frac{2^{52}}{x^3}$

$\implies x^4 =2^{52}$

$\implies x = 2^{13} = 8\;\textsf{KB}$

Min. no. of page color bits $=$ No. of set index bits $+$ no. of offset bits $-$ no. of page index bits (This ensures no synonym maps to different sets in the cache)

We have $1\;\textsf{MB}$ cache and $64\;\textsf{B}$ cache block size. So,

number of sets $= 1\;\textsf{MB}/(64\;\textsf{B} \times$ Number of blocks in each set$) = 16\;\textsf{K}/16 (16$ way set associative) $= 1\;\textsf{K} = 2^{10}.$

So, we need $10$ index bits. Now, each block being $64 (2^6)$ bytes means we need $6$ offset bits.

And we already found page size $= 8\;\textsf{KB} = 2^{13}$, so $13$ bits to index a page

Thus, no. of page color bits $= 10 + 6 - 13 = 3.$

With $3$ page color bits we need to have $2^3 = 8$ different page colors

More Explanation:

A synonym is a physical page having multiple virtual addresses referring to it. So, what we want is no two synonym virtual addresses to map to two different sets, which would mean a physical page could be in two different cache sets. This problem never occurs in a physically indexed cache as indexing happens via physical address bits and so one physical page can never go to two different sets in cache. In virtually indexed cache, we can avoid this problem by ensuring that the bits used for locating a cache block (index+offset) of the virtual and physical addresses are the same.

In our case we have $6$ offset bits $+ 10$ bits for indexing. So, we want to make these $16$ bits same for both physical and virtual address. One thing is that the page offset bits $- 13$ bits for $8\;\textsf{KB}$ page, is always the same for physical and virtual addresses as they are never translated. So, we don't need to make these $13$ bits same. We have to only make the remaining $10 + 6 - 13 = 3$ bits same. Page coloring is a way to do this. Here, all the physical pages are colored and a physical page of one color is mapped to a virtual address by OS in such a way that a set in cache always gets pages of the same color. So, in order to make the $3$ bits same, we take all combinations of it $(2^3 = 8)$ and colors the physical pages with $8$ colors and a cache set always gets a page of one color only. (In page coloring, it is the job of OS to ensure that the $3$ bits are the same).

Correct Answer: $C$

by

edited

IN VIRTUALLY INDEXED CACHE, WE CAN AVOID THIS PROBLEM BY ENSURING THAT THE BITS USED FOR LOCATING A CACHE BLOCK (INDEX+OFFSET) OF THE VIRTUAL AND PHYSICAL ADDRESSES ARE THE SAME.

@Arjun sir do this mean it is a cache hit for every Virtual address(According to the given question) in the Virtually Indexed Cache as A virtual address will be given to cache and if it a hit we will directly return the data as it contains the correspoing physical page asscociated with it ???

You just stated 10+6-13

Thanks
Any good video lectures / book that explains this concept elegantly?  Probably I cannot understand the solution in depth due to the fact that the concept is not explained pictorially.

1 MB 16-way set associative virtually indexed physically tagged cache(VIPT).
The cache block size is 64 bytes.

by

Hope this helps

https://www.cse.iitk.ac.in/users/biswap/CS422/L19-VC.pdf

The second image is what has happened in our solution

The index + offset bits which is 10+6 i.e. 16 exceeded the Block offset (13) by exactly 3 bits

so we have to borrow these 3 bits from the Virtual page number of the Virtual Memory

That is why the answer to this is 3 bits.

That means different page colors are enough to solve the synonym problem,

Thanks

by

Bhai, is this covered in present syllabus? Never came across with coloring, synonym term in OS :(
yes ANKIT, that is why I tried to explain it so beautifully. :)

please can you explain in details as to who is borrowing, how it is being borrowed etc.

I mean to say that :

1. The diagram 1 is clear to me. It is quite intuitive.
2. Now I face problem with the second diagram. The portion of the bits marked in red are from the Virtual Page Number part of the virtual address right. So they are bound to undergo translation. Now if suppose the bits marked in red are $001$ and $010$ and suppose these two bit patterns are for the same page $P$ in the physical memory.  How is the concept of coloring going to work. How shall it help us.

Any good book or video which explains this in details shall be appreciable. [I had seen Morris Mano, Hamacher, Patterson(computer architecture a quantitative approach) but could not find in depth explanation about this topic….]

there is no good book. I learnt it from IIT Guwahati professor on call. He called me and explained me what is page coloring. I can share you his notes if you need.