GATE CSE 2022 | Question: 23

Question

A cache memory that has a hit rate of $0.8$ has an access latency $10 \; \text{ns}$ and miss penalty $100 \; \text{ns}.$ An optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to $15 \; \text{ns},$ whereas the miss penalty is not affected. The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is _______________.

Comments

Avg  = 10 + (0.2) 100  => 30  ...................(1)

30 = 15 + (1-h) 100  ......................(2)
h =  85 / 100

---

Answer is 0.85. 

---

note: this is done in serial connection but not parallel connection ie parallel doesnot even exist according to standard textbooks refer to go classes lectures by deepak sir for better understanding

 

Answer 1

$\text{For a given cache, Average memory access time can be computed as:}$
$\text{AMAT} = \text{HitTime} + \text{Miss rate}*\text{Miss Penalty}$

$\text{Initially,}$
$\text{Hit rate of cache} = 0.8$
$\therefore \text{Miss rate} = 0.2$

$\text{Access Latency = HitTime} = 10\,ns$

$\text{Miss Penalty} = 100\,ns$

$\therefore \text{AMAT}_{unoptimized} = 10 + 0.2(100) = 30\,ns$

$\text{For the optimized cache,}$

$\text{Access Latency = HitTime} = 15\,ns$

$\therefore \text{AMAT}_{optimized} = 15 + x(100)$

$\text{Now,}$

$ \text{AMAT}_{unoptimized} \geqslant \text{AMAT}_{optimized} $

$30 \geqslant 15 + 100x$

$\implies 15 \geqslant 100x$

$\implies 0.15 \geqslant x$

$\implies 0.85 \leqslant 1-x$

$\therefore \text{The required hit rate} = (1-x) = 0.85$

Comments

Detailed Video Explanation with Correct Concepts: https://www.youtube.com/watch?v=v49Qv5CrgdY&t=9357s

AMAT = HitTime + MissRatio * MissPenalty

---

MISCONCEPTION of Simultaneous Access is discussed here: https://youtu.be/v49Qv5CrgdY?si=o42qpaOaqiySQHpk

---

@Deepak Poonia sir I'm very confused about
1. Does Page fault service time include memory access time?

2. Does Miss penalty include memory access time?

Please give me a definite answer because in this answer above, you have taken memory access time in addition to the miss penalty, but on a question with page fault service time given (I dont exactly remember which one but it was 2017 or before GATE pyq), Sachin Mittal Sir said that page fault service time includes memory access time.
[I have a screen shot of the comment and the question but I edited out the year. The comment was made in 2017.]

Operating System: GATE CSE 2018 | Question: 10 here is @Arjun sir's comment also.

---

miss penalty is simply the next time complete access time. suppose L1,L2,MM -> given is miss penalty for L1, it simply means the rest of the work is done for you. miss penalty of L1=missrateL1(L2time+missrateL2*MM accesstime).
for this scenario you can miss penaltyL2=MMaccesstime
also the misspenalty for the l1 doesn't include the access time of l1 so that is why we don't mult by hitrate in the l1 for hierarchical access.

regarding pagefault service time:

yeah it takes because we don't access the page directly from the disk right? we need to have it in main memory. so when servicing the pagefault we need 1 memory access last.

Answer 2

Those who are saying 0.84 can also be the answer, consider the following :

Firstly, it is mentioned in the question that Average memory access time should not increase. This means the new average memory access time should be either equal or less than its original obtained value.

 

In hierarchical access, hit ratio is coming to be 0.85.

Let's check for simultaneous access,

Average memory access time = ( 0.8 * 10 )  +  ( 0.2 * 100 ) = 28 ns.

Now the cache latency has become 15 ns.

 

So, put the value of hit ratio as 0.84 ( simultaneous access ) and compute the average memory access time.

Average memory access time = ( 0.84 * 15 ) + ( 0.16 * 100 ) = 28.6 ns

 

Now if we put the value of hit ratio as 0.85 ( simultaneous access ), then,

Average memory access time = ( 0.85 * 15 ) + ( 0.15 * 100 ) = 27.75 ns 

Now, it can be seen that for hit ratio 0.84 ( simultaneous access ), the average memory access time is 28.6 ns which is more than that its original value 28 ns.

But for hit ratio with 0.85 ns ( simultaneous access ), the average memory access time is 27.75 ns which is less than its original value.

But in the question, it is
clearly written that average memory access time should not increase. This means the average memory access time can be equal or less than the original value.

Hit ratio 0.85 is giving value less than 28 ns whereas hit ratio 0.84 is giving value more than 28 ns. But as per requirement of the question, average memory access time should not be more than its original value.

So, correct answer is 0.85 irrespective of memory access technique.

 

Comments

Hi, In case of rounding off there are always some minor loss of data, hence this is occurring. To give a similar example take (GATE CSE 2017 Set 2 | Question: 29 : https://gateoverflow.in/118371/Gate-cse-2017-set-2-question-29). Here the answer is option A) that is L1 = 0.111 and L2 = 0.056. Now when we substitute these values the AMAT comes out as 1.998889 which is not exactly 2 as given in the question so will we say that the options are wrong?  

Anyways I feel that GATE should consider a range i.e., 0.84 to 0.85 as an answer for the above mentioned GATE CSE 2022 | Question: 23. Because in other NAT questions where rounding off is needed GATE provided range as an answer even if answer comes as a specific decimal number. 

---

Range values are alright only when it does not affect the requirement of the question. If you take 0.84, the AMAT is getting more than original value which is against the main requirement of the given question. Previously in other questions, range values may not impact the question but 0.84 is ultimately increasing the AMAT which is violating the actual requirement of the question. 0.85 does not increase the original AMAT. It's not about whether range values should be given or not. It's about whether the answer is satisfying the main requirement of the question or not.

---

If you are saying that rounding off shouldn’t affect the requirement of the question , please explain why in GATE CSE 2022 | Question: 51 (https://gateoverflow.in/371885/Gate-cse-2022-question-51) the range value of 1.42 to 1.45 is given in the answer key? 

If we take 1.45 as the answer and back calculate as you did for the above question in discussion(GATE CSE 2022 | Question: 23), then we will get the value of prediction accuracy ≠ 80% but requirement is to have 80% prediction accuracy as per question or for that matter any other parameter given in question will not be as per the requirement if we take round off values. So always rounding off will have a negligible affect on the requirement of the question.  

I am not saying to include absurd values in range all i am saying is to include 0.84 as it has been previously seen that GATE has included approximate round off (e.x. as in GATE CSE 2022 | Question: 51 (https://gateoverflow.in/371885/Gate-cse-2022-question-51 the value comes 1.4285 but GATE included 1.42 also as if we ignore the values after 2 decimal place it is comes as 1.42).

So I think challenging this question makes sense.

---

yes, it makes sense to challenge. And no point in arguing here over it – that is no way is going to affect the result of the challenge – let GATE decide that :)

Answer 3

See If mention in que like "Level or Heirarichal" Then use Heirarichal access.

 

Now let's come to this que it is simultaneous now see how ans 0.847 is not correct but 0.85 is 100% correct

Before optimization

0.8*(10) + 0.2*(100) => 28

 

Now if you carefully read the questions it says that The minimum hit rate needed after the optimization such that it should not increase the average memory access time. Let hit is H.

After optimization

28 >= H*(15) + (1-H)*100  

 (Here >= because it say minimum Hit require that emat will remain same means it talk about at least)

 

So if further calculate it will be 

-72 >= -85H

72 <= 85H

0.847 <= H     which is obviously H should be greater than 0.847 then actual answer is 0.85 only

Comments

NOTE: Simultaneous Access is a Misconception..

Detailed Video Explanation with Correct Concepts: https://www.youtube.com/watch?v=v49Qv5CrgdY&t=9357s

AMAT = HitTime + MissRatio * MissPenalty

---

MISCONCEPTION of Simultaneous Access is discussed here: https://youtu.be/v49Qv5CrgdY?si=o42qpaOaqiySQHpk

---

EMAT = hittime + missrate * misspenality

EMAT  = hitrate * hittime + missrate * (hittime + misstime)

miss penality started after the cache is checked whether there is data or not, so the hittime is in both hitrate,missrate.

miss time = misspenality + hit time.

Answer 4

Tree method : 

Comments

BEAUTIFULLY ANSWERED.

Answer 5

• Initial Hit Rate = 0.8

• Initial Cache Access Latency = 10 ns

• Initial Miss Penalty = 100 ns

• Optimized Cache Access Latency = 15 ns

• Optimized Miss Penalty = 100 ns

• New Hit Rate = hhh (to be found)

Step 1: Compute Initial Average Memory Access Time (AMAT)

AMATinitial=(Hit Rate×Cache Latency)+(Miss Rate×(Cache Latency+Miss Penalty))\text{AMAT}_{\text{initial}} = (\text{Hit Rate} \times \text{Cache Latency}) + (\text{Miss Rate} \times (\text{Cache Latency} + \text{Miss Penalty}))AMATinitial​=(Hit Rate×Cache Latency)+(Miss Rate×(Cache Latency+Miss Penalty)) AMATinitial=(0.8×10)+(0.2×(10+100))\text{AMAT}_{\text{initial}} = (0.8 \times 10) + (0.2 \times (10 + 100))AMATinitial​=(0.8×10)+(0.2×(10+100)) =8+(0.2×110)= 8 + (0.2 \times 110)=8+(0.2×110) =8+22=30 ns= 8 + 22 = 30 \text{ ns}=8+22=30 ns

Step 2: Compute Required Hit Rate for New AMAT

For the new cache, the AMAT should not exceed 30 ns:

AMATnew=(h×15)+((1−h)×(15+100))≤30\text{AMAT}_{\text{new}} = (h \times 15) + ((1 - h) \times (15 + 100)) \leq 30AMATnew​=(h×15)+((1−h)×(15+100))≤30 15h+(1−h)×115≤3015h + (1 - h) \times 115 \leq 3015h+(1−h)×115≤30 15h+115−115h≤3015h + 115 - 115h \leq 3015h+115−115h≤30 −100h+115≤30-100h + 115 \leq 30−100h+115≤30 −100h≤−85-100h \leq -85−100h≤−85 h≥0.85h \geq 0.85h≥0.85

Final Answer

The minimum hit rate needed after the optimization is 0.85 (rounded to two decimal places).

Answer 6

Ans