Pipelining improves instruction throughput by allowing different instructions to occupy different portions of a datapath at the same time. It does not make one instruction’s combinational work disappear. Instead, registers divide a long path into stages and establish a repeating schedule. The architectural machine still appears to execute instructions in program order, while the implementation overlaps their internal phases.
The distinction between latency and throughput is fundamental. Latency is the time from an instruction entering the pipeline to its result becoming available or retiring. Throughput is the long-run completion rate after the pipeline is filled. A five-stage pipeline may have five-cycle instruction latency but complete one independent instruction per cycle. A pipeline that accepts one instruction per cycle but stalls frequently has a lower effective throughput than its ideal diagram suggests.
A pipeline as a timed refinement
Suppose an unpipelined datapath performs fetch, decode/register read, execute, memory, and write-back in one cycle. Insert pipeline registers between these phases. The registers carry both data and control: an instruction’s destination register, ALU operation, memory direction, and write-back choice must travel with the values they govern. A common five-stage model is IF, ID, EX, MEM, and WB.
At cycle instruction may be in EX while is in ID and is in IF. The hardware is not executing three complete instructions independently; it is executing three slices of three different instruction transitions. Correctness requires that each slice’s data and controls remain aligned. A classic bug is to pipeline the operand value but not its destination register, causing a result to be written into the wrong architectural register several cycles later.
Worked timeline. For independent instructions
| Cycle | IF | ID | EX | MEM | WB |
|---|---|---|---|---|---|
| 1 | – | – | – | – | |
| 2 | – | – | – | ||
| 3 | – | – | |||
| 4 | – | ||||
| 5 | |||||
| 6 | – |
The first result appears at cycle 5, but the fifth result appears at cycle 9. After filling, completion is one per cycle. For instructions and stages, ideal cycles are not
Pipeline invariant
What does pipelining change first: instruction semantics or the schedule of work?
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Clock period and stage balance
Each pipeline stage has a combinational delay and a register overhead including clock-to-Q, setup, skew, and margin. The clock period must exceed the maximum stage delay:
Splitting a path into more stages helps only if the new maximum decreases enough to justify added register overhead, bypass complexity, power, and branch-recovery cost. Perfectly equal stages are rarely possible because instruction fetch, memory access, and decode have different structures. A stage with 700 ps and four stages with 300 ps determines the clock; splitting a 300 ps stage further does nothing until the 700 ps bottleneck changes.
Worked speedup. An unpipelined path takes 10 ns. A four-stage partition has combinational delays 2.5 ns each and 0.1 ns register overhead, so its clock is 2.6 ns. For one instruction, unpipelined latency is 10 ns while pipelined latency is approximately ns: the pipeline is slightly worse because of register overhead. For 100 independent instructions, the unpipelined time is 1000 ns; the pipeline takes ns, a speedup of about 3.73 rather than the ideal 4. This example explains why pipeline depth is a throughput decision, not a promise of lower single-instruction latency.
A stage boundary can expose a hazard
A pipeline splits instruction memory and data memory logically but maps both to one single-ported physical memory. Fetch and load reach it in the same cycle.
What must the pipeline do to remain correct?
Pipeline registers and control propagation
A pipeline register is a typed bundle. In IF/ID, it may hold the fetched instruction and PC. ID/EX holds operands, immediate, destination identifiers, and decoded controls. EX/MEM holds ALU result, store data, destination, and memory controls. MEM/WB holds loaded data or ALU result, destination, and register-write control. Every field must have a defined value when the associated instruction is valid.
| Pipeline Register | Stage Input -> Output | Propagated Control Fields | Datapath & Identification Fields | Validity & Hazard Invariant |
|---|---|---|---|---|
IF/ID | Fetch Decode | None (not yet decoded) | Instr[31:0], PC, PC_next | Synchronous flush clears valid to 0 on branch misprediction |
ID/EX | Decode Execute | ALUOp[1:0], ALUSrc, Branch, MemRead, MemWrite, RegWrite, ResultSrc | rs1_data, rs2_data, ImmExt, rs1, rs2, rd, PC | Stall freezes contents; bubble injects zeroed write controls |
EX/MEM | Execute Memory | MemRead, MemWrite, RegWrite, ResultSrc | ALU_result, WriteData, rd, BranchTarget, Zero | Preserves rd of executing instruction for forwarding comparison |
MEM/WB | Memory Writeback | RegWrite, ResultSrc | ReadData, ALU_result, rd | Delivers rd and RegWrite to register file write port |
Validity is itself state. A bubble is an invalid pipeline entry that performs no architectural side effect. Reset typically fills the pipeline with invalid entries; a flush converts younger entries to bubbles. Treating a bubble as an instruction with arbitrary opcode is unsafe if control decode can assert writes. A valid bit must gate register writes, memory writes, exceptions, and retirement.
Control signals can be decoded early and pipelined, or regenerated from a pipelined instruction field later. Early decode may reduce repeated logic but increases bundle width; late decode may simplify the bundle but extend a stage’s critical path. The invariant is that the controls used in a stage describe the instruction whose data is in that stage, not the instruction currently being fetched.
Data hazards
A data hazard arises when overlapping instructions have a dependence. A read-after-write (RAW) hazard is a true dependence: must read a value produced by Write-after-read (WAR) and write-after-write (WAW) hazards are name dependences that appear in machines allowing reads, writes, or retirement out of program order. A simple in-order five-stage pipeline primarily faces RAW hazards.
Consider:
add r1, r2, r3
sub r4, r1, r5
The add produces r1 at the end of EX or later, while the sub needs it at the beginning of its EX stage. If the register file is read in ID, the sub may read the old value. Forwarding or bypassing sends the produced value from a later pipeline register directly to the consuming ALU input, avoiding a register-file round trip. The forwarding unit compares source identifiers against destination identifiers of older instructions whose results are available.
Forwarding does not eliminate every stall. For:
lw r1, 0(r2)
add r3, r1, r4
the load’s data becomes available only after MEM, but the dependent add needs it in EX in the immediately following cycle. A one-cycle bubble lets the load reach its data-producing point before forwarding to the add. The hazard detector must freeze the PC and IF/ID register, insert a bubble into ID/EX, and then allow progress. Freezing everything would deadlock; advancing everything would compute with stale data.
Worked trace: load-use hazard schedule. With a load-use pair, cycle 3 has lw in EX and add in ID. The detector sees ID/EX.MemRead=1 and ID/EX.rd equal to the add’s source. In cycle 4, keep the add in ID, keep the PC and fetched instruction stable, and place a no-op control bundle in EX. In cycle 5, the load is in WB or its value is available for forwarding, while the add enters EX. The bubble costs one cycle and preserves architectural semantics.
Structural hazards
A structural hazard occurs when two stages need a resource simultaneously. A single-ported unified memory cannot fetch the next instruction while a load or store accesses data in the MEM stage. Solutions include separate instruction and data caches, multiported memory, scheduling that inserts a stall, or a pipeline organization that separates requests in time. Hardware duplication increases area and power but can increase throughput.
Structural hazards are not data hazards and should not be hidden under a generic “stall.” The cause determines the proof: a data stall waits for a value; a structural stall waits for ownership of a resource. A valid/ready protocol makes the resource conflict explicit and prevents the controller from assuming a response that was never accepted.
Control hazards and speculation
A conditional branch creates a control hazard because the next PC depends on a comparison that may not be resolved until EX. Meanwhile, the fetch stage has already fetched sequential instructions. The simplest policy stalls until the branch resolves or predicts not taken and flushes wrong-path instructions when taken. If the branch resolves after stages and there are younger wrong-path instructions, the recovery cost includes those invalidated cycles and any front-end refill.
| Cycle | IF | ID | EX | MEM | WB | Architectural Action |
|---|---|---|---|---|---|---|
| 1 | beq r1, r2, target | — | — | — | — | Fetch branch; predict not taken |
| 2 | sub r4, r5, r6 (wrong path) | beq | — | — | — | Fetch fall-through instruction |
| 3 | and r7, r8, r9 (wrong path) | sub | beq (resolves TAKEN) | — | — | Condition evaluates true; target computed |
| 4 | target: add r10, r11, r12 | bubble (valid=0) | bubble (valid=0) | beq | — | Pipeline flush: clear IF/ID and ID/EX; redirect PC to target |
| 5 | target+4: lw r13, 0(r10) | target: add | bubble (valid=0) | bubble (valid=0) | beq | Resume fetch along correct path; flush penalty = 2 cycles |
The flush must be precise. A wrong-path instruction may have computed a value internally, but it must not write a register, memory, status register, or device. Valid bits and side-effect gating enforce this. A branch target calculation and condition comparison can be moved earlier to reduce penalty, but doing so increases the earlier stage’s critical path and may introduce new forwarding requirements.
Branch prediction guesses direction and sometimes target. A static predictor uses a fixed rule; a dynamic predictor records history. Prediction accuracy, branch frequency, and misprediction penalty determine benefit. If branches occur with frequency prediction accuracy is and penalty is cycles, the average branch cost is approximately cycles per instruction, ignoring secondary effects. Increasing predictor complexity is worthwhile only when its area, power, and access latency do not erase the gain.
Exceptions in a pipeline
An exception may be detected in one stage while younger instructions have advanced. Precise exception handling requires all older instructions to retire, the faulting instruction to be represented at the specified boundary, and all younger instructions to become bubbles. A page fault on a load must not allow a younger store to modify memory before the handler observes the faulting state.
| Pipeline Stage | Potential Exception | Detection Cycle | Commitment Order | Required Pipeline Control Action |
|---|---|---|---|---|
IF | Instruction page fault / Misaligned fetch | Cycle | Younger | Record status in IF/ID.ExcCode; suppress trap until WB |
ID | Illegal instruction / Reserved opcode | Cycle | Middle | Record status in ID/EX.ExcCode; suppress subsequent decoding |
EX | Integer overflow / Arithmetic trap | Cycle | Middle | Record status in EX/MEM.ExcCode; block register destination write |
MEM | Data access page fault / Misaligned load | Cycle | Older | Overrides younger exceptions; triggers trap handler at WB stage |
WB | Commit boundary | Cycle | Earliest | If ExcCode != 0, annul younger stages, write sepc/scause, redirect PC |
Pipeline control therefore has three distinct actions: stall, which holds an instruction in place; bubble, which inserts invalid work into a stage; and flush, which discards younger work. Confusing them produces subtle bugs. On a load-use hazard, older stages continue, the dependent instruction is held, and one bubble is inserted. On a taken branch, younger instructions are flushed and a target fetch begins. On an exception, the precise recovery boundary is determined by the ISA and retirement design.
Performance model
For a pipeline with clock period ideal time for instructions is Add stall cycles and flush/recovery cycles
The effective CPI for large is approximately plus any base issue limitation. A deeper pipeline can reduce while increasing branch penalty, latch overhead, and hazard complexity. A useful comparison must include both terms.
Worked comparison. Design A has ns, 10 stages, and 0.08 branch-mispredictions per instruction with penalty 8 cycles. Design B has ns, 5 stages, and the same branch frequency with penalty 3 cycles. Ignoring other stalls, A has CPI and time per instruction 1.64 ns. B has CPI and time 1.612 ns. The deeper clock is not automatically better; workload-dependent control penalties nearly erase its frequency advantage.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 2.4.1: Pipeline Latency and Throughput Formula
Schedule five independent instructions in a five-stage pipeline and derive the formula.
HintExpandCollapse
Trace how each instruction progresses stage-by-stage from IF to WB to derive total cycles for N instructions.
Worked solutionExpandCollapse
Instruction enters IF in cycle reaches WB in cycle and the last of instructions therefore completes in cycle In general, the first instruction occupies all stages and each additional instruction adds one cycle, giving
Exercise 2.4.2: ALU vs Load Forwarding Path Comparison
For an add followed by a dependent add, identify the forwarding path and the cycle in which the value is available. Repeat for a load followed by a dependent add.
HintExpandCollapse
Compare when ALU results are available in EX/MEM versus load results returning after MEM stage.
Worked solutionExpandCollapse
An ALU result can usually forward from EX/MEM to the next instruction’s EX input. A load result is not available until after MEM, so an immediately dependent instruction needs one bubble in a basic five-stage design and then receives the value from MEM/WB.
Exercise 2.4.3: Stall Control Logic for Load-Use Hazards
Design the stall control signals for a load-use hazard. State exactly which registers hold, which receive a bubble, and which instruction proceeds.
HintExpandCollapse
Specify which pipeline registers must hold state and which must be cleared to insert a bubble.
Worked solutionExpandCollapse
Hold PC and IF/ID, force ID/EX controls to a no-op, and allow the load in EX to advance. On the next cycle release the hold. Holding ID/EX as well would repeat the load; advancing ID without a bubble would use stale data.
Exercise 2.4.4: Structural Conflicts in Unified Memory
A unified single-ported memory serves IF and MEM. Give a trace containing a load and explain the structural stall. Propose two hardware alternatives.
HintExpandCollapse
Trace cycle collisions when instruction fetch and data memory accesses contend for a single memory port.
Worked solutionExpandCollapse
When a load occupies MEM, IF cannot access the same port in that cycle, so fetch stalls and a bubble may appear in the front end. Separate instruction/data memories or a multiported/cache-banked design remove the conflict at hardware cost.
Exercise 2.4.5: Average CPI Calculation with Branch and Load Stalls
Calculate average CPI for branch frequency 20%, accuracy 92%, and penalty 5 cycles, then add a one-cycle load-use stall for 10% of instructions.
HintExpandCollapse
Weight branch penalties and load-use delays by their instruction mix frequencies to find effective CPI.
Worked solutionExpandCollapse
Branch penalty is CPI. Load-use stalls add 0.10 CPI, so the estimate is 1.18 CPI. The terms assume independent frequencies and no interaction; real traces may correlate hazards.
Exercise 2.4.6: Flushed Store Cancellation Invariants
Explain why a flushed store must be prevented from reaching a memory write even if its address and data were already computed.
HintExpandCollapse
Ensure instructions squashed due to branch mispredictions or traps never assert memory write enables.
Worked solutionExpandCollapse
Computed internal values are not architectural effects. If the store writes after the branch is found taken or an exception is detected, a wrong-path or younger instruction changes memory and violates precise execution. The valid bit must gate the memory-write enable.
Exercise 2.4.7: Deep vs Shallow Pipeline Performance Comparison
Compare a 20-stage and 5-stage design under a workload with branch frequency 15%, misprediction accuracy 90%, and respective penalties 12 and 3 cycles. Include clock periods of 0.7 ns and 1.2 ns.
HintExpandCollapse
Evaluate whether higher clock frequency in a 20-stage pipeline outweighs larger misprediction penalties.
Worked solutionExpandCollapse
The 20-stage design has branch cost CPI 1.18, and 0.826 ns per instruction. The 5-stage design has cost 0.045, CPI 1.045, and 1.254 ns per instruction. Under these assumptions the deeper design wins despite its larger misprediction penalty, but the margin is workload-sensitive.