GATE CSE 2003 | Question: 78

Question

GATE CSE 2003 | Question: 78

gatecse asked Sep 15, 2014 • edited Jun 23, 2018 by Pooja Khatri

46,117 views

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)

$1.5$ ns
$2$ ns
$3$ ns
$4$ ns

gatecse asked Sep 15, 2014 • edited Jun 23, 2018 by Pooja Khatri

gatecse

46.1k views

See all

AakS

commented Dec 25, 2017

i

edited

by AakS Jan 15, 2018

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)

15 Answers

Best answer

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.

gatecse answered Sep 15, 2014 • edited Jul 13, 2018 by kenzou

gatecse

See all

Show 65 previous comments

Page:

1
2
3
4
next »

Related questions

23.9k

views

6 answers

83 votes

go_editor asked Apr 24, 2016

23,902 views

GATE CSE 2003 | Question: 79

A processor uses $\text{2-level}$ page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical...

go_editor

23.9k views

go_editor asked Apr 24, 2016

15.2k

views

6 answers

27 votes

Kathleen asked Sep 16, 2014

15,243 views

GATE CSE 2003 | Question: 26

In a system with $\text{32 bit}$ virtual addresses and $\text{1 KB}$ page size, use of one-level page tables for virtual to physical address translation is not practical ...

Kathleen

15.2k views

Kathleen asked Sep 16, 2014

14.7k

views

7 answers

55 votes

go_editor asked Apr 24, 2016

14,705 views

GATE CSE 2003 | Question: 81

Suppose we want to synchronize two concurrent processes $P$ and $Q$ using binary semaphores $S$ and $T$. The code for the processes $P$ and $Q$ is shown below.$$\begin{ar...

go_editor

14.7k views

go_editor asked Apr 24, 2016

6.7k

views

3 answers

30 votes

Kathleen asked Sep 17, 2014

6,743 views

GATE CSE 2003 | Question: 80

Suppose we want to synchronize two concurrent processes $P$ and $Q$ using binary semaphores $S$ and $T$. The code for the processes $P$ and $Q$ is shown below.Process P:P...

Kathleen

6.7k views

Kathleen asked Sep 17, 2014

Anyone please summarize this thing.It's very difficult to understand for beginner ! — suvasish pal, Sep 19, 2017
Some important lines in this question -->

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

Physically addressed cache. — Chhotu, Dec 5, 2017
3.8 is wrong ?

i am not understanding why it should be 3.152 — A_i_$_h, Dec 18, 2017
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... — AakS, Dec 24, 2017
but to get 3.152 arjun sir has used a different approach

am asking regarding that

look at the best answer — A_i_$_h, Dec 25, 2017
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) — AakS, Dec 25, 2017
@ hem chandra joshi, bcoz there are two level page tables...to access one table, one MM access. — AakS, Jan 1, 2018
Source: https://www.ece.ucsb.edu/~strukov/ece154aFall2012/lecture16.pdf — krishn.jh, Jun 19, 2018
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? — vupadhayayx86, Aug 29, 2018
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. — BASANT KUMAR, Aug 30, 2018
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. — Sheth Nisarg, Nov 13, 2019
Assuming that page tables are not cached. Usually, we donot load page tables in cache. — Gaurav Yadav, May 4, 2020
the details of this question are solution of the question asked 1 year before this question.

https://gateoverflow.in/872/gate2002-19 — Adarsh Pandey, Jun 7, 2020
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) — shashankrustagi, Jan 22, 2021
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. — palashbehra5, Nov 10, 2021
Those who have still do not understood go here ->https://www.youtube.com/watch?v=7NoRhQC_XgI&t=384s — Rohan Agrawal, Dec 29, 2021
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 — Prashant_Dubey, Jan 31
if cache is present in main memory so why we are not addding 10ns along with 1 ns to acess cache?? — Mohnish, Oct 8, 2020

resilientknight · Answer 1 · 2016-08-27T15:36:22+0000

See all

Show 4 previous comments

pC · Answer 2 · 2016-10-02T15:13:34+0000

See all

Show 3 previous comments

Puja Mishra · Answer 3 · 2017-12-31T06:49:13+0000

See all

Show 2 previous comments

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

GATE CSE 2003 | Question: 78

Please log in or register to add a comment.

Please log in or register to answer this question.

15 Answers

Please log in or register to add a comment.

Please log in or register to add a comment.

Please log in or register to add a comment.

Please log in or register to add a comment.

Related questions

20 20 Comments reply

Please log in or register to add a comment.

Please log in or register to answer this question.

15 Answers

68 68 Comments reply

Please log in or register to add a comment.

7 7 Comments reply

Please log in or register to add a comment.

6 6 Comments reply

Please log in or register to add a comment.

5 5 Comments reply

Please log in or register to add a comment.

Related questions

20 20 Comments

68 68 Comments

7 7 Comments

6 6 Comments

5 5 Comments