Euclid CPU

This is a record of the Instruction Set Architecture (ISA) of the CPU we designed together, inspired by the steps necessary to execute Euclid's Algorithm for finding the Greatest Common Divisor (GCD).

Registers

In addition to RAM, the CPU has the following registers.

TestThe 1-bit result of the last conditional.
IPThe Instruction Pointer, the address of the next instruction to be executed. Normally IP increments by 1 after each instruction, but it can be overriden by jumps.

Instruction format

31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
OP A B

OP is a 4-bit opcode chosen from the following. The A and B operands, if used by the operation indicated, are 14-bit addresses into memory; if unused, their values are irrelevant and they are present only to pad out all instructions to the same length (32 bits).

CodeAssemblyComment
0000SUB A BCompute A-B and store the result in A.
0001ZERO AIf A=0, set the Test register to 1; otherwise, set Test to 0.
0010GT A BIf A>B, set the Test register to 1; otherwise, set Test to 0.
0011MOVE A BCopy the value of B into A.
0100GOTO ASet the IP to the address A.
0101CGOTO AIf Test=1, set the IP to the address A; otherwise, increment IP as normal.
0110HALTStop executing new instructions.

Euclid's algorithm

LabelAssemblyBinaryHex
top:ZERO m0001 00000000001110 0000000000000010038000
CGOTO gcdn0101 00000000001000 0000000000000050020000
ZERO n0001 00000000001111 000000000000001003C000
CGOTO gcdm0101 00000000001010 0000000000000050028000
GT m n0010 00000000001110 000000000011112003800F
CGOTO mgtn0101 00000000001100 0000000000000050030000
SUB n m0000 00000000001111 000000000011100003C00E
GOTO top0100 00000000000000 0000000000000040000000
gcdn:MOVE gcd n0011 00000000010000 000000000011113004000F
HALT0110 00000000000000 0000000000000060000000
gcdm:MOVE gcd m0011 00000000010000 000000000011103004000E
HALT0110 00000000000000 0000000000000060000000
mgtn:SUB m n0000 00000000001110 000000000011110003800F
GOTO top0100 00000000000000 0000000000000040000000
m:540000000000000000000000000011011000000036
n:240000000000000000000000000001100000000018
gcd:00000000000000000000000000000000000000000

Logisim implementation

Circuit file

Memory dump for Euclid's algorithm