Pipelining

Computer Science· Unit 4: Processor Fundamentals· 15 min read

1. Pipeline Fundamentals★★☆☆☆⏱ 4 min

📘 Definition

Instruction Pipelining

A performance technique where multiple instructions are overlapped during execution, dividing the instruction cycle into independent stages that operate in parallel.

Example:

A 5-stage pipeline completes one instruction per clock cycle after an initial fill latency.

The standard RISC pipeline splits the instruction cycle into 5 common sequential stages, each completing in one clock cycle:

IF (Instruction Fetch): Retrieve instruction from main memory to CPU registers
ID (Instruction Decode): Decode opcode and read source operands from the register file
EX (Execute): Perform ALU operation or calculate memory address
MEM (Memory Access): Access data memory for load/store instructions
WB (Write Back): Write instruction result back to the register file

📐 Worked Example

Draw the timing diagram for 3 instructions executing on a 5-stage pipeline, showing which stage each instruction occupies per clock cycle.

1
The pipeline fills sequentially: one new instruction enters the first stage each cycle.
2
After filling, each stage processes a different instruction simultaneously. The final timing is:
3
$\begin{array}{c|ccc} \text{Cycle} & I_1 & I_2 & I_3 \\ \hline 1 & IF & - & - \\ 2 & ID & IF & - \\ 3 & EX & ID & IF \\ 4 & MEM & EX & ID \\ 5 & WB & MEM & EX \\ 6 & - & WB & MEM \\ 7 & - & - & WB \\ \end{array}$
4
3 instructions take 7 cycles with pipelining, compared to 15 cycles for non-pipelined execution, giving an early 2x speedup.

2. Ideal Pipelining Speedup Calculation★★☆☆☆⏱ 3 min

📘 Definition

Ideal Pipelining Speedup

The maximum possible performance gain from pipelining, calculated assuming no hazards, stalls, or overhead. Approaches the number of pipeline stages for large numbers of instructions.

For an $n$ -stage pipeline executing $k$ instructions: Total non-pipelined cycles = $n \times k$ (each instruction takes $n$ full cycles) Total pipelined cycles = $n + (k - 1)$ (initial fill, then 1 cycle per instruction) Speedup = $\frac{Non-pipelined cycles}{Pipelined cycles}$

📐 Worked Example

Calculate the speedup of a 4-stage pipeline executing 100 instructions, ignoring all hazards.

1
Identify input values: number of stages $n = 4$ , number of instructions $k = 100$
2
Calculate non-pipelined total cycles:
3
$n \times k = 4 \times 100 = 400$
4
Calculate pipelined total cycles:
5
$n + (k - 1) = 4 + 99 = 103$
6
Calculate speedup:
7
$\text{Speedup} = \frac{400}{103} \approx 3.88$
8
This is very close to the ideal speedup of 4, as expected for a large number of instructions.

3. Types of Pipeline Hazard★★★☆☆⏱ 4 min

📘 Definition

Pipeline Hazard

A conflict that prevents the next scheduled instruction from executing in its allocated cycle, causing one or more pipeline stalls that reduce overall throughput.

There are three core categories of pipeline hazard tested in CIE 9618:

Structural hazard: Resource conflict: two instructions need the same hardware component at the same time.
Data hazard: Dependency conflict: an instruction needs the result of a previous uncompleted instruction.
Control hazard: Flow conflict: a branch or jump changes the program counter, so pre-fetched instructions are invalid.

📐 Worked Example

Identify the type of hazard in this instruction sequence: ADD R1, R2, R3 then SUB R4, R1, R5

1
The SUB instruction needs the value of R1, which is written back by ADD in the 5th (WB) pipeline stage.
2
When SUB reaches the 3rd (EX) stage, ADD has not yet written R1 to the register file, so SUB cannot get the correct operand.
3
This conflict arises from a data dependency between the two instructions, so it is a data hazard.

✓ Quick check

Test your understanding: What type of hazard occurs when the outcome of a conditional branch is not known before the next instruction is fetched?

- Structural hazard
- Data hazard
- Control hazard
- No hazard
Reveal answer
2 —
Correct: Control hazards arise from changes to instruction flow caused by branches and jumps.

4. Resolving Pipeline Hazards★★★☆☆⏱ 4 min

Different hazards are resolved with different hardware and software techniques, summarised in the table below:

Hazard Type	Common Resolution Techniques
Structural	Separate instruction and data caches, duplicate hardware resources
Data	Operand forwarding, compiler instruction reordering, out-of-order execution
Control	Branch prediction, delayed branching, pre-fetch branch target instructions

📐 Worked Example

Explain how operand forwarding resolves the data hazard in the earlier ADD/SUB example.

1
The result of the ADD instruction is available immediately after it completes the EX (execute) stage, before it is written back to the register file in WB.
2
Operand forwarding adds connections that pass the result directly from the output of the EX/MEM pipeline register to the input of the next EX stage.
3
The SUB instruction gets the correct value of R1 directly from ADD's completed result, no pipeline stall is needed, and throughput is preserved.

5. Common Pitfalls

Wrong move:

Claiming pipelining reduces the latency of a single instruction

Why:

Pipelining improves total throughput (instructions per second) not individual instruction latency. Each instruction still takes the same number of cycles to complete.

Correct move:

State that pipelining increases overall instruction throughput, allowing more instructions to complete per unit time.

Wrong move:

Inverting the speedup formula, or using the wrong equation for total cycles

Why:

Many candidates incorrectly calculate speedup as $k / n$ instead of the correct ratio of non-pipelined to pipelined cycles.

Correct move:

Use the formula: $Speedup = \frac{n \times k}{n + ( k - 1 )}$ where $n$ = number of stages, $k$ = number of instructions.

Wrong move:

Confusing structural hazards with data hazards

Why:

Structural hazards come from conflicts over shared hardware, not dependencies between instruction results.

Correct move:

Classify conflicts from hardware resource constraints as structural, and conflicts from instruction dependencies as data.

Wrong move:

Claiming ideal speedup is always achieved in real processors

Why:

Almost all programs have some combination of hazards that cause pipeline stalls, so real speedup is always lower than the ideal maximum.

Correct move:

State that ideal speedup is the theoretical maximum, while actual speedup is lower due to pipeline stalls from hazards.

6. Quick Reference Cheatsheet

Concept	Key Fact
5-stage pipeline order	IF → ID → EX → MEM → WB
Ideal speedup (large k)	Equal to number of pipeline stages $n$
Total cycles (n stages, k instructions)	$n + (k - 1)$
Structural hazard cause	Shared hardware resource conflict
Data hazard cause	Instruction depends on uncompleted result
Control hazard cause	Branch/jump changes instruction flow
Data hazard resolution	Operand forwarding
Control hazard resolution	Branch prediction, delayed branching

7. Frequently Asked

Does pipelining reduce the latency of a single instruction?

No. Pipelining improves throughput (total number of instructions completed per second), but each individual instruction still takes the same number of clock cycles to complete as it would in a non-pipelined processor. Latency per instruction does not decrease.

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2022 · 42
Speedup calculation and hazard identification
2021 · 41
Explanation of pipelining performance benefits
2023 · 43
Describe methods to resolve pipeline hazards

What's Next

Pipelining is a core concept in modern processor design, and forms the foundation for more advanced performance optimisation techniques you will learn for CIE 9618. Pipelining questions appear frequently in Paper 4, ranging from 2-mark calculation questions to 6-mark explanation questions, so you should practice drawing timing diagrams and memorising hazard types and resolution methods. Mastering pipelining will also help you understand how modern high-performance CPUs achieve higher throughput than older non-pipelined designs. Explore the related topics below to build your knowledge of processor fundamentals for the exam.