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

To make it very simple 

 

## Page size is 2^13 bytes,MM is word addressable , so 2^13/ 4 bytes =2,048 words = 2^11 words , each page is 2^11 words.

 

## Some Basics: TLB is a kind od  subset of Page Table , Page table has Page no with frame no , where as TLB has Page number , Frame no , Valid bit and dirty bit to . And the basic concept we need to know to solve this problem is , Each page has one entry in Page table and if so in TLB .So for 2^11 words only one entry in TLB and Page Table .

 

# So if TLB has 128 valid entries(that means there might be more but there are the entries for which valid bit is 1 and this are the one's which can be used)=> Then 128 X 2^11 =2^7 X 2^11 =2^8 X 2^10 = 256 X 2^10.  SO OPTION B .

Answer 2

## Page size is 2^13 bytes,MM is word addressable , so 2^13/ 4 bytes =2,048 words = 2^11 words , each page is 2^11 words.

 

## Some Basics: TLB is a kind od  subset of Page Table , Page table has Page no with frame no , where as TLB has Page number , Frame no , Valid bit and dirty bit to . And the basic concept we need to know to solve this problem is , Each page has one entry in Page table and if so in TLB .So for 2^11 words only one entry in TLB and Page Table .

 

# So if TLB has 128 valid entries(that means there might be more but there are the entries for which valid bit is 1 and this are the one's which can be used)=> Then 128 X 2^11 =2^7 X 2^11 =2^8 X 2^10 = 256 X 2^10.  SO OPTION B .

Answer 3

We can do this by convering to Byte addressable as well
Given , 
Page size = 2^13 B .
TLB has 128== (2^7). entries which means each entry maps to 2^13 distinct Virtual addresses
So in Total 128 entries maps to 2^7*2^13 = 2^20 Bytes 
To convert to word addressable divide by 4
Finally we can do 2^20 / 2^2  = 2^18 = 256 * 2^10

Answer 4

In 128 ($2^7$) TLB entries we can store $2^7$ page to frame translation information.
Which means we have to look how many virtual addresses are present in those 128 pages.

Which can be calculated by:
$$128 \times 8 \text{ kB} \quad (\because \text{Page Size} = 8 \text{ kB})$$
$$= 128 \times 2^3 \times 2^{10} \text{ B} \quad (\because 1 \text{ kB} = 2^{10} \text{ B})$$
$$= 128 \times 2^{13} \text{ B}$$

Since the memory is word-addressable, we provide an address to each word, so we have to convert bytes into words.
To convert to words, we divide by the word size which is $4$ ($2^2$) Bytes:
$$= \frac{128 \times 2^{13}}{2^2} \text{ words}$$
$$= 128 \times 2^{11} \text{ words}$$

Which means $128 \times 2^{11}$ distinct addresses:
$$= 256 \times 2^{10} \text{ addresses} \quad (128 \times 2 = 256)$$

$\because$ Option B is correct.

 

Answer 5

Mathematical Solution

$$\text{Word Size} = 4 \text{ B} = 2^2 \text{ B}$$

$$\text{Page Size} = 8 \text{ kB} = 2^{13} \text{ B}$$

Since the system is word-addressable:

$$\text{Words per Page} = \frac{\text{Page Size}}{\text{Word Size}} = \frac{2^{13} \text{ B}}{2^2 \text{ B}} = 2^{11} \text{ words}$$

$$\implies \text{Page Offset} = 11 \text{ bits}$$

---

TLB Translation Capacity

$$\text{TLB Entries} = 128 = 2^7 \text{ entries}$$

Each TLB entry maps exactly one virtual page containing $2^{11}$ distinct word addresses.

$$\text{Max Virtual Addresses without Miss} = \text{TLB Entries} \times \text{Words per Page}$$

$$= 2^7 \times 2^{11}$$

$$= 2^{18}$$

$$= 2^8 \times 2^{10}$$

$$= 256 \times 2^{10}$$

Correct Option: B ($256 \times 2^{10}$)

Answer 6

Hence correct option B