GATE CSE 2012 | Question: 54

Question

A computer has a $256\text{-KByte}$, 4-way set associative, write back data cache with block size of $32\text{-Bytes}$. The processor sends $32\text{-bit}$ addresses to the cache controller. Each cache tag directory entry contains, in addition to address tag, $2$ valid bits, $1$ modified bit and $1$ replacement bit.

The number of bits in the tag field of an address is

• A. $11$
• B. $14$
• C. $16$
• D. $27$

Comments

block size=32 bytes=2^5 bytes =2^8  bits means 8 bits needed uniquely identify a block.

no. of sets*lines per set*block size=cache size

2^x  * 4 * 2^8 =2^21(cache size=256 kb which is 2^21 bits)

2^x=2^11 (means 11 bits uniquely identify each set)

32 bit address is send to cache means total is 32 bit

32=tag+set+block offset

32=tag+11+8

tag=13

now additional bits required are 4 so total no. of bits required would be 17.

i know 17 is not there in options but tell me where the problem lies in this method.

---

its 256 KB not 256 kb

---

If 20 were one of the options, I’d surely fall for it.

Answer 1

Total cache size $= 256\ KB$
Cache block size $=32\text{ Bytes}$
So, number of cache entries $=\dfrac{ 256\ K}{32}=8\ K$

Number of sets in cache $=\dfrac{ 8\ K}{4}=2\ K$ as cache is $4\text{-way}$ associative.

So, $\log(2048) = 11\ \text{bits}$ are needed for accessing a set. Inside a set we need to identify the cache entry.

No. of memory block possible $=\dfrac{\text{Memory size}}{\text{Cache block size}}$

$=\dfrac{2^{32}}{32} = 2^{27}$.

So, no. of memory block that can go to a single cache set

$=\dfrac{2^{27}}{2^{11}}$

$=2^{16}.$

So, we need $16\text{ tag bits}$ along with each cache entry to identify which of the possible $2^{16}$ blocks is being mapped there.

Correct Answer: $C$

Comments

Additional Bits are not a part of Add. They are extra bits included per cache line for meta data. Add bits only include= Tag bits + Index bits + Block offset bits.

In que. they are asking about addressing bits only

---

here set offset is 11 and block offset is 5 so from 32 we can eliminate these 16 to get tag is this right? iam confusing about that extra bits

---

Note: the extra valid/modified/replacement bits are metadata, not part of the tag field. The tag field itself = 16 bits.)

Answer 2

.......……………………………......................…....….

Answer 3

Ans

Comments

i think this answer is right for this question: https://gateoverflow.in/2145/gate-cse-2011-question-43

Answer 4

Each cache tag directory entry contains, in addition to address tag,  2 valid bits, 1 modified bit and 1 replacement bit.

so this info is irrelevant I guess

Comments

It is relevent for part 2 of this question link