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

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