A tiny processor

Classroom resources

Load these into Waypoints Prepare: choose Load URL and paste the copied address, or download the file and import it. In Prepare, the worksheet's Teacher edition shows the answers; the student copy hides them.

• Slides Download Copy address for Prepare Present from the browser, or export to PowerPoint or PDF.
• Worksheet Download Copy address for Prepare Print the student copy; the Teacher edition has the answers.

Students will be able to

• I can describe the fetch, decode and execute cycle.
• I can say what the program counter and accumulator hold.
• I can explain that instructions are numbers stored in memory.
• I can write a short program for a tiny processor.

Timing

Predict and Try 8 min · Worked example 12 min · Vary 14 min · Practise and Make 16 min

Before class

Try the boards yourself. The instruction set is deliberately tiny: HALT, LOAD, ADD, SUB, STORE, JUMP, JZ (jump if zero) and OUT. Each instruction is a number: operation × 16 + address, so LOAD 6 is 22. Numbers wrap at 256.

The one idea: a processor repeats one cycle: fetch the instruction the program counter points at, decode it, execute it, one step per clock tick. The program is numbers in the same memory as the data (the stored-program idea).

Simplifications: one register (the accumulator), 16 cells, three ticks per instruction. Real processors overlap the steps (pipelining) and have many registers. It is similar in spirit to the Little Man Computer, which some teachers will know.

Running the lesson

1. Predict: students who said 53 are joining digits, not adding.
2. Try: ask what PC shows just after a fetch, and why it is already one ahead.
3. Worked example: model the three ticks for LOAD 6 aloud.
4. Vary: in the loop, ask which instruction makes it repeat and which one stops it.
5. Make: collect programs: who used the fewest cells?

The hard part (on purpose)

Writing the Make program from an empty memory is the hard part. Have students write the outputs they want first, then the instruction before each OUT.

When students get stuck

Answers to the checks

1. what will it output?: Memory holds: cell 0 LOAD 6, cell 1 ADD 7, cell 2 OUT, cell 3 HALT, cell 6 = 5, cell 7 = 3. What does the program output?
   8: load 5, add 3, output the accumulator, stop.
2. Try: tick by tick: Press Clock tick (or Whole instruction) until it halts. Watch the PC, the instruction register and the accumulator.
   
   Four instructions, three ticks each: 12 clock ticks to output 8.
3. LOAD 6, tick by tick: Each instruction takes three clock ticks. How many ticks does the whole program (LOAD, ADD, OUT, HALT) take?
   12
   4 instructions × 3 ticks = 12.
4. Find the mistake: Sam explains the memory. Click the line where it first goes wrong.
   line 3
   Line 3: instructions are numbers, kept in the same memory as the data. If the PC ever reached cell 6, the processor would run 5 as an instruction.
5. Clock speed: A processor runs at 3 GHz. About how many clock ticks is that each second?
   3 billion
   3 GHz is 3 billion ticks a second, so this 12-tick program would take 4 billionths of a second.
6. Change the data: Change one data cell so the program outputs 12. Type in the cell, then run it.
   
   For example cell 7 = 7: 5 + 7 = 12. Same program, different data.
7. Change an instruction: Change one instruction so the program outputs 5 − 3.
   
   ADD 7 becomes SUB 7. One number in memory changed what the program does.
8. Store the answer: This program stores its answer. Run it: what ends up in cell 9?
   
   STORE 9 copies the accumulator into cell 9: the answer is kept in memory for later.
9. A loop: This program counts down from 3 using JUMP and JZ. Make it count down from 5.
   
   Change cell 12 to 5. JUMP 1 sends the PC back to repeat; JZ 5 leaves the loop when the accumulator reaches 0.
10. The PC: The PC is 4. The processor fetches. What is the PC afterwards (if the instruction isn't a jump)?
    5
    Fetch copies the instruction and adds 1 to the PC.
11. Loops: Which instruction lets a program repeat steps?
    JUMP: it changes the PC to an earlier cell
    A jump back makes a loop; a JZ (jump if zero) can leave it.
12. Review: adding: Review: ADD 7 adds two 8-bit numbers. What inside the processor does the adding?
    A row of full adders, made of gates
    Eight full adders side by side, as in Adding with gates.
13. write a program: Memory is empty except cell 15, which holds 2. Write a program that outputs 2, 4, 6 and then halts.
    
    You wrote machine code: the numbers in cells 0 to 6 are the program. Every app ends up as instructions like these.

Solutions

One possible solution for each task. Other correct programs are fine.

Vary: change the program › Change the data

Open task: any program that does what the step asks.

Vary: change the program › Change an instruction

Open task: any program that does what the step asks.

Vary: change the program › Store the answer

Open task: any program that does what the step asks.

Vary: change the program › A loop

Open task: any program that does what the step asks.

write a program

Open task: any program that does what the step asks.

Stretch and support

Stretch: Write a program that multiplies 3 by 4 using a loop of ADDs. How many clock ticks does it take?

Support: An instruction card: each instruction, what it does, and an example.

Exit ticket

Name the three steps a processor repeats, and say what the program counter does.

Fetch, decode, execute. The program counter holds the cell of the next instruction and goes up by one after each fetch (or jumps).

What each step is for

• what will it output?: Committing to the program's output tests the new move: the processor works through the cells one instruction at a time.
• Try: tick by tick: Ticking through the program settles the prediction and shows the new move: each instruction is fetched, decoded and executed in turn.
• Worked example: one instruction, three ticks: Tracing LOAD 6 through fetch, decode and execute models the new move. Sam keeps instructions and numbers apart, the misconception planted after the method.
• Vary: change the program: Each task changes one thing: a data cell, then one instruction, then STORE instead of OUT, then the start of a loop.
• the cycle: Reasoning about the cycle without the board is the same move in mixed forms, plus a review of adders.
• write a program: Writing a program from an empty memory reverses the process: from the outputs wanted to the instructions that make them.

Where it leads

Links: Inside a computer: 3 GHz means about 3 billion clock ticks a second, and each core is a processor like this (much bigger). Code pathway: the Python and MakeCode programs students write are turned into instructions like these.