The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+24 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} \\\hline M _2 & 10^{-5} & 0.00998 & \text{0.1 sec} \\\hline M _3 & 10^{-4} & 0.00002 & \text{---} \\\hline \end{array}

Hierarchy Level $(M_i)$ |
Access Time $(t_i)$ |
Probability of access $(p_i)$ |
Page Transfer Time $(T_i)$ |
---|---|---|---|

$M_1$ $M_2$ $M_3$ |
$10^{-6}$ $10^{-5}$ $10^{-4}$ |
$0.99000$ $0.00998$ $0.00002$ |
$0.001$ sec $0.1$ sec -- |

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.

+21 votes

Best answer

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

0

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

+1

It is not required @hemant

It will be simulteneous access

Page access time required for 1 level

not for all prev levels

It will be simulteneous access

Page access time required for 1 level

not for all prev levels

0

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

0

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

+40 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 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/~fussell/courses/cs352.fall98/Homework/old/Solution3.ps

+4

Fortunately, I still have this downloaded pdf on my PC :)

uploaded it here -http://docdro.id/fIYPp6K

uploaded it here -http://docdro.id/fIYPp6K

+3 votes

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

M_{i} |
t_{i} |
p_{i} |
T_{i} |
---|---|---|---|

M_{1} |
1 microseconds | 0.99 | 1000 microseconds |

M_{2} |
10 microseconds | 0.00998 | 10^{5 }microseconds |

M_{3} |
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^{5 }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**

0 votes

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

+1

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.

0 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

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 586
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,129 questions

53,252 answers

184,785 comments

70,505 users