GATE2006-62, ISRO2016-50

Question

A CPU generates $32$-bit virtual addresses. The page size is $4$ KB. The processor has a translation look-aside buffer (TLB) which can hold a total of $128$ page table entries and is $4$-way set associative. The minimum size of the TLB tag is:

• A. $\text{11 bits}$
• B. $\text{13 bits}$
• C. $\text{15 bits}$
• D. $\text{20 bits}$

Comments

I am having difficulty in solving virtual memory concepts involving the concept of associative caches. Can someone please provide a link where I can gain more knowledge about it .

---

No of entries in TLB= 2^7 4-way set

so each set has 2^7/4= 2^5 sets

2^20 pages of process PTE mapped to 2^5 sets

so each set can accomodate 2^20/2^5= 2^15. so in each set to know which page among 2^15 page table entry preseent we need 15 bits.

Answer 1

Page size of $4KB$. So, offset bits are $12$ bits.

So, remaining bits of virtual address $32 - 12 = 20$ bits will be used for indexing...

Number of sets = 128/4 = 32 (4-way set)  => 5 bits.

So, tag bits $= 20 - 5 = 15$ bits.

So, option (C).

Comments

Can you please tell why you simply subtracted 5 from 20? Is it because Indexing in set associative memory is done via Tag+Set bits?

---

"4-way set associative means number of lines is 4 in each set." So my question does in TLB each page table entry correspond to a line?

---

yes block size in TLB just correspond to one entry, so 128 entries corresponds to 128 blocks and 32 sets.

---

Is the given data is sufficient to find the entry size of the TLB if yes? then how to find it? and is tag bits included in the entry size

---

@rajat_mahajan this is the how the virtual address will be broken up into:

4KB page defines the offset = 12 bits
32 sets in the TLB defines the set = 5 bits
Remaining 32 - 17 = 15 bits will be used to define tag bits.

---

bro can you explain organization of TLB.