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).
These extension ideas are grouped by the grade a high quality implementation (paired with a well-written report and good Digital Style) of that extension could achieve.
Attempting one or more extension(s) in a listed grade band is not a guarantee that you will achieve a mark in that grade band.
Within a certain grade band some extensions may be considered more complex than others, and therefore eligible for higher marks within that grade band.
Each higher grade band requires at least one extension is implemented from the previous grade band(s), and the High Distinction extensions in particular require synergy between multiple extensions from the lower grade bands.
You are welcome to implement your own additional extensions in addition to (not instead of) what we describe here, as long as they do not intefere with your extensions or break backward compatibility with the base QuAC ISA. (Some interesting ideas include adding additional instructions, addressing modes, or conditional execution).
Doing this is optional and will not affect your grade (unless you break your base ISA compatiblity or other extensions, which will negatively affect it!)
Pass (50 - 59%)#
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%)#
To be eligible to receive a mark in this range you must also implement at least one extension listed in the Pass section.
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 and/or Memory Addressing Immediates as well.
It would also be a good idea to consider how you could implement negative offsets as well.
Allowing for the usage of both a register and immediate value as the offset will be considered a more sophisticated implementation of this extension, and if done well, worthy of a slightly higher mark in this grade band.
Distinction (70 - 79%)#
To be eligible to earn a mark in this range, you will need to implement at least one extension from both the Pass and Credit sections.
Pre/Post Offset Memory Operations#
To complete this extension, you should first implement a dual-ported register file. You will need to change your register file such that it has two inputs, allowing two registers to be written to in the same cycle. If the same register is chosen for both destinations, then one takes precedence.
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.
High Distinction (80% - 90%)#
To be eligible for a mark in this range you must both:
- Implement at least one extension from each of the previous Pass, Credit and Distinction lists to a high standard.
- Build on your previously added extensions in a meaningful way when implementing an extension listed below.
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 pop1 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 call1 acts like a jump
(overwriting the pc) that also stores pc+1 onto the stack as a return
address. Another instruction ret1 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
Upper High Distinction (91% - 100%)#
In addition to implementing a Stack for a High Distinction, you can go further by implementing more advanced extension(s) beyond that.
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.
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
Stack Instructions#
Requires: Function Calls and the Stack
You could define instructions that take zero operands, and operate directly onto the data on the stack e.g. addst or subst could pop the first two items off the stack, add/subtract them, and push the result back to the stack. This could be implemented with either the understanding that general purpose registers may be clobbered in the process, or by adding extra temporary registers that only stack instructions may use.
Implementing this as pseduo-instruction(s) does not count!
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
flregister. 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).
Something else…?#
If you have another idea for an advanced extension you’d like to implement, ask on Ed about it so we can check for suitability.
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 to acheive the highest mark, but are only included here for those that are interested.
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.
Pipelining#
Requires: Multi-Cycle Execution
As the computer currently stands, if we were to build it in hardware, it might be quite slow, as the computer waits until the entire instruction has been executed before trying to fetch the next one. A trick to speeding up a computer is called pipelining, where while the computer is executing the current instruction, it is also busy fetching the next instruction simultaneously. This can induce more problems, called hazards where executing a jump can mean the instruction fetched is the wrong one, or executing instructions that depend on the result from the previous instruction.
Textbook Chapter: 7.5