yeolyi.comSeongyeol's CS

Jump

A counter only goes up by 1 every clock. So a program only runs one line at a time from top to bottom. To do the same thing ten times, we have to write the same instruction ten times, and if how many times depends on a number in a register, we can’t build it at all. We need instructions that go back and repeat earlier instructions and stop when a condition is met.

Instructions that change the flow

JUMP and JZ read the last 4 bits as the address of the next instruction to run, so let’s put them in kind 11 as 1100 and 1101. HALT is 1111. The control table gets a Next address column.

InstructionNumberRegister writeMemory writeSubtractKeep ZValue to writeRegister to writeRegister to readALU 2nd valueNext address
LDI01101000ImmediateRd··000(+1)
LOAD10001000MemoryR0··000(+1)
STORE10010100··R0·000(+1)
MOVE00001000RegisterRd··000(+1)
ADD00011001ALURdRdRs000(+1)
SUB00101011ALURdRdRs000(+1)
ADDI01001001ALURdRdImmediate000(+1)
SUBI01011011ALURdRdImmediate000(+1)
JUMP11000000····001(Address)
JZ11010000····010(Address if Z)
HALT11110000····011(Stay)

Here’s an example that adds 1 through R0 and leaves the sum in R1.

Address 0: ADD R1, R0
Address 1: SUBI R0, 1
Address 2: JZ 4          ← if it's 0, go to address 4
Address 3: JUMP 0        ← otherwise, go to address 0
Address 4: HALT

Deciding whether to jump

The control unit sends the table’s Next address column as a select signal NEXT. The next post adds one more choice, more than 2 bits can hold, so NEXT gets 3 bits. Let’s decode NEXT with a decoder and turn on the jump signal J when it’s 001, or 010 with Z being 1, and the stop signal HOLD when it’s 011. From now on we’ll call this circuit JUMP LOGIC.

Change NEXT to 010 (Address if Z). J turns on only when Z is also 1. With 001, J is always on, and with 011, HOLD turns on.

PC

The counter that counts the next address to run is called the Program Counter (PC). A jump puts a different address into the PC instead of PC + 1.

Below, a MUX is inserted in front of each register of the counter circuit. Normally it picks PC + 1 from the half adders, and when J is 1 it picks the address to jump to (A0~A3). HOLD goes through a NOT to the registers’ W, so when HOLD is 1 the PC stays put even when the clock comes.

  1. Change CLK to 1 and back to 0, over and over. The PC goes up by one.
  2. Change A1 and J to 1 and give a clock. The PC goes to address 2.
  3. Change J back to 0 and give another clock. The PC becomes 3. It runs one line at a time again from the address it jumped to.
  4. Change HOLD to 1 and give a clock. The PC stays put.

Abstraction

From now on, let’s draw this circuit as a single PC box, and JUMP LOGIC as a box too.

Change J to 1 and give a clock. The PC goes to address 5.

Attaching it to the machine

Let’s attach these to the machine from the ALU post. The PC’s LOAD gets the instruction’s address, and J and HOLD get JUMP LOGIC. R0 holds 3.

Keep giving clocks. R1 builds up 3, 5, and 6, and when R0 reaches 0 the machine goes to slot 4 and stops.

Wrapping up

JUMP doesn’t remember where it came from. The PC box’s +1 output, which we haven’t used yet, is the address right after the current one. In the next post, let’s use this value to make instructions that go and come back.

Challenge

Without JUMP, we built a loop with JZ alone. When R0 starts at 1 or more, what must go at address 3 so that ADDI R1, 3 runs as many times as R0's starting value and then reaches address 5? The Zero Flag is changed only by ADD, SUB, ADDI, and SUBI, and R2 is not used in this program.

Address 0: ADDI R1, 3
Address 1: SUBI R0, 1
Address 2: JZ 5
Address 3: (blank)
Address 4: JZ 0
Address 5: (next job)