GATE CSE 2006 | Question: 75

Question

Consider two cache organizations. First one is $32$ $kB$ $2$-way set associative with $32$ $byte$ block size, the second is of same size but direct mapped. The size of an address is $32$ $bits$ in  both cases . A $2$-to-$1$ multiplexer has latency of $0.6 ns$ while a $k-$bit comparator has latency of  $\frac{k}{10} ns$. The hit latency of the set associative organization is $h_1$ while that of direct mapped is $h_2$.
The value of $h_2$ is:  

• A. $2.4$ $ns$
• B. $2.3$ $ns$
• C. $1.8$ $ns$
• D. $1.7$ $ns$

Comments

we need both MUX and Comparator to retrieve cache line tag , at least that’s what the question urges us to do .I feel assuming a decoder is not fair for this question. Since cache line selection is 10 bit and tag is 17 bit , we need 17 2^10 to 1 MUX . A 2^10 to 1 MUX can be made using 2 to 1 MUX and the latency will be 10*0.6 = 6ns (Kindly try to make 2^10 to 1 using 2 to 1 , you will figure out). Since 17 2^10 MUX will operate parallel , the total MUX latency of 6ns persists. Now we have 17 bit tag and we put it through a 17 bit comparator and it’s latency is 17/10 = 1.7ns

Hence the total latency for HIT or MISS will be 6 + 1.7 ns = 7.7 ns

---

My comment here will be helpful: https://gateoverflow.in/1851/gate-cse-2006-question-74?show=382102#c382102

---

getting 2.3

mux delay + comparator delay.

---

same here, is it wrong though??

Answer 1

$\text{number of sets}  = \dfrac{\text{cache size}}{\text{no. of blocks in a set } \times \text{ block size}}$

$=\dfrac{32KB}{1 \times 32B} = 1024$

So, number of index bits $= 10,$ and

number of tag bits $=32-10-5=17.$

So, $h2 =\dfrac{17}{10}= 1.7\text{ ns}$

Correct Answer: $D$

Comments

Subbu. How is an index decider implemented? I saw the Prof biswas lecture but in it the implementation of ‘index decider’ is not shown

edit: RBR wasnt wrong. the decoder used in the Prof biswas lecture is the 'index decider' that Subbu. is talking about. and the output of that decoder is going to the AND gate associated with the corresponding tag in the tag directory. Prof has also mentioned that these AND gates are associated with ALL the tags in the tag directory but they have only shown the AND gate which the decoder is going to enable. 

So where is the MUX u might ask? well MUX is implemented by parallel AND gate among which only one AND is enabled. This is exactly what is happening above. So prof has only shown one AND gate of this MUX 

---

@Arjun , @gatecse  @Kabir5454 @Abhrajyoti00 

for h3( full associative)

tag bit = 32-5 = 27 

h3 = 27/10 = 2.7 ns 

 

Please verify.

 

---

@GateOverflow04 For Fully Associative or Set Associative cache, Hit Latency = (Comparator Crkt. Latency + MUX Latency)

You have calculated #tagbits correct for fully associative.

Thus here, for H3 (Fully Associative) hit latency will be = $27/10 + 0.6 = 2.7+0.6ns = 3.3ns$ 

My comment here will be helpful: https://gateoverflow.in/1851/gate-cse-2006-question-74?show=382102#c382102

Answer 2

word offset $=5 \text{-bit}$

block offset $=\dfrac{32\,Kb}{32}=10 \text{-bit}$

so tag bit $=32-10-5=17\text{-bit}$

hit latency$=\text{mux delay + comparator delay}$

1.  mux is not required in direct mapped cache coz we have only one comprator
 (IF IT IS $2\text{-way}$ SET ASSOCITATIVE THEN COMPRATOR WILL BE $2$ AND WE
 NEED A MUX OF $\text{2-TO-1}$ TO DECIDE HIT/MISS) so mux delay$=0.$

2.  comp. delay $=\dfrac{k}{10}=\dfrac{17}{10}=1.7$

so $h2 =1.7$

Comments

now in set associative 2 comparators are needed then( 1.8*2)+0.6 = 4.2 should be the ans?? am i right??

---

But in general, for Direct mapping we need T MUX (T=No. of TAG bits) , so why aren't we taking MUX time into consideration?

---

Mux will be required to select  particular block to be read however in direct mapped cache only one comparator needed so no need to use mux no need to add mux latency

---

that is line bit not block offset!

block offset =32Kb/32=10-bit

Answer 3

Cache Size = 32KB

Block Size = 32 Bytes (2^{5(Number of word bits)}) 

#Lines in cache = 32KB/32B = 1K lines

So, 10 bits are needed for line number of cache

5 bits for Word Number

Tag = 32-(10+5) = 17 bits.

So, comparator latency is k/10 = 17/10 = 1.7ns.

TAG	LINE	WORD
17	10	5

Here we won't need any multiplexer because  the line number is provided, the respective tag number of only that line is compared with the tag value. If if matches, hit occurs otherwise miss.

Now, since in hit/miss comparison only one comparator is involved, hit latency of this cache is 
Latency of K bit comparator (In case of direct mapped cache there is no need of MUX). Line number is provided and using that particular line is selected and tag bits of only that line is checked.
1.7 +0 = 1.7ns (d) ANS

Refer the below figure for more details.

Reference : Computer Organisation and Design : Henessy and David

Comments

@Ayush Upadhyaya But the question urges to consider 2- 1 MUX and k bit Comparator . Why do we assume that a decoder is to be used ? Don’t you think it’s us being presumptuous ?

---

why are we considering that decoder will have no latency, i guess decoder and mux of same size has same latency.

---

@Ayush Upadhyaya Sir,

But what if addressed block has more number of Bytes(64Byte) than data width(2Byte).For that we need a mux.

Answer 4

Here 

Cache size =32 KB , Block size = 32 B . 

Therefore no. of cache lines = cache size / block size = 32KB/32B = 1K or 2¹⁰  .

Now since we have to find out hit latency for Direct Mapped cache organization h2 :

Physical Address = 32 bits.

Block offset or Word offset = 5 ( as 2⁵ is the block size)

Cache Line bits = 10 ( as no. of cache lines = 2¹⁰)

Hence Tag bits = Physical address bits-(Block offset bits + Cache Line Bits)= 32-(10+5) =17.

Latency of comparator depends on no of tag bits as it compares the tag bits from the physical address with the output of the MUX . So here we have 17 tag bits so we need 17 bit comparator. As in question it is mentioned that for k-bit comparator latency is k/10 ns so latency of comparator in this case is 17/10 =1.7 ns

Also from h/w implementation of direct mapping we know the cache line bits (10 in this case) act as select lines for the MUX. Hence here we will need MUX which are all 2¹⁰-to-1 . But in the question it is mentioned 2-to-1 MUX whose latency is essential to calculate hit latency of organization h1 that is 2-way set associative mapping and for our organization h2 that is direct mapping we have to consider MUX latency as negligible as it is not mentioned. So 

Total latency = Latency of comparator(Always 1 comparator is required in Direct mapping) + Latency of MUX(negligible here)

                     = 1.7 ns

Comments

we can convert 2^10 mux to 2^1 mux

we will have 10 series of 2x1 mux working