GATE CSE 2006 | Question: 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

TLB is small, fast lookup CACHE memory 

So same concept can be applied as cache

---

why "minimum" ? why not the exact size?

---

@Adarsh

It is minimum because the tag can also contain the valid/protection bits

Answer 1

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

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

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

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

Correct option C.

Comments

Someone please verify this:

Size of TLB = No. of entries in TLB * Size of page table entries

Size of TLB tag directory = No. of entries in TLB * TLB tag size

---

Size of TLB = No. of TLB entries * Size of one TLB entry(Tag bits+frame bits+extrabits)

http://people.cs.pitt.edu/~musfiq/teaching/cs1541/fall%202008/optional_vm_answer.pdf

---

@rohith1001 Thanks bro for pinning the cache concept video. Thinking of revising the cache concept for solving these questions but due to time constraint unable to do that but this video helped me alot in it.

Answer 2

The size of virtual address is 32,now page size is 4KB given or,number of bits for offset is 12(2^12=4KB).

Page(20bits)

OFFSET(12bits)

Now for TLB header is as:

TAG(y bits)

SET(x bits)

OFFSET(12bits)

Now the set is given as 4 way set associative,and it can hold 128 entries,

Now to divide 128 entries into 4 sets,number of bits required to do so:

set bits(x)=$128(or,2^7)/(4(or,2^2)))$ 

hence sets bits would be: 5

therefore:

$y+5+12=32$

or,$y=15 bits$

Hence option C is correct

 

Comments

this is better explaination than the highlighted ans.

 

Answer 3

We have a total of 2$^{32}$ memory locations each of 1 B and we are grouping 2$^{12}$ entries each of 1 B. so we will have 2$^{20}$ chunks.Now these chunks are stored in the physical memory and in order to keep track of them we need the page table.to enhance the searching we are using the TLB which has 128 page table entries designed as a 4 way set associative TLB so the number of bits for set offset will be 2$^{5}$ .Earlier we have calculated that no of pages = 2$^{20}$ which is the number of page table entries as well.
So we will divide this 20 into 5 for set offset and rest 15 for the TLB tag bits

Hence option c is correct

Answer 4

This question very similar to "Calculating Tag bits for 4-way set Associative cache"

Block = Page to draw parallels. Actually TLB concept as a whole is related to cache. 

Similar parallels in Heirarchical cache AMAT and AMAT involving TLB

Comments

Similar question : Gate 2015 | Set 2 | Q25

Answer 5

32 bit (VAS)

20	12

 

20 bits are used to acces the page table which is in the main memory . But in the case of TLB these 20 bits are used to access the TLB . 

 

Now as the TLB has 128 entries and is 4 way set associative which means that each set has 4 entries hence the number of sets in TLB is 128/4 = 32 

32 sets need 5 bits to get addressed.

 

therefore the TLB address bits division will look like: 

                                                               20(bits needed to access TLB)

15

5

 therefore 15 bits are used for tag. 

Note: when mapping is done then multiple page table entries gets mapped to 1 set or enty of TLB depending on the kind of mapping. To diffrentiate between these multiple entries tag bits are used.

Therefore Tag stores the tag for all the Entries.

 

Answer 6

32 bit (VAS)

20	12

 

20 bits are used to acces the page table which is in the main memory . But in the case of TLB these 20 bits are used to access the TLB . 

 

Now as the TLB has 128 entries and is 4 way set associative which means that each set has 4 entries hence the number of sets in TLB is 128/4 = 32 

32 sets need 5 bits to get addressed.

20-5=15

 therefore 15 bits are used for tag. 

Note: when mapping is done then multiple page table entries gets mapped to 1 set or enty of TLB depending on the kind of mapping. To diffrentiate between these multiple entries tag bits are used.

Therefore Tag stores the tag for all the Entries.