3k views

An $8KB$ direct-mapped write-back cache is organized as multiple blocks, each size of $32$-$bytes$. The processor generates $32$-$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?

1. $4864$ $bits$
2. $6144$ $bits$
3. $6656$ $bits$
4. $5376$ $bits$
edited | 3k views

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}$
edited
+1

In the question it says "the cache controller maintains the tag information for each block comprising of 1 valid bit, 1 modified bit and as many Bits as minimum needed to identify the memory block mapped in the cache".

Does this not mean that the tag contains 1 valid, 1 modified bit?

Tag size is 19 Bits, why are we adding 1+1 to 19 Bits?
The Taq information already comprises the valid and modified bit right?

+5

1 valid bit, 1 modified bit and as many Bits as minimum needed to identify the memory block mapped in the cache

By finding the index and offset bits and then subtracting from the total no. of address bits, what we get is the last part of above - that is the minimum number of bits needed to identify the memory block mapped in the cache. All other bits like valid bit, modified bit, LRU bit etc. are extra.

+3
The processor generates 32 bit address. Of this 32, 8 Bits are used for block indexing and 5 Bits are used for byte indexing. 19 Bits are for tag. The extra bits 1+1 are not stored in the 32 bit address generated by the processor right?

Where will the extra bits for valid and modified be stored? Since we have already used up 19+8+5=32 Bits which was generated by processor.
0
Sir, Answer @Purple., Question clearly using the word compromising.
0
@Arjun Sir, Would the answer be different, had the cache followed a policy other than Write Back?? Please explain.
+4

@anchitjindal07, Yes the answer would be different if cache followed write-through policy as in that case modified bit won't be required.

@Aghori, Total tag information for a block includes-
1) 1 valid bit
2) 1 modified bit
3) tag bits- As many bits as the minimum needed to identify the memory block mapped in the cache -(19 bits).
So total 21 bits are required to store tag information for a block.

0

@Arjun  sir if it was "memory in bytes" then would it be ((total tag bits)/8)* #lines  B or

(total tag bits * #lines)/8 B

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$

edited by

1
2