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

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

Hi All, 

I have understood the solution but I have one doubt. Even in another question(https://gateoverflow.in/8120/gate2015-2-25) I have seen the approach is: number of bits in logical address= number of bits in physical address and then the question is solved further. This is just an assumption correct because nothing is mentioned about the physical address? Please let me know if I am thinking correct.

---

this is simply analogous to TAG directory size

---

I am not getting i saw 3 to 4 questions on TAG directory size, and in all of those questions, they were interested in students to find the answers in BITS.

can anyone tell me why not Bytes?

Are they telling something ? (hinting)

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

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