Part II · Chapter 6

Fetch, Decode, Execute

In the last chapter, each press of "Step" ran a whole instruction as if by magic. Now we open the control unit and slow the clock right down. You'll see that every instruction is really a short sequence of clock ticks, and that each tick does something very simple: it moves one byte from one place to another.

The control unit is often described as the processor's "brain", which makes it sound mysterious. It isn't. By the end of this chapter you'll see that it's little more than a lookup table and a small counter, built entirely from parts we already know.

A closer look inside Tiny-8

To watch an instruction happen, we need to see every register, including three that stayed hidden in Chapter 5:

MAR, the memory address register. Memory always works on the address in the MAR. To read or write a byte, the processor first puts its address here.
IR, the instruction register. It holds the instruction currently being carried out, so the control unit can keep looking at it while the work happens.
B, a second input for the ALU. The ALU always works on A and B, and continuously shows A + B (or A − B) on its output.

All the parts are connected to one shared bus: 8 wires that every part can talk on, or listen to. Only one part may talk at a time, or their signals would collide. But any number of parts may listen. Each part connects to the bus through a special gate, a tri-state buffer, that can either pass the part's value onto the bus or disconnect it completely.

Control signals

Every part has a couple of control wires. One says "put your value on the bus" (talk). The other says "load the value from the bus at the next clock edge" (listen). That second one is just the LOAD signal from the registers in Chapter 4. Tiny-8 has 16 control wires in total, and each one is shown as a light in the simulator's control unit:

Signal	Meaning
PC → bus	The program counter talks.
bus → PC	The program counter loads from the bus (a jump).
PC + 1	The program counter counts up by one.
bus → MAR	The memory address register loads from the bus.
RAM → bus / bus → RAM	Memory reads the byte at the MAR's address onto the bus / writes the bus into it.
bus → IR / IR → bus	The instruction register loads a whole instruction / talks, sending just its operand (the low 4 bits).
A → bus / bus → A	The accumulator talks / listens.
bus → B	The ALU's second input listens.
ALU → bus	The ALU puts its answer on the bus.
SUB	The ALU subtracts instead of adding (the SUB wire from Chapter 2).
flags ←	The Z and C flags load from the ALU.
bus → OUT	The output display listens.
HALT	Stop the clock.

The control unit's entire job is this: on each clock tick, decide which of these wires to switch on. That's all "running an instruction" means.

Fetch: two ticks, every time

Every instruction begins the same way, with two ticks called T0 and T1:

T0: PC → bus and bus → MAR. The address of the next instruction travels from the program counter to the memory address register.
T1: RAM → bus, bus → IR and PC + 1. Memory sends the instruction byte to the instruction register. In the same tick, the program counter steps forward, ready for next time.

That's the fetch. Try it below: press Clock tick twice and watch the first instruction, LDA 14, travel into the IR. Blue marks the part that's talking on the bus; amber marks the parts that will listen at the next clock edge.

Press Clock tick to advance one clock edge, or Whole instruction to finish the current instruction. The lights in the control unit show which signals are on right now; they take effect when the clock ticks. The highlighted cell in the rule book below shows which step the control unit is on.

Decode: looking it up

After T1, the instruction sits in the IR. Now the control unit has to work out what to do next. It's simpler than it sounds. The control unit has a little step counter (T0, T1, T2…, just a counter from Chapter 4), and it feeds two things into a lookup table:

the opcode, the top 4 bits of the IR, and
the current step number.

Out of the table come the 16 control wires. That table is the rule book shown under the simulator: one row per instruction, one column per step. In hardware, it can be a small memory chip, a ROM (read-only memory), that's never written to. Its contents are called microcode. There's no separate "decode" tick: looking something up in a table is plain combinational logic, so the answer is ready as soon as the IR is.

Execute: a few more ticks

From T2 onwards, each instruction does its own thing. Here are three to step through in the simulator above:

LDA 14 takes two execute steps. T2: the IR sends its operand, 14, to the MAR. T3: memory sends the byte at address 14 into A.
ADD 15 takes three. T2: operand into the MAR. T3: the byte at address 15 goes into B, and the ALU instantly shows A + B. T4: the ALU puts the sum on the bus, A loads it, and the flags are updated.
OUT needs just one: T2, A talks and OUT listens.

Why does ADD need register B at all? Because the bus can only carry one value per tick. The ALU needs two numbers at once, A and the byte from memory, so the byte from memory is first parked in B. Every design decision in a processor is like this, a puzzle about what can travel where, and when.

When an instruction's last step is done, the step counter goes back to T0, and the next fetch begins. Fetch, decode, execute, repeat: forever, or until a HALT.

How a jump really works

A jump turns out to be the simplest instruction of all. JMP n has just one execute step: IR → bus and bus → PC. The operand is copied into the program counter, so the next fetch happens to come from somewhere else.

A conditional jump like JNZ is the same, with a twist: the flag is one more input to the control unit. If the flag says "jump", the two signals switch on as usual. If not, the control unit switches nothing on for that step, and the PC simply keeps pointing at the next instruction. A whole decision, in one gate's worth of logic.

This is the countdown program from Chapter 5. Use Whole instruction to move quickly, and slow down to single ticks when you reach JNZ 1. Compare a time when the jump is taken with the very last time, when Z = 1 and nothing happens. Keep an eye on the tick counter.

Counting ticks

Notice that Tiny-8 instructions take different numbers of ticks: 3 for OUT, LDI and the jumps, 4 for LDA and STA, and 5 for ADD and SUB. So clock speed alone doesn't tell you how fast a processor really is. You also need to know how many ticks its instructions take, a number called cycles per instruction (CPI).

The whole "add two numbers" program, for example, takes 4 + 5 + 3 + 3 = 15 ticks. If Tiny-8 ran at the IBM PC's 4.77 MHz, it would finish in about 3 microseconds.

Meanwhile, inside a real CPU

Real processors still fetch, decode and execute, but they've had 50 years to get clever about it:

The 8088 was microcoded, much like Tiny-8, but its instructions varied hugely in length. A register-to-register ADD took 3 clock ticks; a 16-bit MUL took well over 100.
Modern x86 chips translate each x86 instruction into one or more simple internal operations called micro-ops. A complicated instruction may become several micro-ops; a few rare, very complex ones still run from a microcode ROM. That microcode can even be updated: your operating system loads patches into the processor at startup to fix bugs found after the chip was made.
RISC-V was designed so that decoding is easy. Every instruction is the same length, and the register numbers always sit in the same bit positions, so simple hardwired logic can decode it without any microcode.
Overlap. Tiny-8 finishes one instruction before starting the next. Real processors work like an assembly line: while one instruction executes, the next is being decoded and the one after that is being fetched. Modern cores keep hundreds of instructions in flight and finish several per tick, a CPI below 1. That's the subject of Part IX.

Try it yourself

How many clock ticks does each of these take on Tiny-8: LDA, JMP, SUB, HLT?
Show answer
LDA: 4 (2 fetch + 2 execute). JMP: 3. SUB: 5. HLT: 3 (2 fetch + 1 step that stops the clock).
Why can't a single tick have both PC → bus and A → bus switched on?
Show answer
Two parts would be trying to put different values on the same 8 wires at once. That's a bus conflict, and the result would be garbage (on real hardware it can even damage the chip). Only one part may talk at a time.
During T1 of every instruction, the PC is incremented. Why is it safe to do that at the same moment the IR is loaded?
Show answer
Because all registers load on the same clock edge. Memory is reading from the address held in the MAR (copied from the PC back in T0), not from the PC itself, so changing the PC doesn't disturb the read.
In the countdown program, how many clock ticks does the whole run take? (Use the second simulator to check.)
Show answer
64. LDI takes 3 ticks. Then the loop (OUT, SUB, JNZ = 3 + 5 + 3 = 11 ticks) runs 5 times: 55 ticks. Finally OUT and HLT add 3 + 3. Total: 3 + 55 + 6 = 64.
Look at the rule book. Which execute step is identical in LDA, STA, ADD and SUB? Why?
Show answer
T2: IR → bus, bus → MAR. All four work with a byte in memory, so they all start by sending the operand address to the MAR.

What we learned

Inside, every part shares one bus: one part talks per tick, any number listen.
Control signals say who talks and who listens. Running an instruction just means switching the right signals on, tick by tick.
Fetch (T0, T1) is the same for every instruction: PC → MAR, then memory → IR, with PC + 1.
Decode is a lookup: opcode + step number → control signals. The table is microcode.
Execute takes one to three more ticks, depending on the instruction. A jump just loads the PC.
Instructions take different numbers of ticks, so cycles per instruction matter as much as clock speed.

Tiny-8 now holds no secrets: we've built it from switches all the way up. In the next chapter we'll leave our toy behind and look at how real instruction sets are designed: how x86-64 and RISC-V encode registers, numbers and memory addresses, and why their designers made such different choices.