GATE CSE 2021 Set 2 | Question: 19

Question

Consider a set-associative cache of size $\text{2KB (1KB} =2^{10}$ bytes$\text{)}$ with cache block size of $64$ bytes. Assume that the cache is byte-addressable and a $32$ -bit address is used for accessing the cache. If the width of the tag field is $22$ bits, the associativity of the cache is _________

Answer 1

$32$ bit address is used for accessing the cache.

It is given that cache is Set-Associative.

The address bits get split as follows:

Block Size $= 64 B \implies$ Block offset $= 6\; bits.$

Given that Tag field width $= 22\; bits.$

Therefore, width of Set Index field  $= 32-22-6 = 4 \implies 2^4\text{ = 16 sets in the cache.}$

Cache size is $2 KB$ and Block size $= 64 B$  $\implies 2^5 \text{ = 32 blocks present in the cache. }$

$16$ sets contain $32$ blocks  $\implies 2$ blocks per set or associativity $=2.$

Correct Answer: $2$

Comments

If size of Cache is 2KB. then how can 32bit can be used to address the cache?

and moreover how can TAG * SETs NUM * BLOCK OFFSET = 32bit ?

if it is used to address cache then TAG * SETs NUM * BLOCK OFFSET = Cache size??

---

number of blocks in cache * one block size = Cache size.

To store Tag bits we require different space other than cache capacity itself. Those tag bits are stored in Tag directory.

32 bit address is main memory address (generally physical address).

Answer 2

Associativity is $2$

 

Comments

There are 4 bits to represent number of sets, so number of sets should be 16, and so would be the associativity.

---

Associativity is the number of blocks in the cache where a particular memory block can be present. So each memory block can be present in either of the two blocks in the set in which it is present.

---

Yes you’re right, got it

Answer 3

$\text{Tag field width} = \log_2(\text{Address Space})- \log_2 (\text{cache size}) + \log_2(\text{associativity})$  

$\implies 22 = 32 – 11 + \log_2(\text{associativity}) $

$\implies 1 = \log_2(\text{associativity})$

$\implies \text{associativity} = 2^1 = 2.$

Comments

and in case of 1) Fully – associative, 2) Direct mapping?

---

associativity above is set size,

for fully associative, it's number of lines in cache,

for direct, it's $1$.

Answer 4

Given, Set associative cache and cache is byte Addressable

tag size =22bit

Cache size= 2KB

Cache Block size =64Byte =2^6 Byte

Byte offset =6bit

Number of line in cache  = cache size / Block size

                                            = 2 * 2^10/ 2^6

Number of lines in cache= 2^5

32 bit address are use so

32 bit =tag bit + number of set + byte offset

32 bit         = 22 bit + number of set + 6bit

number of set = 4bit

number of sets in cache = number of line in cache / P-way

P-way = number of line in cache / number of sets in cache

           =2^5/ 2^4

           =2