Question

3. Consider an application which has 10% conditional branches and 7.5% unconditional jumps. Assume that the conditional branches are taken 12% of the time. Consider a 5-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 conditional branches. What is the pipelining speedup (over the unpipelined architecture) if

(a) the branch is always predicted to be not taken, and

(b) branch is predicted, but the accuracy is 95% when the branch is not taken, and only 90% when the branch is taken.

ANSWERS:

(a) Branch predicted to be not taken: CPI = 1 + 0.1*(0.88*0+0.12*3) + 0.075*(2) = 1.186 Pipeline speedup = 5/1.186 = 4.216

(b) Branch predicted (95%, 90%) untaken/taken: CPI = 1 + 0.1*(0.88*0.05*3 + 0.12*0.10*3) + 0.075*0.10*2 = 1.0318

Pipeline speedup = 5/1.0318 = 4.846

PLEASE EXPLAIN HOW TO GET THESE ANSWERS

Answer 1

In computer architecture, cycles per instruction (aka clock cycles per instruction, clocks per instruction, or CPI) is one aspect of a processor's performance:

CPI= CPU clock cycles/Instruction count(I)

CPU clock cycles= sum(CPI_I*C_i)

_where

Ci =Count of instructions of typei executed

i = 1, 2, .... n

CPIi= Cycles per instruction for typei

here the types of instructions are Branch instructions and non branch instructions.

(a) Branch predicted to be not taken: CPI = 1 + 0.1*(0.88*0+0.12*3) + 0.075*(2) = 1.186 Pipeline speedup = 5/1.186 = 4.216

in this calculation 1 is base CPI, 0.1 is the execution of 10% of branch instructions . branch instructions are taking 12% of time. so , remaining time is taken by non branch instructions i.e 88% and zero non branch instructions are executed.

so 0.1*(0.88*0+0.12*3) here 3 indicates the number of stalls happened after the third cycle for conditional branches.

7.5 % of unconditional branch instructions are executed and branch is resolved after second cycle.

so cpi=0.075*(2)

there fore total CPI=1 + 0.1*(0.88*0+0.12*3) + 0.075*(2) = 1.186

pipeline speedup is calculated as old speed/new speed=5/1.186=4.216

similarly in

(b) Branch predicted (95%, 90%) untaken/taken: CPI = 1 + 0.1*(0.88*0.05*3 + 0.12*0.10*3) + 0.075*0.10*2 = 1.0318

Pipeline speedup = 5/1.0318 = 4.846

considering the accuracy 5% cycles of non branch instructions are executed with 3 stalls and 10 % cycles of branch(conditional) instructions executed with 3 stalls and 10% cycles of unconditional branches are executed with 2 stalls

therefore

CPI = 1 + 0.1*(0.88*0.05*3 + 0.12*0.10*3) + 0.075*0.10*2 = 1.0318

and

Pipeline speedup = 5/1.0318 = 4.846