Dark Mode

2,747 views

4 votes

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

6 votes

Best answer

$\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$

$\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$

1

0

3 votes

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.

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.

3

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.

4

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.

1