Pipelined Execution; Four-Stage Pipeline; Pipeline Formulas

Pipelined Execution

Pipelining overlaps execution of multiple instructions in different stages — like an assembly line.

Multiple instructions in flight simultaneously.
Throughput increases; latency of one instruction may stay similar.
Known as pipeline processing.

19.1 Throughput Intuition

Non-pipeline: 5 instructions × 4 stages = 20 cycles. Pipeline: first instruction still 4 cycles to complete, but subsequent instructions start every cycle after fill — total 8 cycles for 5 instructions (see below).

Four-Stage Pipeline

Classic four-stage pipeline :

Stage	Abbrev	Action
Instruction Fetch	IF	Get opcode from memory
Instruction Decode	ID	Decode opcode, read registers
Instruction Execute	IE	ALU operation, effective address
Write Back	WB	Store result to register/memory

Some texts add a fifth stage (Memory access) between IE and WB; exams typically use four stages (IF, ID, EX, WB) unless stated otherwise.

20.1 Space-Time Diagram (5 instructions, 4 stages)

Cycle: 1 2 3 4 5 6 7 8
Inst 1: IF ID IE WB
Inst 2: IF ID IE WB
Inst 3: IF ID IE WB
Inst 4: IF ID IE WB
Inst 5: IF ID IE WB

Pipeline Formulas

21.1 Pipelined Cycle Count

[ \boxed{\text{Cycles} = K + (N - 1)} ]

K = number of pipeline stages
N = number of instructions

Derivation sketch: First instruction needs K cycles; each additional instruction adds 1 cycle (one stage per cycle steady state).

21.2 Worked Example

Given: N = 5 instructions, K = 4 stages (IF, ID, IE, WB).

[ \text{Cycles} = K + (N-1) = 4 + (5-1) = 4 + 4 = 8 ]

21.3 Non-Pipeline Comparison

Same problem:

[ \text{Cycles} = K \times N = 4 \times 5 = 20 ]

Speedup (ideal, no hazards):

[ \frac{KN}{K+N-1} = \frac{20}{8} = 2.5 ]

21.4 Another Example (N=8, K=5)

Pipelined:

[ 5 + (8-1) = 5 + 7 = 12 \text{ cycles} ]

Non-pipelined:

[ 5 \times 8 = 40 \text{ cycles} ]

21.5 Hazards (Exam enrichment)

Real pipelines stall on:

Structural hazard: two instructions need same hardware
Data hazard: operand not ready (needs forwarding)
Control hazard: branch misprediction flushes pipe

The formula assumes ideal pipeline (no stalls).

Pipeline Timing and Hazards

A pipeline divides instruction work into stages separated by registers. After filling, different instructions occupy different stages at the same time. A four-stage example may contain fetch, decode, execute and write-back. The clock period must accommodate the slowest stage plus pipeline-register overhead.

For k stages and n instructions, an ideal pipeline needs k + n - 1 cycles. A non-pipelined design taking one cycle per stage needs kn comparable stage cycles. Ideal speedup approaches k for large n, but imbalance, register overhead and stalls reduce it.

A structural hazard occurs when simultaneous stages require one resource. A data hazard occurs when an instruction needs a value that an earlier instruction has not made available. Forwarding supplies results directly where possible while a stall inserts waiting cycles. A control hazard follows a branch because the next program counter is uncertain. Prediction or delayed resolution reduces the lost cycles.