recategorized by
10,791 views
49 votes
49 votes
In the three-level memory hierarchy shown in the following table, $p_i$ denotes the probability that an access request will refer to $M_i$.
$$\begin{array}{|c|c|c|c|} \hline \textbf {Hierarchy Level } &  \textbf{Access Time}& \textbf{Probability of Access} & \textbf{Page Transfer Time}  \\
(M_i) &(t_i)&(p_i) &(T_i)\\ \hline
M _1 & 10^{-6} & 0.99000 & \text{0.001 sec} \\ M _2 & 10^{-5} & 0.00998 & \text{0.1 sec} \\ M _3 & 10^{-4} & 0.00002 & \text{---} \\\hline \end{array}$$
If a miss occurs at level $M_i$, a page transfer occurs from $M_{i+1}$ to $M_i$ and the average time required for such a page swap is $T_i$. Calculate the average time $t_A$ required for a processor to read one word from this memory system.
recategorized by

6 Answers

Best answer
50 votes
50 votes

We are given the probability of access being a hit in each level (clear since their sum adds to $1$).
So, we can get the average access time as:

$t_A = 0.99 \times {10}^{-6} \\+ 0.00998 \times ({10}^{-6} +{10}^{-5} + 0.001)$
$+ 0.00002 \times ({10}^{-6} + {10}^{-5} + {10}^{-4} + 0.1 + 0.001)]$
$\approx (0.99 + 10 + 2 ) \times [10^{-6}] \\= 13 \mu s$.


We can also use the following formula- for $100$% of accesses $M_1$ is accessed,
whenever $M_1$ is a miss, $M_2$ is accessed and when both misses only $M_3$ is accessed.
So, average memory access time,

$t_A = 10^{-6} + (1-0.99) \times (10^{-5} + 0.001) + 0.00002 \times (10^{-4} + 0.1)
\\= 1 + 10.01 + 2 \mu s
\\= 13.01 \mu s.$

edited by
88 votes
88 votes

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.

\line(1,0){250}


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$

\line(1,0){250}

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/~fusse​ll/courses/cs352.fall98/Homework/​old/Solution3.ps

edited by
7 votes
7 votes

All the times can be converted to microsecond or nanoseconds. Modified table is,

Mi ti pi Ti
M1 1 microseconds 0.99 1000 microseconds
M2 10 microseconds 0.00998 105 microseconds
M3 100 microseconds 0.00002  ---

us ==> microseconds

tA = 0.99 (1 us) + 0.00998 (10 us + 1 us + 1000 us) + 0.00002 (1 us+ 10 us + 100 us + 1000 us + 105 us)

    = 0.99 us + 10.09978 us + 2.02222 us 

    = 13.1 us



Another way :

tA = 1 us + 0.00998 (1010 us) + 0.00002 (111 us + 101000 us)

    = 1 us + 10.0798 us + 2.02 us 

    = 13.1 us

3 votes
3 votes

 Here the probability of accessing each level is given, we can calculate the average access time as

We access the 1st level memory with probability 0.99 and its access time is 10^-6 seconds = 1 microsecond, so 0.99*1 microsecond for accessing from level-1.

But when we access 2nd level memory its access time is 10^-5 seconds = 10 microseconds, apart from this the block has to be moved to 1st level and the time taken for it is 0.001 seconds = 1000 microseconds and then the overall access time in level-1, so 0.00998*(1+10+1000) microsecond for level-2.

Similarly when accessing from level-3, access time in level-3 is 10^-4 seconds = 100 microseconds, and the time to move the content to level-2 is 0.1 second = 10^5 microseconds. So the overall time from level-3 = 0.00002(1 + 10 + 100 + 1000 + 10^5)

So the average access time is

tA = 0.99 (1 us) + 0.00998 (10 us + 1 us + 1000 us) + 0.00002 (1 us+ 10 us + 100 us + 1000 us + 10^5 us)

    = 0.99 us + 10.09978 us + 2.02222 us 

    = 13.1 us

Related questions

30 votes
30 votes
4 answers
3
Kathleen asked Sep 29, 2014
4,524 views
Let $\left(\{ p,q \},*\right)$ be a semigroup where $p*p=q$. Show that:$p*q=q*p$ and$q*q=q$