GATE CSE 2022 | Question: 51

Question

A processor $\text{X}_{1}$ operating at $2 \; \text{GHz}$ has a standard $5-$stage $\text{RISC}$ instruction pipeline having a base $\text{CPI (cycles per instruction)}$ of one without any pipeline hazards. For a given program $\text{P}$ that has $30 \%$ branch instructions, control hazards incur $2$ cycles stall for every branch. A new version of the processor $\text{X}_{2}$ operating at same clock frequency has an additional branch predictor unit $\text{(BPU)}$ that completely eliminates stalls for correctly predicted branches. There is neither any savings nor any additional stalls for wrong predictions. There are no structural hazards and data hazards for $\text{X}_{1}$ and $\text{X}_{2}.$ If the $\text{BPU}$ has a prediction accuracy of $80 \%,$ the speed up $\textit{(rounded off to two decimal places)}$ obtained by $\text{X}_{2}$ over $\text{X}_{1}$ in executing $\text{P}$ is _______________.

Answer 1

5 Stage RISC has these stages  

IF

ID

EX

MA

WB

 

Processor has a frequency of 2GHz  means clock pulse = 0.5 nano Sec (tp = 0.5 nsec) 

As per the question CPI is one(1) when there is no any hazard. Now 30% instructions cause 2 cycle stall.

let us suppose we have some x number of instructions.  0.3*x instructions suffer stall of 2 cycles each means total stall cycles is 0.6*x. So total number of cycles for x instructions = 1.6*x.

Avg CPI is 1.6 cc

Now this version is improved which has now a Branch predictor unit. It is mentioned that if prediction goes wrong there is no any penalty(extra stall) means 2 cc stall will still be there which was there in older version.

But when we have a correct branch prediction those extra 2 cc stall in the older version would be eliminated. 

$\textup{80% of 30%}$ instructions has zero(0) stall but  $\textup{20% of 30%}$ instructions has 2 cycle stall.

Number of stall cycles in the new version is $\frac{20}{100} * \frac{30}{100}* 2 = 0.12$ cc and overall CPI is 1.12 cc 

Now speedup of older version X1 : 

$\frac{Non - pipeline \, execution\, time}{Pipelined \, execution\, time}$ = $\frac{5*x* 0.5}{1.6*x* 0.5} = \frac{5}{1.6} = 3.125$

 

Speedup of New version X2 : 

$\frac{Non - pipeline \, execution\, time}{Pipelined \, execution\, time}$ = $\frac{5*x* 0.5}{1.12*x* 0.5} = \frac{5}{1.12} = 4.464$

Now Ratio of Speedup of X2 over X1 = $\frac{Speedup\, X2}{Speedup\, X1} = \frac{4.64}{3.125} = 1.4285$