GATE CSE 1993 | Question: 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.

---

great question to get your fundamentals sorted about global and local misses.

Answer 1

$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

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.

Answer 2

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.