Lab 2: Left Shift 32

CS 3410 Spring 2017

Pairing: You must work in pairs of two on this lab. Your TAs will do the pairing for you.

Due: This lab is to be completed entirely in Lab Section. If you are unable to finish for whatever reason, please go to the Make Up Lab Section on Friday. After you are done, add your partner to the CMS assignment and submit your LeftShift32 with all subcircuits and a test vector file for your LeftShift32.

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 Logisim guideline for designing your circuits to avoid losing points!**

We will be using git this semester to disseminate lab and project materials. Please refer to the git guide for information on how to set-up and use your Cornell github repo. Ask your TAs if you have any questions.

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.

On specifications

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 included a template circuit file for your LeftShift32 in your git repo. It should be located at lab2/leftshift32_template.circ. If you use the template, do not delete or rename any of the input or output pins, and do not add any other pins. However, feel free to move the pins around.

Test Vectors

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 be required to submit a test vector for your Left Shifter. 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 for your LeftShift32 in your git repo. It is located at lab2/leftshift_test_vector_example.txt. This test vector is not holistic and does not cover edge cases you should consider. Therefore, use this as a reference but not as a thorough replacement.

Example Test Vector:

#First line labels input and output pins, labeled with [bit width] if >1
#Each line after is an individual test with each column representing a pin
#Numbers can be in decimal, binary, hexadecimal, or even octal if you want

B[32]                              Sa[5]   Cin   C[32]
34                                 2       0     136                                 #Decimal
325948595                          15      0     -900104192                          #Negative Decimal
00000000000000000000000000000001   00100   1     00000000000000000000000000011111    #Binary
0x00000005                         0x01    0x0   0x0000000A                          #Hexadecimal
0o17777777777                      0o1     0o0   0o37777777776                       #Octal
00011111001010100010110111110001   0o10    0x0   707653888                           #Everything together!


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.

What to Submit