Translated from: http://www.suppertime.co.uk/blogmywiki/2020/06/improved-microbit-cpu/
In the first version of the micro:bit CPU (programmed with MakeCode), there were only four very basic instructions, but it resembled the microprocessors used in many early home computers, such as the Altair 8800, Commodore Kim-1, and Cambridge Science’s MK14:
-
It was programmed without using high-level languages like MakeCode, Scratch, Python, or BASIC, but rather with binary code instructions.
-
Each binary code represented an instruction, an instruction with additional data, or just data.
-
As the program ran, the CPU fetched each instruction sequentially from memory.
-
Then it parsed the instruction.
-
The CPU executed that instruction.
-
It tracked its position in the program with a program counter, incrementing the counter by 1 each time it needed to fetch a new instruction.
-
It continuously fetched, decoded, and executed instructions in order until it reached a halt instruction.
In reality, our simple CPU could only add two numbers and display the answer in binary using an LED. It was merely a calculator, but not a very good one, as it couldn’t subtract, multiply, or divide.
Due to the way the instructions were designed, it was limited to four instructions:
The instruction was limited to 5 bits of binary instead of the 8 bits commonly used in earlier computer systems because I wanted to fit the content of the instruction on one line of the micro:bit’s LED display, where lit LEDs represent 1 and unlit LEDs represent 0.
The operands (data, in this case, addresses) are stored in the last 3 bits of the instruction, leaving only the first two bits to encode the actual instruction.
This is obviously not a good idea, but if I still wanted to keep the 5-bit instruction for display, I needed to separate the operand from the opcode, which is what version 2 of the micro:bit CPU project does.
NewCPUInstructions
In the new design, when the CPU fetches and decodes an instruction that requires an operand (some data or an address where data can be found), it interprets the next address in memory as data rather than an instruction. It does this by reading its contents and incrementing the program counter by 2 instead of 1.
Now we have 5 complete bits to encode the instruction, giving us 31 instructions instead of just 4. Strictly speaking, there could be 32 instructions, but I decided to make 00000 a no-operation opcode, which is an empty instruction.
31 instructions sound like a lot, but even early 8-bit processors (like the 6502 used in early home computers) had over 100 instructions. To keep this project simple while still achieving some useful functions, I decided to use the minimum number of instructions to implement a simple multiplication algorithm:
The algorithm turns multiplying 6 (stored in variable x) by 7 (stored in variable y) into adding 6 seven times, decrementing from y each time, and stopping the loop when y reaches zero, displaying the answer on the LED output.
For this algorithm to work on the micro:bit CPU, it needs the ability to decrement the variable by 1. Decrementing a variable is called decrementing. As we will see, incrementing and decrementing numbers is very useful when performing repetitive tasks.
However, our original algorithm lacked two functionalities:
-
Looping functionality.
-
Conditional branching functionality — exiting the loop when y is zero.
The second point is the ability to change the execution code based on the computation result, which is fundamental to making a computer a computer and not just an adder. This branching capability (taking different paths through the instruction set) is also what distinguishes Charles Babbage’s analytical engine from the simpler difference engine and theoretically makes the analytical engine (though never built) a universal computer.
For simplicity, I decided to combine the looping and exiting functionality into one instruction: “jump if not zero”.
When any decrement instruction results in 0, a flag is set. The microprocessor uses memory to store several flags: these are single bits used to record reaching zero (zero flag), becoming negative (negative flag), or exceeding a number that can be stored in a word (carry flag).
Our new CPU program uses the variable zeroFlag as the zero flag. This is a boolean variable, meaning it can only have two values: true or false, 1 or 0.
This is the new instruction set:
I could have added some registers or a stack to store data, which might be done in future versions, but for simplicity, I only made one accumulator A. You can store numbers in it or add numbers to it, and you can also increment or decrement the contents of memory locations, so you can effectively use any number of memory locations as variables or registers.
When developing this program, I might add the ability to subtract numbers from the accumulator, as well as the ability to store the accumulator in memory locations and directly store and add numbers.
We didn’t use all the above instructions in the multiplication program. Below is the program that implements 5 multiplied by 6 by adding 5 six times:
It places the number 5 in the accumulator. It looks up the number 5 in the storage location specified in the next memory position: telling the CPU to get the number from storage location 8.
Next, it decrements the contents of location 9 by 1. This tracks how many 5’s we have added.
If the zero flag is not set, the instruction in memory location 4 tells it to jump back to location 0. It will continue doing this until the zero flag is set when memory location 9 reaches zero.
Next, it outputs the result (i.e., the number in the accumulator) as a binary number using the LEDs in the bottom row of the display. Then it reaches the HALT instruction, stopping the decoding and execution of any further instructions or data.
What is the clock speed?
My micro:bit CPU does not use a clock to fetch instructions; instead, it relies on you pressing button B to step through the program. Pressing button A puts the CPU in execution mode, so it not only shows the memory content on the first row of LEDs but also executes any instructions.
You can simulate running it in the MakeCode simulator. Press button A to enter program execution mode, and after starting, you will hear a high pitch. Continue pressing button B, and you will see it loop at the same position — each time adding 5 to the accumulator and decrementing storage location 9 by 1. Adding 5 six times gives 5 x 6 = 30. When storage location 9 reaches 0, it displays the result of 5 x 6 in binary on the next line of the display and emits a low sound when it reaches the halt instruction.
You can keep pressing button B, but the program will not execute — the program running indicator will go out, and it will no longer decode or execute any instructions.
Below is its code — a rather complex program, but I tried to use functions wherever possible to make it easier to understand.
Scan the QR code or visit the link below to run the program online.
https://makecode.microbit.org/#pub:_97wd4uWiJfDD