Instruction Pipelining & Hazards

Pipelining is the single largest source of performance in a modern processor, and it is also the topic where intuition most reliably misleads.

A pipeline does not make any individual instruction faster. An instruction still passes through every stage and, in a pipelined machine, usually takes slightly longer than it would in an unpipelined one, because each stage must be separated by a register whose setup and clock-to-output delays are pure overhead.

What a pipeline improves is throughput. By overlapping the stages of different instructions, a new instruction completes every cycle instead of every $k$ cycles, and it is that completion rate that determines how long a program takes.

The second organising fact is that every hazard is a case where the overlap is not safe. A structural hazard means two instructions want the same hardware in the same cycle. A data hazard means an instruction needs a value that an earlier instruction has not produced yet. A control hazard means the machine does not yet know which instruction comes next.

So the way to answer a pipelining question is to draw the stage-by-stage diagram and find the cycle where two instructions collide. Everything else — speedup formulas, forwarding paths, branch penalties — follows from that picture.

1. The Pipeline Model

Divide instruction execution into $k$ stages of roughly equal delay, and place a register between each pair.

A classic five-stage pipeline uses instruction fetch, instruction decode with register read, execute, memory access and writeback.

The clock period is set by the slowest stage plus the pipeline register overhead, not by the average stage. Balancing stages therefore matters more than shortening any one of them.

$T_{clock}=\max (T_{stage})+T_{register}$

For $n$ instructions on a $k$-stage pipeline with no hazards, the first instruction takes $k$ cycles to emerge and each subsequent one takes a single further cycle:

$T_{total}=(k+n-1)\times T_{clock}$

The $k-1$ term is the fill time, the cycles spent before the pipeline reaches steady state, and it is why pipelining pays only when $n$ is large compared with $k$.

2. Speedup and Efficiency

Compare against an unpipelined machine that takes $k$ cycles per instruction.

$S=\frac{n\times k}{k+n-1}$

As $n$ grows, the speedup approaches $k$, so a $k$-stage pipeline can at best make the machine $k$ times faster — and only in the limit of infinitely many instructions with no hazards.

Efficiency is the fraction of that ideal achieved:

$E=\frac{S}{k}=\frac{n}{k+n-1}$

Throughput is instructions completed per unit time, which in steady state is one per clock cycle.

These formulas assume the unpipelined machine has the same clock period, which is a simplification. In reality, splitting into stages allows a shorter clock period, and that is where most of the real gain comes from. Exam questions usually state which assumption applies, and it must be read rather than assumed.

3. Structural Hazards

A structural hazard occurs when two instructions in different stages need the same hardware resource in the same cycle.

The classic case is a single memory port. In a five-stage pipeline, one instruction is fetching while another is accessing memory, and a unified memory serving both cannot satisfy them simultaneously.

The standard fix is duplication: separate instruction and data caches remove this conflict entirely, which is one of the main reasons the split cache design exists.

A second common case is a register file with too few ports. Decode reads two registers while writeback writes one, so the register file needs two read ports and one write port to avoid stalling.

Where duplication is too expensive — a single divider unit, for instance — the hazard is resolved by stalling, and the cost appears directly in the cycles-per-instruction figure.

4. Data Hazards

A data hazard arises when an instruction depends on a value that an earlier, still-executing instruction has not yet made available.

Three dependence patterns exist, named by the order of the accesses.

In an in-order pipeline, only RAW causes a real hazard. WAR and WAW require an instruction to complete out of order relative to an earlier one, which an in-order pipeline never does. They become genuine hazards only in out-of-order machines, where register renaming eliminates them.

Consider ADD R1, R2, R3 followed immediately by SUB R4, R1, R5. The subtract reads R1 during its decode stage, while the add writes R1 in its writeback stage, three cycles later. Without intervention the subtract reads a stale value.

Forwarding, also called bypassing, solves most RAW hazards without stalling. The result is available at the output of the execute stage long before it reaches the register file, so a bypass path routes it directly to the next instruction's execute input.

The one case forwarding cannot fix is the load-use hazard. A load produces its value at the end of the memory stage, but the following instruction needs it at the start of its execute stage — which is the same cycle. There is no way to send a value backwards in time, so one stall cycle is unavoidable.

That single cycle is why compilers schedule an independent instruction into the slot after a load whenever one is available.

5. Control Hazards

A control hazard arises because the machine fetches the next instruction before knowing whether a branch will be taken.

The penalty is the number of cycles between fetching an instruction and resolving the branch. If the branch outcome and target are known at the end of the execute stage in a five-stage pipeline, two instructions have already been fetched incorrectly and must be discarded.

Four mitigations appear, and they are cumulative rather than alternative.

Stalling simply freezes fetch until the branch resolves, paying the full penalty on every branch. It is correct and slow.

Early resolution moves the branch comparison and target computation into the decode stage, reducing the penalty from two cycles to one. The cost is extra comparison hardware in decode and a tighter timing path.

Delayed branching redefines the instruction set so that the instructions immediately after a branch always execute, whatever the outcome. The compiler fills those delay slots with useful work if it can, and with no-operations if it cannot.

Branch prediction guesses the outcome and fetches accordingly, paying the penalty only when wrong.

Static prediction uses a fixed rule: always not-taken is simplest, while backward-taken-forward-not-taken exploits the fact that loop branches jump backwards and are usually taken.

Dynamic prediction keeps history in a branch prediction buffer indexed by the branch address. A one-bit predictor remembers the last outcome and mispredicts twice per loop — once on the final iteration and once on the first iteration of the next execution.

A two-bit predictor fixes that by requiring two consecutive mispredictions before changing its guess, so a loop that is taken many times and not taken once mispredicts only on the exit.

A branch target buffer caches the target address alongside the prediction, so a predicted-taken branch can redirect fetch without waiting for the target to be computed.

6. Computing the Cost of Stalls

Every stall adds cycles, and the effect on average cycles per instruction is additive.

$CPI=1+\text{stalls per instruction}$

For branches specifically, the contribution is the branch frequency times the misprediction rate times the penalty.

A pipeline with a 20 per cent branch frequency, a 10 per cent misprediction rate and a 3-cycle penalty adds $0.2\times 0.1\times 3=0.06$ to the CPI, raising it from 1.00 to 1.06.

The same structure applies to load-use stalls: frequency of loads, times fraction followed immediately by a dependent instruction, times one cycle.

Deeper pipelines raise the branch penalty, which is why very deep pipelines require correspondingly better prediction. The clock period falls, but the misprediction cost in cycles rises, and beyond some depth the two cancel.

7. Beyond the Basic Pipeline

Two extensions appear in questions.

A superscalar processor issues more than one instruction per cycle, using duplicated functional units. Its ideal CPI falls below 1, and the reciprocal measure — instructions per cycle — becomes the natural one.

An out-of-order processor executes instructions as their operands become available, rather than in program order, and commits results in order so that exceptions remain precise.

Out-of-order execution is what makes WAR and WAW hazards real, and register renaming is what removes them: giving each write a fresh physical register means two writes to the same architectural register never collide.

A VLIW processor takes the opposite approach to superscalar issue. It packs several independent operations into one wide instruction word at compile time, so the hardware performs no dependence checking at all.

The trade is where the scheduling intelligence lives. Superscalar hardware discovers parallelism at run time and adapts to unpredictable latencies such as cache misses; VLIW pushes that work onto the compiler and keeps the hardware simple, at the cost of code that is tied to one pipeline configuration.

8. Worked Examples

Example 1. A 5-stage pipeline with a 2 ns clock executes 100 instructions with no hazards. How long does it take, and what is the speedup over a non-pipelined machine taking 5 cycles per instruction at the same clock?

Total cycles for the pipeline are $k+n-1=5+100-1=104$.

$T_{total}=104\times 2=208\text{ ns}$

The non-pipelined machine takes $100\times 5=500$ cycles, which is 1000 ns.

The speedup is $1000/208\approx 4.81$.

Check against the formula: $S=nk/(k+n-1)=500/104\approx 4.81$. They agree.

Note that the speedup is below the theoretical maximum of 5 because of the 4-cycle fill time. With 10,000 instructions the speedup would be $50000/10004\approx 5.00$, essentially the ideal.

Example 2. In a 5-stage pipeline, a LOAD R1, 0(R2) is immediately followed by ADD R3, R1, R4. How many stall cycles are needed with full forwarding, and what if the two instructions were separated by one independent instruction?

The load produces its value at the end of the memory stage, which is cycle 4 of its own execution.

The add needs that value at the start of its execute stage. If the add issues one cycle behind the load, its execute stage is cycle 3 relative to the load's cycle 1 — that is, cycle 3 overall while the value appears at the end of cycle 4.

The value is needed before it exists, and no forwarding path can send a value backwards in time.

One stall cycle is required. After the stall, the add's execute stage aligns with the end of the load's memory stage, and a forwarding path from memory output to execute input supplies the value.

If one independent instruction sits between them, the add's execute stage moves one cycle later and the forwarding path suffices with no stall at all.

This is exactly why compilers schedule an independent instruction into the load delay slot, and why the instruction immediately after a load is the most valuable scheduling opportunity in a simple pipeline.

Example 3. A processor has 20 per cent branches with a 4-cycle misprediction penalty. Compare the CPI under always-not-taken static prediction with a 60 per cent accuracy against a two-bit dynamic predictor with 92 per cent accuracy.

Under static prediction, the misprediction rate is $1-0.6=0.4$.

Added CPI $=0.20\times 0.40\times 4=0.32$, so the CPI is $1+0.32=1.32$.

Under dynamic prediction, the misprediction rate is $1-0.92=0.08$.

Added CPI $=0.20\times 0.08\times 4=0.064$, so the CPI is $1.064$.

The speedup from better prediction is $1.32/1.064\approx 1.24$, about 24 per cent.

The arithmetic shows why prediction accuracy matters more as pipelines deepen. With a 10-cycle penalty instead of 4, the static case would give a CPI of 1.80 while the dynamic case gives 1.16, and the gap widens to 55 per cent.

Example 4. Why does a one-bit branch predictor mispredict twice for a loop executed repeatedly, and how does a two-bit predictor fix it?

Consider a loop whose branch is taken nine times and not taken once, repeated many times.

A one-bit predictor stores the last outcome. During the nine taken iterations it predicts taken and is right. On the tenth iteration the branch is not taken, so it mispredicts and flips its stored bit to not-taken.

When the loop is entered again, the first iteration is taken, but the predictor still says not-taken from last time, so it mispredicts a second time and flips back.

Two mispredictions per execution of the loop, one at the exit and one at the re-entry.

A two-bit predictor uses a saturating counter with four states, and it changes its prediction only after two consecutive mispredictions.

At the loop exit it mispredicts once and moves from strongly-taken to weakly-taken, but its prediction is still taken. On re-entry the branch is taken, which is correct, and the counter returns to strongly-taken.

One misprediction per loop execution instead of two, which halves the branch penalty for the single commonest branch pattern in real code.

Example 5. A 4-stage pipeline has stage delays of 6, 8, 5 and 7 ns, with a 1 ns pipeline register overhead. Find the clock period, the throughput, and the effect of splitting the 8 ns stage into two 4 ns stages.

The clock period is set by the slowest stage plus the register overhead.

$T_{clock}=8+1=9\text{ ns}$

Throughput in steady state is one instruction per clock, which is $1/9$ ns, or approximately 111 million instructions per second.

Now split the 8 ns stage into two 4 ns stages, giving a 5-stage pipeline with delays 6, 4, 4, 5, 7.

The new slowest stage is the 7 ns one, so the clock period becomes $7+1=8$ ns.

Throughput rises to $1/8$ ns, about 125 million instructions per second — a 12.5 per cent gain.

Note that the gain is limited by the new bottleneck at 7 ns, not by how finely the 8 ns stage was split. Splitting it further would achieve nothing until the 7 ns stage is also split, which is the general lesson that balancing matters more than depth.

The added stage also raises the branch penalty by one cycle, which the throughput gain must outweigh.

Example 6. Why are WAR and WAW hazards absent from a simple in-order pipeline?

A WAR hazard means a later instruction writes a register before an earlier instruction has read it. A WAW hazard means two instructions write the same register in the wrong order.

Both require an instruction to reach its write stage before an earlier instruction reaches an earlier stage — that is, they require reordering.

In a simple in-order pipeline, instructions enter in program order, pass through stages in lockstep, and reach any given stage in the same order. The earlier instruction always reads before the later one writes, and always writes before the later one writes.

So neither hazard can occur, and only RAW — where a later instruction genuinely needs a value the earlier one has not yet produced — remains.

The picture changes in an out-of-order machine, where instructions execute as their operands become ready. There a later instruction can write a register before an earlier one reads it, and both anti- and output dependences become real.

Register renaming removes them. Giving every write a fresh physical register means two writes never target the same location, and a read always refers to the specific physical register its producer wrote. Only the true RAW dependence survives, which is exactly the dependence that carries actual information.

Summary

A pipeline does not speed up any instruction; it raises throughput by overlapping stages so that one instruction completes per cycle in steady state.

The clock period is the slowest stage plus register overhead, so balancing stages matters more than shortening one.

For $n$ instructions on $k$ stages, total cycles are $k+n-1$, speedup is $nk/(k+n-1)$ approaching $k$, and efficiency is $n/(k+n-1)$.

Structural hazards come from shared hardware and are fixed by duplication — split caches and multi-ported register files — or by stalling when duplication is too expensive.

Only RAW hazards occur in an in-order pipeline. Forwarding removes most of them by routing a result from a stage output directly to the next instruction's input.

The load-use hazard cannot be forwarded away and costs exactly one stall cycle, which is why the slot after a load is the most valuable scheduling opportunity.

Control hazards cost the number of cycles until the branch resolves. Early resolution, delayed branching and prediction reduce that, and a two-bit predictor mispredicts once per loop where a one-bit predictor mispredicts twice.

Stall cost adds to CPI as frequency times rate times penalty, and deeper pipelines raise the penalty, which is why depth and prediction quality must advance together.

Superscalar issue pushes CPI below 1; out-of-order execution makes WAR and WAW real, and register renaming removes them again.