Question on Pipelining

Question

In a pipeline the maximum ideal speed-up is 5. Let the percentage of unconditional branches in a set of typical program be 5% and that of conditional branches be 10%. If 70% of the conditional branches are taken, calculate % loss of speed-up due to branch instructions.

It is very difficult to understand this question and solve it. Please help.

Comments

is this question complete ? at what stage the branch will be resolved ? or what is the branch penalty ?

---

Yes the question is complete

---

You can assume that branch will be resolved at EX stage and the target branch instruction will be fetched in the next IF stage – so 2 stall cycles per conditional branch taken.

---

@Arjun sir, By assuming the above assumptions ,

The CPI for the new pipeline is =1+ 0.05*2+0.1*0.7*2=1.24

So new speed up= 5/1.24=4.03

So , speed up loss, $\frac{5-4.03}{5}*100=19.4%$ %

Is this correct answer sir ?

---

@Kabir5454 If we assume penalty for unconditional branches. This should have been specified in question.

---

@Arjun sir yes I have taken penalty for unconditional branches as nothing is mentioned. sir how the branch penalty associated with unconditional and conditional branches differ?

---

In case of conditional branch we need to test some condition (typically a flag set by the previous instruction) to decide whether we need to jump or not. But in case of unconditional branch, this check is not required and even at IF stage we know the target address to fetch the next instruction.

---

@Arjun sir Thank you got it  .

---

@Kabir5454 sorry for asking this silly question, but as arjun sir is saying that target address is known at fetch stage for unconditional branch instructions, then in that case we need to employ some special mechanism to detect whether the instruction is unconditional branch, and if yes then changing the PC value when the unconditional branch instruction is just fetched and before it proceeds to decode stage.. So causing us 0 penalty effectively? can you please confirm.

Answer 1

In Ideal Case, Speed Up Factor = no. of Stages

Here Speed Up Factor = 5 , So no. of Stages = 5

So, Branch penalty = 4

Avg. no. of stalls = (frequency of unconditional branch instruction + frequency of conditional branch instruction ) * branch penalty

Avg. no. of stalls = ( 0.05 + 0.1*0.7 ) * 4

Avg. No. of Stalls = 0.48

Avg. CPI = 1+0.48 = 1.48

new Speed Up Factor = no. of stages / avg. CPI …...in ideal case

new Speed Up Factor = 5/1.48 = 3.378

% LOSS = ((Old Speed Up – New Speed UP) / Old Speed Up)* 100

% LOSS = (( 5 – 3.378 ) / 5) * 100

%LOSS = (1.622 / 5 )* 100 = 32.44%

ANSWER = 32.44% loss