Consider a 3-stage pipelined processor having a delay of 10 ns (nanoseconds), 20 ns, and 14 ns, for the first, second, and the third stages, respectively. Assume that there is no other delay and the processor does not suffer from any pipeline hazards. Also assume that one instruction is fetched every cycle.
The total execution time for executing 100 instructions on this processor is ______ ns.
ANSWER
The total execution time for executing 100 instructions on this pipelined processor is 2040 ns.
Official answer: 2040Source: Official answer key, GATE 2023 CS (IIT Kanpur)
The processor is a k = 3 stage pipeline with per-stage delays 10 ns, 20 ns, and 14 ns.
With no hazards and a single shared pipeline clock, the cycle time must be long enough for the slowest stage: cycle time = max(10, 20, 14) = 20 ns.
One instruction is fetched (issued into the pipeline) every cycle, so for n = 100 instructions the pipeline needs k − 1 = 2 extra cycles to fill up plus n = 100 cycles for all instructions to be issued and drained, giving k + n − 1 = 3 + 100 − 1 = 102 cycles total.
Total execution time = 102 cycles × 20 ns/cycle = 2040 ns.
KEY IDEA
In a k-stage pipeline with no hazards, the cycle time is set by the slowest stage, and n instructions (one issued per cycle) finish in (k + n − 1) cycles — k−1 cycles to fill the pipeline plus n cycles for the n issues.
WATCH OUT FOR
Using the sum of all stage delays (10+20+14 = 44 ns) as the cycle time instead of the maximum stage delay (20 ns) — a pipelined cycle time is bounded by the slowest single stage, not the total latency of one instruction.
From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 12 Pipelining questions, with notes
