edited by
28,639 views
65 votes
65 votes

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

The value of $h_1$ is: 

  1. $2.4  \text{ ns} $
  2. $2.3  \text{ ns}$ 
  3. $1.8  \text{ ns}$ 
  4. $1.7  \text{ ns}$ 
edited by

5 Answers

Best answer
74 votes
74 votes

Cache size is $32 \hspace{0.2cm} KB$ and cache block size is $32 \hspace{0.2cm} B$. So,

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

$ = \dfrac{32 \hspace{0.2cm}KB}{2 \times 32 \hspace{0.2cm}B} = 512$

So, number of index bits needed $= 9$ ( since $2^9 = 512$). Number of offset bits $= 5$ (since $2^5 = 32 \hspace{0.2cm} B$ is the block size and assuming byte addressing). So, number of tag bits $= 32 - 9 - 5 = 18$ (as memory address is of $32 \hspace{0.2cm} bits$). 

So, $\text{ time for comparing the data}$ $ \text{= Time to compare the data + Time to select the block in set} \\= 0.6 + 18/10 \text{ ns} \\= 2.4 \text{ ns}.$

(Two comparisons of tag bits need to be done for each block in a set, but they can be carried out in parallel and the succeeding one multiplexed as the output).

Reference: https://courses.cs.washington.edu/courses/cse378/09au/lectures/cse378au09-19.pdf

Correct Answer: $A$

edited by
119 votes
119 votes
 

gives a better insight.

10 votes
10 votes

In Direct Mapped Cache

Hit Latency = 210to 1 MUX Delay + n-bit tag comparator  Delay
                    =  0 + 17/10 =1.7ns 

  ( No information Regarding 210to 1 MUX delay . So let us assume it to be 0 )

only 1 comparator and 17  210-to-1 MUX are required but  MUX are operating in parallel


2-way Set Associative Cache

Hit Latency = 29to1 MUX Delay + Comparator Delay + OR gate delay

                   = 0 + 18/10 + 0.6 = 2.4 ns


18(= 2 comparators per set )  324 (= 36 29to1 MUX  per set ) 9 (= 1 OR gate per set ) are required.
comparators are operating parallelly and MUX are operating parallelly . OR gate can be realised usuing 2to1 MUX

edited by
3 votes
3 votes
Tag bit= 18, set bit= 9, offset bit= 5

Firstly 1 multiplexer or set index decoder(size 2^9 x 1) will be used to reach the required set, then all tag bits of 2 lines in that set will be matched with the help of 2 comparators of size 18(tag bits). Don't bother yourself on how to fetch all tag bits from 2 lines (we could use multiplexer same as we fetch from Direct & Associative mapping) because that will become complex & advanced topic. Then lastly we required an OR gate or a multiplexer(mux. can work as an "OR" gate) to check whether there is a hit or miss.
So ignore mux. delay reach to set no. or to fetch tag bits in all mapping techniques.
Note- A comparator compares 1 bit at a time that's why T.comparator= K * comparator latency

Hit latency=Comparator Delay + OR gate(Mux.) delay

                 =1.8 + 0.6 = 2.4 ns
Answer:

Related questions