Pipelining Questions in GATE CSE: Patterns and Traps

Pipelining questions in GATE CSE come in two families: performance arithmetic, where you turn stage delays into a cycle time and then into a total time or a speedup, and cycle counting, where you trace an instruction sequence through a timing diagram and add stalls. Both are mechanical once the conventions are fixed. This guide works each family with a short example, and spends time on the split-stage trap, which produces a wrong answer that looks right.

Key takeaways

• Clock period = slowest stage delay + latch delay. Everything else follows from that one number.
• Time for n instructions in a k-stage pipeline = (k + n − 1) × period. Add, do not multiply.
• Splitting the slowest stage helps only until the next-slowest stage becomes the bottleneck.
• Forwarding removes arithmetic-to-arithmetic stalls but leaves one stall on a load-use pair.
• Whether the register file is split-phase changes stall counts by a cycle, so read that assumption before counting.

Where pipelining sits in the paper

The GATE 2027 CS syllabus names the topic directly: "Instruction pipelining, pipeline hazards". That wording is unchanged in substance from 2026, even though the rest of the Computer Organization section was reworded; the changes are covered in the guide to the 2027 COA syllabus changes.

Third-party analyst compilations put COA at 3 to 12 marks per paper from 2009 to 2026, typically 8 to 11 marks. These numbers are unofficial and analysts differ by two to three marks. Within that budget, pipelining and the memory hierarchy are the two pillars, and the book's analysis estimates that they have supplied roughly 60 to 70 per cent of COA marks since 2014.

These year attributions are an analyst reconstruction from previous-year repositories and are approximate. For the whole subject in one place, read the COA important topics guide.

The cycle-time template

A four-stage pipeline has stage delays 8, 6, 12 and 10 ns, with a 1 ns pipeline register between stages.

• Clock period = max(8, 6, 12, 10) + 1 = 13 ns.
• Time for 1000 instructions = (4 + 1000 − 1) × 13 = 1003 × 13 = 13,039 ns, about 13.04 µs.
• The same work without pipelining takes 8 + 6 + 12 + 10 = 36 ns per instruction, so 36,000 ns for 1000 instructions. Note that the non-pipelined time carries no latch delays.
• Speedup = 36,000 / 13,039 ≈ 2.76, below the ideal limit of 4.

Three details decide the answer. The latch delay is added to the maximum stage only, not to every stage. The count is (k + n − 1), not k × n. And the non-pipelined reference is the sum of the stage delays, with latches excluded unless the question says otherwise.

The split-stage trap

Setters like to ask what happens when the slowest stage is split into two equal halves. The tempting answer is that the throughput doubles. It does not.

Split the 12 ns stage into two 6 ns stages. The pipeline now has five stages with delays 8, 6, 6, 6 and 10 ns. The slowest stage is now the 10 ns one, so the period becomes 10 + 1 = 11 ns, not 6 + 1 = 7 ns.

• Throughput rises from 1/13 to 1/11 per ns, an increase of 13/11 − 1 ≈ 18.2 per cent, not 100 per cent.
• Time for 1000 instructions = (5 + 999) × 11 = 11,044 ns.
• Speedup over the non-pipelined machine rises to 36,000 / 11,044 ≈ 3.26.

The general rule: splitting or merging stages changes the period only to the extent that the bottleneck moves. Always recompute the maximum across the new stage list before doing anything else.

Data hazards, forwarding and stall counting

The second family gives a short instruction sequence and asks for total cycles. Fix the conventions first, then draw the diagram.

In a standard five-stage pipeline with IF, ID, EX, MEM and WB:

A short example. Five instructions, full forwarding, exactly one load-use pair among them. The hazard-free time is (5 + 5 − 1) = 9 cycles, and the single load-use stall adds one, so the answer is 10 cycles.

When the execute stage takes several cycles, as with a multiply or divide, the dependent instruction waits until the producer's multi-cycle stage ends, and forwarding starts from there. That is the same idea with a longer wait, and it is the shape placed in 2008, 2010, 2015 and 2021 in the reconstruction. A related shape gives a per-class table of cycles spent in one stage and asks for the total over a hundred instructions; there the extra cycles simply add up.

Control hazards and CPI with stalls

Control-hazard questions are usually expressed as a CPI computation. If a branch is resolved at the end of stage s and fetching stops until then, each taken branch costs s − 1 cycles.

Example: branches are resolved at the end of stage 3, so the penalty is 2 cycles. Twenty per cent of instructions are branches and 60 per cent of those are taken, with predict-not-taken.

• Effective CPI = 1 + 0.20 × 0.60 × 2 = 1.24.
• Now add a predictor that is 90 per cent accurate on all branches. Only mispredictions cost the penalty: CPI = 1 + 0.20 × 0.10 × 2 = 1.04.
• Speedup from the predictor at the same clock = 1.24 / 1.04 ≈ 1.19.

The general form is CPI = 1 + the sum over hazard classes of (fraction of instructions) × (stalls each), and execution time = instruction count × CPI / clock frequency. That single expression covers the two-processor comparison questions as well.

The traps that cost marks

• (k + n − 1), not k × n. The most expensive arithmetic slip in the topic.
• Latch delay once. Add it to the maximum stage, not to each stage, and leave it out of the non-pipelined reference.
• Splitting a stage. Recompute the maximum; the gain stops at the next-slowest stage.
• Split-phase register file. Writing in the first half of a cycle and reading in the second half removes one stall. Pre-2021 questions assume it; recent questions state it.
• Forwarding does not fix everything. A load-use pair still costs one stall, so the statement that bypassing removes all read-after-write hazards is false.
• Delay slots always execute. The instruction in a delay slot runs whether or not the branch is taken.
• Prediction only helps when correct. A predictor of accuracy p leaves a penalty on the remaining fraction.
• Clock units. Convert GHz to ns before mixing frequencies with stage delays.
• Cycles in a stage versus stage delay. Questions mix the two deliberately; one is a count, the other a time.

The cross-subject version of this list is in common mistakes that cost marks in GATE CSE, and the formulas are collected in the GATE CSE formula sheet.

How to practise pipelining

Work the performance template in both directions: delays to time, and a target time back to a required stage delay or frequency. Then take one six-instruction sequence and count its cycles four times, once with full forwarding, once without, once with a split-phase register file and once without, so the effect of each convention is something you have measured rather than memorised.

Finish with one CPI expression per paper you practise, written out as 1 plus each stall term, because that single line converts almost every branch, memory and two-processor comparison question into arithmetic. The COA chapter of the GATE CSE 2027 book sets out these patterns with worked solutions and states every convention inside the question, which is the habit that keeps a difficult timing item from becoming a guess.