GATE CS Mastery
Cheat sheets

GATE CS 2022 · Computer Organization and Architecture

Question 61

NAT2 marksNo negative markingMedium (estimate)

Question

A processor X1 operating at 2 GHz has a standard 5-stage RISC instruction pipeline having a base CPI (cycles per instruction) of one without any pipeline hazards. For a given program P that has 30% branch instructions, control hazards incur 2 cycles stall for every branch. A new version of the processor X2 operating at same clock frequency has an additional branch predictor unit (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 X1 and X2. If the BPU has a prediction accuracy of 80%, the speed up (rounded off to two decimal places) obtained by X2 over X1 in executing P is____________.

Official answer and solution
Accepted answers
1.42 to 1.45
From
Official GATE 2022 answer key

Solution

Calculate the effective CPI for processors X1 and X2 and compute their speedup ratio.

Let II be the number of instructions in program P, and pb=0.30p_b = 0.30 be the fraction of branch instructions.

  1. For processor X1:

    • Base CPI = 1.
    • Every branch incurs a penalty of 2 stall cycles.
    CPI1=1+(0.30×2)=1+0.60=1.60\text{CPI}_1 = 1 + (0.30 \times 2) = 1 + 0.60 = 1.60

  2. For processor X2:

    • BPU accuracy = 80% (0.800.80). Correctly predicted branches incur 0 stall cycles.
    • Misprediction rate = 1−0.80=0.201 - 0.80 = 0.20. Mispredicted branches incur the standard 2 stall cycles.
    CPI2=1+(0.30×0.20×2)=1+0.12=1.12\text{CPI}_2 = 1 + (0.30 \times 0.20 \times 2) = 1 + 0.12 = 1.12

  3. Speedup of X2 over X1 at the same clock frequency:

    Speedup=Time1Time2=CPI1CPI2=1.601.12=160112=107≈1.4286\text{Speedup} = \frac{\text{Time}_1}{\text{Time}_2} = \frac{\text{CPI}_1}{\text{CPI}_2} = \frac{1.60}{1.12} = \frac{160}{112} = \frac{10}{7} \approx 1.4286

Rounding to two decimal places gives 1.43 (official key accepts range 1.42 to 1.45).

Final answer

1.43

Common trap

Applying the 80% branch prediction accuracy to all instructions rather than only the 30% branch instructions.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2022 Computer Science and Information Technology (CS)
Question
61 of 65
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.