CS316 Programming Assignment 1

Instructor: Kavita Bala

 PA1: ALU Design

Due: Friday, September 14th, 2007, 11:59pm




Remember that we expect you to work in groups of two for all programming assignments.

Overview: In the first three programming assignments you will design and implement 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, such as the 1-bit and 32-bit full adder you saw in class/recitation, to building complex, general-purpose CPUs. By the end of the third programming assignment we will implement a 32-bit pipelined version of the MIPS architecture. We will ignore more advanced features such as the MIPS coprocessor instructions and traps/exceptions for these 3 programming asssignments. Read this document entirely before implementing your assignment.

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. You may use any of these basic components in your designs, but you may not use the Logisim arithmetic library anywhere in your design. If you wish to download additional libraries from the web to use in your design, please check with the course staff for approval.

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 of the MIPS architecture documentation available to you in order to learn about the instruction set, what each instruction does, etc. But we expect your design to be entirely your own. If you are unsure if it is okay to borrow from some other source, just ask the TAs, and give credit in your final writeup. If you are unsure about asking the TAs, then it is probably not okay. Plagiarism in any form will not be tolerated.

32-bit ALU Implementation: The MIPS ALU (arithmetic and logic unit) performs all of the core computations dictated by the assembly language. You should have already designed a 1-bit full adder circuit in recitation. Begin by implementing the following circuits (numbers in brackets give the number of bits in each input/output). Full Adder: C = A + B + cin
Input: A[32], B[32], cin
Ouput: C[32], cout

The output C is computed by adding A, B, and cin. Any remaining carry bit is output on cout.

Hint: Use sub-components to make wiring easier, by building a 1-bit adder, then a 4-bit adder, and so on up to 32-bits.

Left Shifter: C = (B << sa) | (cin)sa
Input: B[32], sa[5], cin
Ouput: C[32]

The output C is computed by shifting B to the left sa bits, filling the bits on the right with sa copies of cin. The shift amount sa can be anything from 0 to 31, encoded as an unsigned integer. One efficient 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: Note that shifting a value on a 32-bit bus, by a constant amount, either left or right, is simply a matter of adding and removing and renaming the wires on the bus.

ALU: C= f(A, B, sa)
Input: A[32], B[32], op[4], sa[5]
Output: C[32]

The function is selected according the value of the op input: op C Function name

op    C Function    name
000x    C = B << sa    shift left logical
001x    C = A + B    add
0100   C = B >> sa    shift right logical
0101   C = B >>> sa    shift right arithmetic
011x   C = A - B    subtract
100x   C = A & B    and
101x   C = A | B    or
110x    C = A ^ B    xor
111x    C = ~(A | B)    nor

Note the difference between logical right shift (which fills with zero bits), and arithmetic right shift (which fills the empty bits with the copies of the sign bit of B). The right shift operations should be implemented by re-using other circuits (as was done for add/subtract in class).

Getting started with Logisim: Logisim is available here. You can get familiar with Logisim by making some simple circuits and testing them out.

We encourage you to do a pencil and paper design for all components before implementing in Logisim.

We will penalize poorly laid out designs that are hard to understand.

What to submit: Submit a single Logisim project containing your ALU and all sub-components, and a log file showing tests of your circuit (using the Simulate>Logging... feature). The tests you choose to do are up to you, but must convince the course staff that your circuit works as intended.

Turn in a very short written description of each of the components in your ALU: the adder, subtracter, left shifter, right shifter, and ALU.

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 the class grades. 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.
- Implement a carry-lookahead adder
- Minimize the number of gates used by the ALU

Help and Hints: Ask the TAs for help. We expect to see most students in office hours during the course of the programming assignment. Extra hours will be scheduled as needed. If you suspect a bug in Logisim, ask cs316-l@cs.cornell.edu for help. 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 splittter. This does not cause any data loss, but you might have to restart Logisim.

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 Programming Assignment 3, you will be asked to briefly 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) 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.

Check the FAQ page for updates on the assignment.


Page maintained by Kavita Bala