GATE CSE 2006 | Question: 74

Question

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: 

• A. $2.4  \text{ ns} $
• B. $2.3  \text{ ns}$ 
• C. $1.8  \text{ ns}$ 
• D. $1.7  \text{ ns}$ 

Comments

@Abhrajyoti00
we will not have Mux in associative cache

---

@JAINchiNMay why?

 

---

@Pranavpurkar @JAINchiNMay Our doubts have been answered by me here: https://gateoverflow.in/1851/gate-cse-2006-question-74?show=382102#c382102

Answer 1

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$

Comments

How do we came to know that we have to consider the 18 tag bits for “Time to select the block in set” ?

---

If OR gate delay is given, do we need to include OR gate delay also or, do mux and OR gate execution happen parlelly ???

@Arjun 

---

How 2:1 multiplexer’s time is used here? there are 512 sets (in the first 2 way set assoc mapped cache organization given in question) so multiplexer should be of size 512:1 and its latency should be given.

Answer 2

 

gives a better insight.

Comments

@Arjun sir, i think that implementation given in above answer is correct because in implementation we can't keep shift 2*1 multiplexer on basis of  "blocks of which set" we need at any point of time.

---

Finally a satisfactory ans. Thank u.

---

in direct mapped cache why do we  need 17 different multiplexers, total number of lines = 2^10=1024 . So number of multiplexer working in parallel should be 1024 as output of the multiplexer is the entire cache line, including both tag bits and data. Tag bits from all these 1024 multiplexer will be compared using 17 bit comparator.

i.e. 1024 multiplexer of 2^10-to-1.

Please correct if i am wrong...

Answer 3

In Direct Mapped Cache

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

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

only 1 comparator and 17  2¹⁰-to-1 MUX are required but  MUX are operating in parallel

2-way Set Associative Cache

Hit Latency = 2⁹to1 MUX Delay + Comparator Delay + OR gate delay

                   = 0 + 18/10 + 0.6 = 2.4 ns

18(= 2 comparators per set )  324 (= 36 2⁹to1 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

Comments

@Arjun  sir 

We need 

For direct-mapped cache :

                   1) Block-index decoder,

                   2) comparators

For fully associative cache

                   1) comparators

                   2) Block-selection MUX

For Set-associative cache,

                   1) set index decoder,

                   2) comparators,

                   3) Way-selection MUX.

Is this correct ??? Also we can use a decoder to find the correct word within a block using Block-offset bits ...right ??? 

---

only one 1 MUX for Direct mapping

---

why did we assume zero for direct mapping mu latency we can also for 2^10 - 1 mux using 2 - 1 mux and find the mux latency for direct mapping as well

Answer 4

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