GATE CSE 2003 | Question: 78

Question

A processor uses $2-level$ page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both $32$ bits wide. The memory is byte addressable. For virtual to physical address translation, the $10$ most significant bits of the virtual address are used as index into the first level page table while the next $10$ bits are used as index into the second level page table. The $12$ least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are $4$ bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of $\text{96%}$. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of $\text{90%}$. Main memory access time is $10$ ns, cache access time is $1$ ns, and TLB access time is also $1$ ns.

Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest $0.5$ ns)

• A. $1.5$ ns
• B. $2$ ns
• C. $3$ ns
• D. $4$ ns

Comments

Those who have still do not understood go here ->https://www.youtube.com/watch?v=7NoRhQC_XgI&t=384s

---

Great explanation @palashbehera5 !!!

---

It is divided in two parts at first change VA->PA then access the MM.

Case 1: Hit in TLB -> 1ns

Case 2: Miss in TLB -> Miss rate of TLB*(no. of levels *MM access time)

                                          0.04*(2*10)=0.8ns

Case 3: Hit in cache -> 1ns

Case 4: Miss in cache ->Miss rate of cache *(MM access time)

                                        0.1*10=1ns

Average Memory access time=1+0.8+1+1=>3.8ns

Answer 1

78. It's given cache is physically addressed. So, address translation is needed for all memory accesses. (I assume page table lookup happens after TLB is missed, and main memory lookup after cache is missed)

Average access time = Average address translation time + Average memory access time
= 1ns 
(TLB is accessed for all accesses)
+ 2*10*0.04 
(2 page tables accessed from main memory in case of TLB miss)
+ Average memory access time
= 1.8ns + Cache access time + Average main memory access time
= 1.8ns + 1 * 0.9 (90% cache hit) 
+ 0.1 * (10+1) (main memory is accessed for cache misses only)
= 1.8ns + 0.9 + 1.1
= 3.8ns

---

We assumed that page table is in main memory and not cached. This is given in question also, though they do not explicitly say that page tables are not cached. But in practice this is common as given here. So, in such a system, 

Average address translation time 
= 1ns (TLB is accessed for all accesses) 
+ 2*0.04 * [0.9 * 1 + 0.1 * 10] 
(2 page tables accessed in case of TLB miss and they go through cache)

$= 1 \ ns + 1.9 \times .08$

$= 1.152 \ ns $

and average memory access time $= 1.152 \ ns + 2 \ ns = 3.152  \ ns$

If the same thing is repeated now probably you would get marks for both. 2003 is a long way back -- then page table caching never existed as given in the SE answers. Since it exists now, IIT profs will make this clear in question itself.

Comments

Hope this image helps 

 

---

if cache is present in main memory so why we are not addding 10ns along with 1 ns to acess cache??

---

nice image, i saw it in NPTEL IIT delhi videos

Answer 2

0.96(1+(0.9(1) + 0.1(10+1)))   +   0.04(1+ 2* (10) + (0.9(1) + 0.1(10+1))) = 3.8 ns..so 4ns

Comments

@eyeamgl We multiply by 2 because this is 2 level paging. We have to calculate the physical address by visiting two level of pages.

---

 

0.96(1+(0.9(1) + 0.1(10+1)))   +   0.04(1+ 2* (10) + (0.9(1) + 0.1(10+1))) 

what is 1 in (10+1) in above equation ? is it cache  update time ?

---

1 is cache miss and 10 for MM access

Answer 3

Effective memory access time 4 ns (aprox )

Eff Memory Acces Time $=X_{TLB}\begin{pmatrix} C_{TLB}+X_{PAC} [C_{PAC}]+(1-X_{PAC} ) [C_{PAC}+M] \end{pmatrix} +(1- X_{TLB})\begin{pmatrix} C_{TLB}+2M+X_{PAC} [C_{PAC}]+(1-X_{PAC} ) [C_{PAC}+M] \end{pmatrix}$

$=0.96\begin{pmatrix} 1+0.9 [1]+(1-0.9 ) [1+10] \end{pmatrix} +(1- 0.96)\begin{pmatrix} 1+2\times 20+0.9 [1]+(1-0.9 ) [1+10] \end{pmatrix}$

=3.8 ns

Comments

.Let S1= ∑nr/2r (r=0 to logn-1) .S2= ∑r2r (r=0 to logn-1) .

s1 and s2 after expension?

---

Its 1ns given in the question for TLB access time.

---

Perfect Explanation:)

Can you please provide this easy diagram for virtually Indexed cache too?

Answer 4

Average time taken to access virtual address

= ( Virtual address to physical address ) + (fetch the word from process or main memory )

= t+ ( 1- $p_{t}$)(k*m) + C +(1-$p_{c}$) *m          [K= # of levels] [m = main memory access time]

=1 ns + (0.04)*(2*10 ns) + 1 ns + (0.1 ) *10 ns

= 3.8 ns

Comments

it is actually frame. we get frame number by accessing page table entry. a frame is bigger than a word.

---

What is the purpose of framing or paging ??? to fetch the word from main memory ...  so wats wrong in that statement ??

---

thank you for great explanation