+1 vote
433 views

https://gateoverflow.in/1851/gate2006-74

https://gateoverflow.in/43565/gate2006-75

can someone check this questions ?

i am not getting, how without help of MULTIPLEXER or DECODER, we are searching hit/miss

i mean in direct mapping, how we select lines and their respective Tags without help of Multiplexer ?

| 433 views
+1
brother how you are going to select set ?

i mean in direct mapping we take help of MUX and select appropriate Tag,

just like that what hardware/ how you are going to select the set ?

after selecting the set, it is easy ===> no.of comparators, size of comparators and OR gate, we can understood.

One more thing, where we use OR gate, in Direct Mapping ?
+1

A 2-to-1 multiplexer has latency of 0.6nsThis

This 2 - to -1 MUL is given to select the two comparators ( because of 2-way associative mapping). the comparing the tags bits.

Not for the Direct Mapping.

I think this is the point we are not getting ???.

One important point they neglected the MUL implementation in both cases Direct and Se-Associative.

that 2 to 1 MUL is to select the two comparators.

If you are not getting let me know.

+1

One important point they neglected the MUX implementation in both cases Direct and Set-Associative.

then none of the people even did a single comment on those questions regarding this.

that 2 to 1 MUL is to select the two comparators.

i hope it is converted into OR gate but not used as MUX

but what about the implementation of set-associative?

how you are going to select set ?

+1

One more thing, where we use OR gate, in Direct Mapping ?

they have neglected the MUL implementation of the Direct mapping.there is nothing give about it in the question. So, it is zero

if given, then we have to add that also.

0
i mean to say, in direct mapping, we didn't use OR gate....

But on seeing 2 x 1 Mux, i think they implemented 2$^{10}$ x 1 MUX which we used in direct mapping
0

Noting is given related to MUL of the Direct Mapping. So, that's why we have neglected the latency of the MUL. If in any question it is given then we have to take that. ( generally, we neglect the latency of the MUL becuase it is less compare comparator)

Only thing is given that is the latency of the comparator.
+1

But on seeing 2 x 1 Mux, i think they implemented 21010 x 1 MUX which we used in direct mapping

hahah No. it is not the case. I think everyone is confused about seeing that 2 to 1 MUL.

That is to select the two comparators and compare the tag bits. ( that will be useful in the case of the set associative mapping)

0

A 2-to-1 multiplexer has latency of 0.6ns while a k−bit comparator has latency of  k/10 ns

i didn't get anything from this line to say MUX delay neglected....

it's ok, by seeing the options we can realize to neglect it :)

0
In Direct Mapping, there is only one comparator Ok.

==> But in 2-way associative mapping, we need two comparators.

Just tell how you will select this two comparator ???

So, here we need 2 to 1 MUL for set associative.
0

But on seeing 2 x 1 Mux, i think they implemented 2^10 x 1 MUX which we used in direct mapping

then what will be latency can you imagine ??? circuit will be too complex ???

what will be number of such MUL for n bits TAG ???

0

@Shaik Masthan

MUX selects which set of the block active

Means for 2 way set associative, it selects either set1 or set0

but is it needed for direct mapped cache? No

that is why MUX ot needed for direct mapped cache

0
Tag bits need comparator , not MUX

right?
0

@srestha in Direct mapping, Number of MUX = bits in tag. Input to all MUX(select lines) is the line number field. All MUX gets the same input and each MUX is responsible to bring a single bit. I mean For LSB MUX 0 for next bin MUX1 till MSB. Once it is available at comparator, we compare the tag.

I did the same thing while solving this question. Calculated the delay of 2^10 X 1 MUX using 2 X 1 MUX

0

In Direct Mapping, there is only one comparator Ok.

@kumar.dilip OK fine. Input to comparator is tag bits from the address AND Tag bits from the line. How Tag bits of the line is given to the comparator then? I agree with @Shaik Masthan, MUX has to be there but mostly it's delay is too small to consider.

+1

@tusharp

kumar is also saying to use MUX, but that delay is neglected, due to in the question they didn't specify anything about those MUXes.

@srestha mam, @kumar.dilip brother,

But in 2-way associative mapping, we need two comparators.

Just tell how you will select this two comparator ???

So, here we need 2 to 1 MUL for set associative.

in n-way set associative, we have n-block per a set, ===> we have n comparators,

we know that, comparator has two inputs with size bits of tag. let name them as A and B.

for each comparator, A is fixed, which we want to search, for B, each comparator takes from the block which have it's own tag bits.

Finally, i have n-comparators ==> n bit output, in this at a time only one bit is one, we just want a hit therefore connect every comparator output to a OR gate. ( in the question it is specified that HIT latency required but not Which is causing HIT )

in our example we have 2-way associative ==> 2 comparators, and 1 OR gate of FAN-in = 2 required

2-i/p OR gate can be generate with 2 x 1 MUX ===> we use MUX instead of OR gate.

But as you are saying, MUX is not use for selecting the Comparators !

@kumar.dilip

then what will be latency can you imagine ??? circuit will be too complex ???

what will be number of such MUL for n bits TAG ???

yes, circuit must be complex, in that case my latency is

2$^{10}$ x 1 MUX realized with 1023 2 x 1 MUXes but there are only 10 levels ===> 10 * 0.6 = 6 ns

all these 2$^{10}$ x 1 MUX works parallel ===> total delay by MUXes = 6 ns

So, total delay of hit latency = comparator delay + MUX delay = 1.7+6 = 7.7 ns

I know the options are not matching...

0

21010 x 1 MUX realized with 1023 2 x 1 MUXes

But question says we have only one 2X1 MUX. It is given "A 2−to−12−to−1multiplexer has latency of 0.6ns". So may be this MUX has nothing to do with our direct mapped cache implementation but can be used for 2 way associative cache.

0

Just go through my previous comment. you can easily understand the question.

0

@Shaik @MiNiPanda

0
MUX is to select block from cache entry

TAG used to select block from MM

See the diagram, TAG doesnot need MUX but data field need MUX
0
mam, i already read it, but all are saying the implementation is not consider !