IAE Academy

GATE 2024 CS2 Q.58: solution and answer

GATE 2024 · CS2Q.58 · 2 marks · NAT

A non-pipelined instruction execution unit operating at 2 GHz takes an average of 6 cycles to execute an instruction of a program P. The unit is then redesigned to operate on a 5-stage pipeline at 2 GHz. Assume that the ideal throughput of the pipelined unit is 1 instruction per cycle. In the execution of program P, 20% instructions incur an average of 2 cycles stall due to data hazards and 20% instructions incur an average of 3 cycles stall due to control hazards. The speedup (rounded off to one decimal place) obtained by the pipelined design over the non-pipelined design is ____________

See the question in the paper
GATE 2024 CS2 question 58Tap to open full size

Answer and solution

ANSWER

The speedup obtained by the pipelined design over the non-pipelined design is 3.0.

Official answer: 2.9 to 3.1Source: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

  1. Non-pipelined execution time per instruction: with average CPI = 6 and clock frequency = 2 GHz (cycle time = 0.5 ns), time = 6 × 0.5 ns = 3 ns.

  2. Pipelined ideal CPI = 1, since the ideal throughput is given as 1 instruction per cycle.

  3. Expected stall cycles per instruction from hazards: 20% of instructions stall an average of 2 cycles (data hazards) → contributes 0.2 × 2 = 0.4 cycles; 20% of instructions stall an average of 3 cycles (control hazards) → contributes 0.2 × 3 = 0.6 cycles. Total expected stall = 0.4 + 0.6 = 1.0 cycle per instruction.

  4. Average pipelined CPI = ideal CPI + expected stalls = 1 + 1.0 = 2 cycles per instruction.

  5. Pipelined execution time per instruction: same clock frequency (2 GHz, cycle time 0.5 ns), so time = 2 × 0.5 ns = 1 ns.

  6. Speedup = (non-pipelined time per instruction) / (pipelined time per instruction) = 3 ns / 1 ns = 3.0. (Equivalently, since both designs share the same clock, speedup = CPI ratio = 6/2 = 3.0.)

KEY IDEA

Speedup from pipelining = (execution time per instruction, non-pipelined) / (execution time per instruction, pipelined). Since both designs run at the same clock frequency, this reduces to the ratio of average CPIs: CPI_non-pipelined / CPI_pipelined, where CPI_pipelined = ideal CPI (1, since throughput is 1 instruction/cycle) plus the expected stall cycles per instruction from all hazards.

WATCH OUT FOR

Forgetting to add the base ideal CPI of 1 to the stall contributions (using average CPI = 0.4 + 0.6 = 1 instead of 1 + 0.4 + 0.6 = 2), which halves the pipelined execution time and gives a wrong speedup of 6.0; or forgetting that both designs run at the same clock frequency (2 GHz), so speedup can be computed directly as the ratio of average CPIs.

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

More Pipelining questions