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

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