GATE CSE 2015 | Set 2 | Question: 25

Question

A computer system implements a $40\;\text{-bit}$ virtual address, page size of $8\;\text{kilobytes}$, and a $128\text{-entry}$ translation look-aside buffer $\text{(TLB)}$ organized into $32$ sets each having $4$ ways. Assume that the $\text{TLB}$ tag does not store any process id. The minimum length of the $\text{TLB}$ tag in bits is ______.

Comments

Number of virtual pages: Page number bits = 27 → total pages = 2²⁷

Finding the set index bits:

• There are 32 sets → needs 5 bits (since 2⁵ = 32).
• Each page maps to a unique set, based on these 5 bits.

How to calculate the tag bits:

So, the tag bits come from the remaining page number bits after removing the set index bits.

Hence: Tag bits=Page number bits−Set index bits=27−5=22

• In set-associative mapping, each page of virtual memory maps to one specific set.

• Inside that set, there are multiple blocks (or lines) where it could be placed.

• To identify which page currently occupies a line inside the set, we use the tag.

---

TLB stores some of the enteries of page table which is it acts like cache for the page table.
what does page table store? for every virtual page number it stores corresponding frame number .
how many total pages do we have here? 2^40 / 2^13 = 2^27 which means 2^27 enteries are there in page table now they need to be cached in TLB.

Here TLB se set associative with a total of 32 sets .
But what does tag bits tell ? if 2  different entries map to the same set then there set index are same but they are diffrenetiated with the help of tag bits. So if I have x number of tag bits then it means 2^x different entries map to the same set of TLB . 

Since there are 32 sets for 2^27 enteries therefore 2^27/2^5 = 2^22 which means 2^22 enteries map to the same set of TLB so we need 22 bits to differentiate those page table enteries hence 
ANS= 22 bits 

---

Virtual address is divided into VPN and offset. TLB is 128 entries, organized into 32 sets each having 4 ways (32*4=128). So it's a set-associative TLB. The TLB tag is used to identify which virtual page maps to a TLB entry.

Virtual address = 40 bits

page size 8KB => offset 13 bits

VPN = 27 bits.

The TLB is indexed by some bits from the VPN.

Since it has 32 sets, TLB has 32 sets, so index = 5 bits.

So the VPN is divided into: tag (remaining bits) and set index (5 bits).
tag = 27-5 = 22 bits.

VPN (27 bits) = [ Tag: 22 bits | Set Index: 5 bits ]

So answer 22.

Answer 1

Ans $40 - (5+13) = 22$ bits

$\text{TLB}$ maps a virtual address to the physical address of the page. (The lower bits of page address (page offset bits) are not used in $\text{TLB}$ as they are the same for virtual as well as physical addresses). Here, for $8\;\textsf{KB}$ page size we require $13$ page offset bits.

In $\text{TLB}$ we have $32$ sets and so virtual address space is divided into $32$ using $5$ set bits. (Associativity doesn't affect the set bits as they just adds extra slots in each set).

So, $\text{number of tag bits} = 40 - 5 - 13 = 22$

Following diagram shows how $\text{TLB}$ and Cache works:

Comments

I thought that dividing the physical address into (tag bits, index bits, block offset) is sufficient, because I thought that when a system is word addressable (with a word size greater than 1 byte), then a word is the smallest accessible unit across all the components of the system. Looking at the diagram it seems that I am wrong, but I can’t seem to find any reliable resource illustrating how bytes can still be addressed though the system is word addressable. Can someone help me out please?

---

@John_Smith Did you find the answer ? Help a brother out 🐧

---

https://www.youtube.com/watch?v=UbK92_VIgTM

 

video explanation of whole concept for  those who are confused like me

Answer 2

Here is another way to look at it.

The lower bits of page address (page offset bits) are not used in TLB as they are the same for virtual as well as physical addresses.

remaining bits = 40-13=27

So total entries in a page table (let there be one in place of a TLB) = 2^27

So now, we want to map this Page Table to a TLB with 128 entries by the use of a 4-way set-associative mapping.

For mapping purpose,take the Page Table as main memory and TLB as cache memory and the size of a block as x.

So total number of bits for main memory are 27+x.

Now mapping MM 4-way set associatively to CM gives (tag-set-word) as (22-5-x).

So the number of tag bits are 22

Comments

find helpful

Answer 3

Caption

 

Answer 4

Total virtual address size = 40

Since there are 32 sets, set offset = 5

Since page size is 8kilobytes, word offset = 13

Minimum tag size = 40 - 5- 13 = 22

Answer 5

Just think in terms of set-associative cache mapping used in cache organization.

Number of pages = (Total Virtual address space) / (Page size)

                                =(2^40) / (2^13) = (2)^27

No. of bits required to uniquely identify a page is 27

Assume page as a block for simplicity 

Like in the cache we take each main memory block and map it to a block in the cache

Number of blocks = 2^27,  Number of bits to uniquely identify a block =27

So here we are using 4 way set associative mapping and the total number of sets = 32

Number of bits required to uniquely identify a set =5 

So number of tag bits = 27-5 = 22 bits 

Here logic is the same just assume page bits as block bits and subtract set bits from them we can get tag bits.

The answer is 27-5 = 22 tag bits

Answer 6

Number of Tag bits = 22 bits. 
check the attached soln below.