GATE CSE 2018 | Question: 34

Question

The size of the physical address space of a processor is $2^P$ bytes. The word length is $2^W$ bytes. The capacity of cache memory is $2^N$ bytes. The size of each cache block is $2^M$ words. For a $K$-way set-associative cache memory, the length (in number of bits) of the tag field is

• A. $P-N- \log_2K$
• B. $P-N+ \log_2 K$
• C. $P-N-M-W- \log_2 K$
• D. $P-N-M-W+ \log_2 K$

Comments

Answer is option B

---

here physical adress space is 2^p bytes so p bit for adressing now, 

assume for some time that in question they are not asking tag size for set associative instead they are asking tag size for direct mapping
--------------------------------------------------------------------------------------------------------------------------------------------------------------

now if direct mapping and you want to calcualte tag bit then just divide PAS with

 

cache size so here if we will do so here then    2^p/2^n==>2^p-n=======> now from

 

here p-n bit for tag if direct mapping is there (where 2^n is cache size)
---------------------------------------------------------------------------------------------------------------------------------------------------------
now observe here some pattern if  you know tag bit for direct mapping and you want to for set

 

asscoicative mapping then how tag bit change
---------------------------------------------------------------------------------------------------------------------------------------------------------
if two way then means 2^1 and here in tag bit one bit increse means ---->p-n+1
if 4 way -----2^2--------->p-n+2
if 8 way then---------------------->2^3======>p-n+3
in same way if k way then ---->2^log k base2 so ------->it become p-n+logk

so p-n+logK is answer.

-----------------------------------------------------------------------------------------------------------------------

Answer 1

$\text{Physical Address Space} =2^P$ Bytes i.e. $P$ bits to represent size of  total memory.
$\text{Cache Size} = 2^N$ Byte i.e., $N$ bits to represent Cache memory.
$\text{Tag size} = 2^X$ Bytes i.e., $X$ bits to represent Tag.
Cache is $K-$ way associative.

$\text{(Size of Tag)} \times \frac{\text{Cache Size}}{K} = \text{Total Memory Size}$

$\implies 2^X \times \frac{2^N}{K} = 2^P $
$\implies 2^{X+N-\log(K)} = 2^P $
$\implies 2^{X} = 2^{P-N+\log(K)} $

$\implies X (\text{Size of Tag in bits}) = P - N + \log(K)$

Correct Answer: $B$

Comments

Whats wrong in below ?

---

Word field should be M bit, not W.

change it W to M you will get option B which is the right answer.

---

We can convert everything to bytes and solve,in that case byte offset will be M+W.

Answer 2

Since word length is given, it is best that we convert everything to words.

Physical Address Space is $2^P$ bytes.

Word Size is $2^W$ words.

$\therefore$ Total bits for addressing $\rightarrow$ $2^{P-W}$ words.

Cache Size is $2^N$ bytes $\Rightarrow$ $2^{N-W}$ words.

Block Size is $2^M$ words.

# of sets = $\frac{2^{N-W}}{2^M*2^{logK}} = 2^{N-W-M-logK}$

Now we have

TAG($x$)

Set($N-W-M-logK$)

Word Offset($M$)

$\therefore x + N - W - M -logK + M = P - W$

$\therefore x = P - N + logK$

Option (B)

Comments

What if we could meet everything to Bytes? Then M is coming extra in final answer

---

^^

If word size is mentioned, you need to assume that the memory is Word Addressable and therefore, every word would be addressed.

In your case, you'll be considering the number of bytes, therefore you'll be getting an extra $M$

---

Main memories are generally byte addressable. In most of the question we take main memory address to refer to individual byte and in this question you have taken address to refer to individual word.

How can we find out what should we take?

However in this particular question only word addressing leads to an answer which is present in the options.

Answer 3

Let the tag bits be $x$.
Given Main memory size is $2^P$, cache size is $2^{N}$, block size is $2^M$, and cache is $K$ way set associative.

So Set bits will be $N - M - logK$,
Offset bits will be $M$

Therefore $Tag\ bits = Main\ memory\ bits - set\ bits - offset\ bits$

$x = P - (N-M-logK) -M$
$\rightarrow x=P-N+logK+M-M$
$\rightarrow x=P-N+logK$

Cache address

P - N + logK

N - M - logK

M

Option (B).

Comments

Why Word offset is taken as M bits and Not Want bits as it's mentioned word size is 2W

?

---

@Markzuck Word offset is taken as M bits because no. of words  in a block is $2^{M}$. Offset bits are used to represent no. of words. Since there are $2^{M}$ words, M bits are more than enough to represent each word in the block. Offset bits represent the size of a block in terms of no. of words.

Answer 4

Given 1 word = $2^{W} $ byte, Cache m/m= $2^{N}$ byte, PAS=$2^{P}$ byte 

Physical address is of $P$ bits

Size of cache block= $2^{M}$ words * $2^{W}$ byte= $2^{M+W}$ byte

Word Offset= $M+W$

Number of block in cache= $\frac{2^{N}}{2^{M+W}}$= $2^{N-M-W}$ 

Number of sets = $\frac{2^{N}}{2^{log_2K}}$= $2^{N-M-W-log_2K}$ 

Set offset=$N-M-W-log_2K$

TAG = $P-(N-M-W-log_2K)-(M+W)$ = $P-N+log_2K$

Hence Option b) is correct

Comments

thanks