yeolyi.comSeongyeol's CS

ALU

For now, the machine only moves numbers and can’t compute anything, like adding two numbers. Let’s make instructions that add or subtract two numbers in registers and leave the result in a register.

Arithmetic instructions

ADD and SUB write two registers in the last 4 bits, so they get 0001 and 0010 in kind 00. ADDI and SUBI write a register and a number, so they get 0100 and 0101 in kind 01.

InstructionNumberRegister writeMemory writeSubtractKeep ZValue to writeRegister to writeRegister to readALU 2nd value
LDI01101000ImmediateRd··
LOAD10001000MemoryR0··
STORE10010100··R0·
MOVE00001000RegisterRd··
ADD00011001ALURdRdRs
SUB00101011ALURdRdRs
ADDI01001001ALURdRdImmediate
SUBI01011011ALURdRdImmediate
Job
Rd
Rs
Registers
R05
R13
R20
R30

  1. ADD R0, R1 is written. Run it. R0 gets 5 + 3 = 8.
  2. Change the bits to 0100 01 01 and run ADDI R1, 1. The 01 in the Rs position becomes the number 1 to add, not a register number.

ALU

The computing is done by the ALU (Arithmetic Logic Unit). Addition uses an adder, and subtraction, as we saw with two’s complement, flips B, adds 1, and adds. So we put a MUX on every bit of B that picks the flipped B when SUB is 1, and wire SUB into the first bit’s carry input (CIN). Below is a 4-bit version.

Change SUB to 1. S changes from 3 + 5 = 8 (1000) to 3 − 5 = −2 (1110).

Zero Flag

If subtracting two values gives 0, the two are equal, so whether the result is 0 answers “Are the two values equal?” In the next post we’ll use this answer to change the flow of a program.

Feeding the four result bits into a single four-input NOR gives 1 only when every bit is 0.

This value has to be remembered until the next instruction, so we keep it in a 1-bit register. This is the Zero Flag (Z). So that only arithmetic instructions change Z, the register’s W is wired to the control table’s Keep Z column (ZW). Below, this NOR is drawn as a “Zero?” box.

Changing S1 to 0 leaves Z as it is. Only after changing CLK to 1 and back to 0 does Z become 1.

Abstraction

From now on, let’s draw the add/subtract circuit and the Zero Flag together as a single ALU box.

  1. Turn SUB on. OUT shows 254, and below it, −2 read as two’s complement.
  2. Change B to 3, then change CLK to 1 and back to 0. The result is 0, so Z becomes 1.

Attaching it to the machine

Let’s attach the ALU to the machine from the control unit post. ADD has to read two registers at once, so we added another read address (RB) and an output for its value (B). We also added the ALU and the MUXes before and after it.

Change CLK to 1 and back to 0, four times over. R0 goes through 3 and 2 to 0, and on that last clock Z becomes 1.

Wrapping up

In the next post, let’s use the Zero Flag to make instructions that change the flow of a program.

Challenge

Running SUB R0, R1 makes the ALU subtract the two values, and whether the result was 0 is automatically kept in the Zero Flag. But the result overwrites R0, so R0's original value is lost. Keeping the Zero Flag from that comparison, how many instructions at minimum, including the SUB, are needed so that R0 and R1 end up with their original values? You may use only R0 and R1 as registers and only memory slot 15, and the instructions so far are LOAD, STORE, LDI, MOVE, ADD, SUB, ADDI, and SUBI. Answer with a number.