# Pipelining

> Computer Science · CIE A-Level 9618
> Source: https://www.owlsprep.com/study/cie-9618-u4-pipelining/

Pipelining is a core CPU performance optimisation that overlaps instruction execution. This guide covers pipeline structure, speedup calculation, hazard types, and resolution techniques for CIE A-Level 9618.

**Prerequisites:** Understanding of the fetch-decode-execute instruction cycle; Knowledge of CPU performance metrics (CPI, throughput)

## Learning objectives

- Explain how pipelining improves CPU performance
- Calculate ideal pipeline speedup for given inputs
- Identify and classify the three main types of pipeline hazard
- Describe common techniques for resolving pipeline hazards

## Pipeline Fundamentals

**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.

## Ideal Pipelining Speedup Calculation

**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{\text{Non-pipelined cycles}}{\text{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.

> **tip**
>
> For exam questions with large $k$, you can approximate ideal speedup as equal to the number of pipeline stages, since the initial fill latency becomes negligible.

## Types of Pipeline Hazard

**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**.

**Check your understanding**

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

1. 

   - Structural hazard
   - Data hazard
   - Control hazard
   - No hazard

   *Answer:* Control hazard

   *Why:* Correct: Control hazards arise from changes to instruction flow caused by branches and jumps.

## Resolving Pipeline Hazards

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.

## Common pitfalls

- **Wrong:** Claiming pipelining reduces the latency of a single instruction
  - Why it fails: Pipelining improves total throughput (instructions per second) not individual instruction latency. Each instruction still takes the same number of cycles to complete.
  - Correct: State that pipelining increases overall instruction throughput, allowing more instructions to complete per unit time.
- **Wrong:** Inverting the speedup formula, or using the wrong equation for total cycles
  - Why it fails: Many candidates incorrectly calculate speedup as $k/n$ instead of the correct ratio of non-pipelined to pipelined cycles.
  - Correct: Use the formula: $\text{Speedup} = \frac{n \times k}{n + (k - 1)}$ where $n$ = number of stages, $k$ = number of instructions.
- **Wrong:** Confusing structural hazards with data hazards
  - Why it fails: Structural hazards come from conflicts over shared hardware, not dependencies between instruction results.
  - Correct: Classify conflicts from hardware resource constraints as structural, and conflicts from instruction dependencies as data.
- **Wrong:** Claiming ideal speedup is always achieved in real processors
  - Why it fails: Almost all programs have some combination of hazards that cause pipeline stalls, so real speedup is always lower than the ideal maximum.
  - Correct: State that ideal speedup is the theoretical maximum, while actual speedup is lower due to pipeline stalls from hazards.

## 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 |

## 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.

- [Multicore processors](https://www.owlsprep.com/study/cie-9618-u4-multicore-processors/)
- [System software](https://www.owlsprep.com/study/cie-9618-u5-overview/)
- [Operating Systems](https://www.owlsprep.com/study/cie-9618-u5-operating-systems/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u4-pipelining/