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

why we not add 0.6   in case  2 .

---

Second one is direct mapped cache. In an associated cache (here it is 2-way), there are two slots for a cache set entry. So, we need to compare the tag in both the entries and we select the one that matches, and for this a multiplexer is used. We don't need this multiplexer in the case of direct mapped cache. 

---

..

---

sir . one big question to my mind is. why we have not considered the delay of mux. we have seen that the delay for 2*1 is given and we can definitely derive the total number of 2*1 muxs used to implement the 2^10 *1 mux as stated in digital logic. we are taking the delay of or gate even when they have not mentioned it and neglating that we can use the 2* to make 2^10*1 are we moulding the question according to the answer. what i think if we can make it then they should be done .

---

question says 32 kb cache ? Is this typo ?

---

In direct mapping if we want 2 power 10 to 1 MUX then why not realize it using 2 to 1 MUX  using various levels and take 0.6 for every level that we got . Infact he has not mentioned the OR gate delay we can take it zero but why are we taking 0 for mux.

---

Sir pls help me with this doubt..

(Suppose there are 4 sets and each set has 2 lines...and Tag bits are suppose 16)

First a set will be selected...for that we will be needing a 1×4 Demux.....latency of Demux required....(1)

Than

Each line of the selected set will be compared in parallel..so 2 comparators required of size 16 bits.....latency of comparators required....(2)

 

Once the line is selected,

a 2×1 Mux will be used to selected that block to transfer.....so latency of MUX is required....(3)

So total latency = (1) + (2) + (3)

Now all m asking u is to pls put small light on latency of Demux (1)..we ignored it just bcoz nothing is mentioned about in question ?

---

Some Extended Discussions on this topic

• https://gateoverflow.in/108807/discussion-regarding-cache-memory
• https://gateoverflow.in/60482/self-made-hit-latency

---

what if the cache was 4-way set associative and there were only 2:1 MUX ? so how many 2:1 MUX's would be used? 2 or 3? (i.e.0.6 ns latency would be counted twice or thrice?)

---

@just_bhavana

irrespective the associativity of cache we  need always one OR(or 2:1 MUX) gate because we only have to decide if required block is present in cache or not.

---

Comparison is done in parallel and we need to select data for which we require 2*1 mux.

---

@Hemant dont you think this diagram is wrong. It does not uses block offset at all. Also notice the 2nd comparator (=) matching tag has only one input!!! With what it is matching tag?

---

@Arjun sir its really confusing here. Now that I have taken so much of effort, please please clarify.

I guess following steps are performed in 2-way set associative mapping

1. Index set
   With 9 bits (this can be done with inputting 9 bits to DeMUX address input, DeMUX will in turn will make corresponding index bit output HIGH. But information of such indexing DeMUX or any other approach is not given, so assuming negligible)
2. Match line tag inside set indexed in above step
   With 18 bits to select appropriate line with the set (as stated this can be done 18/10=2.4 ns)
3. Offset word inside line chosen in above step
   With 5 bits. Again no information is done here about this, but can be done with MUX. Applying least significant 5 offset bits as MUX address lines and input will be data bits of different words within a line chosen. Output will be data bits of word at given offset. (Somewhat more involved since each word is multi-bit, but anyway we have to select one word present at given offset in set of many words. So many to one is functionality of MUX)

Doubts

1. No information about how to index set (Can done with DeMUX as explained above point 1)
2. No information about how to offset word inside chosen line (can be done with MUX as shown in the diagram below)
3. Not getting where to use that 2-to-1 MUX stated in question. I dont understand for what you have used it while adding its delay 0.6 to 1.8ns. You have sid "succeeding one multiplexed as the output". But I really dont get how we multiplex like that. I feel the reference circuit diagram is flawed:

---

very good explanation arjun sir

---

why we are not considering decoder latency to decode index?

---

For a  "K-way" set associative cache, we need K comparators of size "TAG" bits and $K:1$ Multiplexer to select data.

Nice slide:

http://euler.ecs.umass.edu/ece232/pdf/15-Cache-11.pdf

---

@Ayush Upadhyaya

 https://gateoverflow.in/60482/self-made-hit-latency in this the delay by the or gate has also been added 
why not so in this question?

---

@Ayush Upadhyaya

K:1 Multiplexer to select data.

That means in one set having K blocks we select data from one of the K blocks of which the tag is matched using MUX but is it possible with K : 1 MUX

Here block size is 32 byte..does that means 32 bytes from each block in selected set given to MUX so total inputs  for MUX will be 32 * K...then how K:1 ??

---

Here separate MUX for each block in set 

---

Sir you have written “Time to Select block in set” but according to the figure you have provided, it is selecting “the required word in the selected block using the block offset as the select lines”. Can you elaborate on how we are actually selecting the particular block?

---

@Arjun sir, In the figure that you have provided can you say what are the input lines and the select lines for the 2:1 MUX?

---

If in 2-way set ,we need 2 comparators .then why the time taken to compare data is taken once?

---

For set-associative mapping, we require k comparators if the mapping set is k-way. So, here we’ll require 2 comparators, right?

---

Is the diagram related to the question directly or just the general concept? Why is the width 128 bits? And the MUX output data is 32 bits? Shouldn’t it be 1B (byte addressability) i.e. 8 bits?

---

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