Gateoverflow Computer architecture 2 exam question

Question

Suppose there are 500 memory references in which 50 misses in the 1st level cache and 20 misses in the 2nd level cache . Let the miss penalty from L2 cache to memory is 100 cycles . Hit time in L2 cache is 20 cycles and hit time in L1 cache is 10 cycles . If there are 2.5 memory reference/instruction , average number of stall cycles per instruction will be __________

Ans is : 15

Can any explain how to solve this type of question, Thanks in advance.

Comments

can we solve it like this???

 

1st level memory(10cycles) –

miss → 50/500 → 0.1 

hit – 0.9

2nd level memory(20 cycles) –

miss – 20/50 → 0.4 

hit – 0.6

3rd level – 100 cycles (miss Penalty)

hierarchical access

avg cycles – 0.9*10 + 0.1*0.6 *(10+20) + 0.1 * 0.4 * (10+20+100)

---->16 cycles

1 cycles is required in general

So (16-1) -→ 15

 

---

Its fine till 16 cycles(this is actual cycles per memory reference)

Now we will find cycles per memory reference if there were no stalls i.e if the hit rate of L1 is 1

This will give cycles per memory reference = hit time for L1 cache which is 10 cycles

Therefore, stall cycles per memory reference = 16 – 10 = 6 cycles

Now there are 2.5 memory reference per instruction. Therefore, stall cycles per instruction = 2.5 * 6 = 15 cycles.

Answer 1

Given, L1 misses = 50, L2 misses = 20, Miss penalty of L2 = 100 cycles

Hit time for L2 = 20 cycles, Hit time for L1 = 10 cycles, 2.5 memory reference/instruction

Note:- Miss penalty of L1 cache = Hit time of L2 cache

Total stalls = (Miss rate of L1)* (Miss penalty of L1) + (Miss rate of L1) * (Miss rate of L2) * (Miss penalty of L2)

= (50/500)* 20 + (50/500) * (20/50) * 100

= 6

Given 2.5 memory reference/instruction

so 6 * 2.5 = 15 number of stall cycles per instruction.

 

 

Comments

Thanks @Shamim Ahmed.

Why we have considered this?

Note:- Miss penalty of L1 cache = Hit time of L2 cache

---

Its because whenever there is a miss in L1 cache, we refer to the L2 cache (Hit) which is Miss penalty of L1 cache.

Answer 2

Another way to solve could be like this :

---

They’re asking average number of stalls per instructions , so we need to only find extra cycles taken due to misses.

And hit rate or miss rate is always w.r.t memory references and not instructions.

And for 500 memory references , no. of instructions = 500/2.5 = 200 instructions

Keeping these things in mind :

Miss rate of l1 = 50/500 = 1/10 = 0.1

Miss rate of l2 = 20/50 = 0.4

So , 500 memory references will take = 500 (10 + 0.1( 20 + 0.4 * 100 )) = 500* 16 cycles

And if these were only hits then 500 memory references would’ve taken = 500*10 cycles.

So, extra cycles taken (stalls) = 500*16 – 500*10 = 3000 cycles

These are total no. of stalls and we needed to find the average per instruction , so dividing it just by total no. of instructions :

Average stalls per instruction = 3000/200 = 15 cycles

Comments

Nice approach.. I used the same. Just wanted to add that while solving for cycles per instruction, we can calculate for 1 memory reference which will also give 16 and 10 cycles (16 – 10 = 6 stall cycles per memory reference) And then multiple it by 2.5

6*2.5 = 15 cycles

Answer 3

CPU------------ L1 Cache --------------------- L2 Cache ----------------Main Memory

Formula : 1) Miss penalty L2 = MM Access time

2)Miss penalty L1= Hit time L2 + (Miss rate L2)*(Miss penalty L2)

3)Avg Memory access time= Hit time L1+ (Miss rate L1)*(Miss penalty L1)

Total no. of instructions= 500/2.5 = 200

Miss penalty L1= 10+ (20/200)*100 =20              (since miss rate = No. of misses/total no. of instructions)

Average memory access time = 10 + (50/200)*20 = 15

Comments

L2 Hit time is 20 not 10

---

Miss rate or hit rate is always w.r.t total no of memory references and not instructions.