
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 specialpurpose circuits, such as the 1bit and 32bit full adder you saw in class/recitation, to building complex, generalpurpose CPUs. By the end of the third programming assignment we will implement a 32bit 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.
32bit 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 1bit 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 The output C is computed by adding A, B, and cin. Any remaining carry bit is output on cout. Hint: Use subcomponents to make wiring easier, by building a 1bit adder, then a 4bit adder, and so on up to 32bits.
Left Shifter: C = (B << sa)  (cin)sa 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 32bit 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)
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 reusing 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 subcomponents, 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. 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 cs316l@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 