GATE CSE 2017 Set 1 | Question: 54

Question

A cache memory unit with capacity of $N$ words and block size of $B$ words is to be designed. If it is designed as a direct mapped cache, the length of the $\textsf{TAG}$ field is $10$ bits. If the cache unit is now designed as a $16$-way set-associative cache, the length of the $\textsf{TAG}$ field is ____________ bits.

Comments

Length of the TAG field in k-way set associative = Length of TAG field in Direct Mapping + log base2(k)

                    = 10+log base2(16) =14

 

---

$Direct-mapped:$

$Tag$	$Line-offset$	$Word-offset$
$10-bits$	$(log_{2}N-log_{2}B)-bits$	$(log_{2}B)-bits$

$16-way\ set\ associative\ cache:$

$Tag$	$Line-offset$	$Word-offset$
$x-bits$	$(log_{2}N-log_{2}B-4)-bits$	$(log_{2}B)-bits$

$10+(log_{2}N-log_{2}B)+(log_{2}B)=x+(log_{2}N-log_{2}B-4)+(log_{2}B)$

$x=14-bits$

Answer 1

In set-associative 1 set = 16 lines. So the number of index bits will be $4$ less than the direct mapped case.

So, Tag bits increased to $14$ bits.

Comments

In direct mapped cache. TAG field = 10 bits so 2¹⁰ MM can be mapped to 1 cache line. Now we have 16 lines in 1 cache set so 2⁴*2¹⁰ = 2¹⁴ MM blocks can be mapped to 1 cache set. So in a 16-way set-associative cache, the length of the TAG field is 14 bits.

---

New concept i learned

Answer 2

hope it helps!!!

Comments

Very good explaination thanks.

---

Yes it does !

Explained as simple as it could be.

Thank you.

---

This is the explanation I was searching for, Thanks :)

Answer 3

Cache capacity =N words

Block size= B words,bits for block offset=log(B)

No of lines in Direct  Mapped cache =N/B,bits for no. of lines=log(N/B)

No of Sets in 16-way set associative cache=N/16B,,bits for no. of sets=log(N/16B)

In direct mapped length of tag =10 bits

Length of PHYSICAL ADDRESSES :-

DIRECT-MAPPED

TAG-10

LINE.NO:-LOG(N/B)

BLOCK OFFSET:-LOG(B)

16-WAY SET ASSOCIATIVE

TAG-X

SET.NO-LOG(N/16B)

BLOCK OFFSET:-LOG(B)

As Physical address is same for both cache mappings,

10+LOG(N/B)+LOG(B)=X+LOG(N/16B)+LOG(B)

10+LOG(N/B)=X+LOG(N/16B)                              //AFTER CANCELLING LOG(B) 

2^(10+LOG(N/B))=2^(X+LOG(N/16B))                 //EXPONENTIATION WITH 2 ,BOTH SIDES

(2^10) *(N/B)=(2^X) *(N/16B)

(2^10) =(2^X) *(1/2^4)

2^14=2^X

X=14                                                                 //APPLYING LOG TO BOTH SIDES

Answer 4

in Direct mapping length is 10 bits that means at each index of cache 2^10 lines can be mapped

after 16 way set associative....16*(2^10) lines can be mapped in each set so total 2^14 lines hence tag bit must be able to address these many lines so 14 bits required

answer is 14 bits