25,886 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. $1.5$ ns
2. $2$ ns
3. $3$ ns
4. $4$ ns

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.

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

edited by

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.

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)

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.

by

In case if cache is virtually addressed:

Why we need not count the cache access time in case of cache miss? How without accessing cache we can know whether its cache miss?

You have also not used TLB access time in case of TLB miss but @mayank has considered it. Which one is correct?
@Debashish where is it written in the question that page tables aren't cached? do we have to assume it?

@Arjun sir evrything is fine but I have a doubt here..
in case of TLB, first we search the TLb,if page is present then we access it otherwise we go for page table.

but here TLB access time is given not the TLB search or/Lookup time. So,in case of miss we wont access the TLB then why we are adding it in case of miss.

as here lookup time is given so we add it https://gateoverflow.in/2067/gate2014-3-33

That is wrong-- you should not decide the usage of a time based on access/search/look up. Only when TLB is looked we can know a miss -- the only other alternative is if TLB and page tabkes are looed-up simultaneously. But this is not common as given in standard books.

@Arjun sir

In case when TLB is cached then

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)

I think it should be 1+10 =11

Why? Because,

If cache hit then access cache  i.e. 0.9*1

In case of cache miss ..Access main memory for page table and if we follow hierarchical memory access scheme (as is being followed for page access here) then that page table is transferred to cache memory and thus cache access time should be added. i.e. 0.1 * (1+10) where 1ns is cache access time.

In question it's given that both page tables are stored in the main memory.  So how can we consider that they are in cache memory... Hence when TLB miss then main memory is accessed for page tables.
@VS ,you are correct.

@Arjun sir.Please add the edit suggested by @VS. I took me 30 mins to get the same answer.I could have seen her comment earlier:(

Prerna Chauhan in second line

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

@Arjun sir can you verify @VS answer

I think it is correct
How can TLB be cahed? TLB is itself is buffer storing subset of page table entry.
Physically addressed cache means physical frames containing virtual page are cached in cache am I correct
Can anyone please tell why the 2 ns is added to obtain the average memory access time in the answer (3.152 ns) ? I mean, where is the 2 ns coming from ??

in TLB caching @Arjun sir why have u not taken hierarchical approach?

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

So final answer should be 3.16 ns

@Arjun

how is page table caching done? I am unable to understand? For 2 level paging why is cache also accessed twice in page table caching?

edited by

@Arjun sir, thanks for great explaination and also for the concept of virtually tagged cache. Can you kindly explain the issue in the below written formula ( for virtually tagged cache). I am interpreting the situation as this way. Go to Cache, if you find the frame/data it's good otherwise we need to go to TLB for address translation and then fetching the required frame else I need to access 2 level page table.
=> CacheAccessTime + CacheMissRate( TLB Access time +  TLBMissRate(2 * MM) + MM)

Where I am mostly confused is while reading some comments/answers there are times we are trying to multiply the TLB/CacheAccessTime with there hit rate while in some others we are not. For me safer/easier option is to always add the hit ratio*access-time ( cache/TLB). is it so ? or am I thinking wrong here ?

Kindly guide me here sir and really thanks once again

@Kapil sir, @Bikram sir, @Arjun sir

Yes. That works for the address translation time on virtually addressed cache. And there are 2 ways to write the same formula -- with and without including the hit rate. If you spend some time you can prove their equivalence.

@Arjun sir, thanks alot :)

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

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

I am not understanding 2*(10) ? Please explain.
@eyeamgl Because when you miss the TLB then you have to look into the page table for physical address conversion and page table is in main memory so total twice memory time will be there and here memory access time given is 10 so 2*10(twice of memory access time as i said )
ok thanks
Compare this explanation with Debashish Deka's lovely diagram, you'll get a clear picture. Thanks
@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

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

by

@arjun sir , pls check this one
i think thet will be 2*10 instead of 2*20, though,

Why is everyone taking TLB Access Time as 1 ns and why not 10 ns.

IT IS CLEARLY GIVEN IN THE QUESTION AS

,and TLB Access Time is also 10 ns. !!!

@pc you substituted CTLB = 1 NS ??

.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?
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

(fetch the word from process )

*fetch the frame from cache/physical memory?

Now see ... clear (y) ??
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

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 =

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

by

### 1 comment

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

AMAT= cache hit ratio * cache access time + cache miss ratio*( VA->PA + memory word access)

=( cache hit ratio * cache access time + cache miss ratio*( tlb time+ tlb miss*(2*memory access)+ memory word access))

= 0.9*1+0.1*(1+.04*20+10)= 2.08 ns

by

### 1 comment

edited by

Why cache miss time is not considered in the above formula?? If cache miss occurs then we look into the TLB.

$=C_h*CT + (1-C_h) \times \textbf{\{}CT + T_h \times (T + M) + (1-T_h) \times ((n+1)*M) \textbf{\}}$

$C_h\text{ - cache hit rate}$,

$CT - \text{cache access time}$

$T_h - \text{TLB hit rate}$

$T - \text{TLB access time}$

$M - \text{Main memory access time}$

$n - \text{number of page tables}$

As mentioned by Arjun Sir, Cache miss time must be considered

For virtually indexed and virtually tagged, it looks fine except that you didn't add "cache time" for cache miss (this is true for write through cache and write access only). But for virtually indexed, physically tagged, this becomes complex as to get data from cache TLB must hit or page table must be accessed.

So the question asks 'average time take to access virtual address'. This will comprise of two parts. First, we will use TLB/Page Table to find out which frame we need to access in main memory. Secondly, with calculated frame number, we will try to access byte/data/word which can be in cache or main memory.

The logical address is used to fetch frame number from TLB or Page Table (depending on TLB hit or miss). With TLB hit, we will not need any memory access to fetch desired frame number because we will find the required frame number from TLB. But with TLB miss, we will need one memory access to go to memory and read frame number from page table.

We now calculate the time it takes to get our desired frame number:

According to question,

TLB access time = 1 ns; Main Memory access time = 10 ns; TLB hit ratio = 0.96; TLB miss ratio = 0.04

Average time to get desired frame number = 0.96*1 + 0.04*10 = 0.96 + 0.4 = 1.36 ns

For each frame number, whether it was found in TLB or Page Table, we need to access data/byte. This byte could be found in Cache in case of Cache Hit and in Main memory in case of a Cache Miss.

According to question,

Cache Access Time = 1 ns; Main Memory access time = 10 ns; Cache hit ratio = 0.90; Cache Miss ratio = 0.10

Thus, average time to read the frame from memory = 1.36*0.9*1 + 1.36*0.1*10 = 1.22 + 1.36 = 2.58 ns

Thus, overall time taken to read a logical address = Avg. time to get frame number +Avg. time to get data

### = 1.36 + 2.58 = 3.94 = 4 ns

by
by
Answer to this question boils down to

You will look cache

you will definately look TLB

and you will look main memory once when you wont find in Cache

and you will look k times in Main memory when you wont find in TLB

t+c+ ((1-h1)k + 1-h2)m is the formula

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

2 + 0.18(10) = 3.8ns
by

1
2
3
7,876 views