edited by
14,924 views
36 votes
36 votes

A computer system has a three-level memory hierarchy, with access time and hit ratios as shown below:

$$\overset{ \text {Level $1$ (Cache memory)} \\  \text{Access time = $50 nsec/byte$}}{\begin{array}{|l|l|} \hline  \textbf{Size} & \textbf{Hit ratio} \\\hline \text{$8 M $ bytes} & \text{$0.80$} \\\hline \text{$16 M $ bytes} & \text{$0.90$}   \\\hline  \text{$64 M $ bytes} & \text{$0.95$}   \\\hline \end{array}} \quad \overset{\text {Level $2$ (Main memory)} \\  \text{Access time = $200 nsec/byte$}}{\begin{array}{|l|l|l|}   \hline  \textbf{Size} & \textbf{Hit ratio} \\\hline \text{$4 M$ bytes} & \text{$0.98$} \\\hline \text{$16 M$ bytes} & \text{$0.99$}   \\\hline  \text{$64 M$ bytes} & \text{$0.995$}   \\\hline \end{array}} \quad \overset{ \text {Level $3$} \\  \text{Access time = $5$} \mu \text{sec/byte}}{\begin{array}{|l|l|l|} \hline  \textbf{Size} & \textbf{Hit ratio} \\\hline \text{$260M$ bytes} & \text{$1.0$} \\\hline\end{array}}$$

  1. What should be the minimum sizes of level $1$ and $2$ memories to achieve an average access time of less than $100 nsec$?

  2. What is the average access time achieved using the chosen sizes of level $1$ and level $2$ memories?

edited by

5 Answers

Best answer
28 votes
28 votes

The equation for access time can be written as follows (assuming $a,b$ are the hit ratios of level 1 and level 2 respectively).

$T=T_1 + (1-a)T_2+(1-a)\times(1-b)T_3$

 Here $T\leq 100, T_1 = 50ns ,T_2 = 200ns$ and $T_3 = 5000 ns.$ On substituting the $a, b$ for the first case we get

$T = 95ns$ for $a = 0.8$ and $b = 0.995.$ i.e., $L1 = 8M$ and $L2 = 64M.$
$T = 75ns$ for $a = 0.9$ and $b = 0.99.$ i.e., $L1 = 16M$ and $L2 = 4M$

B.

  1. $L_1 = 8M, a = 0.8, L_2 = 4M, b = 0.98$. So, 
    $T = 50 + 0.2 \times 200 + 0.2 \times 0.02 \times 5000 \\= 50 + 40 + 20 = 110ns$
  2. $L_1 = 16M, a = 0.9, L_2 = 16M, b = 0.99$. So,
    $T = 50 + 0.1 \times 200 + 0.1 \times 0.01 \times 5000 \\=50 + 20 + 5 = 75ns$
  3. $L_1 = 64M, a = 0.95, L_2= 64M, b = 0.995$. So, 
    $T = 50 + 0.05 \times 200 + 0.05 \times 0.005 \times 5000 \\= 50 + 10 + 1.25 = 61.25ns$
edited by
13 votes
13 votes

@, @

A)  In case of 2 - Level Memory, we know for the Hierarchical (serial) Access the average memory time is T = H₁T₁ + (1 - H₁)(T₁ + T₂)

Now, T = H₁T₁ + (1 - H₁)(T₁ + T₂)
or, T = H₁T₁ + T₁ + T₂ - H₁T₁ - H₁T₂
or, T = (H₁ + 1 - H₁)T₁ + (1 - H₁)T₂
or, T = T₁ + (1 - H₁)T₂
Finally we get T = T₁ + (1 - H₁)T₂

Similarly, 
In case of 3 - Level Hierarchical (serial) Access memory the average memory time we get is T = T₁ + (1 - H₁)T₂ + (1 - H₁)(1 - H₂)T₃

where, L₁
L₂L₃ = Levels of Memory
T₁ = Access time for L₁
T₂ = Access time for L₂
T₃ = Access time for L₃
H₁ = Hit rate for L₁
H₂ = Hit rate for L₂

It is given in the question that an average access time T < 100 and the value of T₁ = 50ns, T₂ = 200ns and T₃ = 5μs = 5000ns. We have to find out the required answer by substituting the value of H₁ and H₂.

Now, let's substitute the value of H₁, H₂ one by one.
(I) L₁ = 8M bytes, L₂ = 4M bytes, H₁ = 0.80 and H₂ = 0.98
T = 50 + (1 - 0.80) x 200 + (1 - 0.80)(1 - 0.98) x 5000 = 110ns which is greater than 100ns. 
      L₁ = 8M bytes and L₂ = 4M bytes can't be an answer.

(ii) L₁ = 8M bytes, L₂ = 16M bytes, H₁ = 0.80 and H₂ = 0.99
T = 50 + (1 - 0.80) x 200 + (1 - 0.80)(1 - 0.99) x 5000 = 100ns which is same as given T (100ns).
      L₁ = 8M bytes and L₂ = 16M bytes can't be an answer.

(iii) L₁ = 8M bytes, L₂ = 64M bytes, H₁ = 0.80 and H₂ = 0.995
T = 50 + (1 - 0.80) x 200 + (1 - 0.80)(1 - 0.995) x 5000 = 95ns which is less than 100ns.
      L₁ = 8M bytes and L₂ = 64M bytes might be the answer but let's verify with other conditions too.
But we have to find out the Level - 1 and Level - 2 memory where the sizes are as minimum as possible.

(iv) L₁ = 16M bytes, L₂ = 4M bytes, H₁ = 0.90 and H₂ = 0.98
T = 50 + (1 - 0.90) x 200 + (1 - 0.90)(1 - 0.98) x 5000 = 80ns which is less than 100ns.
       L₁ = 16M bytes and L₂ = 4M bytes will be the minimum possible sizes of both Level - 1 and Level - 2 memory.

Ans: L₁ = 16M bytes and L₂ = 4M bytes

B) We have already find out from the previous question the required sizes of Level - 1 and Level - 2 memory.
We got L₁ = 16M bytes and L₂ = 4M bytes, H₁ = 0.90 and H₂ = 0.98
∴T = 50 + (1 - 0.90) x 200 + (1 - 0.90)(1 - 0.98) x 5000 = 80ns

Ans: 80ns is the average access time achieved using the chosen sizes of level - 1 and level - 2 memories.

edited by
5 votes
5 votes

this is the solve..hope this helps..

reshown by
2 votes
2 votes

.........................……...……….……………………..

Answer:

Related questions

33 votes
33 votes
6 answers
2