edited by
3,744 views
21 votes
21 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
edited by

4 Answers

Best answer
37 votes
37 votes

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

edited by
22 votes
22 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..

2 votes
2 votes
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$
2 votes
2 votes
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

Related questions