GATE IT 2008 | Question: 80

Question

Consider a computer with a $4$-ways set-associative mapped cache of the following character­istics: a total of $1 \ MB$ of main memory, a word size of $1$ byte, a block size of $128$ words and a cache size of $8 \ KB$.

The number of bits in the TAG, SET and WORD fields, respectively are:

• A. $7, 6, 7$
• B. $8, 5, 7$
• C. $8, 6, 6$
• D. $9, 4, 7$

Answer 1

Number of cache blocks $=\dfrac{8KB}{(128\times 1)} = 64$
 

Number of sets in cache $=\dfrac{\text{Number of cache blocks}}{4\text{ (4-way set)}}
=\dfrac{64}{4}= 16$

So, number of SET bits required $=4 \text{(as $2^4$ = 16, and with 4 bits we can get 16 possible outputs)}$

We can now straight away choose (D) as answer but for confirmation can proceed further. 

Since, only physical memory information is given we can assume cache is physically tagged (which is anyway the common case even in case of virtual memory).

So, we can divide the physical memory into $16$ regions so that, each set maps into only its assigned region.

So, size of a region a set can address $= \dfrac{1MB}{16} = 2^{16} \text{ Bytes}= \dfrac{2^{16}}{128}= 2^9$ cache blocks (as cache block size is $128$ words $= 128$ bytes).

So, when an access comes to a cache entry, it must be able to determine which out of the $2^9$ possible physical block it is. In short, it needs $9$ bits for TAG. 

Now, cache block size is $128$ words and so to identify a word we need $7$ bits for WORD. 

Comments

Sir, When u are writing, "we can divide the physical memory into 16 regions so that, each set maps into only its assigned region."
Do u mean 16 continuous regions ?. i.e Block 0 to Block 15 will map to Set 0 ?.

---

@ARJUN  Sir  please  explain  this line again ,I am not getting it .  

"we can divide the physical memory into 16 regions so that, each set maps into only its assigned region. "

---

I don't think these 16 regions of main memory which mapped into cache are continuous.

---

@Arjun I think sir  you are giving some sort of proof of tag bcz generally we find tag bits via subtraction but still I think the whole result depends on the number of sections we make in MM unless we know that we have to make 16 section 

Answer 2

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