MadeEasy Test Series: CO & Architecture - Cache Memory

Question

Suppose that in 250 memory references there are 30 misses in first level cache and 10 misses in second level cache. Assume that miss penalty from L$_2$ cache memory are 50 cycles. The hit time of L$_2$ cache is 10 cycles. The hit time of the L$_1$ cache is 5 cycles. If there are 1.25 memory references per instruction, then average stall cycles per instruction is __________

am getting 2.75. given answer is 4.

number of cycles when there are no misses= 250*5 = 1250
number of cycles with given misses = 1800
stall cycles = 1800-1250 = 550
number of stalls/instruction= 550/200 = 2.75
please verify

Comments

Add hit time + penalty time you will get Ur ans...Ur method is right !

220*5 + 20*15 + 10*(5+10+50) = 2050

2060-1250 =800/200 = 4

correct me!

---

@gabbar yes i dint look at this comment that day. u are correct :)

---

what does miss penalty of L2 cache include??

Answer 1

Memory stall cycles created when CPU has to wait for memory. Here, we can assume no stall cycles for $L_1$ hit.

So, CPU will access from $L_1$ only. If something not found there we need to consider $L_1$ miss penalty (why not $L_2$ miss penalty ?? because we will include it in $L_1$ miss penalty)

Miss penalty of 

$\begin{align*} L1 &= \left ( \text{ HIT time in }L_2 \right ) + \left ( \text{miss rate in } L_2 \right ) *\left ( \text{miss penalty of } \; L_2 \right ) \\ &= 10 \; \text{cycles} + \left ( \frac{10}{30} \right )*50 \; \text{cycles}\\ &= \frac{80}{3} \; \text{cycles}\\ \\ \\ \hline \\ \text{Now,} \\ & \text{Mem stall cycles due to misses per instruction} \\ &= \left ( \text{mem request per instruction} \right ) * \left ( \text{Miss rate in } \; L_1 \right ) \ *\left ( \text{Miss penalty of }\; L_1 \right ) \\ &= 1.25 * \left ( \frac{30}{250} \right )*\frac{80}{3} \\ &= \frac{125}{100} *\frac{3}{25} * \frac{80}{3} \\ &= 4 \end{align*}$

Comments

@debashish tell me only one thing, how many misses are there in total out of 250 references. i have only this doubt.

---

30 miss in L1 and 10 miss L2..those 10 misses handled by 50 cycles given.

---

means there are 40 misses outof 250 references?

---

my doubt is misses of L2 are subset of misses of L1.
it means 20 references are hits in L2. and 10 are misses in l2
is it not correct>

---

ya..if you would say so.

---

then penalty of a hit in L2 is 10 clocks. there are 20 hits. then 200 clocks for 20 references, and 10 misses of L2 cause 50 clocks penalty = 500 clocks. is it correct?
for 30 references penalty is 700
am not getting why this is wrong :/

---

NOT correct  ""it means 20 references are hits in L2. and 10 are misses in l2
is it not correct> "" subset-super relations ...exist in data...we should not co-related it with time.

If some memory x physically missing in some level..it means.. bring that x from a lower level and send it back to CPU. Whether that memory x is present anywhere else ..should not consider in calculating time.

---

in ur approach why

Miss penalty of L1=( HIT time in L2)+(miss rate in L2)∗(miss penalty of L2) ?
is it like (hit ratio of L2)*(hit time)+(miss ratio)(hit time+miss penalty) ?

---

@Anusha Both are same formula rt?

---

Nice Explanation.
I stuck at this question, Now clear :)

---

here why are you not considering stall cycle for L1 hit. When we are accessing the L1 then at that time CPU is also ideal therefore it also stall.

---

yes, L1 hit time is also part of stall cycles.

---

# of cycles required for 250 memory references

= 220*5 + 20*(5+10) + 10*(5+10+15)

= 1100 + 300 + 650 = 2050 cycles.

# of cycles for 1.25 memory references = (2050/250)*1.25 = 10.25 cycles..............(1)

# of cycles for 1.25 memory reference without any miss = Hit time of L1 * 1.25

= 5 * 1.25 = 6.25 cycles..............(2)

Now, we just need to subtract the above equations (1) and (2) in order to get the average stall per instruction = 10.25 - 6.25 = 4 cycles.

I think even this method is correct.

Let me know if there is anything wrong here.

---

Is L1 hit time also a Part of Stall Cycles since CPU is ideal at that time.

If yes, Then why are you not including it ?

Secondly, how did you got the formula ?

Answer 2

Miss penalty of L1 cache is nothing but hit time of L2 cache ..

So miss penalty of L1 cache   =  10 cycles..

Given miss penalty of L2 cache  =  50 cycles

So total no of stalls per memory access = Miss rate of L1 * Miss penalty of L1 +

                                                                Miss rate of L1 * Miss rate of L2 * Miss penalty of L2

                                                           = (30 / 250 * 10) + ((30 / 250) * (10 / 30) * 50)

                                                           = (6/5) + 2

                                                           = 3.2

But here we have 1.25 memory accesses per instruction..

So no of memory stalls per instruction   =  5 / 4 * 3.2

                                                          =  16 / 4

                                                          =  4

Hence 4 should be the correct answer..

Comments

No I m not taking 40 misses..

---

miss rate of L1 * miss penalty of L1 +  miss rate of L2 * miss penalty of L2
miss penalty of L1 is not given
and miss penalty of L1 is not equal to hit time of L2. bcoz there can be some misses which cant be found even in L2.
when we do 30*10 + 10*50, we are saying 30 references can be found in L2 so time for 30 references is 30*hit time of L1= 30*10-->but these 30 references also include those which are misses in L2.
so 30*10 cant be done.

---

But for some misses which cannot be found in L2 even , we have :

(30 / 250)  * (10/30) term..

Answer 3

Stall cycle created due to  some miss happen in cache and CPU need to access memory

In this question we can see ,

there are $30$ misses in $L_{1}$ cache for which we need to access $L_{2}.$

In $L_{2}$ there are $20$ hits, but again for $10$ misses we need to access Main Memory.

So, total stall cycles are $20*10+10*(50+10)=800$ stall cycles

Now,

for $250$ memory reference  , there are $800$ stall cycles.

for $1$ memory reference  , there are $800/250$ stall cycles.

Here, each instruction needs $1.25$ memory reference.

So, for $1.25$ memory reference  , there are $(800/250)*1.25=4$ stall cycles or $4 stall/instruction$

Answer 4

L1	L2
Miss rate = $\frac{30}{250}$	Miss rate = $\frac{10}{30}$
	Miss penalty = 50 cycles
Hit Time = 5 cycles	Hit Time = 10 cycles

“1.25 references for 1 instruction” means that 250 references are for 200 instructions.

We’ll have to access L1 definitely to be able to access data, therefore it will not be considered as stalls.

Only L2 hit and L2 miss will lead to additional work(stalls).

Therefore the total number of stalls = 30 for L2 access and 10 for memory access = (30*10) + (10*50) = 300+500 = 800 stall cycles

And we have 200 instructions. Therefore stalls/instructions = $\frac{800}{200}$ = 4stalls/instruction