The Gateway to Computer Science Excellence

+15 votes

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

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

0

Anusha you are not using 1.25 memory refference per instrucution , since quetion ask stalll per instruction

0

i divided it by 200. which is nothing but number of instructions.

1.25 references-->1 instruction

250 ref--->?

200 instructions

1.25 references-->1 instruction

250 ref--->?

200 instructions

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

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

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

0

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

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>

it means 20 references are hits in L2. and 10 are misses in l2

is it not correct>

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 :/

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) ?

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

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

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

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)

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.

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"

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

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?

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

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.

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,368 answers

198,502 comments

105,271 users