Pipelining
Introduced
Vocabulary
| English | Meaning |
|---|---|
| pipelining/ˈpaɪplaɪnɪŋ/ | Overlapping different stages of several instructions to improve throughput. |
| retires | Commits an instruction's result to the processor state after successful execution. |
| CPI | Cycles per instruction: processor cycles divided by the number of executed instructions. |
| forwarding | Sending a result directly to a dependent pipeline stage before normal register write-back. |
| read-after-write hazard | A dependency in which an instruction needs a value an earlier instruction has not yet made available. |
The assembly line
- Pipelining overlaps instructions in five stages — IF, ID, EX, MEM, WB — like an assembly line: instruction $i+1$ fetches while $i$ decodes. Once full, one instruction retires per cycle.
- $n$ instructions, $k$ stages take $n + k - 1$ cycles: five instructions in five stages take $5 + 5 - 1 = 9$ cycles, not $25$; at $n = 100$: $104$ cycles.
{exercise:uni-cs0603-formula}
Practice
Ten instructions on a five-stage pipeline take —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
n + k − 1 = 10 + 5 − 1 = 14: fill four, then one per cycle.
Stage time and CPI
- The stage time is the slowest stage: with IF 250, ID 150, EX 200, MEM 250, WB 100 ps, every stage costs 250 ps — 250 ps per instruction against the single cycle's 900 ps.
- Ideal CPI is 1; stalls raise it. A 1000-instruction program, 25% loads, half load-use (one stall each): $1000 + 125 + 4 = 1129$ cycles, CPI $1.129$.
{exercise:uni-cs0603-cpi}
Practice
1000 instructions, 25% loads, half load-use: total cycles —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
1000 + 125 stalls + 4 fill = 1129, CPI 1.129.
Hazards and forwarding
- A read-after-write hazard:
add R1, R2, R3thensub R4, R1, R1— the sub reads R1 in ID one cycle before add writes it in WB. - Forwarding routes the ALU output straight back to the next ALU's inputs, hiding the wait — except when the producer is a load:
lw R1, …; add R3, R1, R2still stalls one cycle (data exists only after MEM). A taken branch, resolved in EX, costs one bubble too.
{exercise:uni-cs0603-hazard}
Practice
Forwarding hides ALU-to-ALU waits, but load-use still costs —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Load data exists only after MEM, so the dependent instruction waits one bubble.