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

Consider a $4$-way set associative cache consisting of $128$ lines with a line size of $64$ words. The CPU generates a $20-bit$ address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively:

  1. $9, 6, 5$
  2. $7, 7, 6$
  3. $7, 5, 8$
  4. $9, 5, 6$
asked in CO & Architecture by Veteran (52k points)
edited by | 2.9k views
@Arjun Sir, I guess the correct answer is not in option.  Answer is 9,7,6 ... Because middle one is LINE , not SET ...  for SET we need 5 bits.... but for LINE we need 7 bits.

1 Answer

+19 votes
Best answer

Number of sets $=\dfrac{\text{cache size}}{\text{(size of a block * No. of blocks in a set)}}$

$=\dfrac{128 * 64}{(64 * 4)}\text{ (4 way set associative means 4 blocks in a set)}$

$= 32.$

So, number of index (LINE) bits $= 5$ and number of WORD bits $= 6$ since cache block (line) size is $64.$

So, number of TAG bits $= 20 - 6 - 5 = 9.$

Answer is (D) choice

answered by Veteran (408k points)
edited by
But in some book answer is option B , as it is asking no of bits in TAG , LINE , WORD which will be 7,7,6 . I am confused which is correct ?
If you are not getting explanation answer does not matter. Also, if GATE books were anywhere near good enough this site would not have been made.
Answer would be 9 7 6

@arjun sir

line here refer to  index offset ?
Sir, middle one is LINE, not SET, so it should be 7... not 5 .... answer is not in option.
How we will know in exam, that line means Index is here?
In my opinion, the word "line" has been used interchangeably as both "block" and "set" in the question, thus raising the ambiguity.
Number of word bits is 6 as explained and number of index bits is 5 which will then produce tag bits to be 20-6-5 = 9. As in set-associative cache mapping the bits are Tag + Index + Word = Address. So even if the line in actual meaning is asked the other values won't change and hence the answer would be 9,7,6 which is not given. So it is a fair assumption that line here is interchangeably used as index.
@Arjun sir, what was given in the official answer keys declared by IITs in 2007?

not just here in general too, I think one Cache Line cannot be interpreted as a cache set with multiple "blocks", 

I'm not saying the answer is wrong, just that I think after using 5 bits to reach to a set we cannot use 2 more bits to reach the "line" having our word(because any of the lines might contain it and thus we cannot reach that particular line, we have to compare tags with every line ), thus we have 5 bits in line field also.

Is this thinking correct?

Yes, what you are thinking is correct. "Line bits" here refer to the "Index bits".

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