GATE2014-2-44

Question

If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?

• A. Width of tag comparator
• B. Width of set index decoder
• C. Width of way selection multiplexer
• D. Width of processor to main memory data bus

Comments

I think width of any type of BUS is not affected by associativity of cache whether it is processor to main memory bus OR  bus internal to the CPU!!

---

Right.

Answer 1

If associativity is doubled, keeping the capacity and block size constant, then the number of sets gets halved. So, width of set index decoder can surely decrease - (B) is false.
Width of way-selection multiplexer must be increased as we have to double the ways to choose from- (C) is false

As the number of sets gets decreased, the number of possible cache block entries that a set maps to gets increased. So, we need more tag bits to identify the correct entry. So, (A) is also false.

(D) is the correct answer- main memory data bus has nothing to do with cache associativity- this can be answered without even looking at other options.

Comments

D) Width of processor to Main Memory Data Bus

---

---

sir i did not understand the way selection part, if there are 2 blocks in a set and the tag is k bits then there will be 2* k multiplexers,if there are 4 blocks in a set and the tag is k bits then 4 * k multiplexers, but what role or which one is the way selection multiplexer?

---

"way" is for no. of blocks in a set. For $k-way$, all $k$ blocks in a set are compared simultaneously using tag comparator and the matching one is multiplexed using a $k-way$ multiplexer.

---

got it sir :)

---

@arjun sir...What is the difference between way selection multiplexer and set index decoder.

Please explain...

---

decoder is used to find, which set to look into? it takes set field bits of address as input.

while a multiplexer takes tag bits of cache lines as input and output of these multiplexers is given to comparator that compares them with tag of the address.

---

can you explain with a diagram..

---

Hi Sir , getting confussed with the way selction multiplexer . Sir when it is asking for way seleection multiplexer then does it means no of mux required to compare tag bits

---

width of way selection multiplexer means finding the size of multiplexer as per how many input lines are there .

---

......................

---

Where is decoder??????

---

See the 8 set bits in the figure and for any particular combination of those 8 bits, a set out of 256 possible ones is selected. This is done by the decoder -- not explicitly shown in the above figure.

---

How to visualise this figure

---

Arjun Sir good explanation

---

Main memory data bus has nothing to do with cache even if we double the associativity by maintaining the block size and capacity unchanged.

---

what are the select lines to mux? for 4x1 there should be 2 select lines? I can see four..please explain

---

@Debashish Deka here mux is just selecting datas and what are these 4 tables denote?

All have same index,ple ple clarify.

---

@vineet.ildm here first we have to select a set with the help of the decoder and then after selecting that set ,we have to select a block from that set by comparing all tag bits of the blocks of that particular set with the help of the multiplexer.

Am I wrong?

---

no of multiplexers is equal to no of data bits ??

---

@amarVashishth

If you are increasing set then the tag has to decrease. Reason being physical address is constant and the block size is fixed.

---

@Arjun  Sir

Is it like associativity by default means way associativity??

---

Whats the other associativity?

---

Yes we can assume if associativity is given in question then they are talking about k way set associative cache

because

if we make k = no. of lines in cache $\implies$ it is fully associative cache.

if we make k = 1 in cache $\implies$ it is direct mapped cache.

So all cases of associativity are covered.