Homework 1 - ALU Design

CS3410 Spring 2011

Due: 11:59pm, Tuesday, February 8 Monday, February 7

Please submit required documents to CMS

You must work ALONE for this and all other homeworks. You will work in groups only for projects. Updates to this assignment will be posted on the course web page.

Overview

In the first homework and first two projects you will design a subset of the MIPS32 architecture in Logisim, a software logic simulator. The goal of these projects is to move you from designing small special-purpose circuits to building complex, general-purpose CPUs. By the end of the second project you will have designed a 32-bit pipelined MIPS CPU. For these assignments, we will ignore more advanced features, including the MIPS coprocessor instructions and traps/exceptions.

In this homework you will design a MIPS ALU (arithmetic and logic unit), which performs all of the core computations dictated by the assembly language. You have already seen pieces of the ALU, such as a 32-bit adder circuit, in class. Patterson and Hennessy Appendix C describes a similar ALU but with a different layout than we present here.

We will be using Logisim, a free hardware design and circuit simulation tool. Logisim comes with libraries containing basic gates, memory chips, multiplexers and decoders, and other simple components. In later assignments you will use many of these components to build your final CPU. However, for this assignment you may only use the following Logisim elements:

Academic Integrity. As one of the most widely studied architectures, MIPS has a wealth of information available on the web and in textbooks. You may consult any MIPS documentation available to you in order to learn about the instruction set, what each instruction does, how an ALU works, etc. But we expect your design to be entirely your own, and your submission should cite any significant sources of information you used. If you are unsure if it is okay to borrow from some other source, just ask the TAs. If you are hesitant to ask the TAs or to cite the source, then it is probably not okay. Plagiarism in any form will not be tolerated. It is also your responsibility to make sure your sources match the material we describe here (warning: the top Google hit for "MIPS reference" contains several inaccuracies).

Circuit 1: LeftShift32

LeftShift32: C = (B << Sa) | carrybits
Inputs: B[32], Sa[5], Cin
Outputs: C[32]

The output C is computed by shifting B to the left Sa bits, and filling the vacated bits on the right with carrybits, which is just Sa copies of Cin. The shift amount Sa can be anything from 0 to 31, encoded as an unsigned integer.

Note: Some inputs and outputs are busses (as noted by the bus width in brackets); the rest are 1-bit wide.

One way to implement such a shifter is to perform the shift as a series of stages: the first stage shifts either 0 or 16 bits, the second stage either 0 or 8 bits, the third stage either 0 or 4 bits, and so on. By enabling different combinations of stages the circuit can shift any desired amount. Hint: Shifting a value on a 32-bit bus, by a constant amount, either left or right, is simply a matter of adding, removing, and renaming the wires on the bus, and so requires no gates at all.

Circuit 2: Add32

Add32: C = A + B + Cin; V = overflow
Inputs: A[32], B[32], Cin
Outputs: C[32], V

The output C is computed by adding A, B, and Cin. A, B, and C are signed two's complement numbers. If overflow occurs, the output V should be asserted. In such cases, the output C should correspond to the value computed if all overflow errors are ignored. Hint: Use sub-components to make wiring easier by building a 1-bit adder, then a 2-bit adder, then a 4-bit adder, and so on up to 32-bits.

Circuit 3: ALU32

ALU32: (C, V) = fOp(A, B, Sa)
Inputs: A[32], B[32], Op[4], Sa[5]
Outputs: C[32], V

The C and V outputs are computed according the value of the Op input based on the table of operations below. For the add and subtract operations, the V output should be set to 1 if and only if the C output could be incorrect due to a numerical overflow occurring during computation. The value C output in the presence of overflow should correspond to the value computed if all overflow errors are ignored. For the gt and le operations, you may assume that input B is always 0. This may allow you to simplify your circuit.

Op name C V
----  ----------------------  --------------  ------------
000xshift left logical C = B << Sa; V = 0
001xadd C = A + B V = overflow
0100shift right logical C = B >> Sa V = 0
0101shift right arithmetic C = B >>> Sa V = 0
011xsubtract C = A - B V = overflow
1000and C = A & B V = 0
1010or C = A | B V = 0
1100xor C = A ^ B V = 0
1110nor C = ~(A | B) V = 0
1001eq C = (A == B) ? 1 : 0 V = 0
1011ne C = (A != B) ? 1 : 0 V = 0
1101gt C = (A > B) ? 1 : 0 V = 0
1111le C = (A ≤ B) ? 1 : 0 V = 0

An x in the opcode indicates that the circuit should not depend on the value of that bit when determining the appropriate operation. For example, your circuit should shift left logical when the opcode is either 0000 or 0001.

The expression (test) ? 1 : 0 has a value of 1 if test is true, and 0 otherwise. In both cases, the upper 31 bits of the output are zero. Note the difference between logical right shift (which fills with zero bits), and arithmetic right shift (which fills the new bits with copies of the sign bit of B). The logical and (&), or (|), xor (^), nor, and complement (~) operators are all bit-wise.

Notes & Hints

Getting started: Design your circuits on paper before building them in Logisim. Design, then build, test, and document, the left shifter circuit first. Next, design, build, test, and document a left/right shifting unit to be used in the ALU. Think of the left/right shifter as miniature ALUs: it will have its own opcode-like control input of your choice that selects between its different sub-operations. Repeat the same steps for circuit 2: design, build, test, and document the adder, then a adder/subtractor unit for use in your ALU. Then design a comparator unit that can perform the four comparison operations by processing the output of the adder/subtractor or other sub-components. Finally, design, build and test the complete ALU for circuit 3. The overall idea is to compute several potentially needed values of the output C, using the pieces you have already built, and then to select the appropriate one using a multiplexer.

Hint 1: Your ALU should use your adder and left shifter as components. But, as in class, your ALU should only use a single adder component to implement both addition and subtraction. Similarly, your ALU should use only a single left shifter component to implement all of the shift operations. For instance, right shifting can be accomplished by transforming the inputs and outputs to your left shifter. You will be penalized if your final ALU circuit uses more than one adder or left shifter. Of course, always strive to make your implementation clear, but do not duplicate components in an effort to do so.

Hint 2: Your circuit will compute several values in parallel, but ultimately select only one for output. Your decoding logic can often be simplified if you note that you only need the output of a sub-component to be correct (i.e. for it, to receive the correct inputs) if you know ultimately that it will be selected for output. In short, try to find the cases where you really don't care about the inputs to, or outputs from, a sub-component.

Is optimal always best? We want you to build a good working circuit. What does good mean? It could mean speed, readability, compactness, etc. Eventually, in later assignments, you will be asked to document your goals and justify the choices you made. However, even if you opt for highly optimized circuits, you should make sure all of your designs are clear and easy to follow. They should be annotated (with text labels on the circuits) for any unusual or difficult parts of the circuit. Think and design before you implement. Laying down a very complicated circuit for relatively simple functionality will not work in your favor during grading.

Getting started with Logisim: Cornell's custom version of Logisim is available on the course web page. You can get familiar with Logisim by making some simple circuits and testing them out. The Logisim documentation in the help menu is also useful. When debugging you might want to make use of the "probe" element in the base folder. When connected to any wire, a probe displays the value of that wire. It looks very similar to the input and output components, however it has one advantage: the probe element can be configured to display numbers in decimal, hexadecimal and binary.

Logisim combinational analysis: Take advantage of Logisim's combinational analysis window, which can automatically generate near-optimal circuits given a truth table. This only works for circuits with a few inputs, but is very well suited to control logic.

Logisim logging and test vectors: Make use of the logging and/or test vector modules in Logisim to test your circuits. The help pages describe the file format, and how to run them (either at the command line, or using the graphical interface). While it is not feasible to test every possible input tuple, it is feasible in Logisim to test up to several thousand input tuples. For serious testing, you will want to write programs (e.g. in perl, python, Java, bash, etc.) to generate the test vectors. You should strive to include enough tuples, and to choose the tuples strategically enough, so as to exercise the complete functionality of your circuits. Some of your tuples might be written by hand to test corner cases (e.g. adding combinations of zero, +1, -1, max_int, min_int, etc.). Some might be generated systematically (e.g. testing every possible shift amount, and every possible Op), and others might be generated randomly (to catch cases you didn't think of). Testing is an important part of these project and will be graded.

Getting help: Ask the course staff for help. If you suspect a bug in Logisim, contact cs3410-staff-l@cs.cornell.edu. There is a known bug having to do with bus splitters when the simulation is running. It is best to turn the simulator off when editing the wire ordering on a bus splitter. This does not cause any data loss, but you might have to restart Logisim.

What to Submit

What to submit:

  1. A PDF file containing design drawings and descriptions for each of the three circuits (left shifter, adder, and ALU). Your design should be detailed enough that a novice could re-implement your solution without having to make any significant design decisions. We will penalize overly complex or hard to understand designs. The PDF document you submit must include:
  2. A single Logisim project file containing all three circuits and any other sub-circuits they require. We will use Logisim's test vector function to test your circuits. In order for it to work correctly you must ensure that the Logisim circuits containing your solutions are named precisely "LeftShift32", "Add32", and "ALU32", and the inputs/outputs are named "A", "B", "Op", "Sa", "C", and "V".
  3. Three ascii text files containing test vectors for each of your three circuits. These files should be formatted as Logisim test vectors (see Logisim's in-program help for the format). A brief comment at the top of each file should indicate how the tuples were chosen/generated.

For the Adventurous: These suggestions for an extra challenge will be examined (and commented on, if your project works well) but not graded. They will have no impact on your homework grade. They are here to provide some direction to those who finish their assignments early and are looking for a way to impress friends and family (and us!).