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

are these type of questions in syllabus?

---

for set Assosicative  cache

offset = 5 bit

set  = 9 bit

tag = 18 bit

hit latency for this =  time to campare the data  + time to select block in set  =  0.6 + 18/10 = 6/10 + 18/10

                               24/10 = 2.4 ns

for direct mapped

offset = 5 bit

line index = 10 bit

tag = 19 bit

hit latency for this  = 0.6 + 17/10 = 6/10 + 17/10

                                23/10 = 2.3 ns

---

Set associative Hardware Implementation 

(Go classes slide) 

 

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

---

@swaroopsahoo multiplexer is not used for selecting the set and even if they were used 512:1 mux can't be used only 2:1 mux can be used, which will make the circuit very large. It's assumed sets can be selected without the use of mux but some non defined circuit. The mux can be used only in the selection of line of cache from the 2 way set associate cache. Mux behaving like an OR gate here.

---

This question is quite unclear.

We are given with dealy for a 2:1 MUX, but no dealy for 512:1 MUX.

Now 2:1 MUX can be used to implement an OR gate and as well 512:1 MUX. In the latter case, the circuit will become very complicated (512/2 + 512/4 +.....+ 1, 2:1 MUXes will be needed).

But apparently the question wanted us to ignore the dealy of 512:1 MUX but to include the dealy of compartor and their multiplexed output (through 2:1 MUX).

Hence this question is purposefully confusing, and bad.

Answer 2

 

gives a better insight.

Comments

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

---

https://cs.stackexchange.com/questions/102566/number-of-mux-required-for-cache-mapping

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

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

---

Best Answer!

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

Comments

and also want to add thatevery thing works in parallel so , 2 coparater only take 1.8 ns not 3.6!

Answer 5

 

Comparison is done in parallel for multiplexer 

---

Comments

If MRU works better for any sequence why do we even have LRU as MRU is much easier to implement? So that cant be TRUE. 

Associative cache is “expected” to give a better hit rate than direct mapped cache – but not a guarantee. Like randomized quick sort is expected to run in $O(n \log n)$ time. Expectation matters in practice because exceptions are $\textbf{RARE}$ and often ignored. 

---

Thank-you Sir

---

Thank you very much Sir. Got to know new concepts. Thanks to Mohit too. :)

Answer 6

For calculating extra memory overhead and hardware latency delays , you will always  need to find and use the Tag bits.