GATE CSE 2011 | Question: 43

Question

An $8\text{KB}$ direct-mapped write-back cache is organized as multiple blocks, each size of $32\text{-bytes}$. The processor generates $32\text{-bit}$ addresses. The cache controller contains the tag information for each cache block comprising of the following.

• $1$ valid bit
• $1$ modified bit
• As many bits as the minimum needed to identify the memory block mapped in the cache.

What is the total size of memory needed at the cache controller to store meta-data (tags) for the cache?

• A. $4864$ bits
• B. $6144$ bits
• C. $6656$ bits
• D. $5376$ bits

Comments

check this : 

---

I am bit confused here i think if we say Meta data we mean = tag + valid bit + modified bits

but the question specifically says 

What is the total size of memory needed at the cache controller to store meta-data (tags) for the cache?

so why are we considering other bits apart from tag bits??????? 

---

because the problem explicitly lists exactly what this system's meta-data directory consists of inside its bullet points:

• 1 valid bit

• 1 modified (dirty) bit

• The tag bits ("As many bits as the minimum needed to identify the memory block...")

Answer 1

Number of cache blocks $=\dfrac{\text{cache size}}{\text{size of a block}}$
$=\dfrac{8\ KB}{32\ B}$

$=256$

So, we need $8\text{-bits}$ for indexing the $256$ blocks of the cache. And since a block is $32\text{ bytes}$ we need $5$ WORD bits to address each byte. So, out of the remaining $19\text{-bits}$ (32 - 8 - 5) should be tag bits.

So, a tag entry size $=19 + 1\text{(valid bit)}+1\text{(modified bit)}=21\text{ bits}.$

Total size of metadata $= 21\times \text{Number of cache blocks}$
$= 21\times 256$
$=5376\text{ bits}$

Correct Answer: $D$

Comments

@NAGENDRA_Singh

Bhai block offset kaha kya? 

---

Block offset is of 5 bits ,but in this question ,it is of no use @NAGENDRA_Singh

---

In question, only logical address given, not physical address space. Why did we consider both are same ?

Answer 2

One more Approach:

General case of how to count tag bits:

What is tag bits?

the bits required to count "number of main memory blocks needed to be accomodated in single set of cache"

now here is direct-mapped cache. so number of sets in cache are same as number of blocks in cache. (1 block per set)

$\text{#sets in cache = #blocks in cache} = \frac{2^{3}*2^{10}}{2^{5}}\;=\;2^{8}$

$\text{#no of blocks in main memory} = \frac{2^{32}}{2^{5}}\;=\;2^{27}$

[keep in mind memory is byte addressable so dont convert $2^{32}\; into \;2^{32}*2^{5}$]

now,

$\text{#no of main memory blocks per single cache set (here cache block)}$ $=\frac{2^{27}}{2^{8}}\;=\;2^{19}$

so, tag bits are 19. now each entry has two bits of additional info. so total 19+2=21 bits.

so size of tag meta-data = $21*2^{8}$ [because we have entry for each cache block] = $5376 \;bits$

so answer is option D.

Answer 3

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