GATE CSE 1996 | Question: 26

Question

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

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

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

Comments

Very time taking question.

---

Hi All,

Please share your thoughts. Also correct me if I am wrong.

This question is little confusing for me.

Here in this question they are saying it is a 3 level hierarchical cache memory.

As per my understanding, hit rate of main memory is always 1.

In question they said  L2 is main memory where CPU takes 200 ns/byte to access it with hit ratio != 1. If it is a main memory ideally the hit rate must be 1 correct?.  I am not clear why they mentioned like this?

Varies they have given that L3 cache hit rate is 1 . → This point is also not very clear.  If it is not main memory ideally hit ratio  won’t be 1 correct?

In first question they are asking us to find minimum size of L1 and L2 cache if Tavg time < 100 ns.

To solve this I think we don’t require L3 cache  details. if it is really not required then are they trying to confuse us by giving  L3 cache details?

---

Firstly , it is not necessary that the hit ratio of M.M has be 1 instead the last level of memory has a hit ratio of 1 like here level 3 has 1 hit ratio

Secondly , the question says min size of L1 and L2 to achieve an avg access time of 100n sec the question indirectly doesn't mention L3 as it has only one size available so I think we have to take L3 details also

Answer 1

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$

Comments

svas7246

Yes.

---

Why this is not the correct answer, as by this the $L1$ size is minimum $i.e$ $8MB$

and the $EMAT$ is $<$ $100ns$

https://gateoverflow.in/2778/gate-cse-1996-question-26?show=366180#a366180

---

@Ayush Upadhyaya Thanks man

Answer 2

@Vikrant Singh, @focus _GATE

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.

Answer 3

this is the solve..hope this helps..

Comments

@`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.
Someone please clear!!!

---

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.

Answer 4

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