The Gateway to Computer Science Excellence
+15 votes
1.4k views
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
in CO and Architecture by Boss (12k points)
edited by | 1.4k views
0
Anusha you are not using 1.25 memory refference per instrucution , since quetion ask stalll per instruction
+1
she used it by taking 200 instructions from 250 memory references as 1.25 per instruction
0
i divided it by 200. which is nothing but number of instructions.
1.25 references-->1 instruction
250 ref--->?
200 instructions
0
Yes ....i didnt see that :)
0
answer is 4.
0
ur solution is same as habib?
0
i have a doubt here,
question says "out of 250 references 30 are misses in L1 and 10 are misses in L2."
means there are total of 30 misses. among them 20 are misses in L1 can be found in L2, and 10 cant be found even in L2. so for 20 references which are misses in L1 penalty is 10 clocks, and for other 10 references which are misses also in L2 penalty is 50 clocks.
did they not mean this?
i did it as
so total clocks are 220*5 + 20*10+10*50 = 1800 clocks.
without any misses its 250*5 = 1250 clocks
stalls per instruction = 550/200=2.75
+2
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!
0
@gabbar yes i dint look at this comment that day. u are correct :)
0
what does miss penalty of L2 cache include??

2 Answers

+23 votes
Best answer

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

by Veteran (57.2k points)
edited by
0
@debashish tell me only one thing, how many misses are there in total out of 250 references. i have only this doubt.
0
30 miss in L1 and 10 miss L2..those 10 misses handled by 50 cycles given.
0
means there are 40 misses outof 250 references?
0
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>
0
ya..if you would say so.
0
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 :/
0

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.

0
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) ?
0
@Anusha Both are same formula rt?
+2
Nice Explanation.
I stuck at this question, Now clear :)
0
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.
0
yes, L1 hit time is also part of stall cycles.
0

# 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.

+16 votes

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..

by Veteran (102k points)
0

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

but what if there is also a miss in L2 cache, this too should also be added in the miss of L1 right?

0
as nothing is mentioned dont we need to assume simultaneous access?
 i mean shudnt the stalls  for 1 memory accesses be = (20/250  * 10) + (10/250 * 50)
+1
total stalls  = miss rate of L1 * miss penalty of L1 +  miss rate of L2 * miss penalty of L2

30 * 10 + 10 *50 = 800 stalls

stalls per instruction = 800 / 200 = 4.
0
That is what I have written..Secondly in miss of L1 u have taken 20 instead of 30..Plz check my answer carefully..:)
0
yes u took it correctly :)

and.. this sentence "30 misses in L1 and 10 misses in L2" what does this mean?
there are total of 30 references which cause miss in L1 and among them 20 can be found in L2. and 10 cant be found even in L2. isnt this the meaning of this sentence ""30 misses in L1 and 10 misses in L2"
0
But miss in L2 will occur if only miss occurs in L1 cache that is why we are multiplying the miss rate of both the levels in case of cache miss in L2 cache..

Think it like this : If there is a hit in L2 cache then we take miss rate of L1 * hit rate of L2 fine..So in case of miss penalty of L2 we need to take miss rate of L1 * miss rate of L2..But by default it is simultaneous organisation hence we consider the access time of L2 cache only in case of miss in L2 cache also..

I hope u get my approach @Anusha Motamarri..
0
yeah but actually miss rate is not given here .directly number of misses are given

there are 30 misses in L1 and 10 misses in L2. these 10 misses are also included in 30 misses of L1 isnt it?
there are 220 hits and 30 misses. among them 10 cant be even found in L2(bcoz 10 are misses in L2 also) and 20 can be found in L2. so for 20 references penalty is 10 clocks and remaining 10, penaly is 50 clocks?

is it not like this? :/ those 10 misses are also misses of L1 na?
0
@habib are u assuming that there are 40 misses out of 250 references? and 30 can be found in L2 and 10 cant be found even in L2?
0
No I m not taking 40 misses..
0
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.
0
But for some misses which cannot be found in L2 even , we have :

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,368 answers
198,502 comments
105,271 users