Pipeline Stall

Question

Whenever Question is given on pipeline with branching i am confused to calculate that how many stalls will be there in the pipeline according to the constraint depicted in the pipeline. How to solve Such Questions?

Like in this Question https://gateoverflow.in/683/gate2000-12   How many stalls will be created.Please Explain with any Example ?

And what is meant by this line "If there are N Cycles then N-1 Stalls will be there"?

Please Help

Comments

Please any body help.

Answer 1

look at this example . here five stage pipeline IF,ID,EX,MA,WB . and decoding will be done at ID stage (2nd stage) . when we execute this then expected optput is I1-I2-BI1. BUT in the pipeline IF stage is always overlaping with ID stage so befor decoding the correntlly fetched instn the sequence instn (I3) is already inserted in a pipeline  when ID stage decode the instn as a jump instn then I3 instn become unwanted instn. and actual output is - I1-I2-I3-BI1. HERE decoding (target address) is done at 2nd level and one unwanted instn is fetchd. this unwanted instn is colled branch panality(stall) .

Comments

Thanks sir some doubts though:-

1. In above pipeline the 3rd instruction will not be completely executed becuase when I2 is decoded at that time we have successfully fetched I3 but the decode of I3 will not take place because the branch target will now be fetched hence Branch penalty or stall will be created i.e. only 1 stall am I right? Because only fetch of I3 was incorrect and that is considered as a stall isn't it?  

2. Sir the branch to be taken or not to be taken is decided only when the instruction is executed i.e. branch target is calculated in EX phase then why did u here considered the execution of branch target after decode phase.

3. Sir didn't understood your formulae you said

Branch penalty = stageno - 1 ? Which stageno you talking about is it the stage where we identify that it's a branch instruction so we jump to branch target like in above case according to u after decode phase we identified it's a branch instruction so stage No = 2. So branch penalty = 1??

Am I right Sir? Please give some light on formula as well.

And thanks so much for this valuable reply.

---

1) here target address is calculated in 2nd phase (decode stage) then branch panality become 1. If it is calculated in 3rd stage then two unwanted instn is executed.  Then branch panality become 2.

So I right branch panality =stages no -1.

2) Branch target is not calculated always in ex stages.  It is given in question.

---

Ok sir got it

---

look at this example . here target address is calculated on 3rd stage so branch panality is 2.

---

Sìr for above Texec = (1 + branchfreq * penalty) Tp.

Tp = 1ns.

For 1 instruction = Texec = (1+0.2×2) = 1.4 = CPI

For 10^9 instruction = 1.4 sec  ---> Answer

---

Sir is it not correct?

---

 Na462 you are right.

---

Thanku so much sir

---

Sir Consider :-  "An instruction pipeline has Five Stages where each stage takes 2ns and all instruction use all five stages.Branch instruction aren't overlapped i.e. the instruction after the branch is not fetched till the branch instruction is executed"

Sir what does this line suppose to mean :- 

Branch instruction aren't overlapped i.e. the instruction after the branch is not fetched till the branch instruction is executed

How many Stalls would occur here Sir ?