CS3410 Homework 1

Instructor: Kavita Bala

 HW1: ALU Design

Due: Wednesday, September 17th, 2008, 11:59pm

 


 

  Remember that we expect you to work ALONE for this homework. You will work in groups only for programming assignments.

Overview:
In the first homework, and first two 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 second 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 assignments. 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. In later assignments you will use many of these components to build your final CPU.  However, for this assignment you may only use the Logisim base elements (base folder elements), basic gates (gates folder elements), and multiplexors (in Plexers library/folder).

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. You will implement each of the following circuits (numbers in brackets give the number of bits in each input/output).

Full Adder: C = A + B + cin
Inputs:     A[32], B[32], cin
Outputs:    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
Inputs:       B[32], sa[5], cin
Outputs:      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, op, sa)
Inputs:  A[32], B[32], op[4], sa[5]
Outputs: C[32], O[1]

The output C is selected according the value of the op input based on the table below.  The second output O should be set to 1 if the final output could be incorrect due to a numerical overflow occurring during computation.  The value C output in the presence of overflow should correspond to the value computed if all overflow errors were ignored.

opcode     Value                  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
1000       C = A & B              and
1010       C = A | B              or
1100       C = A ^ B              xor
1110       C = ~(A | B)           nor
1001       C = A == B ? 1 : 0     eq
1011       C = A != B ? 1 : 0     ne
1101       C = A >  B ? 1 : 0     gt
1111       C = A <= B ? 1 : 0     le

The x's in the opcode indicate that the circuit should not depend on the value of that bit when determining the appropriate operation.  For example, your circuit should shift left logical when the opcode is either 0010 or 0011.  For the comparison operations, the notation COMP ? 1 : 0 means to output 1 if COMP is true and 0 otherwise.  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).

How to get started: First, design, build and test the adder and left shifter components.  Next, design, build and test a left/right shifting unit and an adder/subtracter unit.  Think of these units as miniature adding and shifting ALUs.  They will each have a new opcode-like control input that selects between its different sub-operations.  Third, design a comparator that can perform the four comparison operations by processing the output of the adder/subtracter.  Finally, design, build and test the ALU.  The overall idea is to compute several potentially needed values of the output C and then to select the appropriate one using a multiplexer (mux).  Hint 1: Think carefully about the minimum number of additional pieces required to implement the adder/subtracter and left/right shifter units from the original adder and left shifter.  Minimize the components you use as much as possible.  Hint 2:  Your circuit will compute several values in parallel, but ultimately select only one for output.  Your decoding logic can often be simplified if you note that you only need the output of a sub-component to be correct (i.e. for it, to receive the correct inputs) if you know ultimately that it will be selected for output.  In short, try to find the cases where you really don't care about the inputs to a sub-component. 

Getting started with Logisim:
Logisim is available here. You can get familiar with Logisim by making some simple circuits and testing them out. Do a pencil and paper design for all components before implementing in Logisim. You will need to turn this design in.  We will penalize poorly laid out designs that are hard to understand.

What to submit:

  1. A single Logisim project containing your ALU and all sub-components
  2. A list of test case tuples (A, B, op, sa) and their results expressed in binary (or hexadecimal if more convenient).  You should include enough tuples to exercise the complete functionality of the ALU circuit.  Testing is an important part of these project and will be graded.  You will be penalized if the set of tuples you submit is not sufficient to test the correctness of your circuit.
  3. Turn in a block diagram of the ALU showing all the major components and connections between them.  Please label them.  In your diagram, you do not, but can if you wish, draw the internal components of the adder and the left shifter.  You may draw these components as a single element.
  4. A written description of your decoding logic.  For each control input to a sub-component or select input to a mux, state the values on which that control line depends, present a truth table encoding the relationship of these values to the control input and give the Boolean algebra equation you used to implement it.
  5. Turn in a short 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

Help and Hints:
Ask the TAs for help. If you suspect a bug in Logisim, ask cs3410-staff-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 splitter. 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 2, 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 Adam Arbree and Kavita Bala.