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**

41 votes

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 TAG field is 10 bits. If the cache unit is now designed as a 16-way set-associative cache, the length of the TAG field is ____________ bits.

3

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**

4

$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$

56 votes

Best answer

45 votes

44 votes

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** :-

TAG-10 | LINE.NO:-LOG(N/B) | BLOCK OFFSET:-LOG(B) |

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

11 votes

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

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

8 votes

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

0 votes

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.

(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.

–1 vote

One approach will be we can find the number of blocks in main memory with the help of tag bits like given in the following picture

so total number of blocks in main memory is 131072 so we can find number of blocks in the cache as 131072/1024=128 blocks

now when mapping is set associative so total number of sets in cache is 128/16=8 sets so now total number of blocks in main memory is 131072/8=16384 which is 2^14 so 14 bits are needed in tag.