Part IIThe Core
CPU Foundations, ISA, Pipeline, and Hazards
July 31, 2026·38 min read·advanced
Strip away everything you have heard about processors and what remains is a loop. Read a number from memory. Decide what it means. Do it. Move on.
01.Part 1, the contract and the implementation
1.1 What a processor is actually doing
Strip away everything you have heard about processors and what remains is a loop. Read a number from memory. Decide what it means. Do it. Move on.
Make that concrete. Here is a real 32-bit number an Apple chip will execute, split at the boundaries the hardware uses.
The hardware reads bits 31 down to 21, recognizes the pattern meaning "add two 64-bit registers," pulls three register numbers out of three fixed 5-bit fields, and computes . Nothing was parsed. Wires from those bit positions run straight into the register file address inputs. The number is the command.
The rules saying which numbers mean which commands are the instruction set architecture, the ISA. It fixes the visible registers, the encodings, the addressing modes, how exceptions behave, and what a multiprocessor guarantees about memory ordering. Notice what the encoding does not say. Nothing about gate count, cycle count, caches, or execution order, and that silence is the most important structural fact in processor design.
1.2 Architecture versus implementation
The contract is the architecture. Any pile of transistors honoring it is a microarchitecture.
Two machines both execute that instruction correctly. A tiny embedded core fetches in one cycle, decodes and reads registers in a second, adds and writes back in a third, using a ripple-carry adder that eats most of the cycle. A large phone core fetches eight instructions at once, renames the registers, parks the add in a scheduling queue, executes it out of order on one of six integer pipes with a Kogge-Stone adder from Arithmetic Hardware, and retires it 40 cycles after fetch. Both produce , and they differ by roughly a hundred times in performance.
Most of these roles have "microarchitect" in the title, so be precise about the word. A useful test is this. If changing something changes which answers programs produce, it is architecture. If it only changes how fast the same answers arrive, it is microarchitecture.
The test leaks, and knowing where is worth more than the test. The memory consistency model in Virtual Memory and Memory Ordering feels like an implementation detail and is firmly architecture, because it decides which results a multithreaded program may legally observe. Going the other way, Spectre showed that speculative timing leaks architecturally invisible state into something software can measure. The boundary is a design choice, not a law.
1.3 RISC and CISC, and what survived
Feel the difference through an example. Here is one x86-64 instruction.
add dword ptr [rbx + rcx*4 + 8], eax
```text
It computes an address from a base plus a scaled index plus a constant, loads 32 bits, adds a register, stores the result back, and updates the flags. Five operations in 3 to 7 bytes. AArch64 needs four instructions, each exactly 4 bytes.
```text
add x9, x3, x4, lsl #2 ; address
ldr w10, [x9, #8] ; load
add w10, w10, w0 ; add
str w10, [x9, #8] ; store
```text
That is the whole distinction. **CISC** lets one instruction do complex multi-step work including memory operands, with variable length. **RISC** keeps instructions fixed-length and simple, register-to-register, with memory touched only by explicit loads and stores.
The trade lives in the performance equation of 3.1. RISC executes **more instructions**, hurting the instruction-count term, but each is simpler, helping cycles per instruction and helping cycle time because the control logic is less tangled. The arithmetic alone never settled it. What settled it is that the distinction **stopped being visible at the back end**, because a modern x86 core decodes that complex instruction into three or four internal **micro-operations** resembling the AArch64 sequence and executes those. The deep pipeline of an x86 machine is a RISC machine wearing a CISC front end.
### 1.4 The one difference that did not go away
One asymmetry is permanent and lives in the front end. **With fixed-length instructions you know where every instruction starts without decoding any of them.**
The front end fetches a 32-byte block and wants eight instructions this cycle. In AArch64 they start at byte offsets 0, 4, 8, 12, 16, 20, 24, 28, known before a single bit is examined, so eight decoders wire to eight fixed slices and run in parallel with no communication.
In x86-64 an instruction is 1 to 15 bytes. To know where instruction 2 begins you must know the length of instruction 1, which requires partly decoding it. Finding eight boundaries is a **serial chain of eight steps** sitting in front of the real decode work. That is the ripple-carry structure of [Digital Logic and Timing](/learn/hardware-interview-prep/digital-logic-and-timing) in different clothes, with the same $O(N)$ shape. The brute-force fix assumes an instruction might start at **every** byte, so a 32-byte window needs 32 speculative length decoders plus a selection network. The industrial fix is to not do it twice, caching decoded micro-operations in a **micro-op cache**. Public disclosures put modern x86 cores at 4 to 6 instructions per cycle through legacy decode, while independent microbenchmarking measured the M1 performance core at 8-wide decode with no uop cache at all.
Carry that into an interview, and say the counterweight too. Fixed-length encoding costs **code density**, since a 4-byte instruction needing 2 bytes of information still occupies 4 bytes of I-cache and fetch bandwidth. Thumb-2 existed to claw that back, and AArch64 deliberately dropped it to buy decode simplicity.
### 1.5 Microcode, which is your day job
Some architectural instructions are complicated, rare, and awkward. Dedicated hardware for each would cost area and put slow twisty control logic on paths that ought to be fast, to accelerate something that runs once in ten million instructions.
**Microcode** is the alternative. Rather than a hardwired state machine, the machine stores a **program** whose instructions are the internal micro-operations of the core. When the decoder meets the complex instruction it hands control to a sequencer that reads that program from an on-chip ROM and feeds the micro-operations into the pipeline. The architectural instruction becomes software running on the microarchitecture, invisible to the ISA.
Read that next to 1.3. **Microcode is the CISC-to-RISC translation, made explicit and made programmable.** Simple frequent instructions go through fast hardwired decoders and rare ones fall through to microcode, with the line between them revisited every generation. Microcode is usually **patchable** after the chip ships, which is why vendors fix certain functional and security bugs with firmware rather than a recall, and it is where **architectural corner cases** get handled, which makes the microcode engineer the owner of the exact semantics of the messiest parts of the ISA.
You are a CPU Microcode Engineer. Present that as a microarchitecture credential rather than apologizing for it. The bridge sentence is that microcode sits exactly on the boundary between the contract and the implementation, so the job is a daily exercise in 1.2. Keep the public-data guardrail in mind, talking about what microcode **is** and never about the internals of any specific core.
---
## Part 2, why pipelining exists
### 2.1 The unpipelined machine
Break execution into five physical steps. **Fetch** sends the program counter to the instruction cache. **Decode** pulls register numbers from fixed fields and reads the register file. **Execute** runs the operands through the ALU. **Memory** touches the data cache if this is a load or store. **Writeback** writes the result into the destination register.
Say each step takes 2 ns. The obvious machine does all five in one long cycle, so $T = 10$ ns, the frequency is 100 MHz, and one instruction finishes every 10 ns. Now count what the hardware does. During the first 2 ns the instruction cache works and everything else idles. During the third 2 ns the ALU works and everything else idles. At every instant **four of five blocks do nothing**. You paid for all five and are using 20 percent.
### 2.2 Overlap
Nothing forces the fetch unit to idle while the ALU works. Put a bank of flip-flops at each stage boundary holding the partly-processed instruction and everything computed so far, handing it forward on the clock edge.
<Figure src="/figures/hardware-interview-prep/iv-06-CPU-Foundations-Pipeline-and-Hazards-fig02.svg" alt="A bank of flops at every stage boundary hands the partly-processed instruction forward on each clock edge, so all five stages work at once and the clock period is set by the slowest single stage rather than the whole chain." caption="A bank of flops at every stage boundary hands the partly-processed instruction forward on each clock edge, so all five stages work at once and the clock period is set by the slowest single stage rather than the whole chain." id="fig:06-CPU-Foundations-Pipeline-and-Hazards-2" />
That is the alternating flop-logic-flop structure from section 4.3 of [Digital Logic and Timing](/learn/hardware-interview-prep/digital-logic-and-timing). Nothing new was invented. The clock period is now set by the **slowest single stage** rather than the whole chain, so $T = 2$ ns and the frequency goes from 100 MHz to 500 MHz.
### 2.3 The cycle-by-cycle table
| Instruction | c1 | c2 | c3 | c4 | c5 | c6 | c7 | c8 | c9 | c10 | c11 | c12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| I1 | IF | ID | EX | ME | WB | | | | | | | |
| I2 | | IF | ID | EX | ME | WB | | | | | | |
| I3 | | | IF | ID | EX | ME | WB | | | | | |
| I4 | | | | IF | ID | EX | ME | WB | | | | |
| I5 | | | | | IF | ID | EX | ME | WB | | | |
| I6 | | | | | | IF | ID | EX | ME | WB | | |
| I7 | | | | | | | IF | ID | EX | ME | WB | |
| I8 | | | | | | | | IF | ID | EX | ME | WB |
Read **across a row** and you see the life of one instruction, five cycles from fetch to writeback, always. Read **down a column** and you see the machine at one instant, and at cycle 5 five instructions are inside it, each in a different stage, with nothing idle. The four-cycle **fill** at the top left and its mirror **drain** at the bottom right bracket a **steady state** where exactly one instruction completes per cycle. Eight instructions take $8 + 4 = 12$ cycles rather than 40.
### 2.4 Latency and throughput are different numbers
Here is the counterintuitive result, stated bluntly because the intuitive answer is wrong. **Pipelining did not make any single instruction faster. It made it slightly slower.**
Unpipelined, one instruction took 10 ns. Pipelined, it takes 5 cycles of 2 ns, also 10 ns, and that is before the pipeline registers. From section 5.3 of [Digital Logic and Timing](/learn/hardware-interview-prep/digital-logic-and-timing) a flop costs $t_{cq}$ leaving and $t_{su}$ arriving, say 0.1 ns each, so $T = 2.0 + 0.1 + 0.1 = 2.2$ ns.
| Metric | Unpipelined | Pipelined | Change |
|---|---|---|---|
| Clock period | 10 ns | 2.2 ns | 4.5x faster clock |
| Latency of one instruction | 10 ns | 11 ns | 10 percent **worse** |
| Instructions completed per second | 100 M | 455 M | 4.5x better |
| Blocks busy at any instant | 1 of 5 | 5 of 5 | full utilization |
**Latency** is how long one item takes to get through. **Throughput** is how many finish per unit time. Pipelining trades a little latency for a lot of throughput, and that trade reappears in the multiplier of [Arithmetic Hardware](/learn/hardware-interview-prep/arithmetic-hardware), the cache pipelines of [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching), and the fabric of [Interconnect and AMBA](/learn/hardware-interview-prep/interconnect-and-amba).
The 4.5x assumed equal stages, and real stages are not. Suppose the true delays are 1.5, 2.0, 2.5, 1.8, and 1.2 ns, totalling 9.0 ns, so unpipelined runs at 111 MHz. Pipelined, the period is set by the **worst** stage, $T = 2.5 + 0.2 = 2.7$ ns, giving 370 MHz and a speedup of 3.33x rather than 5x. The loss is pure **imbalance**, and that 1.2 ns writeback stage wastes 1.3 ns every cycle forever. Real pipeline design is largely shoving work across stage boundaries to level them out.
### 2.5 What pipelining costs
**Area and power**, since every stage boundary is a few hundred flops holding the instruction, its operands, its partial results, and its control bits, toggling every cycle whether or not the instruction in them is useful. That is the target of [Power Fundamentals and Clock Gating](/learn/hardware-interview-prep/power-fundamentals-and-clock-gating). **Hazards**, since the table in 2.3 assumed independence and Part 4 is about what happens when that fails. **Debuggability**, since one instruction becomes five, or several hundred in [Out of Order Execution](/learn/hardware-interview-prep/out-of-order-execution), which makes [DFT and Silicon Debug](/learn/hardware-interview-prep/dft-and-silicon-debug) much harder. And **bigger penalties**, since deeper means more work thrown away on a misprediction, which is the term in 6.3 that eventually kills you.
---
## Part 3, measuring performance honestly
### 3.1 The performance equation
There is one equation for how long a program takes, and it is an identity rather than a model, which is why it is trustworthy.
$$\text{Time} = \frac{\text{Instructions}}{\text{Program}} \times \frac{\text{Cycles}}{\text{Instruction}} \times \frac{\text{Time}}{\text{Cycle}}$$
The units cancel and what remains is time per program. One billion instructions, 1.5 cycles each, 3 GHz so 0.333 ns per cycle, gives $10^9 \times 1.5 \times 0.333 \times 10^{-9} = 0.5$ seconds.
| Term | Owned by | Moved by |
|---|---|---|
| Instructions per program | ISA designer and compiler | code generation, richer instructions, vectorization |
| Cycles per instruction | microarchitect | caches, prediction, wider issue, out-of-order execution |
| Time per cycle | circuit and physical design | critical path work, process node, pipeline depth |
The value of the equation is that it forces you to check whether improving one term damaged another by more. Vectorizing a loop with the SIMD units of [Execution Units](/learn/hardware-interview-prep/execution-units) cuts instruction count by 4x, and if it raises CPI by 5x because the vector unit has longer latency and the loop is dependent, you made things worse.
### 3.2 CPI, IPC, and where the cycles actually go
**CPI** is cycles per instruction and **IPC** its reciprocal. Slow machines are discussed in CPI and fast machines in IPC because the numbers read better. A perfect five-stage pipeline has $\text{CPI} = 1$, and nobody achieves the ideal. Build a budget for a simple in-order machine with 25 percent loads and 20 percent branches.
| Source | Frequency | Penalty | CPI contribution |
|---|---|---|---|
| Ideal pipeline | every instruction | 1 cycle | 1.000 |
| Load-use stall | 25 percent loads, 40 percent used immediately | 1 cycle | 0.100 |
| Branch misprediction | 20 percent branches, 5 percent wrong | 15 cycles | 0.150 |
| L1 data miss served by L2 | 25 percent loads, 3 percent miss | 12 cycles | 0.090 |
| L2 miss served by DRAM | 25 percent loads, 3 percent, 25 percent of those | 200 cycles | 0.375 |
| **Total** | | | **1.715** |
$\text{IPC} = 1/1.715 = 0.583$, so **42 percent of the performance is gone**, and the largest line is DRAM, from an event happening on well under one percent of instructions. That table justifies the entire memory hierarchy and is the honest reason out-of-order execution exists, because an out-of-order machine does not add these stalls up. It overlaps them, finding independent work during the 200-cycle wait.
### 3.3 The deepening trap
If five stages beat one, why not fifty? Because the terms fight. Let the total logic be 10 ns split over $n$ stages with 0.3 ns per-stage overhead from setup, clock-to-Q, skew, and jitter margin, so $T = 10/n + 0.3$. Let aggregate hazard cost grow with depth as $\text{CPI} = 1 + 0.05n$, since a deeper machine flushes more on a misprediction and separates producer from consumer further.
| Stages $n$ | Period $10/n + 0.3$ | CPI $1 + 0.05n$ | Time per instruction |
|---|---|---|---|
| 5 | 2.30 ns | 1.25 | 2.88 ns |
| 10 | 1.30 ns | 1.50 | 1.95 ns |
| 15 | 0.97 ns | 1.75 | 1.69 ns |
| 20 | 0.80 ns | 2.00 | 1.60 ns |
| 25 | 0.70 ns | 2.25 | **1.58 ns** |
| 30 | 0.63 ns | 2.50 | **1.58 ns** |
| 40 | 0.55 ns | 3.00 | 1.65 ns |
| 60 | 0.47 ns | 4.00 | 1.87 ns |
The curve has a minimum and turns back up. Deeper is better right until it is not. The coefficients are illustrative rather than measured, published studies put the pure-performance optimum in the high teens, and the bottom of the curve is **broad and flat**, so performance alone does not pick a depth.
Power picks it. Dynamic power scales with frequency and with the square of voltage per [Power Fundamentals and Clock Gating](/learn/hardware-interview-prep/power-fundamentals-and-clock-gating), and pushing frequency requires pushing voltage, so the last few hundred megahertz are brutally expensive. Optimize energy-delay instead of delay and the optimum moves far shallower. That is why real cores sit near 15 stages and why the 31-stage Pentium 4 Prescott is the cautionary tale in [Pipeline Optimization Beyond 5 Stages](/learn/computer-architecture/deeper-pipelines). It was not wrong about frequency, it was wrong about what frequency costs. For Apple this matters doubly, since performance per watt on a battery pushes the answer shallower and wider.
### 3.4 Amdahl's law
If a fraction $f$ of the work is sped up by $s$ and the rest is untouched, $\text{speedup} = 1 / ((1-f) + f/s)$.
Take the memorable case first. Make $f = 0.2$ **infinitely fast**, so $s \to \infty$, and the speedup is $1/0.8 = 1.25$. You deleted a fifth of the program entirely and gained 25 percent.
| $f$ | $s = 2$ | $s = 10$ | $s = \infty$ |
|---|---|---|---|
| 0.20 | 1.11 | 1.22 | 1.25 |
| 0.50 | 1.33 | 1.82 | 2.00 |
| 0.90 | 1.82 | 5.26 | 10.0 |
| 0.99 | 1.98 | 9.17 | 100 |
$f$ matters far more than $s$. At $f = 0.5$, going from $s = 10$ to infinite buys 10 percent, while going from $f = 0.5$ to $f = 0.9$ at fixed $s = 10$ buys almost 3x. Profile before optimizing, an accelerator for 5 percent of runtime is nearly worthless however good it is, and the serial fraction caps multicore scaling.
### 3.5 Little's law
$$L = \lambda W$$
The average number of items **in** a system equals arrival rate times time spent in the system, and it assumes nothing about distributions. Check it physically. A coffee shop serves 2 customers per minute, each spending 5 minutes inside, so on average 10 people are inside, and six chairs is a problem caused by the seating rather than the door or the barista.
Same sentence in hardware. To sustain 2 memory requests per cycle against 200 cycles of latency you need $L = 2 \times 200 = 400$ requests simultaneously outstanding. If the miss queue holds 16 entries you will sustain $16/200 = 0.08$ per cycle, and no amount of bandwidth elsewhere changes that, because the structure holding in-flight requests is binding. That is why miss status holding registers in [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching) are sized as they are. Apply it again to the reorder buffer. To sustain IPC 6 when the average instruction lives 40 cycles between rename and retire you need $6 \times 40 = 240$ entries, and independent microbenchmarking put the M1 performance core near 600, which back-solves into a machine built to keep wide issue fed across long memory latency.
---
## Part 4, hazards, or why the table in 2.3 was a lie
Part 2 assumed eight independent instructions. Real code is dependency-dense. A **hazard** is any situation where the next instruction cannot start next cycle, and there are exactly three kinds.
### 4.1 Structural hazards
Two instructions need the same physical hardware in the same cycle. Suppose one memory port is shared by fetch and data access, and look at cycle 4 of the table in 2.3.
<Figure src="/figures/hardware-interview-prep/iv-06-CPU-Foundations-Pipeline-and-Hazards-fig03.svg" alt="With a single shared memory port, I1's memory access and I4's fetch both land in cycle 4 and one of them has to wait." caption="With a single shared memory port, I1's memory access and I4's fetch both land in cycle 4 and one of them has to wait." id="fig:06-CPU-Foundations-Pipeline-and-Hazards-3" />
One must wait, and since loads and stores are 25 to 35 percent of instructions this is not small. The fix is duplication, and this one is universal enough to have a name. **Separate the instruction cache from the data cache at L1**, giving each its own port and array. That is why every processor you will meet has an L1I and an L1D but a unified L2, and it is the expected answer when someone asks why L1 is split.
Structural hazards appear elsewhere. **Register file ports**, since each instruction reads two operands and writes one, so a 4-wide machine needs 8 read and 4 write ports, and SRAM cell area grows roughly with the square of port count because every port adds wordlines and bitlines through every cell. That cost, developed in [SRAM Arrays and ECC](/learn/hardware-interview-prep/sram-arrays-and-ecc), is a real limit on issue width. **Long-latency units**, since the divider of [Arithmetic Hardware](/learn/hardware-interview-prep/arithmetic-hardware) is iterative and usually unpipelined, so back-to-back divides collide for 20-plus cycles. A structural hazard is always fixable with money, so the question is never whether you can fix it, it is whether the traffic justifies the area and power.
### 4.2 Data hazards, and the one that is real
<Figure src="/figures/hardware-interview-prep/iv-06-CPU-Foundations-Pipeline-and-Hazards-fig04.svg" alt="The ADD has its result at the end of cycle 3 but does not write it architecturally until cycle 5, while the SUB needs x1 at the start of cycle 4, so the value is late by two cycles." caption="The ADD has its result at the end of cycle 3 but does not write it architecturally until cycle 5, while the SUB needs x1 at the start of cycle 4, so the value is late by two cycles." id="fig:06-CPU-Foundations-Pipeline-and-Hazards-4" />
`ADD` writes x1 during writeback in cycle 5. `SUB` reads the register file during decode in cycle 3, **two cycles before the write**, so without help it reads stale garbage and the program is silently wrong.
That is **RAW**, read after write, a **true dependence**. Data genuinely flows from producer to consumer, and no renaming, scheduling, or compiler transformation removes it, because removing it would change what the program computes. True dependences can only be **tolerated**, and Part 5 plus [Out of Order Execution](/learn/hardware-interview-prep/out-of-order-execution) are about tolerating them cheaply.
### 4.3 WAR and WAW, which are not real dependences
Two patterns look like dependences and are not, and understanding why is the highest-value idea in this note.
```text
ADD x1, x2, x3 ; WAR case: reads x3
SUB x3, x4, x5 ; writes x3
MUL x1, x2, x3 ; WAW case: 4 cycles, writes x1
ADD x1, x4, x5 ; 1 cycle, writes x1
```text
**WAR**, write after read. Ask what data flows from the first instruction to the second. **Nothing.** The `ADD` consumes x3 and the `SUB` produces an unrelated new value filed under the same name. If the `SUB` wrote x3 before the `ADD` read it the answer would be wrong, but the problem was created entirely by the **name** x3 being reused.
**WAW**, write after write. Again nothing flows, yet if `ADD` finishes first and the slow `MUL` writes x1 afterwards, x1 ends up holding the wrong value. The corruption is real and the cause is again the reused name.
Say the conclusion out loud. **RAW is a dependence between values. WAR and WAW are dependences between names. Names are free.**
Watch it evaporate. Give the machine a large pool of internal physical registers and assign a **fresh, previously unused physical register** to every instruction that writes an architectural register, keeping a table of which physical register currently holds each architectural name.
| Original code | Architectural write | Physical register assigned | Map after |
|---|---|---|---|
| `ADD x1, x2, x3` | x1 | p37 | x1 -> p37 |
| `SUB x3, x4, x5` | x3 | p38 | x3 -> p38 |
| `MUL x1, x6, x7` | x1 | p39 | x1 -> p39 |
The `ADD` reads whatever x3 mapped to **before** the `SUB` renamed it, so it is immune to the `SUB` finishing early and the WAR is gone. The `MUL` writes p39 while the earlier x1 lives in p37, so no ordering is needed and the WAW is gone. Only RAW chains survive, because those are the ones where a consumer actually reads a producer's physical register. That is **register renaming**, and this paragraph is its entire justification. When [Out of Order Execution](/learn/hardware-interview-prep/out-of-order-execution) and [Register Renaming](/learn/computer-architecture/register-renaming) introduce it you will already know **why** rather than merely what.
### 4.4 Control hazards
Fetch must produce an address every cycle or the machine starves. After a branch the correct address depends on whether the branch is taken and where it goes, neither known until the branch has been decoded, its operands read, and its condition evaluated.
<Figure src="/figures/hardware-interview-prep/iv-06-CPU-Foundations-Pipeline-and-Hazards-fig05.svg" alt="The branch direction is not known until the branch reaches EX in cycle 3, yet fetch has already pulled in two instructions whose addresses were guesses." caption="The branch direction is not known until the branch reaches EX in cycle 3, yet fetch has already pulled in two instructions whose addresses were guesses." id="fig:06-CPU-Foundations-Pipeline-and-Hazards-5" />
Two cycles of exposure in a five-stage machine. In a fifteen-stage machine where the branch resolves at stage 12 it is eleven cycles of fetched, decoded, renamed, and possibly executed work. That work must be **undone**, not merely stopped, which is why control hazards drag in the speculation and recovery machinery of Part 7.
---
## Part 5, forwarding, the fix that pays for itself
### 5.1 The cost of doing nothing
The naive fix stalls the consumer until the value is architecturally written.
| Instruction | c1 | c2 | c3 | c4 | c5 | c6 | c7 | c8 |
|---|---|---|---|---|---|---|---|---|
| `ADD x1,x2,x3` | IF | ID | EX | ME | WB | | | |
| `SUB x4,x1,x5` | | IF | ID | **stall** | **stall** | **stall** | EX | ME |
Three lost cycles per dependent pair. In ordinary compiled code roughly **one instruction in three** consumes a value produced by one of the two immediately before it, because that is what computing anything looks like. Three cycles on a third of instructions adds a full 1.0 to CPI, doubling runtime. Stalling is not a solution, it is a description of failure.
### 5.2 The observation
Look again at 4.2. The `ADD` finished computing at the **end of cycle 3** and the `SUB` needs the result at the **start of cycle 4**. The value exists in time. It is in the wrong place, sitting in a pipeline register on its way toward a register file the `SUB` already finished reading. So do not read the register file. Run a wire from the ALU output back to the ALU input, put a multiplexer in front of each operand, and when the control logic sees a previous destination matching this source, select the wire.
<Figure src="/figures/hardware-interview-prep/iv-06-CPU-Foundations-Pipeline-and-Hazards-fig06.svg" alt="Two bypass paths carry the result back from the pipeline registers into a multiplexer in front of the ALU, so the consumer never has to wait for the register file." caption="Two bypass paths carry the result back from the pipeline registers into a multiplexer in front of the ALU, so the consumer never has to wait for the register file." id="fig:06-CPU-Foundations-Pipeline-and-Hazards-6" />
That is **forwarding**, also called **bypassing**, and it turns the 3-cycle stall into **zero** for arithmetic producers.
### 5.3 Which distances each path covers
| Distance | Example | Where the value is | Mechanism |
|---|---|---|---|
| 1, back to back | `ADD x1,..` then `SUB ..,x1,..` | EX/MEM pipeline register | EX/MEM bypass mux |
| 2, one apart | `ADD x1,..`, filler, `SUB ..,x1,..` | MEM/WB pipeline register | MEM/WB bypass mux |
| 3, two apart | `ADD x1,..`, 2 fillers, `SUB ..,x1,..` | being written to the regfile now | internal regfile bypass |
The distance-3 case uses a trick worth knowing. The register file **writes in the first half of the cycle and reads in the second half**, so a read in the same cycle as a write returns the new value. That costs nothing but a clocking convention and removes an entire bypass path.
### 5.4 The load-use bubble, and why forwarding cannot fix it
Here is the case forwarding cannot save, and one of the few places where the honest answer is that you cannot.
<Figure src="/figures/hardware-interview-prep/iv-06-CPU-Foundations-Pipeline-and-Hazards-fig07.svg" alt="The loaded value is ready at the end of cycle 4 and the consumer needs it at the start of cycle 4, so no wire can close the gap and one bubble is unavoidable." caption="The loaded value is ready at the end of cycle 4 and the consumer needs it at the start of cycle 4, so no wire can close the gap and one bubble is unavoidable." id="fig:06-CPU-Foundations-Pipeline-and-Hazards-7" />
Ready at the end of cycle 4, needed at the start of cycle 4. Forwarding is a wire, and a wire moves a value across space. **It cannot move a value backwards in time.** No bypass path exists because none could exist, so the machine inserts one bubble.
| Instruction | c1 | c2 | c3 | c4 | c5 | c6 | c7 |
|---|---|---|---|---|---|---|---|
| `LDR x1,[x2]` | IF | ID | EX | ME | WB | | |
| `ADD x3,x1,x4` | | IF | ID | **bub** | EX | ME | WB |
| next instruction | | | IF | **bub** | ID | EX | ME |
One unavoidable cycle on a fully forwarded machine, every time a load is immediately followed by a use. That is the **load-use penalty**, which is why L1 load-to-use latency is quoted for every processor and why removing one cycle of it is a generational achievement. Two consequences follow. **Compilers schedule around it**, moving an unrelated instruction into the gap, which is why compiled code looks shuffled relative to source. And **deeper load pipelines cost more**, since a 4-cycle L1 gives 3 bubbles instead of 1, so the price of a bigger slower L1 shows up here rather than in the miss rate. That trade is the heart of [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching) and of the VIPT constraint in [Virtual Memory and Memory Ordering](/learn/hardware-interview-prep/virtual-memory-and-memory-ordering).
### 5.5 What the bypass network costs
Forwarding looks free in a five-stage drawing and is not free in a wide machine. A machine with $W$ execution pipes has $W$ result sources, and each pipe needs 2 operand inputs, so there are $2W$ operand positions each needing a multiplexer over $W$ bypass sources plus the register file. For 8 pipes that is 16 multiplexers of roughly 9 inputs each, every one 64 bits wide, fed by wires reaching from every result to every input.
Wire count grows as $O(W^2)$, and those wires are **long** because execution units are physically spread out, which from section 1.2 of [Digital Logic and Timing](/learn/hardware-interview-prep/digital-logic-and-timing) makes them capacitive and slow. The bypass network is routinely a top critical path and a major dynamic power consumer. The standard mitigation is **clustering**, splitting execution units into groups with fast bypass inside a group and a one-cycle-slower path between groups, covered in [Execution Units](/learn/hardware-interview-prep/execution-units). It is a clean example of physical design reaching up and changing the microarchitecture.
---
## Part 6, control hazards and the arithmetic of getting it wrong
### 6.1 Three strategies
**Stall** until the direction is known. Simple, correct, slow. With 20 percent branches and 2 cycles of exposure that is $0.2 \times 2 = 0.4$ added CPI, a 40 percent slowdown before you have done anything interesting.
**Expose it to software.** Define the instruction after a branch to **always** execute so the compiler can fill the slot, which is a **delay slot**, used by MIPS and SPARC.
```text
beq r1, r2, target
add r3, r4, r5 ; delay slot, ALWAYS executes
```text
It worked when exposure was one cycle and aged terribly, because the number of slots is baked into the **architecture**, so a later deeper implementation still gets exactly one and needs several, and every implementation forever must reproduce the semantics. It is a microarchitectural detail that leaked into the contract, which 1.2 says is exactly the thing not to do. AArch64 has none, and that is the right call.
**Predict** the direction and target, fetch down the predicted path, and throw the work away if wrong. Every high-performance processor since the early 1990s does this, and it is the subject of [Front End and Branch Prediction](/learn/hardware-interview-prep/front-end-and-branch-prediction).
### 6.2 What a misprediction costs
The penalty is not the depth of the pipeline. It is the cycles between **fetching down the wrong path** and **discovering the mistake**, plus restarting fetch and refilling the front end.
<Figure src="/figures/hardware-interview-prep/iv-06-CPU-Foundations-Pipeline-and-Hazards-fig08.svg" alt="Everything fetched between the branch and its resolution is discarded, so the misprediction penalty is the distance from fetch to resolve plus the cost of restarting the front end." caption="Everything fetched between the branch and its resolution is discarded, so the misprediction penalty is the distance from fetch to resolve plus the cost of restarting the front end." id="fig:06-CPU-Foundations-Pipeline-and-Hazards-8" />
Everything fetched between the branch and its resolution is discarded, and in a wide machine each of those cycles held several instructions, so a 15-cycle penalty on an 8-wide front end means up to 120 instruction slots thrown away per misprediction.
### 6.3 The penalty arithmetic at several accuracies
With penalty $P$, branch fraction $b$, and accuracy $a$, the added CPI is $\Delta \text{CPI} = b \cdot (1 - a) \cdot P$. Take $b = 0.2$ and $P = 15$, and evaluate the damage against a wide machine with ideal IPC 6, meaning ideal CPI $1/6 = 0.1667$.
| Accuracy $a$ | Miss rate | $\Delta$CPI | Wide-machine CPI | Wide-machine IPC | Performance lost |
|---|---|---|---|---|---|
| 100 percent | 0 | 0 | 0.1667 | 6.00 | 0 |
| 99 percent | 0.01 | 0.03 | 0.1967 | 5.08 | 15 percent |
| 97 percent | 0.03 | 0.09 | 0.2567 | 3.90 | **35 percent** |
| 95 percent | 0.05 | 0.15 | 0.3167 | 3.16 | **47 percent** |
| 90 percent | 0.10 | 0.30 | 0.4667 | 2.14 | **64 percent** |
| 50 percent | 0.50 | 1.50 | 1.6667 | 0.60 | 90 percent |
Read the 97 percent row and sit with it. A predictor right **97 times in 100** throws away more than a third of a wide machine's performance. That is the answer to "why are branch predictors so absurdly complicated." Not because 95 percent is bad in any ordinary sense, but because the ideal CPI of a wide machine is so small that the misprediction term dwarfs it, making every tenth of a percent worth real area and power. This arithmetic is what justifies the TAGE-class predictors of [Modern Branch Predictors](/learn/computer-architecture/modern-branch-predictors).
Now hold $a = 0.97$ and vary depth instead.
| Pipeline depth | Penalty $P$ | $\Delta$CPI | IPC from an ideal 6 |
|---|---|---|---|
| 5-stage | 3 | 0.018 | 5.49 |
| 10-stage | 8 | 0.048 | 4.65 |
| 15-stage | 15 | 0.090 | 3.90 |
| 20-stage | 22 | 0.132 | 3.35 |
| 31-stage | 35 | 0.210 | 2.66 |
That is the CPI term of 3.3 made concrete, and it shows the two decisions are coupled. **A deeper pipeline demands a better predictor to stay even**, so the cost of depth is not only the flops at the boundaries, it is the predictor you must build to pay for it.
---
## Part 7, speculation and precise exceptions
### 7.1 Speculation, generalized
Predicting a branch means **speculating**, doing work that might be undone, and the idea generalizes far past branches. **Branch direction and target**, fetching down the predicted path. **Memory dependence**, where a load might alias an earlier store whose address is not yet computed, so predict that it does not and squash if it did, per [Load Store and Memory Ordering](/learn/hardware-interview-prep/load-store-and-memory-ordering). **Cache hit**, scheduling the consumer of a load assuming L1 hits, with replay if it misses, which is a notorious source of complexity and bugs. **Prefetching**, fetching data before anyone asked, at the cost of wasted bandwidth on wrong guesses.
The structure is always the same three parts. Guess, proceed as though the guess were true, and keep enough information to undo it. The third part is the expensive one.
### 7.2 What a precise exception is
The ISA promises something about faults, whether divide by zero, unaligned access, page fault, illegal instruction, or an external interrupt arriving. The promise is this.
**When the handler starts, machine state must look exactly as if every instruction before the faulting one had completed and no instruction from the faulting one onward had started.**
That is a **precise exception**. It sounds like a formality and is not. Work a page fault, the ordinary mechanism behind demand paging in [Virtual Memory and Memory Ordering](/learn/hardware-interview-prep/virtual-memory-and-memory-ordering).
```text
LDR x1, [x2] ; page not present, faults
ADD x4, x4, #1 ; independent, no reason it cannot run
```text
The OS handler brings the page in, fixes the page table, and returns to **re-execute the load**, which is the entire point of demand paging. Now suppose the machine let the `ADD` complete and write x4 before reporting the fault. On return the `ADD` re-executes too and x4 is incremented **twice**. The program is wrong in a way that depends on the timing of physical storage activity, which makes it both catastrophic and unreproducible. The same requirement covers debuggers showing consistent state at a breakpoint, signal handlers, and virtualization.
### 7.3 Why a pipeline makes it hard
At the instant the load faults there are four other instructions inside the machine. Some are older and unfinished, some are younger and have already computed results, and in the machine of [Out of Order Execution](/learn/hardware-interview-prep/out-of-order-execution) there may be several hundred in flight with the finished ones scattered arbitrarily through program order. So the machine must answer two questions at fault time. Which instructions were **before** this one, and did all of them complete? Which were **after** it, and can their effects be erased? Neither is answerable if instructions write architectural state whenever they happen to finish.
### 7.4 Separate computing a result from committing it
**Let instructions execute in any order, but do not let them change architectural state when they finish. Put the result somewhere private. Change architectural state later, strictly in program order, and only once every older instruction is known exception-free.**
The private holding area is the **reorder buffer**, the ROB. Instructions enter in program order, sit while they execute in whatever order the scheduler likes, mark themselves complete along with any exception raised, and leave from the head, in order.
<Figure src="/figures/hardware-interview-prep/iv-06-CPU-Foundations-Pipeline-and-Hazards-fig09.svg" alt="Instructions enter the reorder buffer in program order and complete in whatever order the scheduler allows, but only the entry at the head may change architectural state, so a fault surfaces exactly where a sequential machine would have taken it." caption="Instructions enter the reorder buffer in program order and complete in whatever order the scheduler allows, but only the entry at the head may change architectural state, so a fault surfaces exactly where a sequential machine would have taken it." id="fig:06-CPU-Foundations-Pipeline-and-Hazards-9" />
I5 and I6 finished **before** I4 and it did not matter, because their results sat in the ROB rather than in the register file. When the fault surfaces, everything from I4 onward is discarded by resetting the tail pointer and restoring the register map, and architectural state is exactly what a one-instruction-at-a-time machine would have produced.
### 7.5 Two things fall out for free
**In-order commit is not a choice, it is a consequence.** If you want precise exceptions and out-of-order execution, results must be buffered and applied in order, which is why every question of the form "why retire in order when you execute out of order" has the same one-word answer, exceptions.
**Misprediction recovery uses identical machinery.** A mispredicted branch is structurally the same event as a fault, since some instruction turned out not to belong and everything after it must be erased, so the ROB and the register map checkpointing built for exceptions handle mispredictions with no extra structure.
Notice the direction of the argument, because that is the part worth carrying. The ROB was motivated by a pure **correctness** requirement that says nothing about performance. Out-of-order execution then becomes nearly free, since the only thing stopping you from executing early was that results would appear too soon, and the ROB already solves that. **Out-of-order execution largely falls out of solving precise exceptions properly.** That framing is uncommon, true, and better than the usual answer. Machines did ship with imprecise floating-point exceptions historically, software hated it, and the industry converged on precision, as [Exception and Interrupt Handling in a Pipelined CPU](/learn/computer-architecture/exceptions-pipeline) describes.
---
## Part 9, check yourself
Answer out loud, in full sentences, as if an interviewer asked. If you cannot, reread the section named.
1. Distinguish architecture from microarchitecture, give one concrete example of each, and name a case where the boundary is not clean. (1.2)
2. Write an x86 instruction that does five things and the AArch64 sequence replacing it. Which term of the performance equation does each side win? (1.3, 3.1)
3. Why does fixed-length encoding make an 8-wide front end nearly free, and what does it cost instead? (1.4)
4. What is microcode, why does it exist, and how does it relate to the RISC and CISC distinction? (1.5)
5. Five-stage pipeline, 2 ns stages, 0.1 ns setup and 0.1 ns clock-to-Q. Give the period, the latency of one instruction, and the throughput, then explain why latency got worse. (2.4)
6. Stage delays are 1.5, 2.0, 2.5, 1.8, 1.2 ns. What is the speedup from pipelining and what would you do about it? (2.4)
7. Build a CPI budget for an in-order machine with 25 percent loads and 20 percent branches. Which line dominates and what does that imply? (3.2)
8. Why does deepening the pipeline eventually make the machine slower, and why do real cores sit shallower than the pure-performance optimum? (3.3)
9. You made 20 percent of a program infinitely fast. What is the speedup, and what does it say about accelerator design? (3.4)
10. Use Little's law to size a miss queue for 2 requests per cycle at 200 cycles latency, then use it to explain a 600-entry reorder buffer. (3.5)
11. Name the three hazard types with a code example of each. Which one is always fixable with money? (4.1 to 4.4)
12. Which of RAW, WAR, and WAW are false dependences, why are they false, and what single mechanism removes them? (4.3)
13. Why can forwarding not eliminate the load-use stall? Answer in one sentence about time, then say what a compiler does about it. (5.4)
14. Why does the bypass network become a critical path in a wide machine, and what is the standard mitigation? (5.5)
15. Branches are 20 percent, penalty 15 cycles, accuracy 97 percent. Give the added CPI, then the IPC of a machine whose ideal IPC is 6, then explain why 97 percent is not good enough. (6.3)
16. What is a precise exception, give an example where imprecision breaks a real program, and explain why it forces in-order commit. (7.2, 7.5)
---
## Part 10, related notes
- [Digital Logic and Timing](/learn/hardware-interview-prep/digital-logic-and-timing) for the flop-logic-flop structure and the pipeline register overhead in 2.4
- [Out of Order Execution](/learn/hardware-interview-prep/out-of-order-execution) for register renaming as promised in 4.3 and the reorder buffer as promised in 7.4
- [Front End and Branch Prediction](/learn/hardware-interview-prep/front-end-and-branch-prediction) for the predictors that the arithmetic in 6.3 justifies
- [Execution Units](/learn/hardware-interview-prep/execution-units) for the bypass network, clustering, and the ports that Part 4 hazards contend for
- [Load Store and Memory Ordering](/learn/hardware-interview-prep/load-store-and-memory-ordering) for memory dependence speculation and where load-use latency is paid
- [Virtual Memory and Memory Ordering](/learn/hardware-interview-prep/virtual-memory-and-memory-ordering) for the other half of the foundation and the page fault used in 7.2
- [Performance Modeling](/learn/hardware-interview-prep/performance-modeling) for turning the CPI budget of 3.2 into a working skill
- [The Control Unit](/learn/computer-architecture/control-unit) for microcode, the strongest bridge from your day job to this material
- [The Classic 5-Stage Pipeline (IF-ID-EX-MEM-WB)](/learn/computer-architecture/five-stage-pipeline) and [Pipeline Hazards](/learn/computer-architecture/pipeline-hazards) for the vault's full datapath treatmentBook mode
Was this helpful?