1 votes 1 votes 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 ? CO and Architecture cache-memory direct-mapping comparators + – Shaik Masthan asked Dec 18, 2018 Shaik Masthan 2.3k views answer comment Share Follow See all 34 Comments See all 34 34 Comments reply Shaik Masthan commented Dec 18, 2018 reply Follow Share @Mk Utkarsh @MiNiPanda @srestha @tusharp @kumar.dilip @eyeamgj please help on this if you know and you are free :) 0 votes 0 votes MiNiPanda commented Dec 18, 2018 reply Follow Share MUX is used when we have to select one among many. In direct mapping first we go to the right block using the block no. provided in the field, then when we arrive at the right block, we need to compare the tag bits of the block already present in the cache(if any) with the tag bits in the address referred to. This can be done using comparators only. If block is present then comparator outputs 1 else 0. From this we can check the hit or miss.We don't have multiple options to choose from. So MUX isn't required here. While in Set associative mapping, after going to the right set, we can see k no. of block present there. Now we need to choose exactly one among them. First we check whether the block we want is present in the set using k comparators to compare k lines in the given set with the referred address parallely. If the block is present at all, then exactly one of the comparators will output 1. But we need to know which one among the k comparators has output 1 so that we can get the right block. For this purpose MUX is used. 0 votes 0 votes Shaik Masthan commented Dec 18, 2018 reply Follow Share In direct mapping first we go to the right block using the block no. provided in the field, how we can do this without help of some hardware ? 0 votes 0 votes Shaik Masthan commented Dec 18, 2018 reply Follow Share But we need to know which one among the k comparators has output 1 so that we can get the right block. For this purpose MUX is used. MUX size should be the size of the Set, right ? 0 votes 0 votes MiNiPanda commented Dec 18, 2018 reply Follow Share MUX size should be the size of the Set, right ? Yes.. how we can do this without help of some hardware ? I had the same doubt I searched a lot on this..nowhere could I find any proper detailing..but like page table indexing, I assumed the cache is also indexed. The page table is indexed by page number, here cache is indexed by block no. Maybe pointers are maintained to each block no. Not sure :/ 0 votes 0 votes Shaik Masthan commented Dec 18, 2018 reply Follow Share yes brother i am also struck there only... One approach which i have seen is for direct mapping, Using MUXES, there are n bits in tag ====> take n MUXES where each provide one bit of tag, and each MUX size = no.of lines in the cache, take the cache line bits as select lines. i mean, we have k cache lines, each of them have tag bits of size n, so by taking n MUXES, for tag$_0$ bit, connect 0th bit of every cache line, for tag$_1$ bit, connect 1st bit of every cache line, ===> size of MUX = k x 1, no.of MUXes = n, By using select lines we get correct Tagbits of required location, then we have to compare with original tag. i mean output of every MUX, arrange in order tag$_{n-1}$....... tag$_2$ tag$_1$ tag$_0$ give input to the n-bit comparator, from another side give n-bit tag of Main memory Block. 0 votes 0 votes Hemanth_13 commented Dec 18, 2018 reply Follow Share In direct mapped cache TAG LINEnumber BlkOffset --> we take line number give these as select line to MUX --> From the output of MUX we take the Tag bit, if we have n tag bits we use n MUX --> Now compare the Tag from Physical address and TAG bits given by MUX (cache) if they are same its HIT else a MISS. 0 votes 0 votes Shaik Masthan commented Dec 18, 2018 reply Follow Share @Hemanth_13 did you checked those GATE questions ? 0 votes 0 votes kumar.dilip commented Dec 18, 2018 reply Follow Share For Direct mapping. For k-bits of tag , we need k-multiplexer and only one comparator. Implementation. As we know for k-bits tag we need k-multiplexer. Each of the multiplexers takes the one-one bit from each of the the tags.So, the k-bits are taken by the k multiplexer.here line number works as the select line for the multiplexer. So, each of the output of the multiplexer is given to the comparator and each bits of tags bit are also give to the comparator. According to that it will decide hot or miss. For example. Lets take 1 tag bits and 2 bits line. there will be 4 line numbers. here we need one 1*4 multiplexer. one comparator. ==>> Each of input lines(4) will take the one bit from each of the tags of cache. ==> the output of the comparator is compared with the tags bits. According to that it will show hit or miss. if the latency of multiplexer is 1ns and latency of comprator is 1ns the hit latency will be 1 + 1 = 2 ns ======================================================================================== If there is 2 bit of TAG. The 2 multiplexer one for taking the first bits of the tag from each lines.Second Mul for taking the second bits from each of lines of the cache. ===>>> these 2 bits output of the MUL are compared with the TAG , According to that it will show hit or miss. 2 votes 2 votes Hemanth_13 commented Dec 18, 2018 reply Follow Share Yes.. above explanation from amarVashishth explains it. 0 votes 0 votes Shaik Masthan commented Dec 18, 2018 reply Follow Share @Hemanth_13 A 2−to−1 multiplexer has latency of 0.6ns it is given 2 x 1 MUX in question, from there i derived the latency for 2$^{10}$ x 1 MUX. there is no term saying 0.6 for OR gate @kumar.dilip yes, what i wrote in the previous comment, you write exactly that one, but i don't know the implementation part for set associative, could you explain it like what you did for Direct Mapping, by the way, i can't tag you at that time, but i am able to tag you now, is there any issue regarding with that ? 0 votes 0 votes Hemanth_13 commented Dec 18, 2018 reply Follow Share As MUX is functionally complete we have to use it as OR gate. i too didn't understand why the latency for $2^{10 }$x 1 MUX was not calculated and used. 1 votes 1 votes kumar.dilip commented Dec 18, 2018 reply Follow Share I'm explaining you set associative mapping according to the question. As we have 2-way associative mapping. here we are going to divide the cache into the sets of size two each. ==>So, here there will be 2-comparator because the cache is divided of sets of size 2 each( 2- ways associative mapping) ====>> .when we go to set number, where required block are present. then there is the problem. the problem is that we have to search it all the lines of the sets. ( Remeber this not, in the case of the direct mapping that's why we are not adding the OR gate Delay, this most important point) ===>So, that's why we required 2-comparator for each of the lines of that set number. ====>>>then both of the comparator are compared with TAG bits According to that it will show hit or miss ===> So, here we required the OR for the final result that's why we are adding the Delay. 0 votes 0 votes kumar.dilip commented Dec 18, 2018 reply Follow Share So, it is important to add the OR gate delay in associative mapping. But we can ignore in the case of the Direct Mapping. 0 votes 0 votes Shaik Masthan commented Dec 18, 2018 reply Follow Share 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 votes 1 votes kumar.dilip commented Dec 18, 2018 reply Follow Share 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. 2 votes 2 votes Shaik Masthan commented Dec 18, 2018 reply Follow Share 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 votes 1 votes kumar.dilip commented Dec 18, 2018 reply Follow Share 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. 1 votes 1 votes Shaik Masthan commented Dec 18, 2018 reply Follow Share 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 votes 0 votes kumar.dilip commented Dec 18, 2018 reply Follow Share Please read the question again. 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. 0 votes 0 votes kumar.dilip commented Dec 18, 2018 reply Follow Share 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) 1 votes 1 votes Shaik Masthan commented Dec 18, 2018 reply Follow Share 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 votes 0 votes kumar.dilip commented Dec 18, 2018 reply Follow Share 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 votes 0 votes kumar.dilip commented Dec 18, 2018 reply Follow Share 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 votes 0 votes srestha commented Dec 18, 2018 reply Follow Share @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 votes 0 votes srestha commented Dec 18, 2018 reply Follow Share Tag bits need comparator , not MUX right? 0 votes 0 votes tusharp commented Dec 19, 2018 reply Follow Share @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 votes 0 votes tusharp commented Dec 19, 2018 reply Follow Share 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. 0 votes 0 votes Shaik Masthan commented Dec 19, 2018 reply Follow Share @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... 1 votes 1 votes tusharp commented Dec 19, 2018 reply Follow Share 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 votes 0 votes kumar.dilip commented Dec 19, 2018 reply Follow Share tusharp Just go through my previous comment. you can easily understand the question. 0 votes 0 votes srestha commented Dec 22, 2018 reply Follow Share @Shaik @MiNiPanda chk this https://gateoverflow.in/60482/self-made-hit-latency 0 votes 0 votes srestha commented Dec 22, 2018 reply Follow Share 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 votes 0 votes Shaik Masthan commented Dec 23, 2018 reply Follow Share mam, i already read it, but all are saying the implementation is not consider ! 0 votes 0 votes Please log in or register to add a comment.