CS 3410 Fall 2016
Due: Show your finished work to your TA in Lab Section.
Upload your work to CMS by Saturday, September 3 @ noon
You may work in pairs on this lab (with someone in your Lab Section), but you must upload your work separately.
Important: the ALU project which follows this assignment
is not a pair project. You must work on that alone. In
other words, after this lab designing the Left Shift, you and your
partner must go your separate ways to complete the ALU.
In this lab and the first three 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 third 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 your first project 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. In this lab you will create a subcircuit that will ultimately be a part of your MIPS ALU: the LeftShift32.
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:
**Important - Use this guideline for designing your circuits to avoid losing points!**
| 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.
It is important that your implementation of the circuit described above adhere to the specification in this document. Adhering to specification is important in most all design processes, and it will also have a more immediate effect on your grade for this lab. Automated grading will expect that the circuit above (and their inputs and outputs) are named exactly as specified (case-sensitive!) and behave exactly as specified.
Also recall that when the specification denotes a pin as A[32], the
pin should be named "A" and be 32 bits wide. The pin should not be
named "A[32]".
To make things easier for you, we have created a circuit template with the correct circuit inputs and outputs. If you use the template, do not delete or rename any of the input or output pins, and do not add any other pins. Feel free to move the pins around though.
Extensively testing your circuit is important to ensure correctness. Logisim, luckily, allows the use of test vectors for automated testing of circuits.
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 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.
For this lab, you will not be required to submit a test vector for your Left Shifter. However, since the Left Shifter will be an important component in the ALU you are designing, you should create a test vector to ensure that it is working correctly. You can find an example of a test vector we have made for you for your LeftShift32. This test vector is not holistic and does not cover edge cases you should consider. Therefore, use this as a reference but not a thorough replacement.
Getting started: Design your circuits on paper before building them in Logisim. Design, then build and test the left shifter circuit first.
Getting help: Ask the course staff for help. We are always available on Piazza.