Pipelining in COA: Speedup, Hazards, and Worked GATE Examples

Pipelining can look like disconnected formulas: speedup, throughput, k + n - 1, latch delay, and stall cycles. Memorise them without a picture and one twist can break the solution. Build the picture first, and the formulas follow. Work it on an awkward machine, stages of 8, 5, 9, 7 and 6 ns with a 1 ns latch between them, because unequal stages are what GATE sets and are exactly where the speedup-equals-k shortcut fails.

What pipelining actually does, and what it does not

A processor uses pipelining by breaking execution into stages and overlapping successive instructions. Think of a laundry where different loads occupy the wash, dry, and fold stations at the same time.

The classic five-stage RISC pipeline is:

1. IF, instruction fetch: read the instruction from memory.

2. ID, instruction decode and register read: understand the instruction and obtain its operands.

3. EX, execute: perform the ALU operation or calculate an address.

4. MEM, memory access: read or write data memory when required.

5. WB, write back: place the result in the destination register.

Pipelining does not make one instruction finish faster. Its latency still covers all stages and can increase because pipeline registers add delay. It improves throughput, the instructions completed per unit time. Once full, an ideal pipeline completes one instruction per clock.

The clock period: the slowest stage rules

Every stage shares one clock. Its period must accommodate the slowest stage and the register, or latch, delay between stages:

Pipeline clock period, Tp = maximum stage delay + latch delay

Suppose the stage delays are IF = 8 ns, ID = 5 ns, EX = 9 ns, MEM = 7 ns, and WB = 6 ns. The latch delay is 1 ns. EX is the slowest stage at 9 ns, so:

Tp = 9 + 1 = 10 ns

Unbalanced stages waste time. ID needs 5 ns but receives a 10 ns slot, leaving 5 ns unused there every cycle. Balanced stages move the design closer to ideal speedup.

Speedup, throughput, and efficiency: Worked Example 1

For n instructions and k pipeline stages:

• Non-pipelined time = n × sum of all stage delays

• Pipelined time = (k + n - 1) × Tp

• Speedup = non-pipelined time divided by pipelined time

• Efficiency = speedup divided by k

Use the same five stages for n = 100 instructions. Their total delay is:

8 + 5 + 9 + 7 + 6 = 35 ns

Without pipelining, each instruction takes 35 ns:

100 × 35 = 3500 ns

After the pipeline fills, the remaining results emerge one per cycle:

(5 + 100 - 1) × 10 = 104 × 10 = 1040 ns

Therefore:

Speedup = 3500 / 1040 = 3.365... ≈ 3.37

As the instruction count grows, fill and drain cost matters less. The limiting speedup is:

35 / 10 = 3.5

It does not reach five because the stages are unequal and the latch adds 1 ns. Perfectly balanced stages with no latch delay push the limit to k = 5.

The pipeline completes one instruction per 10 ns in steady operation:

1 / (10 ns) = 100 million instructions per second, or 100 MIPS

The non-pipelined machine completes one per 35 ns:

1 / (35 ns) ≈ 28.57 MIPS

Efficiency is 3.37 / 5 ≈ 0.67, or about 67 percent. Stage imbalance, latch overhead, and fill and drain time keep it below the ideal.

The three hazard families that break the ideal

A structural hazard occurs when two instructions need the same hardware in one cycle. For example, IF and MEM may need one memory port together. Separate instruction and data memories remove the conflict.

A data hazard occurs when instructions depend on the same value:

• RAW, read after write: ADD R1, R2, R3 followed by SUB R4, R1, R5. The subtraction needs R1 produced by the addition. This is the important data hazard in a simple in-order pipeline.

• WAR, write after read: a later instruction writes a register before an earlier instruction has read it.

• WAW, write after write: two instructions write the same register in the wrong order.

WAR and WAW arise with out-of-order or multi-cycle execution, not in the basic five-stage in-order pipeline.

A control hazard comes from a branch. Until the branch decision is known, the processor may fetch instructions from the wrong path. Those instructions must be flushed if the chosen path was wrong, creating a branch penalty.

Making hazards cheaper: Worked Example 2

Operand forwarding, also called bypassing, sends a result directly from a stage output to a following instruction's input. Most RAW dependencies between arithmetic instructions then need no stall. A load-use dependency still needs one bubble because the loaded value becomes available only after MEM.

For branches, a processor can freeze and flush the pipeline, predict the branch and squash wrong-path work after a miss, or use a delayed-branch slot. Each technique changes the average number of stall cycles.

Now consider an ideal five-stage pipeline with CPI = 1 and equal stage clocks. Suppose branches form 20 percent of instructions and impose a 3-cycle penalty. Load-use hazards affect 30 percent of instructions and each adds one stall cycle.

Average stall cycles per instruction are:

(0.20 × 3) + (0.30 × 1) = 0.6 + 0.3 = 0.9

Effective CPI is:

1 + 0.9 = 1.9

Under this standard equal-clock model, speedup over the unpipelined machine is:

5 / 1.9 = 2.6315... ≈ 2.63

The ideal speedup was five, but hazards reduce it to about 2.63. Better forwarding and branch prediction matter because they reduce the frequency or cost of those stalls.

How GATE and interviews test pipelining

Most questions reduce to a small set of patterns:

• Given stage delays and a latch delay, find the minimum clock period. Here the 9 ns EX stage plus the 1 ns latch gives 10 ns.

• Count cycles for n instructions using k + n - 1, then multiply by the clock period if time is required. Here 104 cycles, so 1040 ns.

• Calculate speedup, throughput, or efficiency. Here 3.37, 100 MIPS, and about 67 percent.

• Count bubbles in an instruction sequence with and without forwarding. A load followed immediately by a use of the loaded value costs one bubble even when forwarding is present.

• Combine branch frequency and penalty into average stalls and effective CPI. Here 0.9 stall cycles per instruction and a CPI of 1.9.

An interview may instead ask why real speedup is less than the number of stages. The complete answer is fill and drain time, hazards, unbalanced stages, and latch overhead.

The official GATE CS syllabus lists Computer Organization and Architecture, including pipelining, as a core area. For any current marks split, weightage, or negative-marking rule, check the current-year syllabus and information brochure published by the organising institute. The GATE CS Exam Preparation category places this topic in the wider syllabus, while the GATE Test Series provides timed topic-wise practice.

The short version and your next step

Keep five ideas together:

1. Overlap improves throughput, not the latency of one instruction.

2. The slowest stage plus latch delay sets the clock period.

3. Speedup is [n × sum of stage delays] / [(k + n - 1) × Tp], and approaches k only under ideal conditions.

4. Structural, data, and control hazards add conflicts, bubbles, and flushes.

5. Forwarding and prediction recover performance by cutting stall cycles.

If pipelining still feels like formula soup, study it inside the full COA sequence in GATE Guidance by Sanchit Sir, then solve timed questions instead of rereading formulas.

Pipelining in Computer Architecture works the same model with equal-length stages, where speedup is (n × k) / (k + n - 1) and the latch delay never enters the clock period, and Cache Memory: Mapping and Hit Ratio covers the memory side, since a cache miss is what stalls a real pipeline in the first place.