GATE1993-11

Question

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.

Comments

everything converts into  microsecond then calculate  

I'm getting  13.10198 microsecond

---

Note :- I am not completely satisfied with Arjun sir's answer. But @susmita mam's comments very helpful to understand the answer completely. 

Susmita mam's 2nd comment (that contains formula) and 4th comment (that contains calculation of answer) are too good.

Note that susmita mam's 4th comment contains "0.002", not say that here should be "0.00002". If you able to understand the point, why she used "0.002", then think that you have good understanding about this topic.

Answer 1

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

Comments

Sir, I am getting ans= 13.1 us.

---

Difference between Hit ratio and Probability as per my understanding;;

Hit Ratio....

Suppose H1=.8 H2=.9 H3=1

Suppose 100 Request came then 80 are handled by L1 . 18 are handled by L2. 1 is Handled by L3.

Note:-Hit ratio means... (No. Of hit / No. Of reference made)

Now Probability...

P1=.8 P2=.11 P3=.09 (sums Upto 1)

Then if 100 request came then 80 are handle by L1 ,11 by L2, 9 by L3

Plz Correct Me!!!

@Arjun sir

---

@Rajesh even in 1st case we have to think about miss in previous level and hit in that level.

Which is not considered here. rt?

---

@srestha ,assuming u r talking abt arjun sir's ans case-1

It is considered there..

And this is the best link to understand the whole picture:-

Read AMAT part only

https://www.cs.uaf.edu/2011/spring/cs641/lecture/04_05_modeling.html

---

@Rajesh yes, but for the second it must be clear that the probability is with respect to total no. of memory references as mentioned in the given question.

---

Thanks a lot sir :)

---

@rajesh for . 1 is Handled by L3. it should b . 2 is Handled by L3.

---

@ vijaycs

 me too getting 13.102μs  ...?

---

how ?

and one more doubt that why we are not taking probability like

p₁ (m₁) + (1-p₁) (p₂) m_2+....

---

ME TOO. ANY IDEA HOW 4 MICROSEC?

---

after determining hit rates from probabilities, we get relative hit rates then why are we not using that formula?? please clear arjun sir.

T1+(1-H1)(T2+(1-H2)T3))

why not this formula?

---

@sushmita What answer you get from it?

---

13.2 microsec sir. please clear it sir. Its really confusing.

---

That's a big jump :O Can you show it?

---

10^-6+ 0.01((0.00001+0.001)+0.002*(0.0001+0.1)= 13.2 microsec

Sir why have u not used hierarchical access here?? My concepts are shattering :(

---

@sushmita It is same only and you are correct. There was calculation mistake in the given answer-- corrected now.

---

thanx a lot sir. All confusion gone :)

---

@sushmita,

In the formula, you have given above. T1+(1-H1)(T2+(1-H2)T3)).

while calculating T3, you have not added the extra time required 0.001 sec to moving the page from 2nd level to 1st level.

Read this, mentioned in the question.

If a miss occurs at level Mi, a page transfer occurs from Mi+1 to Mi and the average time required for such a page swap is Ti.

---

It is not required @hemant

It will be simulteneous access

Page access time required for 1 level

not for all prev levels

---

I think they have given "Probability of access" instead of "probability of hit" in the table ...Because by probability of access they mean that this is the fraction of time only during which access to this memory will happen ... But access to 1 st level memory will always happen and access to 2 nd level memory will always happen when 1 miss in first level .. and so on ...

---

not getting

---

@srestha i feel that in the table, heading of 3 rd column should have been "probability of hit" instead of "Probability of access" right ?

---

It is correct @ Hemant.

---

@sushmita

0.99000(10^-6) + (1-0.99000)*(0.00998)*(10^-6+10^-5+0.001) + (1-0.99000)*(1-0.00998)*0.00002*(10^-6+10^-5+10^-4+0.001+0.1)

Why this is wrong?

---

Please update in GO pdf as well I went crazy calculating this stuff. It's still 4.01 in there

---

CAN ANY ONE EXPLAIN THE FORMULA?

WE WRITE T2 AS (T1+T2)?

---

in this question absolute miss rates are given

---

For anyone wondering with the hierarchical access formula, its the same. Refer this  question's best answer comments.

---

@Bad Doctor, your method to multiply probabilities of hierarchical levels is totally wrong. Let see the reason, by taking about M2 level.

In question it is not said that 0.00998 (0.998 %) accesses of total miss in M1 level (i.e 0.01 or say 1%) are from M2 level . So, don't do it as "0.01 * 0.00998"

Answer 2

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

Here, Probabilities are given, We need to convert it into Hit ratios.
$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)$
Ref:  question 3 here

https://www.cs.utexas.edu/~fusse​ll/courses/cs352.fall98/Homework/​old/Solution3.ps

Comments

^ link is dead....

---

Fortunately, I still have this downloaded pdf on my PC :)
uploaded it here -http://docdro.id/fIYPp6K

---

thnx bro....

---

Nice explanation about the relative probabilities!!

---

This answer should be included in GO book. Thanks a ton!! This a clear explanation on relative probabilities.

---

I am not getting desired answer using this. can someone help.

---

It is mentioned that pi is probability that an access will REFER to Mi. But the first memory level i.e. M1 is always referred in the sense that firstly , any information is checked first in M1 then in successive memory levels. So why not p1 is 1? Which means probability that a request will refer to M1 is 1.

EDIT: pi should be fraction of requests satisfied by Mi.

---

@Sachin Mittal 1

we hit 0.00002 times in M3 out of 0.00002 misses from M2

I think this line is wrong as there will be 0.002 misses from M2.

Miss of M2 = 1- hit of m2 = 1-0.998 = 0.002.

 

---

@Satbir sir I think misses from M2 will be (1-0.99)(1-.998)

Please clear.

---

Please see second method of arjun sir answer.

probability of accessing $M_1$ is $1$ since we always start searching data from memory $M_1$

$0.99$ gives probability that we will access $M_1$ and get the data i.e. hit in $M_1$

this means probability that we access $M_1$ but don't get data $=1 - M_1 = 1- 0.99$ i.e. we will now access $M_2$ and try to get data from it. This is miss in $M_1$

So probability that we access $M_2$ is $1-0.99$ i.e. when there is miss in $M_1$.

Probability that we access $M_2$ and get data is $0.00998$

this means probability that we access $M_2$ but don't get data $=1 - M_2 = 1- 0.00998$ i.e. we will now access $M_3$ and try to get data from it. This is miss in $M_2$ given that there is already a miss in $M_1$.

So now at last we access $M_3$ and we will definitely get the data so Hit in $M_3$ is 1 and miss in $M_3$ is $0$.

Also probability that we will access $M_3$ is $1-0.00998$ or $0.00002$ i.e. when there is miss in $M_2$

Now what to do when there is a miss is given in question.

Here they have given relative probability so thats why we don't need to write like $(1-0.99)(1-0.998).$

 

---

NOTE- Hit rate of last level in any case is always going to be 1,because if the word(or data) you want is not in the last level it means that it is not present in the system at all , and for a word which is not in the system the miss rate is always going to be 100% that implies that Hit rate is 0% and for that EMAT  is not calculated since it will always miss.

 

@Sachin Mittal 1 did a mistake of mentioning the line "we hit 0.00002 times in M3 out of 0.00002 misses from M2" which is false and unnecessary,if you by any chance try to calculate

H3=(0.00002/0.002)

     =0.01 (and this makes no sense ,as explained above,so don't do it)

----------------------------------------------------------------------------------------------------------------------

for eg, suppose you have a game like Counter Strike .. stored in your hard disk then if you want to play that game then Operating System will bring that into main memory (suppose to do that access time takes 5 seconds), and then you can happily enjoy the game until you quit the game.This is the scenario in which the game exists in the hard disk(last level),but if the game doesn't exist in the Hard Disk then how can your OS bring that into Main Memory,it will search into the Hard Disk trying to find it, and at that moment EMAT particularly will tend towards infinity (like a minute or something) and the OS will give error of not able to find the file,so considering EMAT in this type of situation is of no use ,so EMAT is always considered for the data which is always present atleast in the last level. 

 

@Arjun sir correct me if I am wrong.   

 

---

 Lets just take an example-

1 lakh(10^5) memory accesss….

M1 probability of acccess 0.99 hence 99,000 hits. and 1,000 misses ..hence hit ratio 0.99

M2 probability access of access 0.00998 hence . 0.00998*10^5=998 accesses  but only 1000 came for M2(which got miss in M1)  hence

hit ratio=998/1000=0.998 and misses are 2/1000=0.002

M3 probability of access 0.00002*1lakh=2   and 2 came for M3 out of 1000 hence hit ratio of m3=1

Reason it worked out like this   – summation of probability is 1 hence  M3 will have hit ratio 1 

 

Answer 3

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

t_A = 0.99 (1 us) + 0.00998 (10 us + 1 us + 1000 us) + 0.00002 (1 us+ 10 us + 100 us + 1000 us + 10⁵ us)

    = 0.99 us + 10.09978 us + 2.02222 us 

    = 13.1 us

---

---

Another way :

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

    = 1 us + 10.0798 us + 2.02 us 

    = 13.1 us

Answer 4

 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

Answer 5

The standard way is (hierarchical memory access) :

AMAT = Hit Ratio for L1 x  L1 access time  +

              Miss Ratio for L1 x Hit Ratio for L2 x (page transfer time from L2 to L1 + L1 access time + L2 access time) +

             Miss Ratio for L1 x Miss Ratio L2 x Hit Ratio for L3 x (page transfer time from L3 to L2 + page transfer time from L2 to L1 + L1 access time + L2 access time + L3 access time)

 

    =  0.99 x 1 us   +   .01 x .998 x (1000 + 1 + 10)us  +  .01 x .002 x 1 x (100000 + 1000 + 1 + 10 + 100)

    =  13.102 us

 

Note: you have to convert probabilities into Hit Ratios respectively as specified by sachin mittal.

Comments

@mint 

like we have calculated $H_2$ as $\frac{0.00998}{0.01} = 0.998$

then we get miss $M_2 = 1- 0.998 = 0.002$

 

So why are not following the same method to get H3 ?

$H_3 = \frac{0.00002}{0.002} = 0.01$

 

---

@Satbir

 Denominator of H3 will be 1 - P2 and not 1 - H2.

Answer 6

$0.99000 \times {10}^{-6} + (1-0.99000) \times [(0.00998)\times ({10}^{-6} +{10}^{-5} + 0.001) + (1-0.00998){(0.00002)\times ({10}^{-6} + {10}^{-5} + {10}^{-4} + 0.1)}] \\= 1.1\times {10}^{-6} s.$

Comments

are you missing something on the third part of the expression, because you eventually have to transfer the page from m3->m2->m1, where as , you have missed out the transfer time from m2->m1.

---

missed probability of missed in M1 in accessing the M3.

---

0.99000(10^-6) + (1-0.99000)[(0.00998)(10^-6 +10^-5 + 0.001) + (1-0.00998){(0.00002)*(10^-6 + 10^-5 + 10^-4 + 0.1 + 0.001)}] 

---

What is given is not the hit rates :O

---

@arjun sir....

0.99000(10^-6) + (0.99000)[(0.00998)(10^-6 +10^-5 + 0.001) + (0.00998){(0.00002)*(10^-6 + 10^-5 + 10^-4 + 0.1 + 0.001)}] 

This should be the answer as we should consider the probability of access of M1 while accessing M2 also..

same for M3.