retagged by
11,772 views
44 votes
44 votes

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

  1. $P-N- \log_2K$
  2. $P-N+ \log_2 K$
  3. $P-N-M-W- \log_2 K$
  4. $P-N-M-W+ \log_2 K$
retagged by

9 Answers

Best answer
43 votes
43 votes
$\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$
edited by
53 votes
53 votes

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)

12 votes
12 votes

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

9 votes
9 votes

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

Answer:

Related questions