Skip to content
GATETECH
Official PYQ · 2006Q42Instruction PipeliningMCQ1 mark

GATE CS 2006 Q42 — Instruction Pipelining

Explain with AI

A CPU has a five-stage pipeline and runs at 11 GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is known. A program executes 10910^9 instructions out of which 20%20\% are conditional branches. If each instruction takes one cycle to complete on average, the total execution time of the program is: 

Choose one option
View worked solution

Answer: C

To find the total execution time, we need to determine the total number of clock cycles required to execute the program, taking into account the stalls introduced by conditional branch instructions.

1. Determine the Branch Penalty (Stall Cycles)

The pipeline has 5 stages, and instruction fetch (IF) occurs in Stage 1. For a conditional branch instruction:

  • Cycle 1: The branch instruction is fetched in Stage 1.
  • Cycle 2: The branch instruction moves to Stage 2. Since the processor stops fetching new instructions until the branch outcome is known, no new instruction is fetched. (1st stall cycle)
  • Cycle 3: The branch instruction moves to Stage 3, where the target address and condition are evaluated. Still, no new instruction is fetched. (2nd stall cycle)
  • Cycle 4: The branch outcome is now known, and the next instruction (either the target or sequential instruction) is fetched in Stage 1.

Thus, each conditional branch instruction introduces a penalty of 22 stall cycles.

2. Calculate Total Cycles

Given:

  • Total instructions (NN) = 10910^9
  • Base CPI (without stalls) = 11 cycle per instruction
  • Percentage of conditional branches = 20%20\% of 109=0.2×10910^9 = 0.2 \times 10^9

The total number of clock cycles is calculated as:

Total Cycles=Base Cycles+Total Stall Cycles\text{Total Cycles} = \text{Base Cycles} + \text{Total Stall Cycles} Total Cycles=109+(0.2×109×2)=109+0.4×109=1.4×109 cycles\text{Total Cycles} = 10^9 + (0.2 \times 10^9 \times 2) = 10^9 + 0.4 \times 10^9 = 1.4 \times 10^9 \text{ cycles}

3. Calculate Execution Time

The CPU clock frequency is 1 GHz=109 Hz1\text{ GHz} = 10^9\text{ Hz} (cycles per second).

Execution Time=Total CyclesClock Frequency=1.4×109 cycles109 cycles/second=1.4 seconds\text{Execution Time} = \frac{\text{Total Cycles}}{\text{Clock Frequency}} = \frac{1.4 \times 10^9 \text{ cycles}}{10^9 \text{ cycles/second}} = 1.4 \text{ seconds}

Therefore, the total execution time of the program is 1.4 seconds.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Instruction Pipelining questions