#pipeline

Question

Consider execution of 100 instructions on a 5 stage pipeline. let P be the probability of an instruction being branch. The value of P such that speed up is atleast 4 is_____(assume each stage takes 1 cycle to perform its task and branch is predicted on forth stage of the pipeline)

Comments

0.083?

---

Yes in solution 0.083 is given but how can we solve by formula when 200 instructions given

---

https://gateoverflow.in/108984/pipeline

Check this out. 

---

https://gateoverflow.in/?qa=blob&qa_blobid=6176833211935305887

Don't have have to solve like this?

---

@Gokulnath I understand solution but that formula is for when instructions is not given we to calculate here for 200 instructions right?

---

https://gateoverflow.in/?qa=blob&qa_blobid=6176833211935305887

Check this out @Gokulnath

---

Yeah, your method is correct too. I assumed in my answer that the number of instructions are large, which is not correct.

However, the branch penalty should be three cycles, not four. Since the result is available at the end of the 4th stage, we'll have to wait for 3 cycles.

---

I took cpi=4 which is right penalty is 3 but cpi will be 4 https://gateoverflow.in/?qa=blob&qa_blobid=16246862257139630479

And thanks

---

I'm sorry if I confused haha, I thought you wrote stalls in the formula. Hope I was able to help.

---

Thanks for helping. In exam which method I should prefer?

---

$4 = 5*100/(5+99+100*3*p)$

$104 + 300p = 125$

$p = 7/100 = 0.07$

---

5 * 100 /  100 * ( ( P(1+3) + (1-P) (1) ) > =4

500 / 100 * ( 4P +1 - P) >= 4

500/ 100 * (3P +1) >= 4

500/ 300P + 100  >=4

500 >= 1200P + 400

100 >= 1200P

100/1200 >= P

0.083 >= P

---

Don't we have to multiple 99+5 with (p-1)

@shreyansh jain

---

@Utkarsh Joshi

why are you not considering the fact that first instruction in pipeline will take 5 cycles? 

---

We can't do like this for first stage 5 cpi after that 1 cpi for 99 instructions with out branch and same way for with branch @Utkarsh Joshi

---

I am agree with you @shreyansh jain

---

Check this out @shreyansh jain

https://gateoverflow.in/?qa=blob&qa_blobid=6176833211935305887

---

If the instruction is not a branch 1 cycle. if it is, 1+3 clock cycles. what is wrong with this?

---

@Utkarsh Joshi

you are missing 4 extra cycles for first instruction.

refer: https://gateoverflow.in/204125/gate2018-50

---

@Shaik Masthan dude help!

---

@Utkarsh Joshi

you are doing by taking CPI, we are using CPI means, no.of instructions are very large.

i mean CPI = 1, but it is not true for limited number of instructions,

when we take infinite number of instructions, then we can take CPI = 1

and follows your method...

but in this question, it is given that number of instructions are 200

follow the 2$^{nd}$ method of @Debashish Deka sir method, which is in the link provided by @Gokulnath

which is exactly did by the @shreyansh jain

---

Hmm so by considering those initial cycles getting 0.07 is it correct? @Gokulnath @Shaik Masthan

---

yes, it is correct !

By the way, the answer in that link, need small correction, i updated it, if you want you can see it !

---

okay!

---

We usually use the formula that Speedup = $\frac{\text{Pipeline Depth}}{\text{CPI_{ideal} + Pipeline Stalls Per Instruction}}$.

Now, this formula works only in the case when all the instructions pass through all the stages of the pipeline. Here, I I've assumed that all the instructions pass through all the stages, and hence wrote the numerator as five. Regarding the denominator, we take the ideal CPI of a processor to be 1 on a pipelined processor.

For the other term, assuming the stalls are only from branches, we can write the stall cycles as $\text{Branch Frequency*Branch Penalty}$. Here, the branch frequency will be $p$ and using the same, I've solved the question.

The important assumption is that CPI of a pipelined processor is $1$ only when the number of instructions are large. For a finite number of instructions, using the exact value of instructions should give a more accurate answer.

---

@Shaik Masthan @shreyansh jain can you update the final answer? 

My doubts are 

1) don't we have to multiple with (p-1) in non branch instruction here

2) we have to multiply branch with cpi=4 why are we taking penalty=3?

---

@Shaik Masthan@shreyansh jain sry sry got it final answer is 0.07 I just did from other method I will update it in ans section soon

Answer 1

Taking some assumptions  , let the 5 stages be IF, D, EX, M ,WB. Since in the case of pipeline it is given that branch will not be known till M, so there will be  3 stall cycles. Branch penalty=3(for branch instructions).

                                                IF  |  ID | E | M | WB

                                                        X |  X | X |  IF |......    so, 3 stall cycles will be there  in case of branch instruction.

Avg CPI(pipelined)= 1(in the ideal case)  +  Branch penalty *# of branch instructions=1+3*P (let P will be the number of branches

instructions)=1+3p.

       In the case of non-pipelined CPI=5(since there will be no overlapping).

Given speedup>=4  

=> 5/1+3p>=4

=>p<=0.084

Comments

Why you have not consider value of n and taken ideal case … I think answer should be 0.07

500/(5+100-1)+100(3x)=4  

By solving this we get x=0.07

Hence, thats the probability