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

The number of bits for virtual address and physical address were not needed to solve this question, right?

---

yeah, not needed; question asks for no. of virtual addresses that can be addressed w/o any TLB miss

any adress except for address already in TLB will for sure give a TLB miss rest is explained

---

Since memory is word-addressable, the lowest addressable unit is a 4-byte word. 

Calculation for the offset size ($2^{13}\text{ B} / 2^2\text{ B} = 2^{11}$ words, requiring 11 bits) 

Let's visualize exactly how these bits look in the address formats, and how the TLB uses them to translate addresses without missing.

 

How to See the "No-Miss" Translation Step-by-Step

1. The Page Offset (11 bits):
   Because every single page contains exactly $2^{11}$ words, the 11-bit offset stays exactly the same during translation. It just points to the specific word slot inside a page.

2. What the TLB Caches:
   The TLB only stores mappings for the Virtual Page Numbers (VPN) to Physical Frame Numbers (PFN). It has room for exactly 128 rows (entries).

3. Translating Without a Miss:

   • If a virtual address comes in, the CPU looks at its 53-bit VPN.
   • If that VPN matches one of the 128 rows currently sitting inside the TLB, it's a TLB Hit (no miss).
   • Since there are 128 rows, the TLB can cover a maximum of 128 unique pages at one time.

4. Counting the Total Word Addresses:

   • Inside each of those 128 cached pages, you can change the 11-bit offset to any value from 00000000000 to 11111111111 ($2^{11}$ options) without generating a new page translation request.
   • Therefore, the total number of distinct, individual virtual word addresses you can request completely from the TLB is:
     $\text{128 pages} \times 2^{11}\text{ words/page} = 2^7 \times 2^{11} = 2^{18}\text{ addresses}$

Which, simplified, gives us $2^8 \times 2^{10} = \mathbf{256 \times 2^{10}}.$

 

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

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.

---

TLB contains 128 valid entries,

each entry points to a word in page size of page table

no of words in page = page size / word size = 8KB / 4B = 2^11 words are present in a page

and each tlb entry refers to word in a page,

thus, total virtual addresses can be translated without any TLB miss is 128 * 2^11 = 256 * 2^10

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

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

 

Answer 4

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 5

Option B) 

Answer 6

ANS =B 

They Will not(Never) miss