The Instruction Cycle — Fetch, Decode, Execute
In one line
A CPU is a machine that endlessly repeats fetching one instruction from memory (fetch), working out what it means (decode), and actually carrying it out (execute).
Why this was needed
A program is ultimately a lump of numbers laid out in memory. Someone has to decide who reads these numbers, in what order, and what to do with them. The decisions made by the early designers have continued to this day, and the core is two things. First, instructions and data are kept in the same memory (the von Neumann architecture). Second, the address of the next instruction to execute is held in one register (the program counter).
Thanks to these two decisions, the CPU has to follow only one very simple rule. "Fetch the instruction from where the program counter points, execute it, and move the counter to the next one." Loops, function calls, and conditional branches are all nothing more than changing this counter value.
How it works
One cycle flows roughly like this.
- Fetch — read the instruction from the address the program counter points to and put it into the instruction register.
- Decode — look at the bit pattern and work out what operation it is and where the operands are.
- Execute — the arithmetic logic unit computes, accesses memory, or moves the counter elsewhere.
The problem is that if you do this strictly in sequence, most of the circuitry sits idle. While the decoder works, the fetch unit rests. What came out of this is the pipeline. Like sharing a washer and a dryer, while instruction 1 is being decoded, instruction 2 is fetched in advance. With 5 stages, throughput is in theory 5 times higher.
It is not free. A pipeline creates three kinds of hazards.
| Hazard | Situation | Response |
|---|---|---|
| Structural hazard | Two stages want the same circuit at the same time | Separate the resources, or delay one side |
| Data hazard | A later instruction needs the result of an earlier one | Forwarding, and if that is not possible, stall the pipeline |
| Control hazard | The result of a branch is not yet known | Branch prediction, and flush the pipeline if wrong |
The third is especially expensive. When a branch prediction misses, all the instructions already in progress must be discarded. The pipelines of modern CPUs can exceed 15 stages, so each miss wastes dozens of cycles. This is where the famous phenomenon comes from in which a loop over a sorted array is several times faster than over an unsorted one. When the condition is regular, the predictor guesses right.
What you see in the field
A metric you often see in performance measurement is IPC (instructions per cycle). Even at the same clock, double the IPC is double the speed. Conversely, if IPC comes out low, such as 0.3, it is a signal not that the CPU cannot compute but that it is waiting for something. Usually that something is memory.
So "100 percent CPU utilization" must not be read directly as "the execution units are 100 percent busy computing." A core can be in a non-idle state and still stall execution while waiting on the memory hierarchy, as with a cache miss. However, the time of a task sleeping on blocking I/O is normally not counted as that process's CPU time, so you have to distinguish memory latency from I/O wait.
What to check in the quiz that follows
Check whether you can explain on your own why a pipeline raises throughput yet cannot reduce the latency of a single instruction, and why a branch misprediction is expensive.