Instructions and pipelines

You know a program is a list of instructions. This chapter is about the interface those instructions define and the simplest machine that runs them well. Amdahl, Blaauw and Brooks defined the architecture of the IBM System/360 in 1964 as the structure a machine-language programmer must understand to write a correct, timing-independent program; the 360 was the first family to separate that from its implementations.¹ Everything below the line, the microarchitecture, is free to change as long as results match.

Three threads run through the chapter:

• ISA design shapes the pipeline. Fixed-length, load-store encodings with registers in fixed fields make decode cheap and pipelining natural; variable-length CISC encodings push work into a decoder that cracks instructions into simpler internal operations.⁵
• Pipelining trades latency for throughput. Five stages cut the cycle time roughly fivefold at best, while dependences and branches add stall cycles. The pipeline’s quality is its CPI.¹¹
• Performance is a product. The iron law, time = instructions × CPI × cycle time, is the frame for every trade-off here and in the rest of the CPU chapters.

We use RISC-V as the worked ISA because the ratified specification is open², and set it beside x86-64 and Arm A64 where they differ. Depth versus clock frequency is treated in the Design Flow guide’s Architecture stage; here the pipeline has five stages.

RV32I has 32 registers of XLEN bits with x0 hardwired to zero, a pc, and six formats, all 32 bits: R (register–register), I (12-bit immediate, loads, JALR), S (stores), B (branches), U (20-bit upper immediate) and J (JAL).³ The design keeps rs1, rs2 and rd in the same bit positions in every format, so the register file can be read before decode finishes, and the S format splits its immediate (imm[11:5] high, imm[4:0] where rd would be) precisely to keep that true; the sign bit is always bit 31.⁵ Waterman counts 47 base instructions, 40 of them mandatory user-level hardware.⁵ The base is frozen, and everything else comes as extensions (M, A, F, D, C, and later V and others).²

Encoding and decode cost

• x86-64: variable length up to 15 bytes, with optional prefixes, an opcode of one to three bytes, ModRM and SIB bytes for addressing, a displacement and an immediate. Most integer instructions are destructive two-operand forms and can take a memory operand; Waterman counts about 1,300 instructions as of 2015.⁵ Since AMD’s K5 and Intel’s Pentium Pro, x86 cores have broken complex instructions into sequences of simpler internal operations.⁵
• Arm A64: fixed 32-bit encodings with 5-bit register fields, 31 general registers (X0–X30) and a zero register that shares encoding 31 with the stack pointer.⁹⁸⁵ ARMv8 dropped the 16-bit Thumb encodings of the 32-bit architecture, so it is less dense than variable-length code.⁵
• RISC-V C extension: 16-bit forms that each expand to one 32-bit instruction; many reach only x8–x15 through 3-bit register fields. IALIGN drops to 16 bits.² Waterman reports RVC code about 25–30% smaller, enough to make RV64C denser than x86-64 and A64 on SPEC CPU2006.⁵

In iron-law terms, CISC aims to lower the instruction count and RISC to lower CPI and cycle time. Blem et al. measured Cortex-A8 and A9 against Atom and Sandy Bridge and found instruction counts similar across the ISAs (compilers mostly pick x86’s RISC-like instructions), micro-op to instruction ratios usually below 1.3, and no intrinsic performance or energy advantage for either style: “the ISA being RISC or CISC seems irrelevant.”¹⁵ The costs that remain are in the front end: finding instruction boundaries in a variable-length stream, and decoders or micro-op caches to feed a wide core.

The architectural contract is sequential: each instruction appears to complete before the next begins, and the PC names the next one (PC + 4, or a target for taken branches and jumps; PC + 2 steps exist once the C extension is present).³² Every microarchitecture in this guide preserves that illusion.

Cornell’s ECE 4750 notes derive three implementations of the same RISC-V subset and compare them with the iron law: single-cycle (CPI 1, long cycle), FSM or multi-cycle (CPI greater than 1, short cycle), and pipelined (CPI near 1, short cycle).¹¹ With their component delays (in units of τ), the single-cycle machine runs at 74τ and the FSM machine at 36τ with CPI 6.7 on a vector-add loop, so the FSM loses despite a clock twice as fast.¹¹ The single-cycle critical path is the load: PC → instruction memory → register read → ALU (address) → data memory → write-back mux → register-file setup.

Two details carry into the pipeline. The register file is written on one edge and read combinationally, so a read in the same cycle as a write can see the new value if the write happens in the first half of the cycle. And a taken branch needs the comparison result before the next PC can be chosen, which in a single-cycle machine just lengthens the cycle, and in a pipeline becomes a hazard.

The five stages are F, D, X, M and W, with pipeline registers F/D, D/X, X/M and M/W carrying each instruction’s operands, destination, control signals and PC.¹¹ Control is decoded once in D and travels with the instruction, which keeps every later stage’s control a function of its own pipeline register. A valid bit per stage marks bubbles.

With stage delays $t_i$ and per-stage register overhead $t_{\mathrm{o}}$, the cycle is $\max_i t_i + t_{\mathrm{o}}$, and $N$ instructions with no hazards take $(N + k - 1)$ cycles on a $k$-stage pipeline. The asymptotic speedup over single-cycle is therefore

reached only with perfectly balanced stages and no overhead. For the figure’s illustrative delays (200, 100, 200, 200 and 100 ps, overhead ignored) $S_\infty = 800/200 = 4$. Cornell lists the same lessons: pipelining helps throughput, not latency; speedup is limited by the slowest stage and reduced by fill time.¹¹

The memory stages assume a one-cycle access, which in practice means separate instruction and data caches that hit; misses are the subject of Caches and coherence. The optimum depth, and the studies that put it at a handful of gate delays per stage, are in the Architecture stage; where the registers go in RTL, and why retiming can’t add them for you, in RTL design.

Cornell’s notes list five ways to resolve a hazard: expose it in the ISA (software must schedule around it), stall in hardware, bypass, speculate, or schedule dynamically.¹¹ The five-stage pipeline uses several at once.

• Structural: resolved by duplication (split I- and D-memories, enough register ports) or by stalling. Cornell’s example creates one on purpose by letting ALU instructions skip M, so two instructions reach the single write port in the same cycle, and then fixes it with a second write port.¹¹
• Data (RAW): only read-after-write hazards occur in this in-order pipeline, since every instruction reads in D and writes in W, in program order. Write-after-read and write-after-write hazards appear once instructions can complete out of order, the case that out-of-order execution handles with renaming.¹¹
• Control: Cornell defines a resolution latency, the number of cycles the next fetch must wait to avoid any control hazard: two cycles for jumps, whose target is known in D, and three for branches, decided in X.¹¹ Exceptions are a control hazard too: flags travel with the instruction to a commit point, so that the oldest faulting instruction is the one reported and younger ones are squashed.¹¹

The forwarding unit compares the source registers of the instruction in X with the destinations in X/M and M/W, giving priority to X/M (the newer value) and ignoring x0; the hazard unit in D stalls when the instruction in X is a load whose destination matches either source of the instruction in D. A stall holds the PC and F/D and injects a bubble into D/X.¹¹ Under the hood shows the logic.

Distances at which a consumer of a value stalls, with full bypassing:

These follow from the stage timings, with write-first-half, read-second-half register-file timing; they are what the simulation implements. A load feeding a store’s data can also be forwarded M/W → M with no stall in designs that add that path; the simulation treats store data as an X-stage operand.

For control hazards, predict-not-taken with resolution in X costs two cycles per taken branch, and resolution in D one, at the price of a comparator and target adder in D and the extra branch-operand stalls in the table.¹¹ Small real cores show the same arithmetic: lowRISC’s two-stage Ibex documents taken branches at two cycles, or one with an extra branch-target adder, and loads that stall at least one cycle for their data.¹⁶ Dynamic prediction (a branch target buffer plus history-based direction predictors) moves the redirect into F; the five-stage Rocket core has a configurable BTB, branch history table and return-address stack.¹⁷ The mechanisms belong to the next chapter.

The model is the textbook in-order pipeline: one instruction per stage, write-first-half register file, bypasses X/M → X and M/W → X, predict-not-taken with a taken branch flushing the instructions fetched behind it. The Expert view adds a toggle to resolve branches in D (one-cycle penalty, operands needed a cycle earlier) and shows IPC. Try:

• In the loop, resolve branches in D. The flush cost halves, but a new stall appears in front of the branch. Reorder to remove it.
• With forwarding off, compare the dependent chain (CPI 2.60) with the load-use program. Why does reordering help less without bypassing?

Reordering is checked against read-after-write, write-after-read and write-after-write dependences in the original order; an order that breaks one is flagged, since a compiler may not use it.

With $N$ dynamic instructions, average CPI and clock period $t_{\mathrm{c}}$:

where $\mathrm{CPI}_0$ is the ideal (1 for a scalar pipeline), $f_j$ the frequency of stall event $j$ per instruction and $p_j$ its penalty in cycles. The factors are not independent: the ISA moves $N$ and CPI in opposite directions; pipeline depth moves $t_{\mathrm{c}}$ down and every $p_j$ up; a bypass network removes stall terms but can lengthen $t_{\mathrm{c}}$. Cornell frames the single-cycle, multi-cycle and pipelined designs exactly this way.¹¹ The name comes from Clark, after his and Emer’s VAX-11/780 characterization.¹⁴

Two cautions when using it. Compare designs on $T$ for the same program and compiler, never on MIPS or GHz, since $N$ differs across ISAs (though Blem et al. found dynamic instruction counts close between Arm and x86 for compiled code).¹⁵ And CPI measured on a real core is dominated by events this chapter leaves out:cache misses and branch mispredictions in the CPI stacks of every modern core.

Blem et al.’s CPIs are measured at each part’s own frequency (0.6 GHz A8 to 3.4 GHz i7) with different cache hierarchies, so they fold memory stalls into the comparison; the authors attribute the gaps to issue width, out-of-order capability and caches rather than to the ISA, and report x86 micro-op to instruction ratios usually below 1.3.¹⁵ Intel’s APX data point illustrates the instruction-count side of the iron law from within one ISA: doubling the architectural registers to 32 removes about 10% of loads and more than 20% of stores in compiled code.¹⁰

• Bypass cost scales badly. Each extra stage that holds a result adds a mux input per operand; a superscalar core, which issues several instructions per cycle, multiplies sources and destinations. The bypass mux sits on the X-stage loop (ALU output → mux → ALU input), which is often the critical path that sets the clock.
• Static scheduling is brittle. Compiler schedules assume a pipeline; code tuned for one core can stall on another, and a cache miss turns a one-cycle load-use slot into hundreds of cycles that no static schedule covers. GCC’s first scheduling pass is conventionally on at -O2, but targets override it: off at every level on x86, only at -O3 on AArch64.¹³ Hiding variable latency dynamically is what out-of-order execution is for.
• Exposed hazards age poorly. MIPS-I exposed load, multiply and divide hazards and branch delay slots; interlocks later replaced the data hazards, but the branch delay slot stayed for compatibility, and for superscalar and deep pipelines it is pure cost. Waterman notes that even for a five-stage pipeline, dropping the slot and adding a small branch target buffer typically gives better performance and performance per area.⁵
• Encoding constraints are permanent. MIPS’s 16-bit immediates left too little opcode space for a compressed encoding, forcing a mode switch; RISC-V reserved space for 16-bit instructions from the start.⁵

1. Hazard detection and forwarding

The control for a fully bypassed five-stage pipeline is a few comparators. Forwarding selects, per ALU operand, the newest in-flight value for that register; the hazard unit handles the one case forwarding can’t, a load at distance 1. Cornell’s notes derive the same signals (their ostall_load_use and bypass_waddr terms), including the valid bits and the x0 check.¹¹

// Operand A of the instruction in X (operand B is the same with rs2).
always_comb begin
  if      (xm_wen && xm_rd != 5'd0 && xm_rd == dx_rs1) fwd_a = FWD_XM;  // ALU result, 1 back
  else if (mw_wen && mw_rd != 5'd0 && mw_rd == dx_rs1) fwd_a = FWD_MW;  // load data or result, 2 back
  else                                                   fwd_a = FWD_RF;  // value from the register file
end

// Load-use: the instruction in D needs what the load now in X hasn't read yet.
assign stall_d = dx_valid && dx_is_load && dx_rd != 5'd0 &&
                 ((fd_uses_rs1 && dx_rd == fd_rs1) || (fd_uses_rs2 && dx_rd == fd_rs2));

// Stall: hold PC and F/D, insert a bubble into D/X.
assign pc_en    = !stall_d;
assign fd_en    = !stall_d;
assign dx_valid_next = fd_valid && !stall_d && !squash;

// Taken branch resolved in X: squash the two younger instructions (in F and D).
assign squash = xm_br_taken_now;

Two refinements are common. Branches resolved in D need their own bypass into the comparator and a stall rule for ALU (1) and load (2) producers. And the register file’s write-before-read timing removes the need for a third bypass from W into D.

2. A CPI model for the in-order pipeline

For a scalar in-order pipeline with full bypassing and predict-not-taken branches resolved in X:

where $f_{\mathrm{ld}}$ is the fraction of loads, $u_1$ the fraction whose first use is the very next instruction, $f_{\mathrm{br}}$ the fraction of branches and $\tau$ the fraction taken; the last term collects cache misses per instruction $m_\ell$ times their penalties, which this chapter leaves to Caches and coherence. The Trade-offs figure is this model with illustrative $f_{\mathrm{ld}} u_1 = 0.10$ and $f_{\mathrm{br}} \tau = 0.09$. The simulation measures the same quantity directly as $1 + (\text{stalls} + \text{flushes})/N$, excluding the $k - 1 = 4$ fill cycles, which vanish as $N$ grows.

3. Scheduling to fill the load-use slot

Compilers typically hide the slot with list scheduling on each basic block. Build the dependence graph (edges for read-after-write, write-after-read and write-after-write, weighted by latency: 2 after a load, 1 after an ALU instruction in this pipeline); give each node a priority, usually its longest latency-weighted path to the end of the block; then cycle by cycle issue the highest-priority instruction whose predecessors have completed. GCC has a pass before register allocation (-fschedule-insns) and one after (-fschedule-insns2), which its manual calls especially useful on machines with few registers and loads that take more than one cycle; it also has -fdelayed-branch to fill branch delay slots on targets that have them.¹³

before:  lw  x1, 0(x10)        cycle 1
         add x2, x1, x3        cycle 3   <- stall, x1 not ready
         lw  x4, 4(x10)        cycle 4
         add x5, x4, x6        cycle 6   <- stall
         sub x7, x8, x9        cycle 7       CPI 1.40

priorities (longest path to end): lw x1 = 3, lw x4 = 3, add x2 = 1, add x5 = 1, sub = 1

after:   lw  x1, 0(x10)        cycle 1
         lw  x4, 4(x10)        cycle 2
         add x2, x1, x3        cycle 3   x1 ready via M/W bypass
         add x5, x4, x6        cycle 4
         sub x7, x8, x9        cycle 5       CPI 1.00

4. Exposing hazards in the ISA

The alternative to interlocks is to make the hazard part of the contract: a delay slot after each load or branch that the compiler must fill (with a no-op if nothing fits). Cornell lists this first among the ways to resolve data and control hazards: it removes the stall logic but makes software scheduling necessary for correctness.¹¹ MIPS-I did it for both; later MIPS revisions replaced the load slot with interlocks because that was simpler for software and could perform better, while the branch delay slot had to stay for compatibility, even though dropping it and adding a small branch target buffer usually gives better performance and performance per area, even in a five-stage pipeline.⁵ RISC-V’s control transfers have no architecturally visible delay slots.³

5. Precise exceptions in the pipeline

A load can fault in M while a younger instruction is already in X and an older one in W. The pipeline must report the oldest fault and make the architectural state look as if every older instruction completed and no younger one started. Cornell’s design records exception flags as the instruction flows, acts on them at a commit point after the last stage that can raise one and before any state is updated, squashes younger instructions, saves the PC of the faulting instruction and redirects fetch to the handler; asynchronous interrupts are injected at the same point.¹¹ The same idea, scaled up with a reorder buffer, is how out-of-order cores keep exceptions precise.

Every limit of the scalar in-order pipeline is a lever pulled in the next chapters: the two-cycle taken branch (branch target buffers and direction predictors), the load-use slot and every longer latency (dynamic scheduling, register renaming and a reorder buffer in Branch prediction and out-of-order execution), the one-cycle memory stage (Caches and coherence), and the single instruction stream per core (Multicore and vector units). The depth–frequency optimum stays in the Architecture stage.