IAE Academy

GATE 2018 CS Q.50: solution and answer

GATE 2018 · CSQ.50 · 2 marks · NAT

The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. Assume that there are no data hazards and no control hazards.

The number of clock cycles required for completion of execution of the sequence of instructions is ______.

See the question in the paper
GATE 2018 CS question 50Tap to open full size

Answer and solution

ANSWER

The total number of clock cycles required is 219.

Official answer: 219Source: Official answer key, GATE 2018 CS (IIT Guwahati)

  1. Identify the bottleneck: IF, ID, OF and WB are fixed at 1 cycle each; only PO varies per instruction, and with no data/control hazards, PO is the sole structural constraint (only one instruction occupies it at a time).

  2. Pipeline fill: the first instruction must pass through IF, ID, OF (1 cycle each) before it can enter PO, costing 3 cycles.

  3. PO never idles: since 100 instructions are queued with no other hazards, once the first instruction enters PO, the PO unit stays continuously busy — its total busy time is the sum of every instruction's own PO duration.

  4. Sum the PO durations: cycles.

  5. Pipeline drain: after the last instruction leaves PO, it still needs the WB stage, adding 1 more cycle.

  6. Total cycles .

KEY IDEA

When one pipeline stage (here PO) has a variable, instruction-dependent duration while every other stage is fixed at 1 cycle, that stage becomes the sole structural bottleneck (no data/control hazards are present). The total completion time is: (cycles for the first instruction to reach the bottleneck stage) + (sum of the bottleneck stage's occupancy over all instructions, since it is never idle once started) + (cycles for the last instruction to drain through the stages after the bottleneck).

WATCH OUT FOR

Treating this like an ordinary 5-stage pipeline and using the naive formula (number of instructions + stages − 1) with some "average" PO time, or forgetting that once PO starts working it stays continuously busy (no idle gaps) so its total busy time is simply the sum of all 100 instructions' individual PO durations — not multiplied by a cycle count or averaged. Another common error is forgetting to add the 1-cycle WB drain after the last instruction leaves PO, or forgetting the 3-cycle fill (IF+ID+OF) before the first instruction enters PO.

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

More Pipelining questions