The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+10 votes
2.4k 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$
asked in CO & Architecture by Veteran (101k points)
edited by | 2.4k views

2 Answers

+28 votes
Best answer
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}$
answered by Veteran (357k points)
edited by
+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?

+3

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.
0

@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.

+5 votes

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.

answered by Active (3k points)
edited by
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,440 questions
46,623 answers
139,373 comments
57,020 users