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 $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 $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

It makes easy to understand flow ...

Good Explanation !

---

Here is the calculation laid out using the Tree Method.

Every single request starts at the top of the tree at the CPU and branches downward based on whether we get a Hit or a Miss.

---

🌳 The Address Translation & Access Tree

                     [ Start Memory Request ]
                                |
                         ( Check TLB: 1 ns )
                                |
            +-------------------+-------------------+

            |                                       |
     [ TLB Hit (96%) ]                      [ TLB Miss (4%) ]

            |                                       |
   (Got Physical Address)               (Must Read Page Tables)
            |                            - Level 1 Table: +10 ns
            |                            - Level 2 Table: +10 ns

            |                                       |
            |                             (Got Physical Address)

            |                                       |
            +-------------------+-------------------+
                                |
                       ( Check Cache: 1 ns )
                                |
            +-------------------+-------------------+

            |                                       |
    [ Cache Hit (90%) ]                    [ Cache Miss (10%) ]

            |                                       |
    (Done! Got Data)                       (Must Read Main Memory)
                                             - Fetch Data: +10 ns
                                                    |
                                             (Done! Got Data)

---

---

Didn't account for cache hit after tlb miss

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

nice image, i saw it in NPTEL IIT delhi videos

---

in later part where page table are cached when there is miss in cache why arent we taking 0.1*(10+1). why cache time is not taken are we considering simultaneous access?

---

Can anyone tell me why did we not use the TLB emat formular  Hit_rate(Ttlb+Mem) + Miss_rate(2*Mem+Tlb+mem) ??

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

wrong

---

On a TLB miss:
TLB lookup = 1 ns

Need to access 2-level page table
Level 1 PT entry → 1 memory access = 10 ns
Level 2 PT entry → 1 memory access = 10 ns

so that why: 2×10=20 ns

---

it is given in the tqable that we have two level page table 
So, We need to access: 2 level page table
so that why: 2×10=20 ns

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

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

---

Perfect Explanation:)

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

---

I think tere will be 2*10 instead of 2*20 cause 2 times memory access and each mem. access 10ns time..

Am i right??

Answer 4

i tried from my side to make solution easier,after reading all the answers.

Comments

good explanation

---

Nice explanation

---

Really helpful

 

---

Nice Explanation.

Answer 5

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

Answer 6

Both TLB and CACHE Memory is a type of Cache. But you can understand in this way that TLB is somehow related to accessing  the page table  and CACHE is related to accessing the element of the main memory

Whenever TLB and CACHE MEMORY  are involved simply do in this way.

Since CPU always generates the logical address.

Effective Memory Access Time =

Time  taken to convert Logical access to physical address  + Main memory access time

EMAT =  { TLB ACCESS TIME  +  Ptm (k* Main memory access  time) }  +  Cache access time  +  Pcm ( main memory access time + (Pf * Page fault service time ) )

k : no of level of page table

Ptm : TLB MISS RATE

Pcm :CACHE MISS RATE

Pf     :  PAGE FAULT RATE.

Whatever written in { } Curley braces is time to convert logical address to physical address.

According to the question, you can put the value and get your answer. for this question, no page fault is given so you can assume Pf = 0

 

Comments

@ambikesh Does your formula work if cache is not mentioned? ie only TLB and page fault is mentioned?