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

Anyone please summarize this thing.It's very difficult to understand for beginner !

---

Some important lines in this question -->

Page tables for both levels are stored in the main memory.

Physically addressed cache.

---

3.8 is wrong ?

i am not understanding why it should be 3.152

---

its coming 3.8 only...in questn it is said to round off the value upto nearest o.5 ns so nearest is 4 ns and thus the answer...

---

but to get 3.152 arjun sir has used a different approach

am asking regarding that

look at the best answer

---

There is no point of confusion in this question. Firstly we should know the access sequence of TLB, Cache, page tables and MM. The following figure depicts this clearly:

Now coming to our question following sequence will be followed:

1. TLB will be accessed

     1.1 TLB Hit

         cache access....if cache Hit...word will be accessed from cache....If cache MISS word will be accessed from MM(no page fault)

    1.2 TLB Miss

         2 Page tables will be accessed(it is given page tables are in MM, so 2 MM access)....then cache will be accessed.....if cache Hit, word will be accessed from cache....if cache miss word will be accessed from MM...

So following the above sequence, AMAT is as following:

          =3.8

         =4ns (round off to the nearest 0.5ns)

---

(it is given page tables are in MM, so 2 MM access)  why?

---

@ hem chandra joshi, bcoz there are two level page tables...to access one table, one MM access.

---

 

Source: https://www.ece.ucsb.edu/~strukov/ece154aFall2012/lecture16.pdf

---

I know Processor can simultaneously look in multiple blocks of TLB, but in case of main memory we need multiple access to main memory for accessing page table depending on levels ? Can someone clear this?

---

in this question there is no any page fault .consider a situation in which there is page fault having page fault rate is 10% then what will be expression for it.

---

Thank you for such a good explanation

---

If page faults are also to be considered, then can anyone verify the following expression:

AMAT = $t_h[(T + c_h(C) + (1-c_h)\{C + p_f(PS + M) + (1-p_f)M\}] + (1-t_h)[T +2M + c_h(C) + (1-c_h)\{C + p_f(PS + M) + (1-p_f)M\}]$

where $t_h$ = tlb hit, $T$ = TLB access time, $c_h$ = cache hit, C = cahce acces time, $p_f$ = page fault rate, $PS$ = page fault service time, $M$ = main memory access time.

Thanks.

---

Assuming that page tables are not cached. Usually, we donot load page tables in cache.

---

the details of this question are solution of the question asked 1 year before this question.

https://gateoverflow.in/872/gate2002-19

---

TLB access time + cache access time

now when not there in cache, memory will be accessed only once as there is no page fault

and VA-->VA translation might require you to walk down the page table (main meory) upto k levels

 

Hence I conclude that when we have TLB with multilevel paging, then it is very costly in case of a TLB miss you may have to walk down the entire page table

 

c + t + missrate of cache(m) + miss rate of TLB(k*m)

---

This will clear up how EMAT is getting calculated.

Edit: Need to clear up a few things; As already pointed out in the selected answer, the physical address is required to check the cache for recently used data.
However, if not found in the cache, 2 Main Memory references for translation of LAS, Then one cache reference to see if there's still any hope left :P if not, the final main memory reference for loading data into the cache and to CPU eventually.

---

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