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

Isn't Tavg = a*T1 + (1-a)b*T2 + (1-a)(1-b)T3? can someone give me the link for above formula?

a = hit rate at L1

b = hit rate at L2

---

in this question we are using hierarchical access.....
 

t avg=H1*L1+(1-H1)H2(L1+L2)+(1-H1)(1- H2)H3(L1+L2+L3).

H1  (hit ratio for L1 cache )

H2  (hit ratio for L2 cache )

H3  (hit ratio for L3 cache )

and l1 l2 and l3 are  cache access time...

i think we should use above formula to solve above question...
i am wrong than plzzz correct me....!!

---

Yes. Hierarchical access is specified. But a part is confusing..

---

As in question it is not mentioned that a strict hierarchy is maintained I think we can use the below formula for Tavg,

Tavg = a*T1 + (1-a)b*T2 + (1-a)(1-b)T3

using this formula Tavg = 61.6 ns < 100 n. for L1 size = 8K bytes and L2  size  = 4M byte.

---

Edited

8MB ->>110ns

16MB:->75ns

So 16MB is Ans.

---

3rd access is in micro second

rt?

then how 121?

---

@srestha

5Microsecond is given =5000ns

But it costs only 20ns in case1 and 5ns in case2 bcz We are calculating here average acess time and thirld level acess is rare(0.4% overally for case1, 0.1% for case2) so the ans is in ns only.

For better understanding read AMAT portion from below link:-

https://www.cs.uaf.edu/2011/spring/cs641/lecture/04_05_modeling.html

---

why not hierarchical used??

---

In the part b,

the first one is having 110 ns ,why are we considering that.We need to <100 ns.Please verify once?

---

For those who are scratching their head why this formula while hierarchical access is used(Like I did for a while), this a more modified formula of hierarchical access.

$hierarchical\ access\ formula = HitRate_{1}(Access_{C1})+ MISSRate_{1}(Access_{C1}+MainMemory)$

if you open the second bracket it will be hitrate1(c1)+missrate1(c1)+missrate1(main memory), as we know hit rate+miss rate =1, so the final equation becomes

$$hierarchical\ access\ formula = Access_{C1}+ MISSRate_{1}(MainMemory)$$Similarly for this question too, which is a three level memory.

---

Hierarchical Access is being used but the formula used is above is bit simplified form of what we usually see for hierachical access.
 

h1.t1+ (1-h1) h2(t1+t2) +(1-h1)(1-h2)(t1+t2+tm)

= h1.t1+ (1-h1)h2.t1 + (1-h1)(1-h2)t1
+ (1-h1)h2.t2 + (1-h1)(1-h2)t2
+(1-h1)(1-h2)tm

= h1t1 + (1-h1)t1[h2+(1-h2)]
+(1-h1)t2[h2 + (1-h2)]
+(1-h1)(1-h2)tm

=t1 [h1 + (1-h1)]
+ (1-h1)t2
+(1-h1)(1-h2)tm

= t1
+ (1-h1)t2
+(1-h1)(1-h2)tm

---

Thanks, @Ayush. Now it's clear.

---

by applying this  Tavg = a*T1 + (1-a)b*T2 + (1-a)(1-b)T3?

a = hit rate at L1

b = hit rate at L2

i got :

5250  -  200*a   +   5000 * (a*b - a - b )     ....now how to  choose the best pair of (a,b) from the tables to get Tavg required in the question part(a)..??

---

For part a,in the given answer we have,

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

I think we need to consider only L1 = 16M and L2 = 4M, as minimum size is asked.

Also the calculation for this will not given 75,it will give 80.And this 80 should be answer to second part.

On the given answer for part b, we have taken the sizes more than the min. sizes satisfying the condition.

---

@rahul sahrma yes, "I think we need to consider only L1 = 16M and L2 = 4M, as minimum size is asked." i agree to this point of yours ! correct it will give 80ns.

---

@manu, @rahul-Agree

---

Can we have Cache memory(Level 1) larger than main memory (level 2)  ???

---

Did you got your answer?? I am also looking for the answer cause according to me it should not be the case?

---

Thanks for this it clears doubt , i was thinking this .

---

@ rahul sharma 5

I also agree that when we take min size for both the cache i.e. 8MB for L1, 4MB for L2, then access time = 110 ns, which is not less than 100 ns , so it's not the answer.

Now at this point, we have two choices of either increasing size of L1 or L2, Now I think as we generally tend to reduce the cost of memory and we know that L1 cache is more expensive than L2, so we increase size of L2. So for 8MB for L1, 16 MB for L2 we get access time = 100 ns, which is not less than 100 ns (strict inequality), so not the answer.

Now another choice is to increase L1 size. So for 16MB for L1 and 4MB for L2, we have access time = 80 ns < 100 ns. so it is the correct answer.

Please coorect me if I am wrong

---

what's wrong with this formuls:-

EAT= h1*t1 + 1-h1(t1 + h2t2 + 1-h2(t2+ t3))

---

.Tavg= H1*T1+(1-H1)*H2*(T1+T2) SO ON..., Now here

in your answer (T1+T2) is missing @ 2 LEVEL and (T1+T2+T3) @3 LEVEL

---

@Gate Fever, @CHïntän ÞäTël, you both used the same formula which is mentioned in the question.

---

yes , i got it now!

---

In this question we can use either of the formulaes.

formula 1 :- $T_{avg} =H_1*T_1 + M_1*\{ H_2*(T_1+T_2) + M_2(T_1+T_2+T_3) \}$

formula 2 :- $T_{avg}=T_1 + (M_1*T_2) +(M_1* M_2*T_3) $

where $M_i=1-H_i$

---

Satbir

from formula 2, it's looks like you've taken simultaneous or parallel access.

where is Hit in the equation ??

---

No , I have just modified formula 1 by opening the brackets. see my comment on the answer given below.

---

Vishal but by the inclusion property size of L1 cannot be greater than the size of L2.

so by this property, we cannot take L1=16MB and L2 = 4MB.

---

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

---

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

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