CPU Architecture §

Step 1 — The basic cycle. The CPU repeats four actions forever: (1) Fetch the instruction word at address IP from memory, (2) Decode the opcode and identify operands, (3) Execute the operation (ALU, FPU, or memory access), (4) Update IP (increment, or jump/branch to a new address). Each action takes one or more clock cycles.

Step 2 — The components.

• ALU (Arithmetic Logic Unit): performs integer add, subtract, AND, OR, shift, compare.
• FPU (Floating-Point Unit): performs IEEE-754 add, multiply, divide, square-root.
• Control unit: generates the control signals that route data through the ALU/FPU and update the IP.
• Register file: 16–32 general-purpose registers, each 32 or 64 bits wide. Access time: 1 cycle (the fastest memory in the system).

Step 3 — Worked example. Consider the RISC-V instruction addi t0, t1, 5 (add immediate):

1. Fetch: read the 32-bit word at IP = 0x0040 → 0x00500293.
2. Decode: opcode = 0010011 (OP-IMM), rd = t0 (register 5), rs1 = t1 (register 6), imm = 5.
3. Execute: ALU computes R[t1] + 5.
4. Writeback: store the result into R[t0].
5. Update IP: IP ← IP + 4.

Step 4 — Integer overflow. When an arithmetic operation exceeds the representable range, the result wraps around. In two’s complement, $2^{31} - 1 + 1 = -2^{31}$ (32-bit). The CPU sets an overflow flag; some languages (Rust in debug mode) trap on overflow.

Step 5 — Harvard architecture. Some processors (DSPs, microcontrollers) use separate instruction and data memories. This allows a simultaneous fetch and data access in the same cycle, eliminating the von Neumann bottleneck.

Authoritative sources

• Computer Architecture: A Quantitative Approach (Hennessy & Patterson)
• The RISC-V Reader

Step 1 — CISC vs. RISC. x86 is CISC (Complex Instruction Set Computer): instructions like MOVSB or LEA do multiple things in one opcode. Modern x86 CPUs (Intel, AMD) decode these CISC instructions into RISC-like micro-ops (µops) internally, then execute them on a superscalar, out-of-order pipeline. The ISA remains CISC for software compatibility; the microarchitecture is effectively RISC.

Step 2 — Worked example. The x86 instruction movsb (move string byte) copies a byte from [RSI] to [RDI] and increments both pointers. A modern Intel CPU decodes this into 3 µops: (1) load from [RSI], (2) store to [RDI], (3) increment RSI and RDI. Each µop is then scheduled independently on the execution units.

Step 3 — Why it matters. A compiler targets the ISA (see Compilation), not the microarchitecture. The same x86-64 binary runs on Intel and AMD with different internal pipelines, different cache sizes, and different branch predictors, yet produces identical results.

Authoritative sources

• The RISC-V Reader

Step 1 — The five stages. Each instruction passes through five functional units in sequence. At steady state, one instruction enters Fetch per cycle while another is in Decode, another in Execute, etc. The pipeline is full after 5 cycles and then produces one result per cycle.

Step 2 — Worked example: 5 instructions, cycle by cycle.

Consider this RISC-V sequence (no branches):

I1: add  r1, r2, r3
I2: mul  r4, r1, r5      (depends on I1)
I3: sub  r6, r7, r8      (independent)
I4: add  r9, r4, r10     (depends on I2)
I5: sw   r9, 0(r11)      (depends on I4)

Total: 9 cycles for 5 instructions → CPI = 9/5 = 1.8 (including fill/drain). At steady state (long program), CPI → 1.

Step 3 — Data hazards and forwarding. I2 needs the result of I1, which is not written back until cycle 5. Without forwarding, I2 would stall 2 cycles. With forwarding (bypassing the register file), the ALU output of I1 (available at the end of Execute, cycle 3) is routed directly to the ALU input of I2 (cycle 4). No stall.

Step 4 — Control hazards and branch prediction. A branch changes the IP. The CPU predicts the outcome (taken/not-taken) and speculatively executes the predicted path. A misprediction flushes the pipeline and restarts from the correct target. Modern predictors (TAGE, perceptron) achieve $> 97\%$ accuracy. On a 14–20 stage pipeline, a misprediction penalty is typically 14–20 cycles.

Step 5 — Structural hazards. Two instructions need the same resource in the same cycle (e.g., one ALU). Resolved by adding resources (superscalar) or stalling.

Authoritative sources

• Computer Architecture: A Quantitative Approach (Hennessy & Patterson)

Step 1 — Encoding. The exponent is stored biased by 127 (float32) so that a simple unsigned comparison of the exponent field gives the correct ordering. The mantissa stores the fractional part after the leading 1 (which is implicit for normal numbers).

Step 2 — Worked example: encode 6.5 as float32.

1. $6.5 = 1.625 \times 2^2$.
2. Sign: $s = 0$ (positive).
3. Exponent: $e = 2 + 127 = 129 = 10000001_2$.
4. Mantissa: $0.625 = 0.101_2$, so the 23-bit field is 10100000000000000000000.
5. Final: 0 10000001 10100000000000000000000 = 0x40D00000.

Step 3 — Special values. $+0, -0, +\infty, -\infty, NaN$ (Not a Number). $0/0 = NaN$, $\infty/\infty = NaN$, $0 \times \infty = NaN$.

Step 4 — Rounding modes. Round-to-nearest (default), round-toward-zero, round-toward-$+\infty$, round-toward-$-\infty$.

Step 5 — Precision and denormals. float32 has $\approx 7$ decimal digits; float64 has $\approx 15$. $0.1 + 0.2 \neq 0.3$ in float32 (and float64): $0.1$ and $0.2$ are not exactly representable. When the exponent is all zeros, the leading 1 is dropped (denormal), allowing gradual underflow to zero.

Authoritative sources

• IEEE 754-2019 Standard for Floating-Point Arithmetic

Step 1 — Why OOO is needed. In a 5-stage in-order pipeline, if I2 depends on I1’s result, I2 stalls even if I3 and I4 are independent. With OOO, the CPU dispatches I3 and I4 to execution units while I2 waits, keeping the hardware busy.

Step 2 — Register renaming. Architectural registers (e.g., R0–R31) are mapped to a larger pool of physical registers (e.g., 128–256). This eliminates false dependencies: a Write-After-Read (WAR) or Write-After-Write (WAW) hazard disappears because each write gets a fresh physical register. Only true data dependencies (Read-After-Write) remain.

Step 3 — Worked example. Consider:

I1: add  r1, r2, r3    → writes P5 (renamed r1)
I2: mul  r4, r1, r5    → reads P5, writes P8 (renamed r4)
I3: sub  r6, r7, r8    → reads P9, P10, writes P11 (renamed r6)
I4: add  r1, r4, r9    → reads P8, P12, writes P13 (renamed r1 again)

I3 is independent of I1/I2 and can execute immediately. I4 must wait for I2’s result (P8). The ROB ensures I1 commits before I2, I2 before I3, I3 before I4 — even though I3 may finish before I2.

Step 4 — Speculative execution. Modern CPUs execute instructions that have not yet committed. The ROB tracks all in-flight instructions. The CPU also performs speculative store forwarding (a load can read a value from a prior store that has not yet committed) and speculatively executes past a branch before the target is known. This is distinct from branch prediction: even with a perfect predictor, the CPU speculatively fills the ROB with instructions that will only become architecturally visible at commit. On a misprediction or exception, all speculative (uncommitted) entries in the ROB are flushed.

Step 5 — Interaction with branch prediction. The CPU speculatively executes down the predicted path, filling the ROB with speculative instructions. On misprediction, the ROB is flushed and refilled from the correct path. The penalty is the number of cycles to refill the pipeline (typically 14–20 cycles on modern CPUs).

Authoritative sources

• Computer Architecture: A Quantitative Approach (Hennessy & Patterson)

Step 1 — How SIMD works. A vector register (e.g., a 128-bit XMM register) is divided into fixed-width lanes. A single opcode is broadcast to all lanes simultaneously. For ADDPS (add packed single-precision floats), one instruction performs 4 independent 32-bit floating-point additions.

Step 2 — Worked example. Add two arrays of 4 floats: a = [1.0, 2.0, 3.0, 4.0], b = [10.0, 20.0, 30.0, 40.0].

1. Load a into XMM0 (128 bits: four 32-bit floats).
2. Load b into XMM1.
3. Execute ADDPS XMM0, XMM1 → XMM0 = [11.0, 22.0, 33.0, 44.0].
4. Store XMM0 back to memory.

Four additions in one instruction (vs. 4 scalar instructions). With AVX-512, 16 additions in one instruction.

Step 3 — When SIMD helps. SIMD is most effective for data-parallel workloads: image processing, audio, scientific computing, matrix operations. The compiler (auto-vectorization) or the programmer (intrinsics) must ensure that the data fits in the vector register width and that the operations are uniform across lanes.

Step 4 — Limitations. If the data has irregular access patterns (e.g., a linked list), SIMD cannot help. If the operation is not uniform (e.g., a branch that depends on per-element data), the lanes must be masked or the code must fall back to scalar.

Authoritative sources

• Computer Architecture: A Quantitative Approach (Hennessy & Patterson)

Step 1 — Amdahl’s law. The speedup of a parallel system is limited by the serial fraction. $S = 1 / (f + (1-f)/p)$ where $f$ is the serial fraction and $p$ is the number of cores. If 10% of the code is serial, the maximum speedup with infinite cores is $1/0.1 = 10$.

Step 2 — Worked example. A program takes 100 s single-threaded. 80% is parallelizable. With 8 cores: $S = 1/(0.2 + 0.8/8) = 1/0.3 \approx 3.33$. New time: $100/3.33 \approx 30$ s.

Step 3 — L1 bandwidth. A 3 GHz Intel Golden Cove (Alder Lake) core has two 32-byte load ports, giving 64 B/cycle L1 read bandwidth → $3 \times 10^9 \times 64 = 192$ GB/s per core. Older cores (Skylake client) have two 16-byte load ports → 32 B/cycle → 96 GB/s. DRAM bandwidth is shared across all cores and is much lower (typically 50–100 GB/s for dual-channel DDR4); see Memory Hierarchy for the full memory bandwidth picture and Interfaces and Buses for bus bandwidth.

Step 4 — Cache coherence. In a multicore system, the MESI protocol (Modified, Exclusive, Shared, Invalid) ensures that all cores see a consistent view of shared memory. Each cache line tracks its coherence state; a write by one core invalidates the line in other cores’ caches. See Memory Hierarchy.

Authoritative sources

• Computer Architecture: A Quantitative Approach (Hennessy & Patterson)

Step 1 — Hardware interrupts. External devices (timer, disk controller, network card) assert an interrupt request line. The CPU, at the end of the current instruction, acknowledges the interrupt: it saves the current state (IP, flags, registers) onto the kernel stack, looks up the handler address in the interrupt vector table (IVT), and jumps to the handler. On x86, the APIC (Advanced Programmable Interrupt Controller) routes and prioritizes interrupts; the IVT is a table of 256 entries (one per vector number).

Step 2 — Software exceptions. Certain instructions raise exceptions synchronously:

• Divide-by-zero (vector 0): div by zero.
• Invalid opcode (vector 6): illegal instruction.
• Page fault (vector 14): access to an unmapped virtual page. The OS loads the page from disk and resumes the instruction.
• General protection fault (vector 13): privilege violation (e.g., user-mode code writes to kernel memory).

Step 3 — Worked example: a timer interrupt.

1. The timer counts down and asserts IRQ0.
2. The APIC delivers vector 32 to the CPU.
3. The CPU finishes the current instruction, pushes IP and RFLAGS onto the kernel stack.
4. The CPU loads the handler address from IVT[32] into IP.
5. The handler (kernel code) increments a tick counter, checks if a process’s time slice expired, and may schedule another process.
6. The handler executes IRET (interrupt return): the CPU pops IP and RFLAGS, resuming the interrupted instruction.

Step 4 — Pipeline flush. An interrupt or exception flushes the pipeline: all in-flight (speculative) instructions in the ROB are discarded. The CPU restarts fetch from the handler address. This is the same mechanism as a branch misprediction flush, but triggered by an external event rather than a wrong prediction.

Step 5 — Relation to the OS. The operating system uses interrupts for: timer ticks (scheduling), I/O completion (disk, network), and system calls (a syscall instruction is essentially a controlled interrupt). See Operating System for how the OS uses these mechanisms for process scheduling, virtual memory, and I/O.

Authoritative sources

• Computer Architecture: A Quantitative Approach (Hennessy & Patterson)
• The RISC-V Reader

Ideal CPI: 1 (one instruction per cycle in a perfectly pipelined machine).

Branch frequency: 1 branch per 5 instructions → branch is $1/5 = 0.2$ of all instructions.

Misprediction penalty: 15 cycles (realistic for a 14–20 stage pipeline; the 15 in-flight instructions are flushed and the pipeline refills).

Average CPI: $1 + (1/5) \times 0.10 \times 15 = 1 + 0.30 = 1.30$ cycles per instruction.

Note: On a simple 5-stage teaching pipeline, the penalty would be only 1–2 cycles. Modern out-of-order CPUs have 14–20 stages, making the penalty 14–20 cycles. The 10% misprediction rate is optimistic; real workloads often see 2–5% with good predictors, but the penalty per misprediction is much higher.

A RISC-V CPU has a 5-stage pipeline with full forwarding. It executes the following code:

loop:
  lw   r1, 0(r2)       # load
  add  r1, r1, r3      # depends on lw
  sw   r1, 4(r2)       # depends on add
  add  r4, r5, r6      # independent
  bne  r4, r7, loop    # branch (predicted not-taken, 90% accurate)

The misprediction penalty is 4 cycles (for this simplified 5-stage pipeline). What is the approximate CPI?