Lab 2: Left Shift 32

CS 3410 Spring 2018


Due: After you are done, submit your LeftShift32 with all subcircuits and a test vector file to CMS by Sunday 2/11 at 11:59 PM


Overview

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!**

Circuit 1: LeftShift32

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

Start by downloading the provided template to ensure that your input and output pins are correct

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]".

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 on the assignment page. You can download it at this link: LeftShift_test_vector_example. 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!

Once you have created your test vector text file, you can run the tests automatically within Logism, by accessing Simulate --> Test Vector --> Load Vector and selecting your test vector file.

Notes

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