GATE IT 2006 | Question: 43

Question

A computer system has a level-$1$ instruction cache ($1$-cache), a level-$1$ data cache ($D$-cache) and a level-$2$ cache ($L2$-cache) with the following specifications:

\begin{array}{|l|c|c|c|} \hline \text {} &  \textbf{Capacity }& \textbf{Mapping Method} & \textbf{Block Size}\\\hline \text{$I$-Cache} & \text{$4K$ words}& \text{Direct mapping} & \text{$4$ words} \\\hline \text{$D$-Cache} & \text{$4K$ words}& \text{$2$ -way set associative mapping} & \text{$4$ words}\\\hline \text{$L2$-Cache} & \text{$64K$ words}& \text{$4$-way set associative mapping} & \text{$16$ words} \\\hline \end{array}

 

The length of the physical address of a word in the main memory is $30$ bits. The capacity of the tag memory in the $I$-cache, $D$-cache and $L2$-cache is, respectively,

• A. $1$ K x $18$-bit, $1$ K x $19$-bit, $4$ K x $16$-bit
• B. $1$ K x $16$-bit, $1$ K x $19$-bit, $4$ K x $18$-bit
• C. $1$ K x $16$-bit, $512$ x $18$-bit, $1$ K x $16$-bit
• D. $1$ K x $18$-bit, $512$ x $18$-bit, $1$ K x $18$-bit

Comments

why have we considered word addressable instead of default byte addressable ?

---

because word size is not given!

---

I think there is typo in question.

A computer system has a level-$1$ instruction cache ($1$-cache)

I think it should $I$-cache rather than ($1$-cache).

Answer 1

1. I-cache

• Number of blocks in cache $=\dfrac{4K}{4} = 2^{10} \text{ blocks}.$
• Bits to represent blocks $= 10$
• Number of words in a block $= 4 = 2^2 \text{words}.$
• Bits to represent words $= 2.$
• tag bits $= 30 - (10+2) = 18.$
• Each block will have it's own tag bits. So total tag bits $= 1K \times 18 \text{ bits}.$

2. D-cache

• Number of blocks in cache $=\dfrac{4K}{4} = 2^{10} \text{ blocks}.$
• Number of sets in cache $= \dfrac{2^{10}}{2} = 2^9 \text{ sets}.$
• Bits to represent sets $= 9.$
• Number of words in a block $= 4 = 2^2 \text{ words}.$
• Bits to represent words $= 2$
• tag bits $= 30 - (9+2) = 19$
• Each block will have it's own tag bits. So total tag bits $= 1K \times 19 \text{ bits}.$

3. L2 cache

• ​Number of blocks in cache $=\dfrac {64K}{16} = 2^{12} \text{ blocks}.$
• Number of sets in cache $= \dfrac{2^{12}}{4} = 1024\text{ sets}.$
• Bits to represent sets $= 10$
• Number of words in cache $= 16 = 2^4\text{ words}.$
• Bits to represent words $= 4.$
• tag bits $= 30 - (10+4) = 16$
• Each block will have it's own tag bits. So total tag bits $= 2^{12} \times 16\text{-bits} = 4K \times 16\text{-bits}.$

Option (A).

Comments

@Deepak Poonia Sir please clear @Abhijit Sen doubt.

---

@Abhijit Sen

No, actually it is 

($no$. $of$ $cache$ $blocks$) $*$ $(no$. $of$ $tagbits + additional$ $bits)$

$additional$ $bits$ may be valid,dirty,protection etc , as given in the question.

and it is because cache maintains these bits for all the blocks present inside it.

---

Adding more details here

Tag-Directory-size = ( Tag bits * # of blocks )

For a k-way set associative cache, k is the no. of blocks in a set. 

No. of blocks can be calculated as follows for each type of cache. 

1. I-Cache – Direct mapped cache – Tag dir = (18 tag bits * ( # of blocks ) ) = (18-bit * 1K )
    
2. D-Cache – Set associative – Tag dir = (19 tag bits * No of sets * set associativity ) = (19 * 2$^9$ * 2 ) = ( 19-bit * 1K )
    
3. L2-Cache – Set associative – Tag dir = ( 16 tag bits * No of sets * set associativity )
   
   = ( 16 * 2$^{10}$ * 4 ) = ( 16 * 2$^{12}$ ) =  ( 16-bit * 4K )

Similarly, for a fully-associative cache, tag dir = ( Tag bits * (# of blocks) )

A fully associative cache is also a B-way set associative cache ( only 1 set and B is the # of blocks and all blocks remain in single set )

So, Tag-directory-size for fully associative = ( tag bits * No of sets * set associativity ) = ( tag bits * 1 * ( # of blocks ) )

Hope this helps

 

Answer 2

………………………....………………………………………..