The Fetch-Decode-Execute Cycle

The fetch-decode-execute cycle (sometimes called the instruction cycle) is the fundamental control loop of a processor built on the Stored-Program Computer architecture. In that architecture, instructions and data live together in one memory, encoded as bit patterns with no external tag distinguishing "this is code" from "this is a number." The processor imposes meaning on these bits by treating a special hardware register, the program counter (PC), as the sole source of truth about what to do next. The PC holds the memory address of the instruction that will be fetched in the current cycle. The cycle has three logical phases, executed in order for every single instruction. Fetch: the processor reads the memory word at the address held in the PC and loads it into an internal register (often called the instruction register, IR). Decode: the processor examines the bit pattern of the fetched instruction, splitting it into an opcode (which operation to perform) and operand fields (which registers, memory addresses, or immediate constants are involved), consulting the rules defined by the Instruction Set Architecture as a Contract. Execute: the processor performs the operation the decoded instruction specifies — an arithmetic computation, a memory load or store, or a change of control flow — and, as part of this, updates the PC so the next iteration fetches the correct instruction. The crucial subtlety is that PC update is not an afterthought bolted onto the end — it is part of execute, because some instructions (branches, jumps, calls, returns) redirect control flow by writing an address other than "PC + instruction size" into the PC. Ordinary instructions like additions or loads leave control flow unchanged, so their execute phase implicitly advances the PC by the width of one instruction. This single mechanism — a mutable PC read at the start of each cycle and rewritten at the end — is what gives programs sequencing, loops, conditionals, and function calls, all without any change to the underlying loop structure.

The cycle can be described precisely as an unbounded loop with a fixed body. The pseudocode below models a simple, non-pipelined processor with a register file, a data/instruction memory, and a PC register. It captures the semantics common to essentially all instruction sets, from a toy accumulator machine to RISC-V or ARM. ``` // State: // PC : program counter register (holds a memory address) // Regs[0..N-1]: general-purpose register file // Mem[0..M-1] : unified memory holding instructions and data // IR : instruction register (holds the fetched instruction word) // running : boolean flag, false once a HALT is executed initialize PC to the address of the program's first instruction running <- true while running: // ---- FETCH ---- IR <- Mem[PC] // read instruction word at address PC next_PC <- PC + INSTR_SIZE // default: move to the next instruction // ---- DECODE ---- opcode <- extract_opcode(IR) operands <- extract_operands(IR) // register numbers, immediates, addresses // ---- EXECUTE ---- switch opcode: case ADD: rd, rs1, rs2 <- operands Regs[rd] <- Regs[rs1] + Regs[rs2] case LOAD: rd, base, offset <- operands addr <- Regs[base] + offset Regs[rd] <- Mem[addr] case STORE: rs, base, offset <- operands addr <- Regs[base] + offset Mem[addr] <- Regs[rs] case BEQ: // branch if equal rs1, rs2, target <- operands if Regs[rs1] == Regs[rs2]: next_PC <- target // override default PC update case JUMP: target <- operands next_PC <- target // unconditional redirect case HALT: running <- false default: trigger_illegal_instruction_fault() // ---- ADVANCE ---- PC <- next_PC ``` Two design points deserve emphasis because they are the source of almost every subtlety in real processors. First, `next_PC` is computed as a default (PC + instruction size) before decode is even finished, and it is overridden only by instructions that explicitly redirect control flow. This mirrors real hardware: an incrementer sits next to the PC register and always computes "PC + 4" (for a 4-byte instruction width) speculatively, while a multiplexer downstream decides whether to keep that value or replace it with a branch/jump target. Second, decode does not "look up what a MIPS or x86 instruction means" abstractly — it applies a fixed, mechanical mapping from bit-field positions to meaning, defined once and for all by the instruction set. The processor performs no reasoning; it performs table lookup and field extraction at circuit speed.

Time. Each iteration of the loop executes exactly one instruction, so running a program of $I$ dynamically-executed instructions takes $\Theta(I)$ cycle-iterations under this simple model, where each iteration itself takes constant time (assuming constant-time memory access and fixed-width ALU operations). This gives a total instruction-count-proportional running time — the familiar statement "runtime is proportional to instructions executed," which is why instruction count and clocks-per-instruction (CPI) are the two levers architects manipulate. Real memories are not constant-time (cache misses, DRAM latency), which is precisely why memory hierarchies exist, but that is a refinement layered on top of, not a contradiction of, this model.

Space. The cycle itself needs only a handful of fixed-size registers — PC, IR, and the register file — independent of program size, i.e., $O(1)$ additional control state beyond the memory that already holds the program and data. This is the architectural payoff of the stored-program idea: control logic does not grow with program size, because the program's instructions themselves live in the same address space the PC walks over.

Correctness. The argument is an invariant proof, the natural mode of reasoning for a control loop that runs forever (or until HALT). Define the invariant: > Invariant. At the start of every iteration, `PC` holds the memory address of the instruction that the programmer/compiler intends to execute next, given the program's control-flow semantics and all side effects of previously executed instructions. Base case. Before the first iteration, PC is initialized to the program's entry point by convention (e.g., address of `main`, or a reset vector) — the invariant holds trivially. Inductive step. Assume the invariant holds at the start of iteration $k$. Fetch reads `Mem[PC]`, which by the invariant is exactly the intended next instruction, into IR — no other address is ever consulted. Decode is a pure, deterministic function of IR's bits (defined by the ISA), so it recovers the unique intended opcode and operands, introducing no error as long as IR's bit layout matches the ISA specification. Execute performs the specified operation and computes `next_PC`: for non-control instructions this is `PC + INSTR_SIZE`, which is correct because sequential execution semantics say "do the next instruction in memory order"; for control instructions (branch/jump/call/return) `next_PC` is set to the address the ISA defines as the target under the current register/condition state, which is correct because that is the definition of what those instructions mean. Either way, at the end of the iteration, `PC <- next_PC` restores the invariant for iteration $k+1$. Termination / conclusion. By induction the invariant holds for every iteration the loop performs; the loop faithfully executes the intended program until `HALT` sets `running` to false (or, in real hardware, until an external interrupt or reset intervenes). Because decode and execute are pure functions of `IR` and the visible architectural state, the entire cycle is deterministic given a deterministic program and inputs — a property essential for debugging, testing, and formal verification of both software and hardware.

Honesty about tradeoffs. This model is intentionally the simplest correct description of instruction execution — it is not how modern high-performance CPUs are physically built. Real cores overlap fetch/decode/execute of different instructions (pipelining), execute several instructions per cycle (superscalar issue), reorder instructions around stalls (out-of-order execution), and guess branch outcomes before they're known (speculative execution with branch prediction). All of these techniques preserve the logical one-instruction-at-a-time semantics described here — a correct pipelined CPU must produce results identical to this simple sequential model — while achieving far higher throughput. The fetch-decode-execute cycle is therefore best understood as the specification that faster hardware implementations are obligated to honor, not a description of transistor-level timing in a modern chip.

Consider a tiny register machine with 4-byte instructions, registers `R0`–`R3` initialized to zero except where noted, and this program stored starting at address `0x00`:

Trace the cycle, PC starting at `0x00`:

Two things this trace makes concrete. First, at iteration 3 the default next PC would have been `0x0C`, but because R1 ≠ R2 the branch's condition failed, so the default was kept — the mux in the diagram passed through the "PC+size" path. Had R1 equaled R2, `next_PC` would instead have become `0x18`, and the program would have executed the `ADDI R3,R0,99` instruction and produced R3 = 99, never reaching address `0x0C` at all. Second, at iteration 5 the jump unconditionally overrides the default, deliberately skipping address `0x14`'s `HALT` so the program reaches the intended termination at `0x1C` with `R3 = 8`. The final architectural state is `R1=5, R2=3, R3=8`, PC halted at `0x1C` — exactly what the sequential, invariant-preserving reasoning above predicts.

The fetch-decode-execute cycle is not attributed to one inventor; it crystallized as engineers turned the abstract stored-program idea into working machines with control units that had to physically sequence operations.

Every general-purpose CPU — x86 chips in laptops and servers, ARM cores in phones and tablets, RISC-V cores in embedded devices and open-source silicon — implements a fetch-decode-execute loop as its architectural contract, even while its physical pipeline overlaps stages across many instructions simultaneously. Compilers generate code assuming this exact sequential semantics; debuggers single-step by literally pausing after one iteration of the loop; and formal hardware verification tools check that a complex pipelined implementation is equivalent to this simple sequential specification for every possible instruction stream. Microcontrollers in cars, thermostats, and industrial equipment run the identical loop at kilohertz-to-megahertz speeds, proving the idea scales down as gracefully as it scales up to gigahertz server chips. Understanding this cycle is the prerequisite for the next layers of computer architecture: how an Instruction Set Architecture as a Contract precisely defines what "decode" and "execute" must mean for every opcode, and how The Single-Cycle Datapath wires registers, ALUs, memories, and multiplexers together so that fetch, decode, and execute happen as one physical circuit traversed once per clock tick.

Ask the tutor: How does pipelining overlap fetch, decode, and execute across multiple instructions while still preserving this cycle's sequential correctness guarantee?