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

. 

---

Increasing associativity from 1 to K increases TAG by log₂(K)
 

• Direct mapped → TAG = 10
• 16-way → log⁡2(16)=4

New TAG=10+4=14

---

An Intuitive Approach Could be:

For the direct mapped cache, total lines (sets) = $\frac{N}{B}$

Since there are 10 bits in the Tag for this cache, therefore, number of blocks that can get mapped to one set = $2^{10}$ = $1024$

Therefore, total blocks in main memory

= Number of sets in cache * Number of blocks mappable to single set 

= $\frac{N}{B} \times 1024$

Remeber, no matter what type of cache you use, the number of blocks in main memory will stay the same, provided you do not mess with the block size.

Turning this cache into 16-way set associative:

Now the number of sets = $\frac{N}{B \times 16}$

Lets assume the number of memory blocks mappable to each set be $\text{x}$ in this case

$\frac{N}{B \times 16} \times x = \text{total blocks in main memory}$

$\frac{N}{B \times 16} \times x = \frac{N}{B} \times 1024$

$\therefore x = 1024 \times 16 = 2^{14}$

Thefore number of memory blocks mappable to each set in the 16-way set associative cache = $2^{14}$

Therefore, number of bits in tag required for this cache = $14 \text{ bits}$.

Let me know if I missed anything?

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

---

Associativity increase => TAG increases => Index decreases

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

Answer 5

Since offset not given so we can neglect it because line offset in (direct cache) and set offset in (set - associative cache) is same.

In direct cache = Tag(10) + line (x, assume) + offset (neglect it)

In set associative = Tag(t assume) + Set(x - 4) + offset (neglect it) , since set = $\frac{Number -of- Lines }{16- way -set- associative}$ = 2^x-4

Now , In direct cache = 16- way set associative

         Tag(10) + line (x, assume) =  Tag(t assume) + Set(x - 4)

              10 + x = Tag + (x - 4)

               Tag = 10+4 = 14 bits

Answer 6

When it is directed mapped cache, the physical address can be divided as
(Tag bits + bits for block number + bits for block offset)
With block size being B words no. of bits for block offset = log (B)
Because the cache capacity is N words and each block is B words, number of blocks in cache = N / B
No. of bits for block number = log (N/B)
So, the physical address in direct mapping case
= 10 + log (N/B) + log (B)
= 10 + log (N) – log B + log B
= 10 + log (N)
If the same cache unit is designed as 16-way set associative, then the physical address becomes
(Tag bits + bits for set no. + Bits for block offset)
There are N/B blocks in the cache and in 16-way set associative cache each set contains 16 blocks.
So no. of sets = (N/B) / 16 = N / (16*B)
Then bits for set no = log (N/16*B)
Bits for block offset remain the same in this case also. That is log (B).
So physical address in the set associative case
= tag bits + log (N/16*B) + log B
= tag bits + log (N) – log (16*B) + log B
= tag bits + log (N) – log 16 – log B + log B
= tag bits + log N – 4
The physical address is the same in both the cases.
So, 10 + log N = tag bits + log N – 4
Tag bits = 14
So, no. of tag bits in the case 16-way set associative mapping for the same cache = 14.