Why Pipelining Exists: Latency, Throughput, Hazards, and Out-of-Order Execution

Lesson 1, Part 7.

We've traced fetch → decode → execute as a sequential story.

In Part 3, we established the relationship between clock frequency, latency, and throughput.

Now we pipeline that trace for real, and deal with the mess it creates.

Instructions that depend on each other. Branches that don't reveal the next instruction in time. A CPU that wants to run everything out of order while still pretending it didn't.

Where We Left Off

As established in Part 3, a CPU's clock period is bounded by its slowest stage of combinational work.

Increasing frequency without changing the work per cycle just means doing less work per tick.

Pipelining is the architectural answer to that constraint.

Instead of one long clock period sized for the entire instruction, split the datapath into stages:

Each stage gets its own short clock period, sized only for the slowest stage — not the slowest instruction.

The consequence, also from Part 3, is that pipelining is a throughput trick, not a latency trick.

Any single instruction still takes 5 cycles to cross the whole datapath.

What changes is that a new instruction can enter the pipeline every cycle.

So once the pipeline is full, the CPU retires roughly one instruction per cycle — even though each one individually took five cycles start to finish.

Cycle →     1    2    3    4    5    6    7    8
I1         IF   ID   EX   MEM  WB
I2              IF   ID   EX   MEM  WB
I3                   IF   ID   EX   MEM  WB
I4                        IF   ID   EX   MEM  WB

That diagram is the entire promise of pipelining.

This post is about everything that goes wrong when you try to keep it true.

The Three Hazard Types, at a Glance

The moment multiple instructions sit in different stages of the datapath at once, they can interfere with each other.

Computer architecture groups the interference into three categories.

Hazard type	Cause	Example
Data hazard	An instruction needs a value another in-flight instruction hasn't produced yet	`ADD R3,R1,R2` then `ADD R4,R3,R5`
Control hazard	The next instruction to fetch depends on a branch outcome not yet known	`BEQ` followed by whatever comes next
Structural hazard	Two instructions want the same piece of hardware in the same cycle	Two instructions both needing the one memory port

Each one gets a full treatment below.

Each one drove a different piece of real CPU hardware into existence — forwarding networks, branch predictors, and Harvard-style split memory ports, respectively.

Data hazards get the most space here, because they're also the doorway into out-of-order execution.

Data Hazards: When One Instruction Needs Another's Answer

The RAW Dependency

Consider two back-to-back instructions:

I1: ADD R3, R1, R2
I2: ADD R4, R3, R5

I2 reads R3.

R3 is produced by I1.

This is a read-after-write (RAW) dependency, also called a true dependency — it reflects a genuine data-flow requirement in the program.

I2 cannot compute a correct answer until I1's result exists.

Unlike the hazards we'll meet later, a RAW dependency isn't a pipelining artifact you can design away.

It's baked into the meaning of the program.

What pipelining does is expose when, physically, that dependency becomes a problem.

Watching It Break in the Pipeline

Lay the two instructions on the pipeline timeline:

Cycle →      1    2    3    4    5
I1: ADD R3  IF   ID   EX   MEM  WB
I2: ADD R4       IF   ID   EX   MEM  WB

I2 needs the value of R3 to feed its ALU during its own EX stage — cycle 4.

But I1 doesn't officially deposit R3 into the register file until its WB stage — cycle 5.

If I2's EX stage reads the register file the ordinary way in cycle 4, it reads the stale value of R3 — the one from before I1 ran — and computes garbage.

Two fixes exist for this, and real CPUs use both, in different situations.

Fixing Data Hazards: Stall or Forward

Stalling: The Blunt Instrument

The simplest fix is to freeze the dependent instruction until the value it needs is safely available:

Cycle →      1    2    3    4    5    6    7
I1: ADD R3  IF   ID   EX   MEM  WB
I2: ADD R4       IF   ID   --   --   EX   MEM  WB
                      (stall)  (stall)

This works, but it's expensive.

Every RAW dependency between adjacent instructions costs cycles.

In real code — where nearly every instruction consumes a value produced one or two instructions earlier — that adds up to a pipeline that spends much of its time stalled rather than working.

If stalling were the only mechanism, the throughput promise of pipelining would collapse under realistic dependency density.

Forwarding: Give the Result a Shortcut

The better fix notices something: I1 actually computes R3's value at the end of its EX stage, in cycle 3.

That's a full two cycles before it's architecturally written back.

The value exists. It's just sitting in a pipeline latch — the EX/MEM register — instead of the register file.

Forwarding (also called bypassing) wires that latch directly to the ALU input of whatever instruction is in EX next cycle, skipping the register file entirely.

Two forwarding paths do the work.

EX→EX forwarding (formally, EX/MEM → EX): the ALU result sitting in the EX/MEM latch — produced one cycle ago — feeds straight back into the ALU input for an instruction currently in EX.

This covers the case where the dependent instruction immediately follows the producer.

MEM→EX forwarding (formally, MEM/WB → EX): if there's one independent instruction between producer and consumer, the result has moved one stage further down the pipeline by the time it's needed.

So it's forwarded from the MEM/WB latch instead.

Re-running the earlier example with forwarding:

No bubble needed.

This is the mechanism referenced back in the pipeline hazard diagram earlier in the series — the mux feeding the ALU isn't decoration.

It's the entire reason back-to-back dependent arithmetic doesn't tank pipeline throughput.

In practice, a hazard detection unit compares source-register numbers of the instruction entering EX against destination-register numbers of instructions further along the pipeline, and steers the forwarding muxes accordingly, cycle by cycle — in hardware, not software.

Forwarding lets a result skip the register file and go straight from the stage that produced it to the stage that needs it, closing most RAW hazards without stalling — but it can only forward a value that already exists.

That last clause is the whole story of the next section.

The Hazard Forwarding Can't Fix: Load-Use

Why the Load Is Late

Forwarding assumes the producing instruction has computed its result by the time the consumer needs it — just hasn't written it back yet.

That assumption holds for ALU instructions, whose result exists at the end of EX.

It does not hold for loads.

I1: LOAD R1, [A]
I2: ADD  R2, R1, R3

A LOAD doesn't have its value at the end of EX — EX for a load just computes the memory address.

The actual data doesn't arrive until the MEM stage completes — one full stage later than an ALU result.

Lay it out:

Cycle →       1    2    3    4    5    6
I1: LOAD R1  IF   ID   EX   MEM  WB
I2: ADD R2        IF   ID   EX   MEM  WB
                             ▲
                        needs R1 *now*,
                        but I1 doesn't have it
                        until MEM finishes (also cycle 4)

I2's EX stage falls in cycle 4 — the exact same cycle I1 is still inside MEM, fetching the value from the data cache.

There is no forwarding path in the universe that can send a value backward in time to before it exists.

EX→EX forwarding can't help — the value isn't in the EX/MEM latch; a load's EX stage never produced it.

MEM→EX forwarding can't help yet either, because I1 hasn't finished MEM.

The Mandatory Bubble

The only fix is to delay I2 by exactly one cycle.

That lines up its EX stage with the cycle after I1's MEM completes — at which point the loaded value sits in the MEM/WB latch and ordinary MEM→EX forwarding delivers it:

This is the load-use hazard.

It is the one and only data hazard in a classic in-order pipeline that requires a stall cycle even with a fully populated forwarding network.

A hazard detection unit checks, specifically: is the instruction ahead of me in EX a load, and does its destination register match one of my source registers?

If so, it holds the dependent instruction — and everything behind it — for one cycle, and injects a bubble.

Compilers know about this.

A decent instruction scheduler tries to place an independent instruction between a load and its first use, so the one-cycle penalty is hidden behind useful work instead of a bubble — the same trick a juggler uses by keeping one more ball in the air than seems necessary.

Control Hazards: The Cost of Not Knowing What's Next

Why Branches Are Different

Data hazards are about values arriving late.

Control hazards are about not even knowing which instruction to fetch next.

A conditional branch's outcome — taken or not-taken, and its target address — typically isn't known until it has been decoded and, often, evaluated in EX.

But the pipeline has to fetch something every cycle, starting the very next cycle after the branch.

The naive options are: stall fetch entirely until the branch resolves (safe, slow), or guess and fetch speculatively (fast, sometimes wrong).

Every real CPU does the second, with a branch predictor, and pays a penalty whenever the guess is wrong.

Quantifying the Flush: N−1 Wasted Cycles

Say a branch's outcome is known at pipeline stage R, counting from 1.

Every cycle between fetching the branch and stage R resolving, the pipeline was forced to fetch something down a guessed path.

If the guess was wrong, everything fetched during those cycles has to be discarded — flushed, or squashed — and refetched from the correct address.

misprediction penalty ≈ R − 1   wasted cycles

where R is the stage, out of N total pipeline stages, at which the branch resolves.

In the worst case — a design where branch outcomes aren't known until very late in a deep pipeline — this approaches N − 1.

Almost the entire pipeline's worth of work, thrown away.

Worked Example: Shallow vs Deep Pipelines

Classic 5-stage in-order pipeline (IF ID EX MEM WB), branch resolved in ID — stage 2, assuming the datapath includes an early comparator so simple equality/inequality branches don't need the full ALU:

Cycle →        1    2    3    4    5
Branch        IF   ID   EX   MEM  WB
wrong-path 1        IF   X          ← 1 instruction fetched down
                                       wrong path, flushed

R = 2, so penalty = 2 − 1 = 1 wasted cycle — just one bubble.

Same 5-stage shape, but branch resolved in EX — stage 3 — instead, a common case when the branch condition genuinely needs the ALU:

Cycle →        1    2    3    4    5    6
Branch        IF   ID   EX   MEM  WB
wrong-path 1        IF   ID   X          ← 2 instructions fetched down
wrong-path 2             IF   X            wrong path, both flushed

R = 3, penalty = 3 − 1 = 2 wasted cycles.

Now scale this up.

Deeply pipelined designs built for very high clock frequency — the canonical example is the Pentium 4's 20-to-31-stage pipeline — push branch resolution much further downstream, to keep each stage's combinational logic tiny.

Misprediction penalties in that class of design are commonly cited in the range of roughly 15 to 20-plus cycles.

Every one of those cycles executed real instructions that turned out to be on the wrong path, and had to be thrown away.

This is precisely why branch prediction accuracy became one of the highest-leverage investments in CPU design once pipelines got deep.

A processor that mispredicts 10% of branches with a 20-cycle penalty is paying a steep, constant throughput tax that no amount of extra ALU width can buy back.

Branch prediction itself — the algorithms that make that guess accurate in the first place — is a big enough topic to deserve its own lesson later in this series.

For now, the important fact is just this cost function: penalty grows with how late in the pipeline the branch resolves, a direct, unavoidable consequence of pipeline depth.

A branch misprediction doesn't slow the pipeline down — it makes the pipeline do real work that turns out to be entirely wasted. The deeper the pipeline, the more cycles of wasted work a single wrong guess buys.

Structural Hazards: Running Out of Hardware

The third hazard type is the most mechanical.

Two instructions, correctly scheduled with no data or control conflict between them, can still collide because they both want the same physical resource in the same cycle:

I_A: LOAD R1, [X]      →  wants the data memory port
I_B: LOAD R2, [Y]      →  also wants the data memory port, same cycle

If the datapath has only one memory port, one of these has to wait.

A structural hazard resolves either by stalling the later instruction, or by building more hardware — a second memory port, a second ALU, a second load/store unit — until the collision stops happening in practice.

This is a large part of why modern CPUs are described by their execution port count.

An eight-wide execution engine is, among other things, a structural-hazard-avoidance strategy: enough independent hardware that instructions rarely have to queue for a shared resource.

Beyond In-Order: Why the CPU Wants to Reorder Itself

Everything above assumes instructions execute in the order the program specifies — a strictly in-order pipeline.

But program order is not the same thing as data-flow order.

A CPU that insists on the former is leaving performance on the table.

The Motivating Example

I1: LOAD R1, [A]
I2: ADD  R2, R3, R4
I3: MUL  R5, R6, R7
I4: ADD  R8, R1, R9

I4 depends on I1's load result.

I2 and I3 depend on nothing I1 produces — they're entirely independent, both of each other and of the load.

An in-order pipeline, upon hitting a stall for I1's load (memory can take many cycles on a cache miss), simply parks.

I2 and I3 sit behind it in program order, unable to issue, even though every operand they need is already sitting in the register file.

In-order:            I1 stalls on memory → I2, I3, I4 all wait behind it
 
Out-of-order:         I1 → waiting for memory
                       I2 → executes now (independent)
                       I3 → executes now (independent)
                       I4 → waits, correctly, for I1

An out-of-order (OoO) CPU looks past the stalled instruction, finds work it can do, and does it.

That's instruction-level parallelism (ILP) — parallelism program order was hiding.

This is one of the central performance ideas in every high-end CPU built since the mid-1990s.

Tomasulo's original algorithm, which underlies this whole approach, actually dates to 1967 — developed for the IBM System/360 Model 91's floating-point unit (see Further Reading).

But reordering execution creates two new categories of hazard that an in-order pipeline never has to think about.

The Hazards Out-of-Order Execution Invents: WAR and WAW

In-order pipelines only ever worry about RAW hazards, because in-order execution guarantees two useful properties for free.

Every instruction reads its operands before any later instruction has had a chance to write them.

And every instruction writes its result before any later instruction writes to the same destination.

Break the "in-order" assumption, and both of those free guarantees disappear.

Anti-Dependence (WAR)

Write-after-read (WAR), or anti-dependence: a later instruction writes a register that an earlier instruction still needs to read.

I1: ADD R3, R4, R5      ; reads R4
I2: SUB R4, R6, R7      ; writes R4

In program order, I1 must read the old value of R4 before I2 overwrites it.

In a strictly in-order pipeline this is automatic — I1 enters the pipeline first and reads R4 in its ID stage cycles before I2 even decodes.

There's nothing to protect, because the read physically cannot happen after the write.

But suppose I1's other operand, R5, isn't ready yet — waiting on some long-latency instruction upstream — while I2's operands (R6, R7) are ready immediately.

An out-of-order scheduler, hunting for ready work, might issue and execute I2 before I1.

If I2 writes its result to R4 first, and I1 then reads R4 expecting the value from before I2 ran, it gets the wrong value.

I1 needed to read R4 "before" I2 wrote it, in program order — but nothing enforced that once execution order stopped matching program order.

Output Dependence (WAW)

Write-after-write (WAW), or output dependence: two instructions write the same destination, and the final value in that register has to reflect whichever one is later in program order.

I1: MUL R2, R3, R4      ; writes R2 (long latency)
I2: ADD R2, R5, R6      ; also writes R2 (short latency)

Architecturally, R2 must end up holding I2's result — it's the later write.

In an in-order pipeline, I1 always reaches WB before I2 does, so this is automatic.

But MUL is typically a multi-cycle operation, while ADD is single-cycle.

If both are dispatched to functional units and allowed to complete whenever they finish, I2 (fast) may finish and write R2 first, and I1 (slow) may finish later and clobber it.

That leaves R2 holding the multiply's result instead of the add's — architecturally wrong.

Why In-Order Pipelines Never See Them

Both WAR and WAW hazards are false dependencies — not data-flow dependencies in the sense RAW is.

No actual value flows from I2 to I1 in the WAR example, or from I1 to I2 in the WAW example.

The dependency exists purely because both instructions happen to reuse the same architectural register name, combined with the fact that execution order no longer matches program order.

Rename the register, and the dependency evaporates — which is exactly the fix real hardware uses.

RAW hazards are real — they reflect actual data flow and can never be eliminated, only hidden with forwarding. WAR and WAW hazards are artifacts of reusing a small, fixed set of architectural register names combined with out-of-order execution — and they can be eliminated outright.

Register Renaming: Deleting the False Dependencies

The fix follows directly from the diagnosis.

If WAR and WAW hazards exist only because two unrelated instructions happen to share a register name, give them different names.

A CPU has a small number of architectural registers — the ones the ISA exposes, say 32 general-purpose registers — but implements a much larger pool of physical registers internally.

A rename table maps each architectural register to whichever physical register currently holds its live value.

Every instruction that writes a register gets allocated a fresh, previously-unused physical register for that write.

The rename table is updated so later instructions that read that architectural register find the new physical register.

Re-running the WAR example through a renamer:

Before renaming:                    After renaming:
 
I1: ADD R3, R4, R5                  I1: ADD p10, p4, p5
I2: SUB R4, R6, R7                  I2: SUB p11, p6, p7

I1 now reads p4 — a physical register I2 never touches.

I2 writes to a completely different physical register, p11.

There is no longer any register in common between the two instructions.

I2 can execute before, after, or simultaneously with I1 — the result is identical either way, because the false dependency was never a real one.

The rename table keeps track that, architecturally, R4's current live value is p11 (from I2) for anything that reads R4 after this point.

Meanwhile I1 still correctly reads p4, the physical register holding R4's old value at the point I1 was renamed.

The same trick kills the WAW example.

I1's MUL writes some physical register p20.

I2's ADD writes a different physical register p21.

The rename table simply records that, after I2, the architectural R2 maps to p21.

Whichever instruction physically finishes first, no value gets clobbered — they were never sharing a location to begin with.

The rename table, not completion order, decides which physical register is the "real" one for later readers.

WAR and WAW are sometimes grouped under the term name dependencies, precisely because renaming — giving things new names — is a complete, general solution to both.

RAW hazards, by contrast, are true dependencies and must actually be waited on, or forwarded around. They can never simply be renamed away.

The Machinery: Reservation Stations, the Reorder Buffer, and Commit

Renaming solves false dependencies.

But the CPU still needs machinery to figure out, cycle by cycle, which renamed instructions have all their real operands ready and can execute.

And it needs machinery to make the whole out-of-order mess look, from the outside, exactly like sequential execution.

Three structures do this work.

Together they form the modern descendant of Tomasulo's 1967 algorithm.

Reservation Stations / the Scheduler

After decode and rename, each instruction is dispatched into a reservation station — older terminology — or, in more modern designs, a unified scheduler: a buffer sitting in front of the execution units.

Each entry holds the operation to perform and, for each operand, either the actual value (if it's already known) or a tag identifying which in-flight instruction will eventually produce it.

Execution units broadcast their results on a shared bus — historically the common data bus, or CDB — tagged with the identity of the instruction that produced them.

Every reservation station entry watches that bus.

When a broadcast tag matches a tag it's waiting on, it latches the value in place of the tag.

The moment an entry has all its operands as real values — regardless of which instructions in program order are still waiting on something else — it becomes eligible to issue to a free functional unit.

This is the mechanism, concretely, by which "readiness" rather than "program order" determines execution order.

The Reorder Buffer

Executing out of order is only useful if the CPU can still guarantee, to the outside world, that results become visible in program order.

Otherwise exceptions, interrupts, and even simple sequential program semantics would be undefined.

The reorder buffer (ROB) is a FIFO queue, allocated in strict program order at dispatch time, that tracks every in-flight instruction from dispatch until it's safe to make its result permanent.

When an instruction finishes execution, its result is written into its ROB entry and marked complete.

But it is not yet written to the architectural register file, and it is not yet visible to anything outside the core.

It sits there, speculative — possibly completed wildly out of order relative to older instructions still waiting on a cache miss or a long multiply.

Retirement: Restoring the Illusion of Order

Retirement, also called commit, walks the ROB strictly from its head, in program order, one or a few entries per cycle.

An entry can retire only once it's marked complete and every entry ahead of it has already retired.

Retiring an entry is the moment its result becomes architecturally real — written to the actual register file, made visible to the rest of the machine, made irrevocable.

This single mechanism is what lets a CPU execute wildly out of order internally while looking, from any external observer's point of view — including the programmer's — exactly as if it executed one instruction at a time, in order:

a = 10;
b = 20;
c = a + b;

Internally, the additions, loads, and renames backing these three statements might complete in almost any order, on almost any cycle, across several functional units simultaneously.

But the ROB guarantees they retire in the order a = 10, then b = 20, then c = a + b — the only order the architectural state is ever allowed to reflect.

It's also what makes precise exceptions possible.

If c = a + b somehow faulted, the CPU can point to exactly the architectural state as of the instruction just before it in program order — because nothing later than that has been allowed to retire yet, no matter how far ahead it may have already executed.

Reservation stations decide execution order by data readiness. The reorder buffer decides commit order by program order. Out-of-order execution is real inside the core and invisible outside it — by design.

Putting It All Together: A Modern Superscalar OoO Pipeline

Every mechanism from this post slots into one picture:

Fetch and the branch predictor deal with control hazards.

The forwarding network wired around the execution units deals with RAW data hazards — and, as we saw, sometimes can't, hence the load-use stall.

Rename deals with WAR and WAW.

The scheduler is what actually reorders execution to extract ILP.

The reorder buffer plus commit stage is what stitches all of that speculation back into a single, sequential, architecturally correct story.

It's the same story the fetch-decode-execute trace told at the start of this series — just executed by hardware that no longer respects that story internally, while still being required to honor it externally.