The Fetch-Decode-Execute Cycle

Overview

A CPU does one thing, over and over, billions of times a second: it fetches an instruction from memory, decodes it, and executes it. This worksheet brings together everything from the earlier CPU worksheets, the registers, the buses, the control unit and the ALU, and runs real programs on a simulated CPU one register transfer at a time. You will trace programs by hand, check your traces against the simulator, and write a short program of your own. Work through the tasks in order and try each question before checking.

Learning Objectives

By the end of this lab you will be able to:

Describe each step of the fetch-decode-execute cycle in register transfer notation
Explain the role of the PC, MAR, MDR, CIR and ACC at each step
Complete a trace table for a short program
Explain how jump instructions and the Z flag create loops
Write and test a short machine code program
Explain how clock speed and the Von Neumann bottleneck affect performance

Concept

The programs in this worksheet use the same small instruction set as the Control Unit worksheet. Each instruction is 8 bits: a 4-bit opcode and a 4-bit operand that holds an address.

Opcode	Mnemonic	What it does
`0001`	`LOAD n`	Copy the value at address n into the ACC
`0010`	`STORE n`	Copy the value in the ACC into address n
`0011`	`ADD n`	Add the value at address n to the ACC
`0100`	`SUB n`	Subtract the value at address n from the ACC
`0101`	`JMP n`	Jump: carry on from address n
`0110`	`JZ n`	Jump to address n, but only if the Z flag is 1
`0000`	`HALT`	Stop the program

The cycle has three stages.

Fetch. Copy the next instruction from memory into the CIR, and move the PC on to the instruction after it.
Decode. The control unit splits the instruction into its opcode and operand and works out what to do.
Execute. The control unit sends the signals that carry out the instruction. This might read memory, use the ALU, write memory or change the PC.

Then the cycle starts again with the next fetch, and keeps going until a HALT instruction.

Tasks

Task 1 - The cycle at a glance

Every instruction starts with the same four fetch steps and a decode step. Only the execute steps differ. The wheel below shows the steps for one instruction at a time. Choose an instruction, then step or play round the cycle and compare the execute steps of LOAD, ADD, STORE and JMP.

Here is the fetch stage written in register transfer notation. Remember that square brackets mean "the contents of".

\begin{array}{ll} 1. & \text{MAR} \leftarrow [\text{PC}] \\ 2. & \text{MDR} \leftarrow [\text{Memory}[\text{MAR}]] \\ 3. & \text{PC} \leftarrow [\text{PC}] + 1 \\ 4. & \text{CIR} \leftarrow [\text{MDR}] \end{array}

The fetch stage takes register transfers.

LOAD, ADD and STORE each have execute steps, but JMP has only .

The execute stage of STORE copies the ACC into the and then writes it to memory.

Why is the PC incremented during the fetch stage, before the instruction has even been decoded?

Once the instruction’s address has been copied into the MAR, the PC is not needed for this instruction any more. Incrementing it straight away means it already points at the next instruction, so the next fetch can start as soon as this instruction finishes. A jump instruction can still overwrite the PC during its execute stage if it needs to.

Task 2 - Watch a program run

The simulator below is the CPU from the Registers worksheet, with a control unit, ALU and flags. Memory holds the program Add two numbers.

0: LOAD 5     put the value at address 5 into the ACC
1: ADD 6      add the value at address 6 to it
2: STORE 7    store the result at address 7
3: HALT
5: 3   6: 4   7: 0

Press Step to perform one register transfer at a time. Each time, a value travels along the bus that is used and the register it lands in turns gold. Signals the control unit switches on light up in the CU. Every step is recorded in the trace table under the diagram. Step through the whole of LOAD 5 before answering the questions, then use Next instruction or Run to finish the program.

After step 1 (MAR ← [PC]) the MAR holds .

After step 2 the MDR holds , the instruction LOAD 5.

After step 3 the PC holds .

During the execute stage of LOAD 5, the MAR is set to , and the value arrives in the MDR and is copied to the ACC.

LOAD 5 takes steps in total, from the first fetch step to the end of its execute stage.

When the program halts, address 7 holds .

Task 3 - Trace the program

A trace table records the values of registers and memory as a program runs. Complete this one for the Add two numbers program, showing the values after each instruction has finished. Work it out on paper first, then check with the simulator in Task 2 (press Reset, then Next instruction four times).

After	PC	CIR	ACC	Address 7
LOAD 5	a	LOAD 5	b	0
ADD 6	c	ADD 6	d	0
STORE 7	e	STORE 7	f	g
HALT	h	HALT	i	j

After LOAD 5: PC (a) = , ACC (b) =

After ADD 6: PC (c) = , ACC (d) =

After STORE 7: PC (e) = , ACC (f) = , address 7 (g) =

After HALT: PC (h) = , ACC (i) = , address 7 (j) =

After HALT the PC holds 4, but there is no instruction at address 4. Why is that not a problem?

The PC was incremented during the fetch of HALT, before the instruction was decoded. HALT then stops the cycle, so the CPU never goes on to fetch from address 4.

Task 4 - Jumps and loops

Programs need to repeat things. A jump instruction does this by changing the PC, so the next fetch comes from a different address. JMP n always jumps. JZ n only jumps if the Z flag is 1, which means the last ALU result was zero.

The simulator below starts with Multiply 4 × 3. There is no multiply instruction, so the program adds 4 to a running total three times, counting down each time.

0: LOAD 15    total
1: ADD 13     total + 4
2: STORE 15   save the new total
3: LOAD 14    count
4: SUB 12     count - 1
5: STORE 14   save the new count
6: JZ 8       if the count is now 0, finish
7: JMP 0      otherwise go round again
8: HALT
12: 1   13: 4   14: 3 (the count)   15: 0 (the total)

Before you run it, predict what address 15 will hold at the end. Then press Run (try the Fast speed) and watch the PC jump back from 7 to 0.

At the end, address 15 holds and address 14 holds .

The instructions at addresses 0 to 7 run times, except JMP 0, which runs times.

The program runs instructions in total before it halts.

The loop ends when SUB 12 makes the count 0, which sets the flag to 1.

Explain how JZ 8 changes the PC on the last time round the loop, and why the program would never stop without it.

On the last time round, SUB 12 takes the count from 1 to 0, so the ALU sets Z to 1. When JZ 8 executes, Z is 1, so the operand 8 is copied into the PC and the next fetch is HALT at address 8. Without JZ, JMP 0 would always send the PC back to 0, so the loop would repeat forever.

Task 5 - Write your own program

You can change memory in either simulator by clicking a memory row. Type an instruction such as SUB 9, or a number from 0 to 255, then press Set.

First, a prediction. In the Task 2 simulator, change address 6 from 4 to 10 (choose the Add two numbers program and press Reset first if you have run it). Predict what address 7 will hold, then run it to check.

With address 6 changed to 10, address 7 ends up holding .

Now write a program of your own. It should work out 9 − 4 and store the answer at address 10. Put your instructions at addresses 0 upwards, end them with HALT, and store the numbers 9 and 4 at addresses of your choice after the program. Test it in a simulator and check that address 10 holds 5.

Write out your program, one memory location per line, in the form address: contents.

0: LOAD 8
1: SUB 9
2: STORE 10
3: HALT
8: 9
9: 4

Any addresses after the program can hold the 9 and the 4, as long as the LOAD and SUB operands point to them. After it runs, address 10 holds 5.

Task 6 - The cycle and performance

Look back at the trace table from Task 2. Only some steps use the buses to memory. These are the steps where the CPU has to wait for the slow trip out to memory and back.

Instruction	Steps that use the buses to memory
LOAD n	Fetch the instruction (step 2) and read the data (step 7)
ADD n	Fetch the instruction (step 2) and read the data (step 7)
STORE n	Fetch the instruction (step 2) and write the data (step 8)
JMP n	Fetch the instruction only (step 2)

Every step of the cycle takes one clock tick. What happens to a program’s running time if the clock speed is doubled?

A. It halves, as long as memory can keep up B. It doubles C. It stays the same D. The program runs twice

Each tick takes half as long, so every step finishes in half the time. In a real computer this only works if memory can supply instructions and data that fast.

Why do LOAD, ADD and STORE each have to use the bus to memory twice?

A. Once to fetch the instruction and once to read or write its data B. Once for the opcode and once for the operand C. The bus can only carry 4 bits at a time D. Memory has to be read twice to be sure the value is right

The instruction and its data both live in main memory and share one bus. That second trip is the Von Neumann bottleneck at work.

In the Von Neumann Architecture worksheet, the Harvard machine was faster because it could fetch one instruction while moving data for another. Using the steps of the cycle, explain why this simulated CPU cannot do that.

This CPU has one memory and one set of buses for both instructions and data. During the execute stage of LOAD or ADD, the address and data buses are busy reading the data. The next fetch needs those same buses to read the next instruction, so it has to wait until the execute stage has finished.