Pipelining

Pipelining is a technique used in processor design to increase instruction throughput by overlapping the execution stages of multiple instructions. For the OCR H446 exam, you must understand how pipelining works, its advantages, the types of hazards that can occur, and how branch prediction addresses control hazards.

---

How Pipelining Works

In a non-pipelined processor, each instruction must complete all stages (Fetch, Decode, Execute) before the next instruction begins. This leaves parts of the CPU idle during each stage.

Without pipelining (sequential execution):

Time:       1   2   3   4   5   6   7   8   9
Instr 1:    F   D   E
Instr 2:                F   D   E
Instr 3:                            F   D   E

Three instructions take 9 clock cycles.

With pipelining:

Time:       1   2   3   4   5
Instr 1:    F   D   E
Instr 2:        F   D   E
Instr 3:            F   D   E

Three instructions take only 5 clock cycles. After the pipeline is full, one instruction completes every clock cycle.

The Principle

Pipelining divides the processor into separate stages, each handled by dedicated hardware. While one instruction is being executed, the next is being decoded, and a third is being fetched — all at the same time.

General Formula

For a k-stage pipeline processing n instructions (assuming no hazards):

• Total cycles = k + (n - 1)
• Without pipelining: k x n cycles

For example, a 3-stage pipeline processing 100 instructions:

• Pipelined: 3 + 99 = 102 cycles
• Non-pipelined: 3 x 100 = 300 cycles
• Speedup: 300 / 102 = approximately 2.94x

---

Deeper Pipelines

Modern processors use more than 3 stages. A typical pipeline might have 5 stages:

Stage	Abbreviation	Action
Fetch	IF	Retrieve instruction from memory
Decode	ID	Decode instruction and read registers
Execute	EX	ALU performs the operation
Memory Access	MEM	Read from or write to memory (if needed)
Write Back	WB	Write the result back to a register

Time:       1    2    3    4    5    6    7    8    9
Instr 1:    IF   ID   EX   MEM  WB
Instr 2:         IF   ID   EX   MEM  WB
Instr 3:              IF   ID   EX   MEM  WB
Instr 4:                   IF   ID   EX   MEM  WB
Instr 5:                        IF   ID   EX   MEM  WB

After the first 5 cycles to fill the pipeline, one instruction completes every cycle.

Advantages of Deeper Pipelines

• Higher throughput — more instructions are in flight at any given time.
• Higher clock speeds — each stage does less work, so each stage can complete faster, allowing a higher clock frequency.

Disadvantages of Deeper Pipelines

• Greater penalty for hazards — when the pipeline must be flushed (e.g. branch misprediction), more partially-completed instructions are wasted.
• More complex hardware — more pipeline registers (latches) are needed between stages.
• Diminishing returns — at some point the overhead of pipeline registers and hazard handling outweighs the benefits.

---

Pipeline Hazards

A hazard is a situation that prevents the next instruction from executing in its designated clock cycle, causing the pipeline to stall (insert a "bubble" — an empty cycle).

1. Data Hazards

A data hazard occurs when an instruction depends on the result of a previous instruction that has not yet completed.

Example:

ADD R1, R2, R3    ; R1 = R2 + R3
SUB R4, R1, R5    ; R4 = R1 - R5   <-- needs R1, but ADD has not written it yet

The SUB instruction needs the value of R1, but R1 has not been updated by ADD yet because ADD is still in its MEM or WB stage.

Solutions:

Technique	How It Works
Stalling (bubbling)	Insert NOP (no operation) cycles until the required data is available. Simple but reduces performance
Forwarding (bypassing)	The result is sent directly from the ALU output of the producing instruction to the input of the consuming instruction, without waiting for it to be written back to the register file
Compiler reordering	The compiler rearranges instructions so that independent instructions fill the gap between dependent ones

2. Control Hazards

A control hazard (also called a branch hazard) occurs when the processor encounters a branch instruction and does not know which instruction to fetch next until the branch condition has been evaluated.

Example: