Pipelining

Question

Consider a 4 stage pipeline where the branch is resolved at the end of the second cycle for unconditional branches and at the end of the third cycle for the conditional branches. Assume that no instruction starts at first stage time the branch condition is evaluated. Let the branch instruction have the following frequencies:-
Conditional Branches=20%
Jump and call=5%
Taken conditional branches=60%
On an average each instruction has a CPI of one clock cycle and ignoring other kinds of stalls how much faster would the machine be without any branch hazards?
a)0.729             b)0.459         c)0.689         d)1.45

Comments

qs 3.4. ans @ Page 25: http://www.eit.lth.se/fileadmin/eit/courses/eit090/HT1Ovn.pdf

---

Can u explain,in the PDF ans is something E lse

---

ya, I noticed. Their numerical values are changed. Explanation is given in the pdf. Where did you get this questions btw? and something changed "Assume that no instruction starts at first stage time the branch condition is evaluated" ?

---

In Facebook group

Answer 1

Let me take the data given in the question ==>

Conditional Branches = 20%

Jumps and calls = Unconditional Bramches = 5%

These two branches types generalize to total branch instructions ==> 25%

Hence, our code includes 75% simple instructions (not causing any stalls) .

---

Hence, now we start from non branch instructions ==> 75% * number of stalls caused = 0.75 * 0 = 0

We see for unconditional branches ==>  branch is resolved at the end of the second cycle for unconditional branches , causing 1 stall = 0.05 * 1 = 0.05

For conditional branches ==> at the end of the third cycle for the conditional branches 

This will lead to 2 stalls , if branch taken ==> 0.20 * 0.60 * 2 

and, also will lead to 2 stalls , if branch not taken ==> 0.20.* 0.40 * 2 (Assume that no instruction starts at first stage time the branch condition is evaluated)

---

On an average each instruction has a CPI of one clock cycle (This condition is given , which means base CPI =1 , without any hazards which will surely increase , if stalls occur due to hazards.)

New CPI = 1 + (0.05) + (0.20.* 0.60 * 2) + (0.20 * 0.40 * 2) = 1.45

Take clock cycle time = T

Hence, speed up , if there were no stalls due to hazards ==> Base CPI * clock cycle time / New CPI * clock cycle time 

= 1 * T / 1.45 * T

= 0.6896

Comments

@Kapil,

"otherwise , will lead to 1 stall , if branch not taken ==> 0.20.* 0.40 * 1"    Logic behind this ? 

I think you have stopped instructions entering into second stage while evaluating branch condition at third stage ? and when found that branch condition is false, then resume it again. So, one cycle stall. is that correct ?

---

@Debashish

Yes.

---

and Sir, for calculating speedup of pipleline over non_pipeline we put time of pipeline in the denominator. (because it is less)

Going by the same logic, for calculating speedup if no hazard we should put no_hazard_pipeline time (cpi=1) in the denominator. (because it is less)

---

according to the explanation u gave the answer will be somewhat 1/1.38 =0.724...

I followed the same approach plz verify where I am wrong my answer is coming to be 1/1.3925=0.719 ...But answer given is 0.689

---

@Debashish, no

Speedup = ET without pipe / ET with pipe

@Amit

Conditional branches are 20% , rt...

---

Actually that is not what i asked.

---

Bro ,my confusion is 5% is unconditional branches so why it will not be remaining to be  95% as conditional branches????

Moreover is the final ans 0.724 correct which is not in option I think so u selected A as the answer..plz clear my confusion

---

@ Amit puri  your diagram is somewhat wrong. Total instruction are divided into tree parts :

1. Non branch instruction (75%)

2. Unconditional Branch instruction. (5%)

3. Conditional Branch instruction (20%). thats it.

---

Bro branch instructions are of two type conditional and non conditional branch instructions for u agree???

---

@kapil "Assume that no instruction starts at first stage time the branch condition is evaluated "

please explain this line

---

@kapilp
" Assume that no instruction starts at first stage time the branch condition is evaluated "

what is the meaning of this

---

if branch not taken ==> 0.20.* 0.40 * 1

@Kapil...why 1 stall when branch is not taken?

---

@vaishali, I guess someone has changed the question. My answer was for a different question.

Correcting now !!!

---

No...but there should not be any stall na..

We have to consider only two cases ...

1/ uncinditional branch

2 branch when taken

other all have cpi 1

---

@Kapil

New CPI = 1 + (0.05) + (0.20.* 0.60 * 2) + (0.20 * 0.40 * 1) ??

right in calculation u have done 

New CPI = 1 + (0.05) + (0.20.* 0.60 * 2) + (0.20 * 0.40 * 2) 

---

@Amit Why $1$ ?

In question, it says 

 Assume that no instruction starts at first stage time the branch condition is evaluated

---

@Kapil

This will lead to 2 stalls , if branch taken ==> 0.20 * 0.60 * 2 

otherwise , will lead to 1 stall , if branch not taken ==> 0.20.* 0.40 * 2

u have written 1 stall if branch is not taken  and multiplied it by 2 so thats my confusion..

and plz do check this question on the similar basis

https://gateoverflow.in/185745/previousgatemodification

---

Yes, that's a typo. Corrected !!

---

Can u Plz verify the answer from the above link

---

Can you provide your answer there ?

---

@Kapil

https://gateoverflow.in/185745/previousgatemodification

plz check the answer in the link

Answer 2

From this line I'm evaluating "Assume that no instruction starts at first stage time the branch condition is evaluated. " that if condition takes or not takes in conditional branch instructions it takes same time ...So here 60% of time branch takes having no significance...

So .avgTime=( 1+ 20 % * stall cycles + 5% * stallcycles)* clock time say t

= 1+ 0.2 *2 + 0.05 *1

= 1.45t

If no hazard it takes 1t time..

So ans should be: 1/1.45 = 0.689

Comments

Bro how u calculated the stall cycles plz explain!!!

---

@Gabbar 

I think it is correct. But one doubt :

( with branch hazard ) speedup_compared_to_non_pipeline = 4/1.45 = 2.7586 ( fast )

( without branch hazard ) speedup_compared_to_non_pipeline = 4/(1+0) = 4 ( faster )

Speed_up with no branch hazard in comparision with hazard = 4/2.7586 = 1.45

I have taken some reference from the pdf answer (last portion)

---

"On an average each instruction has a CPI of one clock cycle " clock per instruction given 1...we r getting 1.45...

@Debashish

@Amit ..see the PDF given by debashish

---

no. no. that i understand, what i am saying, pipilene with no. hazard is 1.45 times faster than pileline with hazard.

Answer 3

Without any branchi pipeline CPI= 1 clock cycle

TO find the average lets suppose there is 100 instruction

Total time taken by 100 instruction is = 12*3 +  8*2 + 5*2 +  75 * 1=137 clock cycle

AVG time=  137 clock cycle/100  =1.37 clock cycle

Speed up=time of pipeline without branching / time of pipeline with branching 

                                  =1 clock cycle/ 1.37 clock cycle

So, correct ans is 0.729