11,691 views

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?

@Pavan Singh- what edit you made such that access time of L3 is lost?

From inclusion Property we cannot take lower lever cache size(say L1) greater than higher level (say L2) memory.
https://gateoverflow.in/446/gate2008-35

we must keep this in mind while giving answer of this question.

edited by
Unable to  understand the question :(
I got it now
Very time taking question.

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

shouldn’t we include the inclusion part here? like size of L1< size of L2
why the inclusion policy is not taken into consideration? anyone?
How do we get to know which one’s to choose should we be going by brute force

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.

this is the solve..hope this helps..

by

@`JEET to remember the formula through miss rates ...actually it resembles the slope eqn of line ..
Y=mX+c
T (ave) = p(miss penalty) + constant

here miss rate is p which is X in line equation..it means whenever miss rate increases average access time increases... and constant (intercept) is the time which will always occur ...means it is best case time ..you cant go lower than this...like if miss rates of level 1 cache is 0 ..then average cache access time is t1 only(access time of level 1 cache)

My doubt is that the access time is given for per byte then if we are choosing the memory of size 8M bytes then the access time should e multiplied with 8M.
No ...we are accessing only 1B from cache in all the cases (not 8 B) . If nothing is mentioned then we always assume 1 word is of 1B.

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

by