edited by
11,151 views
35 votes
35 votes

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:  

  1. $2.4$ $ns$
  2. $2.3$ $ns$
  3. $1.8$ $ns$
  4. $1.7$ $ns$
edited by

4 Answers

Best answer
22 votes
22 votes
$\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$
edited by
22 votes
22 votes

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$

edited by
17 votes
17 votes

Cache Size = 32KB

Block Size = 32 Bytes (25(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

edited by
10 votes
10 votes

Here 

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

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

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 25 is the block size)

Cache Line bits = 10 ( as no. of cache lines = 210)

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 210-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

Answer:

Related questions