Quick Cache Maths:-
Suppose that in 250 memory references there are 30 misses in L1 and 10 misses in L2.
Miss rate of L1 = $\frac{30}{250}$
Miss rate of L2 = $\frac{10}{30}$ (In L1 we miss 30 requests, so at L2 we have 30 requests, but it misses 10 out of $30$)
See this GATE 2017 Question or this question.
Here, Probabilities are given, We need to convert it into Hit ratios.
First, we need to understand the difference between both.
$\text{Hit Rate = }\frac{\text{Number of chache hits}}{\text{Total requests to chahe}} $
$\text{Probability of access }:-$ It is with respect to total requests.
Hit Ratio is with respect to THAT PARTICULAR cache whereas probability is with respect to total requests to all caches.
For Example – Suppose we put a total of $10^5$ requests and we hit
- $M_1 \quad 99000$ times
- $M_2 \quad998$ times
- $M_3 \quad 2$ times
Then,
- The probability of accessing $M_1 = \frac{99000}{10^5} = 0.99$
- The probability of accessing $M_2 = \frac{998}{10^5} = 0.00998$
- The probability of accessing $M_3 = \frac{2}{10^5} = 0.00002$
Now, Let’s calculate hit rate –
Hit Rate for $M_1 – $
- $\quad$ Total requests to $M_1= 10^5 $.
- $\quad$ We hit $M_1 = 99000$
- $\quad$ Hit Rate = $\frac{99000}{10^5} = .99$
Hit Rate for $M_2 – $
- $\quad$ Total requests to $M_2= 1000$ (Because that is miss from $M_1$. See above “Quick cahe maths”).
- $\quad$ We hit $M_2 = 998$
- $\quad$ Hit Rate = $\frac{998}{1000} = .998$
Hit Rate for $M_3 – $
- $\quad$ Total requests to $M_3= 2$ (Because that is miss from $M_2$).
- $\quad$ We hit $M_3 = 2$
- $\quad$ Hit Rate = $\frac{2}{2} =1$
Now Coming to the data given in question –
$p_1 = 0.99000$, it says we hit 0.99 times in $M_1$ but we miss 0.01 times. Here hit rate is same as probability $H_1 = 0.99$
$p_2 = 0.00998$, it says we hit 0.00998 times out of 0.01 requests (0.01 misses from $M_1$), $H_2 = \frac{0.00998}{0.01} = 0.998$
($H_3$ is of course 1. we hit 0.00002 times in $M_3$ out of 0.00002 misses from $M_2$)
$H_1 = 0.99$, $H_2 = 0.998$, $H_3 = 1$. $t_i$ is Access time, and $T_i$ is page transfer time.
$t_A = t_1+(1-H_1)\times \text{Miss penalty 1}$
$\text{Miss penalty 1} = (t_2+T_1)+(1-H_2)\times \text{Miss penalty 2}$
$\text{Miss penalty 2} = (t_3+T_2)$
Edit: Completing the calculation:-
Converting all times in $ \mu s$:-
$t1 = 1 \mu s$
$t2 = 10 \mu s$
$t3 = 100 \mu s$
$T1 = 1000 \mu s$
$T2 = 100000 \mu s$
$\text{Miss penalty 2} = (t_3+T_2) = 100100 \mu s$
$\text{Miss penalty 1} = (t_2+T_1)+(1-H_2)\times \text{Miss penalty 2} = (1010 + 0.002*100100) = 1,210.2 \mu s$
$t_A = t_1+(1-H_1)\times \text{Miss penalty 1} = 1+ 0.01* 1,210.2 \mu s = 13.102 \mu s $ (ANSWER)
--------------------------------------------------------------------------------------------------------------------------------------------------------------
Ref: question 3 here
https://www.cs.utexas.edu/~fussell/courses/cs352.fall98/Homework/old/Solution3.ps