GATE CSE 2019 | Question: 33

Question

Assume that in a certain computer, the virtual addresses are $64$ bits long and the physical addresses are $48$ bits long. The memory is word addressible. The page size is $8$ kB and the word size is $4$ bytes. The Translation Look-aside Buffer (TLB) in the address translation path has $128$ valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?

• A. $16 \times 2^{10}$
• B. $256 \times 2^{10}$
• C. $4 \times 2^{20}$
• D. $8 \times 2^{20}$

Comments

$256 × 2^{10}$ (b)

---

Memory is word addressable. 1 word = $2^{2}$ Bytes

Page Size = 8 KB = $2^{13}/ 2^{2}$ words = $2^{11}$ words

So, 1 page covers $2^{11}$ memory words. 

Now TLB can contain 128 page entries at max. 

So at most 128*$2^{11}$ memory address can be addressed in a TLB without any TLB miss. i.e 256*$2^{10}$

---

For better understanding :
 
https://youtu.be/BQ2GkdDjA_E

Answer 1

TLB Entry: $\begin{array}{|l|l|} \hline  \text{Page Number} & \text{Frame Number} \\ \hline \end{array}$

Memory is $\text{word addressable.}$

• Word size $=  4 \text{ Bytes} $
• Page size $ =  8\;\text{KB} = 2^{11}  \text{ words}$
• Virtual Memory size $= 2^{64} \text{ words}$
• Number of pages possible $= 2^{53}$
• Number of bits required for Page number $= 53 \text{ bits}$
• Number of bits required for Page offset $= 64-53 =11 \text{ bits}$

At a time TLB contains $128=2^{7} $ distinct page numbers.

If a page number is found in TLB then there will be a hit for all the words (Word addresses) of that Page.

$1$ - page hit implies $2^{11}$ distinct virtual address hits.

So $2^{7} $page hit implies $2^7 \ast 2^{11} = 2^8\ast 2^{10} = 256 \ast 2^{10} \text{ virtual  address hits}$

Option B. At most, $256 \ast 2^{10}$  distinct virtual addresses can be translated without any TLB miss.

Comments

From where to practice these types of questions?

I have never seen this type before...

---

If in the question,memory is word addressable is mentioned,we don't have to convert it to word?

Like as per this question it won't be 46bits pa and 62bits va?

Asking for future reference

---

simply word offset * no of TLB entries is the answer.

Answer 2

VA = <pageNo, offset>

Here total no of TLB entries is 128 which means 128 Virtual Address to Physical Address translations can be stored. These entries store frame no for the corresponding page no. Assuming we already have 128 distinct valid TLB entries present.

Now 1 page contains #words = Page Size / 1 word = 8 KB/ 4 B = 2K

Now each TLB entry contains 1 frame no  and each page/frame can contain max 2K words.

Thus the TLB can address 128 * 2K or 256 * 1K words without any miss.

Ans B) $256 * 2^{10}$

Comments

simple and concise

Answer 3

TLB that contains page table entries (those are most frequently used) is a hardware device to reduce memory access time. It has 128 entries(pages). 

since the memory is word addressable, means cpu will access 1 word at a time. so we need to find no. of words in 1 page = 4kB/4B = 2^11.

so now 1 page has 2^11 addresses & tlh has 128 pages so total distinct addresses that can be translated with tlb = 2^11 * 128 = 256*2^10.

option B

Answer 4

Each address corresponds to a word. (Page number + Page offset leads to a word in a page. Same for Frame number + Frame Offset)

TLB has $128=2^7$ valid entries. Each entry leads to a page. Each page has $\frac{8kB}{4B}=2^{11}$ words.

So, for a maximum number of $2^{11}*2^7=2^{18}$ addresses, we can have a hit.

 

Option B

Comments

shashank023 

I think by subset he meant to say,page table entries(i.e.frame numbers) are subset of what are present in page tables.(frequently used)

see-

 The TLB is a cache of the page table, representing only a subset of the page-table contents

Each entry in the TLB consists of two parts: a tag and a value. If the tag of the incoming virtual address matches the tag in the TLB, the corresponding value is returned.

so in this case Tag is page number and value is frame number.

size of TLB = (no of entries in TLB) * (tag bits + frame no bits + extra bits if any)

refer-https://gateoverflow.in/8120/gate2015-2-25

reference -https://en.wikipedia.org/wiki/Translation_lookaside_buffer

 

---

If following is scenario

A computer system implements a 40−bit physical address, page size of 8 kilobytes, and a 128−lines cache organized into 32 sets each having 4 ways.

Then the Tag size = 40−(5+13)=22 bits and cache size is 128*8KB.

Here tag bits are not taken into account for calculating Cache size, although the tag bits are present to identify which frame is mapped to that cache line.

I think the same applies for TLB size.

 

---

shashank023

Why 128*8kb ??  we are not storing page per entry in TLB ..we are storing mappings so it  should be 128*(13+22(add tag bits which is your doubt))....

see comment Thread for that question..….

--------------------------------------------------------------------------------------------------------------------------------------

See for cache organization techniques(direct,set associative,associative) we are calculating Tag memory and cache size different ..and tag memory is not included in cache size.. But there we are talking about data cache not TLB

refer- https://gateoverflow.in/12746/total-size-of-cache