IAE Academy

GATE 2020 CS Q.43: solution and answer

GATE 2020 · CSQ.43 · 2 marks · NAT

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 ____.

See the question in the paper
GATE 2020 CS question 43Tap to open full size

Answer and solution

ANSWER

The speedup achieved by the pipelined processor over the non-pipelined processor is 2.16.

Official answer: 2.15 to 2.18Source: Official answer key, GATE 2020 CS (IIT Delhi)

  1. Non-pipelined processor: clock = 2.5 GHz ⟹ cycle time = 1/2.5 = 0.4 ns. CPI = 5 (given). Time per instruction = 5 × 0.4 ns = 2 ns.

  2. Pipelined processor: clock = 2 GHz ⟹ cycle time = 1/2 = 0.5 ns. Ideal pipeline CPI (no stalls) = 1.

  3. Instruction mix: memory = 30%, ALU = 60%, branch = 100% − 30% − 60% = 10%.

  4. Average stall cycles/instruction from memory misses = 0.30 (fraction memory) × 0.05 (fraction of those that miss) × 50 (stall cycles) = 0.75.

  5. Average stall cycles/instruction from branch stalls = 0.10 (fraction branch) × 0.50 (fraction of those that stall) × 2 (stall cycles) = 0.10. ALU instructions contribute 0 stall cycles (given).

  6. Total average stall cycles per instruction = 0.75 + 0.10 = 0.85. Effective pipelined CPI = 1 + 0.85 = 1.85.

  7. Time per instruction, pipelined = 1.85 × 0.5 ns = 0.925 ns.

  8. Speedup = time per instruction (non-pipelined) / time per instruction (pipelined) = 2 ns / 0.925 ns = 2.1621... ≈ 2.16.

KEY IDEA

Speedup from pipelining = (time per instruction, non-pipelined) / (time per instruction, pipelined), where each "time per instruction" = CPI × clock cycle time, and the pipelined CPI must include average stall cycles contributed by each instruction class weighted by its frequency and its own stall probability.

WATCH OUT FOR

Forgetting that the branch instruction fraction is the remainder (100% − 30% − 60% = 10%), not 30% again, or adding the base CPI of 1 after computing average stall cycles incorrectly instead of before multiplying by cycle time; also mixing up which processor's cycle time (0.4 ns vs 0.5 ns) goes with which CPI.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 12 Pipelining questions, with notes

More Pipelining questions