The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 votes

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

  1. $11$
  2. $14$
  3. $16$
  4. $27$
asked in CO & Architecture by Boss (16k points)
edited by | 4.4k views
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



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.

1 Answer

+29 votes
Best answer
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\ 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



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$
answered by Veteran (408k points)
edited by
So number of bits for tag field = 32- (11 +5) = 16.

5 bits cache offset and 11 bits to identify a set.
here they are asking for tag bits which is 16.How the ans is coming 11????
Answer is 16 only. I have added the missing part.
Can you please tell why you didn't consider additional 4 bits, these extra bits are also stored in tag memory.
We have solved so many questions when we considered tag bits + additional bits together

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

I think we add those additional bits when we translate virtual address to physical address.

Means if we are given physical address and try to traslate it in virtual address, then we add or subtract extra bits
@Vijay "Tag bits" mean address tag - that is the bits which are required for identifying a particular memory block in cache. Cache Tag directory includes the other bits as mentioned in question.

@ Vijay Thakur

Because it says "number of bits in the tag field of an address". Those extra bits are not part of address, they are present in tag directory.

@Arjun Suresh Sir can I say we add those additional bits when we translate virtual address to physical address or when calculating Tag directory.

@Arjun, why did you consider block size of main memory as equal to Cache block size ?

No. of memory block possible =Memory size / Cache block size

@arjun sir, why we are not adding the 4 extra bits to get final answer?
16 + 4 = 20 bits in tag field
Someone please explain the significance of extra bits, please. If not applicable to this sum then places where it is used as mentioned in above comments.

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
49,576 questions
54,190 answers
71,147 users