GATE CS Mastery
Cheat sheets

GATE CS 2020 · Computer Organization and Architecture

Question 53

NATPrinted as CS Q.432 marksNo negative markingMedium (estimate)

Question

Consider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5-stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipelined processor at 2 GHz. In a given program, assume that 30% are memory instructions, 60% are ALU instructions and the rest are branch instructions. 5% of the memory instructions cause stalls of 50 clock cycles each due to cache misses and 50% of the branch instructions cause stalls of 2 cycles each. Assume that there are no stalls associated with the execution of ALU instructions. For this program, the speedup achieved by the pipelined processor over the non-pipelined processor (round off to 2 decimal places) is _______.

Official answer and solution
Accepted answers
2.15 to 2.18
From
Official GATE 2020 answer key

Solution

Compute average instruction execution time for both non-pipelined and pipelined processors, then take their ratio.

Non-pipelined processor:

  • Frequency f1=2.5 GHz=2.5×109 Hzf_1 = 2.5\text{ GHz} = 2.5 \times 10^9\text{ Hz}
  • Clock cycle time T1=12.5×109=0.4 nsT_1 = \frac{1}{2.5 \times 10^9} = 0.4\text{ ns}
  • Cycles per instruction = 5
  • Average instruction time tnonpipe=5×0.4=2.0 nst_{\text{nonpipe}} = 5 \times 0.4 = 2.0\text{ ns}

Pipelined processor:

  • Frequency f2=2.0 GHz=2.0×109 Hzf_2 = 2.0\text{ GHz} = 2.0 \times 10^9\text{ Hz}
  • Clock cycle time T2=12.0×109=0.5 nsT_2 = \frac{1}{2.0 \times 10^9} = 0.5\text{ ns}
  • Program mix: 30% memory, 60% ALU, and remaining 100−30−60=10%100 - 30 - 60 = 10\% branch.
  • Average stall cycles per instruction:
    • Memory instructions: 0.30×(0.05×50)=0.30×2.5=0.75 cycles0.30 \times (0.05 \times 50) = 0.30 \times 2.5 = 0.75\text{ cycles}
    • ALU instructions: 0.60×0=0 cycles0.60 \times 0 = 0\text{ cycles}
    • Branch instructions: 0.10×(0.50×2)=0.10×1.0=0.10 cycles0.10 \times (0.50 \times 2) = 0.10 \times 1.0 = 0.10\text{ cycles}
    • Total stalls = 0.75+0.10=0.85 cycles0.75 + 0.10 = 0.85\text{ cycles}
  • CPIpipe=Ideal CPI+Stalls=1+0.85=1.85 cycles\text{CPI}_{\text{pipe}} = \text{Ideal CPI} + \text{Stalls} = 1 + 0.85 = 1.85\text{ cycles}
  • Average instruction time tpipe=1.85×0.5 ns=0.925 nst_{\text{pipe}} = 1.85 \times 0.5\text{ ns} = 0.925\text{ ns}

Speedup calculation:

Speedup=tnonpipetpipe=2.0 ns0.925 ns≈2.16216…\text{Speedup} = \frac{t_{\text{nonpipe}}}{t_{\text{pipe}}} = \frac{2.0\text{ ns}}{0.925\text{ ns}} \approx 2.16216\dots

Rounding off to 2 decimal places yields 2.16 (official accepted range: 2.15 to 2.18).

Final answer

2.16

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

Source

Paper
GATE 2020 Computer Science and Information Technology (CS)
Question
53 of 65, printed as CS Q.43
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.