edited by
12,114 views
32 votes
32 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 size of the cache tag directory is:

  1. $160$ $\text{Kbits}$
  2. $136$ $\text{Kbits}$
  3. $40$ $\text{Kbits}$
  4. $32$ $\text{Kbits}$
edited by

4 Answers

Best answer
40 votes
40 votes

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\text{ bits}$ are needed for accessing a set. Inside a set we need to identify the cache entry. 
Total number of distinct cache entries $=\dfrac{2^{32}}{\text{cache entry size}}=\dfrac{2^{32}}{32}=2^{27}$
Out of this $2^{27},$ each set will be getting only $\dfrac{2^{27}}{2^{11}}=2^{16}$ possible distinct cache entries as we use the first $11 \text{ bits}$ to identify a set. So, we need $16$ bits to identify a cache entry in a set, which is the number of bits in the tag field.

Size of cache tag directory$=\text{Size of tag entry}\times \text{Number of tag entries}$ 
$=16 +(2+1+1) \text{ bits (2 valid, 1 modified, 1 replacement as given in question)}\times 8\ K$
$= 20\text 8 = 160\text{ Kbits}$

Not needed for this question, still:

Valid bit: Tells if the memory referenced by the cache entry is valid. Initially, when a process is loaded all entries are invalid. Only when a page is loaded, its entry becomes valid. 

Modified bit: When processor writes to a cache location its modified bit is made $1.$ This information is used when a cache entry is replaced- entry $0$ means no update to main memory needed. Entry $1$ means an update is needed. 

Replacement bit: This is needed for the cache replacement policy. Explained in the below link:

https://www.seas.upenn.edu/~cit595/cit595s10/handouts/LRUreplacementpolicy.pdf

Correct Answer: $A$

edited by
47 votes
47 votes

No of Line or block=$\frac{256KB}{32B}$

                            =$2^{13}$

No of sets=$\frac{No\ of\ Line}{P-way}$

               =$\frac{2^{13}}{4}=2^{11}$

tag controller maintains=Tag bit+valid bit+modified bit and+replacement bit.

                                     =16+1+2+1=20 bits

So tag directory size=No of Line * Tag controller bits

                               =$2^{13}\times 20$

                             =160Kbits

0 votes
0 votes

Cache size=256KB=2^18 Byte

K=4-way associative

Block Size=32 Byte=2^5 Byte

lines=CS/BS=2^18/2^5=2^13

Sets=lines/K=2^13/2^2=2^11

So

tag bits=16 set number=11 bits block offset=5 bits

Therefore

tag directory=tag bits x number of cache lines=160Kbits

Answer:

Related questions

33 votes
33 votes
2 answers
1
37 votes
37 votes
2 answers
2
gatecse asked Aug 5, 2014
15,582 views
Register renaming is done in pipelined processors:as an alternative to register allocation at compile timefor efficient access to function parameters and local variablest...
48 votes
48 votes
4 answers
4
go_editor asked Apr 21, 2016
13,582 views
Consider the following relations $A, B$ and $C:$ $$\overset{\textbf{A}}{\begin{array}{|c|c|c|}\hline\\\textbf{Id}& \textbf{Name}& \textbf{Age} \\\hline12& \text{A...