The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+35 votes
7.9k views
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.
in CO and Architecture by Veteran (420k points)
retagged by | 7.9k views

9 Answers

+43 votes
Best answer

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.

by Boss (12.1k points)
selected by
+10

In direct mapped cache. TAG field = 10 bits so 210 MM can be mapped to 1 cache line. Now we have 16 lines in 1 cache set so 24*210 = 214 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.

+3
New concept i learned
+41 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 :-

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

by Active (4.7k points)
+35 votes

hope it helps!!!

by Boss (41.6k points)
edited by
+1
Very good explaination thanks.
0
Yes it does !

Explained as simple as it could be.

Thank you.
+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
by Active (3.4k points)
+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}$ = 2x-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

by Veteran (62.5k points)
0 votes

So answer is tag bits = 14 bits.

by (271 points)
–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.

by (231 points)
–1 vote

No of TAG bits in Direct Map Cache : (No. of bits Required for Main Memory Address M)-(number of bits for index I+bits for offset O)

No of TAG bits in 16-way set associative : M -(set bits + offset bits)

number of bits for set : index bits - 4 // 16 way set associative

No of TAG bits in 16-way set associative : M -(index bits - 4 + offset bits)

   : (M-I-O)+4=10+4=14

 

 

by Active (3.6k points)
–1 vote

Here we go

by (175 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,309 questions
55,743 answers
192,222 comments
90,490 users