Fetch-Execute Cycle

The problem

The von Neumann article sums up the control unit's job in one line: fetch an instruction, decode it, execute it, repeat. That line hides the details. Memory is a separate unit. The CPU cannot look into a drawer. It can only send an address out on one set of wires and wait for a word to come back on another.

This article opens up the CPU. Each phase of the cycle turns out to be a short list of register transfers: copy one register into another, or move one word between a register and memory. Once you can list those transfers, you can trace any program by hand.

Registers and buses

The CPU in Fig 1 has five registers. Each holds one 6 bit word.

Register	Holds
PC	Program counter. The address of the next instruction to fetch.
MAR	Memory address register. The address the CPU is about to read or write. Only MAR drives the address bus.
MDR	Memory data register. The word just read from memory, or the word about to be written. Only MDR connects to the data bus. Some books call it MBR, the memory buffer register.
IR	Instruction register. The instruction being decoded and executed. Some books call it CIR, the current instruction register.
ACC	Accumulator. The ALU's working value: the input and the result of each calculation.

Words move between the units on buses. A bus is a group of wires that carries one value at a time.

Bus	Carries	Direction
Address bus	An address, from MAR	CPU to memory only
Data bus	A word, to or from MDR	Both ways
Control bus	Signals such as read, write and the clock	Both ways
Internal bus	A word between registers inside the CPU	Inside the CPU

The width of the address bus sets how much memory the CPU can reach. Fig 1 has a 3 bit address bus, so it can name 2³ = 8 drawers. A 32 bit address bus can name 2³² locations.

The machine

Fig 1 runs a countdown. It outputs n, then n − 1, and so on down to 1, then stops. Press Play to watch it, Step to run one register transfer, or Cycle to finish the current instruction at once. Change n to change how many times the loop runs.

A word in transitInternal busAddress busData busControl busEvery transfer copies one word. A window flashes when its register is written. The active bus moves.

0 steps

n 2

Output so far: nothing yet

Memory, live. Green words are instructions, brown words are data. The filled address is the one in PC. The shaded slot is the drawer on the bus.

The machine is the one from the von Neumann article, with two more instructions. Opcodes 110 and 111 were unused there.

Opcode	Mnemonic	Effect
`001`	LOAD a	ACC ← M[a]
`010`	ADD a	ACC ← ACC + M[a]
`011`	STORE a	M[a] ← ACC
`100`	OUT a	Output ← M[a]
`101`	HALT	Stop
`110`	SUB a	ACC ← ACC − M[a]
`111`	JNZ a	If ACC ≠ 0, PC ← a

The countdown program:

Address	Word	Meaning
0	`001 111`	LOAD 7
1	`100 111`	OUT 7
2	`110 110`	SUB 6
3	`011 111`	STORE 7
4	`111 001`	JNZ 1
5	`101 000`	HALT
6	`000 001`	Data: the constant 1
7	`000 010`	Data: n = 2, the counter

Fetch

Every instruction cycle starts with the same three transfers, whatever the instruction turns out to be:

1. MAR ← PC 2. MDR ← M[MAR], PC ← PC + 1 3. IR ← MDR

Step 1 copies the address of the next instruction into MAR, because MAR is the only register wired to the address bus. In step 2 the control unit puts a read signal on the control bus. Memory finds the word at that address and returns it on the data bus into MDR. Step 3 moves the word into IR, which frees MDR for the execute phase.

PC goes up by 1 during the fetch, before the instruction is even decoded. So while an instruction runs, PC already points at the one after it. Most instructions leave PC alone, and the program runs in address order. A jump works by writing a new value into PC.

In a simple CPU each numbered step takes one tick of the clock. Steps written on the same line, like the read and the increment in step 2, happen in the same tick because they use different hardware.

Decode

The control unit splits IR into its fields. In this machine bits 5 to 3 are the opcode and bits 2 to 0 are the address, written IR[5:3] and IR[2:0]. The opcode selects which list of execute steps the control unit runs next. Nothing moves on any bus during decode.

Example. IR holds 110 110. The opcode 110 is SUB and the address 110 is 6, so the instruction is SUB 6. The control unit will read M[6] and have the ALU subtract it from ACC.

Execute

Each opcode has its own list of transfers. Here are the lists for this machine.

Instruction	Execute steps	Memory accesses
LOAD a	MAR ← IR[2:0]; MDR ← M[MAR]; ACC ← MDR	1 read
ADD a	MAR ← IR[2:0]; MDR ← M[MAR]; ACC ← ACC + MDR	1 read
SUB a	MAR ← IR[2:0]; MDR ← M[MAR]; ACC ← ACC − MDR	1 read
STORE a	MAR ← IR[2:0]; MDR ← ACC; M[MAR] ← MDR	1 write
OUT a	MAR ← IR[2:0]; MDR ← M[MAR]; Output ← MDR	1 read
JNZ a	if ACC ≠ 0: PC ← IR[2:0]	none
HALT	stop the cycle	none

The pattern repeats. Any instruction that touches memory first copies its address field into MAR, then reads into MDR or writes from MDR. A read leaves memory unchanged. A write replaces the old word. JNZ and HALT never touch memory: all they need is already inside the CPU.

Jumps and loops

The fetch phase does not know about programs or loops. It reads whatever address is in PC. That one rule is enough to build a loop: JNZ 1 at address 4 writes 1 into PC, so the next fetch reads address 1 again instead of address 5.

JNZ is a conditional jump. The control unit looks at ACC during execute and only writes PC when ACC is not zero. In the countdown, SUB 6 lowers ACC by 1 each time round. When it reaches 0 the jump is skipped, PC keeps the value 5 it got during the fetch, and the next instruction is HALT.

Trace table

A trace table records the registers after each instruction cycle. Here is the countdown with n = 2.

Cycle	PC at fetch	IR	Instruction	PC after	ACC after	M[7] after	Output
1	0	`001 111`	LOAD 7	1	2	2
2	1	`100 111`	OUT 7	2	2	2	2
3	2	`110 110`	SUB 6	3	1	2
4	3	`011 111`	STORE 7	4	1	1
5	4	`111 001`	JNZ 1	1	1	1
6	1	`100 111`	OUT 7	2	1	1	1
7	2	`110 110`	SUB 6	3	0	1
8	3	`011 111`	STORE 7	4	0	0
9	4	`111 001`	JNZ 1	5	0	0
10	5	`101 000`	HALT	6	0	0

Ten instruction cycles make 10 fetches. The execute phases add 5 reads (LOAD once, OUT twice, SUB twice) and 2 writes (STORE twice), so the program uses the bus to memory 17 times. More than half of that traffic is instruction fetches, which is the von Neumann bottleneck again.

Interrupts

A real CPU adds one more check at the end of every cycle: has a device asked for attention, for example a key press or a finished disk read? If an interrupt is waiting, the CPU saves PC and the other registers, then loads PC with the address of an interrupt handler. The next fetch runs the handler. When the handler finishes, the saved values are restored and the interrupted program carries on from where it stopped. The cycle itself does not change. Only the value in PC does.

Check your understanding

Set n = 3. Before pressing Play, write the trace table. How many instruction cycles and how many memory accesses does it take? Run it and compare.
List the register transfers for ADD 6, from the first fetch step to the end of execute. Which ones use the address bus?
Why does the fetch copy PC into MAR instead of putting PC straight on the address bus?
Address 4 is changed to 111 010 (JNZ 2). What does the program output for n = 2? Does it still stop?
Suppose PC were incremented at the end of execute instead of during fetch. What would go wrong with JNZ 1?

Summary

Fetch: MAR ← PC; MDR ← M[MAR] and PC ← PC + 1; IR ← MDR. Every instruction starts this way.
Decode: the control unit splits IR into opcode and address. The opcode picks the execute steps.
Execute: memory instructions copy the address into MAR, then read into MDR or write from MDR.
The address bus carries addresses from MAR, the data bus carries words to and from MDR, and the control bus carries read and write signals.
PC always names the next instruction. A jump is just an instruction that writes PC.