QuAC Extensions

Given here (in roughly increasing order of difficulty) is a list of potential extensions you may want to consider for QuAC. Note that any extensions must be backwards compatible with the base ISA (you can’t redefine instructions that are already defined, for example).

Pass (50 - 59%)#

ALU Instructions#

Add multiple additional ALU operations that are not included in the base ISA. Some ideas for new operations include:

• xor Logical XOR
• not Invert all bits of the register
• inc/dec Increment/decrement
• lsl/lsr Logical shift left/right by 1 bit
• asr Arithmetic shift right by 1 bit

You have already implemented an extended ALU as part of the Checkpoint. While you may re-use some of the additional operations defined in that exercise you should have at least a few different operations exclusive to your extended CPU.

Also consider how your new instruction(s) might (or might not) affect the flags register.

Sign Extension Instructions#

The movl instruction sets the low byte to a value, and clears the high byte to zero. This is great normally, but makes setting a register to negative value a little annoying.

A movn (‘move negative’) instruction could be added that moves an 8 bit immediate to the low byte, and sign extends the high byte, i.e. sets bits 15-8 to the contents of bit 7 (we use zero-based indexing, so the least significant bit is bit 0). Another idea is to have a sext instruction which sign extends the low byte of a register (overwriting what was in the high byte).

See below for some examples:

movl r1, -4          @ r1 has the value `0x00FC`
sext r1              @ r1 now has the value `0xFFFC`, i.e. -4

movn r2, 4           @ r2 has the value `0x0004`
movn r3, -4          @ r3 has the value `0xFFFC`, i.e. -4

ALU Immediates#

It’s frustrating to have to use up an extra register increment a different register. Allowing operations with immediates would allow add r2, 1 directly, without having to first do movl r1, 1 or similar.

Implementing this would allow us perform ALU operations with a register and constant (e.g. and r1, 0x3F, sub r2, 15), and also allow for PC relative jumps (i.e. add pc, 15).

Memory Addressing Immediates#

Similarly to ALU immediates, you could add the ability to store or load directly from a specified memory location without first needing to load the address into another register. This would allow you to perform ldr rd, 0x12 instead of needing to do movl r1, 0x12; ldr rd, r1 as two separate instructions.

This means you could easily load constants and variables into registers without first needing to load their address. This is especially useful given the limited number of general purpose registers available.

Credit (60 - 69%)#

Base+Offset Addressing#

The other register slot in the encoding for load and store is unused. This could be changed to allow for instructions to use for specifying an offset address, which is added to a base address (given by a register or immediate value) before loading from/storing to memory. This means you can execute instructions like the following:

ldr r1, [r2, r3] @ r1 := [r2 + r3] 
str r3, [r4, r1] @ [r4 + r1] := r3
ldr r2, [r2, -1] @ r2 := [r2 -  1]
str r1, [r2,  9] @ [r2 + 9] := r1

If you choose to implement base+offset addressing with immediates values we recommend implementing ALU Immediates as well. It would also be a good idea to consider how you could implement negative offsets as well.

Conditional Execution#

As written, the ISA only conditionally executes on the Zero (Z) flag. You could extend this functionality such that the processor can execute on any arbitrary condition, such as the negative flag, or if one register was greater than another register, and so on.

For example, how could you extend the ISA to make it easy to execute the following code?

if x > y:
    z = x
else:
    z = y

Distinction (70 - 79%)#

Pre/Post Offset Memory Operations#

When loading out values from an array of data, it’s often useful to have the ability to load from an address, and then increment that address afterwards to move to the next piece of data. This can be done with a post-offset memory access:

ldr/str rd, [ra], rb

which is equivalent to

ldr/str rd, [ra]
add ra, rb

It is also useful to reverse the order of operations and update the value of the address first and then store/load to memory. This is a pre-offset memory access.

ldr/str rd, [ra, rb]!

which is equivalent to

add ra, rb
ldr/str rd, [ra]

Like with Base+Offset Addressing you can also have pre/post offset loading and storing with immediate values rather than just registers:

ldr/str rd, [ra], imm
@ is equivalent to:
ldr/str rd, [ra]
addi ra, imm

and

ldr/str rd, [ra, imm]!
@ is equivalent to:
addi ra, imm
ldr/str rd, [ra]

The difference here is that a pre/post offset takes only a single instruction cycle, whereas the two instructions it represents take two, which speeds up execution of code.

Expanded Register File#

The ISA as written only has 4 general purpose registers. This is fairly restrictive, and quite small as far as most CPUs go. Using reserved bits, could you add additional registers without fundamentally changing the instruction format to maintain backwards compatibility?

Some ideas/hints:

• restricting destination registers to gain more bits for source registers (or vice versa)
• add register shuffling for extra registers that may not be able to be used in all instructions

Another approach is to have different banks (sets) of registers, and add instruction to switch the current bank. e.g.:

movl r1, 0x12       @ r1 contains 0x12
usebank 2           @ r1's contents are undefined
movl r1, 0x34       @ r1 contains 0x34
usebank 1           @ r1 contains 0x12 again
usebank 2           @ r1 contains 0x34 again

The real-life Z80 CPU had a similar system of shadow registers.

Accessing More RAM#

Modern computers have far more than 64K words of RAM.

One way of allowing your CPU to access more RAM would be to introduce segment registers, whose value gets left shifted by some constant (e.g. by 16 bits) and then implicitly added to all memory accesses to form a 24 or 32 bit address.

Here’s an example:

movl rseg, 0
movl r1, 0x3456
ldr r2, r1            @ this accesses memory address 0x003456

movl rseg, 0x12
ldr r2, r1            @ this now accesses memory address 0x123456

Special care will be needed when changing segment registers, as it will change which instruction the CPU executes next! Some ways of fixing this might be:

• have instruction fetches ignore the segment register (i.e. code must be located within the first 64K words)
• have a bit in the instruction to determine whether a segment register is used or not
• have a seperate segment registers for instruction fetching than for str/ldr
• the segment register is only used on certain addresses (e.g. only those with bit 15 set)

If you implement the harder wider registers extension then accessing more RAM would be trivial.

High Distinction (80% - 100%)#

Function Calls and the Stack#

Functions are a very common feature of programming languages, allowing you to write a piece of code within a function and then use it over and over again by calling the function instead of copying and pasting the code everywhere. This decreases the size of programs greatly.

To implement function calls in assembly, you need to jump to where the function’s code starts upon a call, and also have a mechanism that allows jumping back to where you were in the main code after the function is done. For nested function calls, you will need to keep track of multiple addresses to jump back to.

Stack#

This is where the “stack” data structure facilitated by most modern ISAs is useful. This is a dynamically sized data structure in memory that acts as an array that grows downwards as you “push” (append) and “pop” (remove) the elements. The ISA typically defines a fixed base address that the stack starts at and a “stack pointer” register that keeps track of the address where the stack ends, i.e. of the last element of the stack (typical mnemonic is sp).

Pre/post offset memory operations are very useful for implementing the stack, as performing a push or pop instruction you need to both update the value of the stack pointer and store or load (for push and pop respectively) in the same instruction.

Your first task for this extension is to add the stack and stack pointer register sp. To implement the “stack” portion of this extension you will need to add push and pop¹ instructions that allow you to push and pop any of the general purpose registers.

Function Calls#

Once a stack has been added, function calls are now also possible and can be implemented with composite instructions. A call¹ acts like a jump (overwriting the pc) that also stores pc+1 onto the stack as a return address. Another instruction ret¹ that returns from functions would then just pop the return address into the pc register.

One could implement call as one pseudo-instructions that “actually” executes two separate instructions (the push and the jump) in quac.json. But since you have made it this far already, you should instead implement a hardware instruction that performs this in a single step.

push and pop, for pushing and popping data to/from the stack can also be defined as pseudo-instructions. Note that while this section has mostly described storing return addresses on the stack it can be used to store other data in a last-in-first out order as well.

We recommend reading Textbook Chapter: 6

Some of the extensions listed from this point will cause the part-1 tests to fail (which is okay). Ensure that you are leaving your standard CPU in basic-cpu.dig and are completing your extension in extended-cpu.dig.

Wider Registers#

Extend the ALU, and some registers from 16 bits wide to 32 bits wide. The extension needs to remain backwards compatible with the original CPU (e.g. by default, a register with 0xFFFF in it must wrap around to zero when incremented).

Some potential ways of doing this:

• Introduce new registers which are able to store 32 bit results. The other registers will remain at 16 bit (and therefore will truncate larger values that are passed to them).
• Make all registers 32 bits wide, but introduce a new flag in the fl register. When the flag is clear, results are truncated to 16 bits before being placed in a register. If the flag is set, then the registers will store the full 32 bits.
• Use one of the unused bits in the instruction encoding to determine if the register(s) will use all 32 bits, or just 16 bits.

You could also extend memory addressing to 32 bits, to allow the CPU to access 2^32 words (8GB).

Extreme Ideas#

We caution against the following extensions, and recommend them for only the bravest, most adventurous students. Many of these require a fundamental redesign of the entire computer, and/or require research into topics we don’t cover. These extensions are not required for a HD mark, but are only included here for those that are interested.

Multi-Cycle Execution#

Up to this point the labs and the course have implicitly been leading you on a path to a single-cycle computer, one where each instruction is executed in a single clock cycle. This is unrealistic, as most real CPUs can often take a varying number of clock cycles depending on complexity. This allows splitting up the amount of logic that has to occur within a single clock cycle for long instructions and keep the clock period small, and hence single-cycle instructions will occur quickly.

With multi-cycle execution you could have instructions that take a 16-bit immediate, which is useful for jumping to a 16 bit absolute address.

Textbook Chapter: 7.4

Intermediate Registers#

Many complex instructions may take more than one cycle to execute. You could add intermediate registers that are only accessible by multi-cycle instructions to use as temporary scratch space without clobbering other registers. For example, call rd may be implemented as

add tmp, pc, 1
push tmp
mov pc, rd

Floating Point Unit#

Implement a separate ALU able to perform floating point arithmetic (called an FPU), and implement instructions for converting between values in integer format, and those in floating point format.

Either create new instructions for the FPU, or introduce new floating point registers that use the FPU instead of the ALU when operated on.