Lab 6: CPU, Part III: Conditional Execution

Outline#

In this week’s lab you will:

1. Make design decisions for implementing new features to the QuAC CPU.
2. Implement conditional execution of instructions based on the status of the flag register.
3. Make the program counter a destination operand for instructions to automatically modify program (control) flow.

Preparation#

In preparation for this lab, you should make sure to have the working automatic CPU circuit, cpu.dig, and all of its sub-circuits from CPU, Part II.

This lab has no template files. You should continue from the previous lab’s circuit files.

Introduction#

Last week we constructed a fully automatic CPU that fetches instructions from memory and executes them. Our CPU can now load data words from memory into registers, perform simple arithmetic operations on the data words, and store data words to memory. Unfortunately, the programs we can write for our CPU are relatively simple and boring. Specifically, we lack a way to conditionally execute instructions based on the result of an earlier instruction. We also lack a way to write conditional statements: if/else statements, switch/case statements, and for/while loops.

So far, we have guided you with implementing specific instructions in the QuAC ISA. You will need to work out the design details for the remaining features in the base QuAC ISA on your own from now onward. There are multiple ways to approach the implementation of instructions and other elements in the ISA. As you make your decisions think about the advantages and disadvantages of competing approaches.

Keep notes on the design and implementation choices you make, as you will need these later when writing your assignment report.

We have been ignoring the four flags produced by the ALU: negative (N), zero (Z), carry (C), and overflow (V) since CPU, Part I. These flags are called condition flags or status flags. We will now use these flags to perform conditional execution. Each arithmetic instruction changes these flags based on the results of the ALU operation. The subsequent instructions can then execute conditionally, based on the status of the flags. In the QuAC specification, a special register called the flag register stores the four status flags.

Exercise 1: Flag Register#

We first add another register, the flag register, into which the flags are stored when an instruction is executed. The flag register should have the following properties:

• The flag register may be read like any other register.
• Writing to the flag register is undefined behaviour.
• If any arithmetic/logic instruction (add, sub, and, orr) is executed, the flags are updated to the flags generated by the ALU.
• If any non-ALU instruction (str, ldr, movl, seth) is executed, the flags should be left unchanged.
• The register code for the flag register is 101, with mnemonic fl.
• The flag register is 16 bits wide, and the flags are stored as follows.

• Z - Zero flag
• N - Negative flag
• C - Carry flag
• V - Overflow flag
• Undefined - Reserved for future use

We update the table of register codes as follows:

Now, you need to make suitable adjustments to the CPU microarchitecture yourself to implement the flag register and the associated behaviour.

In cpu.dig and control_unit.dig, make suitable changes to the CPU design and add a flag register, labelled fl, that satisfies the properties mentioned above.

Exercise 2: Conditionally Execute on Zero#

Now that we have a register to store the flags in, we can modify our ISA to conditionally execute an instruction based on the status of the flag register.

We modify the instruction encoding, and define the eleventh bit to be the conditional cond bit.

Register Operands Format (R-Format)#

Immediate Format (I-Format)#

• If the cond bit in the instruction is zero, the instruction is executed as normal.
• If the cond bit in the instruction is one, then:
  • If the Z flag in the flag register is one, then the instruction is executed as normal.
  • If the Z flag in the flag register is zero, then the instruction does nothing (no changes to the register file or memory).

All instructions can now execute conditionally, and an instruction is denoted as being conditional on the Z flag by appending eq to the end of the name of the instruction. This suffix is handled by the assembler; your CPU only needs to worry about the cond bit in the resulting machine code.

All the above instructions may now have the suffix eq added to indicate setting the cond bit to 1 in the machine code. E.g., add has cond == 0 and addeq is add but with cond == 1.

In control_unit.dig, modify the control unit to implement conditional execution on the zero flag. The control unit will need to read the Z bit from the flag register as an additional input.

You may want to first add an additional control signal EXEC that is internal to the control unit, and indicates whether the current instruction should be executed or not. You can then use the value of EXEC to decide what should happen to the other control signals. As a bonus, you can also output EXEC from the control unit and add a status LED Components -> IO -> LED to keep track of the computer. Of course, you should test EXEC too.

Exercise 3: Modifying Program Flow#

As it stands, our computer is a little boring, as there’s no way to control the flow of the program. Our computer executes instruction sequentially (i.e., one after the other) until it runs out of instructions. To implement loops and make the computer perform different tasks based on the input, we need the ability to modify the program counter during execution. Doing so is called changing the program flow. Modifying the pc register makes the computer execute a different part of the program.

We would like the program counter to have the following behaviour:

• The program counter is assigned register code 111 and mnemonic pc.
• Reads and writes to the pc register are defined in the same way as for any other general purpose register.
• The address of the current instruction to execute lives in the program counter.
• If the current instruction (i.e., one about to be executed) does not overwrite the program counter, then the program counter is incremented (pc := pc+1) on the next clock cycle.

We modify the table of register codes to allow the program counter to be a valid source and destination operand for all instructions.

In cpu.dig, modify the CPU to allow all instructions to read and write to the pc.

If the current instruction executes conditionally, and has the pc as the destination register (addeq pc, r2, r3), and the instruction do not execute, we still increment pc := pc+1 as normal. Can you see why this is the case?

Exercise 4: The seth Instruction#

There is one last instruction, namely seth, short for set high (byte), left to do to have the full functionality of the base ISA.

This instruction can be used to move an 8-bit value into the most significant byte of a register, leaving the least significant byte unchanged.

For example, if r1 = 0x12 and we executed seth r1, 0x34, the result would be that r1 = 0x3412. Formally, seth rd, imm8 performs the operation rd := (#imm8 << 8) | (rd & 0xff).

In cpu.dig, modify the CPU to allow execution of the seth instruction.

Conclusion#

We hope the last three weeks were fulfilling for you and that you learned a lot. If you have made it through all this, you now have a working CPU that satisfies the QuAC ISA for the assignment.

Now is a good time to document your design decisions to implement all the instructions. Note that you will need to recall all these details when writing the report for the assignment.

You have been pushing your work to GitLab, right?