G51CSA Coursework 2014 — updated 03/11/2014

Implementing an Arithmetic and Logic Unit


In this coursework, you will implement an 8-bit variant of the Arithmeitc and Logic Unit (ALU) used in the nand2tetris Hack CPU. You will be guided to build the ALU in three stages, starting with the simpler components and building these blocks together to build the final ALU. The details of each component will be released in a staggered fashion over the next few weeks so that you have time to complete them all. This coursework is worth 25% of your final G51CSA mark.

Each of the components are to be developed using the Hardware Design Language (HDL) of the nand2tetris Hardware Simulator. Therefore, it is strongly recommended that you read Appendix A and Project 1 of that before you start the coursework if you have not already done so to gain some experience with the Hardware Simulator. You may also find it helpful to read the chapter on ‘Boolean Arithmetic’ for more information about the ALU. In addition, we will supply test scripts that you can use within the simulator to test your circuits.

Each component will be marked in the G51CSA and G51PRG computing labs by the Preceptors. You will need to show the Preceptors your finished component and run it against the supplied test script. Full Assessment details and a release schedule for the next set of components can be found below

Introduction

The ALU is found at the heart of all CPUs and is responsible for performing all the mathematical and logic operations in a CPU. As was described in the lecture, one of the aims is to produce an ALU with as much functionality as needed using the least logic.

A C implementation of the ALU logic can be download here, you might want to use this in conjuction with the lecture slides to experiment with how an ALU works.

Our ALU is represented pictorially below and consists of two 8-bit inputs, X and Y and one 8-bit output. It also has six control inputs, which are described in both lecture seven, and the ‘Boolean Arithmetic’ chapter of nand2tetris.

The inputs and output are multibit, and so we represent in the HDL as buses. A bus is just a collection of logic signals that we keep together (in this case they reach represent a numeric value in binary). We can define them in the HDL by suffixing the pin name with square brackets, thus: a[8]. This denotes that a is a bus 8 bits wide, numbered 0–7. Each individual bit can be accessed by placing the number of the required bit in the square brackets. So a[3] would access the fourth bit (remember, numbering starts from zero!). Again, reread Appendix A of nand2tetris for more details on the HDL syntax.

Component Set One

As described, the ALU can either add the two inputs together, or boolean and the two inputs together. In addition, both inputs and the output can also be inverted (each bit of the bus is passed through a NOT gate). For this component set, you will create 8-bit versions of these operations that we will combine in later stages to produce the final ALU. In addition, you will also create an 8-bit MUXer that can be used to switch between one of two inputs based on a control signal.

For this set of components, you will be implementing four circuts:

You can download the skeleton .hdl files, and test scripts in this ZIP file. You may assume that the logic gates listed in the Appendix are pre-defined and available for you to use in your circuits.

Component Set Two

You are going to develop two additional components in this section, both can be built using the components created during the previous section along with the logic gates listed in the Appendix. As described in the lecture and the nand2tetris chapter on ‘Binary Arithmentic’, our modified Hack ALU allows for both inputs to be either zeored (all bits set to zero) and/or negated (each bit inverted, or run through a not gate) based on the value of a control signal.

The first component you are to create is called ZeroOrIn, and has one input bus, in, and one output bus, out. It also has an input, z which is used to say whether the output (out) matches the input (in) when z is 0, or whether the output is forced to have all bits set to zero (when z is 1).

The second component you are to create is similar and called NegateOrIn. Again, it has one input bus, in, and one output bus, out. It also has an input, z which is used to say whether the output (out) matches the input (in) when z is 0, or whether the output is logical inversion (i.e. all bits of the bus have been inverted, or notted) when z is 1.

Again, you can download skeleton .hdl files as starting points, along with test scripts in this ZIP file. Although, this week, you are required to specify the INputs and OUTputs for CHIPs in the HDL yourselves, but remember the names must match those given above otherwise they will not be compatible with the test scripts.

Component Set Three

There's only one component to implement in this section, the modified Hack ALU itself. You can find the skeleton .HDL file and the test scritps in this ZIP file.

The ALU can be constructed purely by using the components you have created in the previous sessions, although you may need to have more than one instance of some of them. Therefore, you should make sure all the .hdl files, test scripts and .cmp files are all in the same folder on your computer. It helps when constructing this component to mentally follow the signals through the chip from the input buses to the output bus and remember that you cannot change the value of the input signals (as the example C implementation I gave you does). Instead, as with component set two you must produce a new set of signals and select between that new signal and the original. You might find it helpful to draw a diagram on paper showing the connections between the different component while you are developing you solution.

This description refers only to the x input, the y input bus requires an equivalent path through the chip (apart from the control signals used to control it, which will use the zy and ny signals instead). The first thing that should happen is that the input on the x bus, should be switched to zero if the zx control input is 1. This new signal should then be switched to a negated (bitwise “not”) version if the nx signal is 1.

Having formed an equivalent circuit, for the signal on the y bus, you now need to select between the and-ed or add-ed versions of the two input buses based on the control signal f, the function code (1 for add, 0 for and). Finally, the selected result should be negated if no is 1 before the signal is fed to the output bus, out.

Assessment

Each component will be marked in the G51CSA and G51PRG computing labs by the Preceptors. You will need to show the Preceptors your finished component and run it against the supplied test script. The Preceptors will then award it a mark based on how it performs against the test script and how well-implemented it is. Each component will be marked on a three point scale — checking whether it works and if it is well implemented. The marks will be awarded thusly:

However, since you will be provided with the test scripts for each component there should be no reason why your circuit fails (since you can test it yourself beforehand). Therefore, YOU WILL ONLY GET ONE DEMONSTRATION ATTEMPT to a preceptor, so remember to check your code first!

The deadline for this coursework is 14th November at 5pm, by which point you will need to have shown all your components to a Preceptor for marking as well as submitting them via Moodle (details to follow). Marking will start, in the labs, the week commencing 27th October. We strongly advise you to get the components marked as soon as you have finished them and not to leave them all to the last minute.

This page will be updated on the dates specified above with details of the next set of components. The (provisional) release schedule for each component set is:

Appendix

You may assume that the following logic gates are pre-defined and available for you to use in your components: