CS 316 Programming Assignment 2

Instructor: Kavita Bala

PA2: Simple Execution Loop

Due: Tuesday, September 25th, 2007, 11:59 pm

Check the FAQ page for updates on the assignment.

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 three 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.

Programming Assignment 2: Simple Execution Loop

Here we will implement the basic execution loop for the processor, but only implementing two flow control instructions (unconditional jumps), and a few arithmetic and logic instructions. Your design should consist of a program counter, a MIPS Program ROM to store the compiled assembly code of the program, a 32x32 register file, your 32-bit ALU, and other components, along with the instruction decode logic and control circuits needed to connect them together.

The design will be non-pipelined, so that in each clock cycle the processor fetches and executes a complete instruction. For the arithmetic instructions, this includes: fetching the instruction to execute from the program ROM, decoding the instruction, selecting arguments from the register file, computing a result, storing the result in the register file, and incrementing the program counter by 4. For jump instructions, no value is written to the register file, and the program counter is set to a value selected from the register file or from the immediate field of the instruction.

Begin by connecting a register file, your ALU, and enough circuitry to implement a few arithmetic instructions. Once this is working, you can add logic to handle the jump instructions. For this project, your processor must implement the following MIPS instructions:

Jumps (without a delay slot) J, JR
Immediate arithmetic ADDIU, ANDI, ORI, XORI
Register arithmetic ADDU, SUBU, AND, OR, XOR, NOR

The MIPS standard uses a single delay slot for all jump/branch destinations because it is usually pipelined. That is, the PC is updated only after a delay of one instruction, and the instruction in the delay slot (i.e., the instruction following the jump or branch) is executed even if the jump or branch is taken. The destination PC is computed not from the address of the jump or branch, but from the address of the delay slot.

Updated 19 Sep: For this assignment, we are asking you to deviate from the MIPS standard for jump instructions. Compute your jump addresses based on the PC of the jump instruction. Do not try to execute the delay slot instruction.

Write a test program that fully tests all of the features you have implemented in this project. This is a critical step, and you should spend a fair amount of time developing a comprehensive set of test programs that exercise all of the different parts of your processor.

Components you will need The cs316 library contains a "Register File," a triple-ported (dual read, single write) 32-bit wide by 32-registers deep register file; a "MIPS Program ROM," a program memory module capable of loading a MIPS assembly language file directly into its memory; a "Mips ALU," an ALU module encapsulating a working solution to PA1; and an "Incrementer (General)" for you to use to increment the PC. More detailed descriptions of these components can be found below.

Updated 19 Sep: For this assignment, do not use your ALU from PA1. Instead, you are required to use the "Mips ALU" component included in the cs316 library. We are also requiring that you use the "Incrementer (General)" to increment the PC. (Note that the incrementer only computes +1, whereas the PC increments by 4.)

By using these components, you will reduce your chances of triggering a bug in Logisim's simulator and make it easier for us to grade your circuit.

Logisim's memory library contains registers you can use for your program counter.

Hint The instruction decode logic in this project should be extremely simple – do not waste time implementing an efficient decoder, because you will have to build a new decoder in Programming Assignment 3 anyway.

What to submit Submit a single Logisim project file containing your processor and a text file containing a MIPS assembly test program of your choice. The test program should exercise the instructions and features of the processor enough to convince the staff of its correctness. Please comment your program, indicating what it is doing and what results should be expected when running the program.

Help and Hints Ask the TAs and consultants for help. You can contact us through the course staff mailing list or the class newsgroup. We also expect to see most students in office hours during the course of the project. Extra hours will be scheduled as needed.

If you suspect a bug in Logisim or the cs316 library, ask the course staff 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.

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.

Deviation from the MIPS standard You can ignore any MIPS instruction or feature not mentioned in this document, and can assume that your processor will never encounter anything but legal instructions from the list above. In addition:

Logisim and cs316 Library Guide

Logisim and the cs316 library are available on the course homepage.

Loading the cs316 library Select ProjectLoad LibraryJar Library.... Select cs316.jar, and enter edu.cornell.cs316.Components as the class name. This library contains the following circuits:

Register File A 32-bit wide by 32-registers deep register file. Register $0 is hard-wired to zero at all times, and writes to $0 are ignored. Inputs rA and rB are used to select register values to output on the A and B outputs. On the falling edge of the clock, if WE is high, the data value at input W is stored in register rW.

MIPS Program ROM A 32-bit wide byte-addressed ROM, with built-in MIPS assembler. Use the attributes panel to load a MIPS assembly file into the ROM. The PC input specifies the address of the current instruction, and must be a multiple of 4. The output is the 32-bit instruction at the PC address, or zero if the PC has gone past the end of the ROM. Note that zero also happens to encode a no-op in MIPS. The assembly language is in the format described below.

Mips ALU An ALU component encaspulating the solution to PA1.

Incrementer (General) An adjustable-width incrementer. Takes its input A on the left and outputs A+1 on the right.

MIPS (subset) Assembly Syntax

The Program ROM component understands all of the instructions you will implement. The syntax is standard MIPS syntax. Labels are case sensitive, everything else ignores case. Anything following a '#' is a comment. In this project, you will only use a few of the instructions listed below.

Labels are used to mark places in the code. Jumps and branches can refer to these labels (for jumps, the address is inserted directly; for branches, a relative offset from the branch instruction is computed and inserted, accounting for the delay slot).

The instruction syntax is the same as given in the MIPS standard (and different from the output of gcc and many other tools). Registers are written as $0, $1, ..., $31, and the destination register goes on the left, followed by source registers and immediate values on the right. Absolute addresses (for J) are given in hex (i.e., 0x12ab), and all other integers can be in hex or signed decimal (i.e., 0x12ab or 1234 or -1234). The special constant PC can be used anywhere an integer is needed, and the assembler will replace it by the address of the instruction itself. The PC will normally fit in 15 bits or less.

Some examples of instructions are:

Jumps J 0x24
J my_label
JR $31
Branches BEQ $5, $6, -12
BEQ $5, $6, my_loop_top
BLEZ $9, 16
BLEZ $9, my_loop_done
Memory Load/Store LW $12, -4($30)
SW $12, 0($30)
Immediate Load LUI $14, 0x123
Immediate Arithmetic ADDIU $12, $0, PC
Register Arithmetic ADDU $13, $0, $20
Shifts SLL $13, $13, 2
SLLV $15, $14, $3
Labels my_loop_top: BNE $5, $6, 16

MIPS (subset) Opcode Summary (from the MIPS Handbook)

NB: Items in white are required for this assignment.

Table 1: MIPS32 Encoding of the Opcode Field
opcode bits 28..26
bits 31..29 0 1 2 3 4 5 6 7
000 001 010 011 100 101 110 111
2 010 COP0 δ COP1 δ COP2 θδ COP3 θδ BEQL φ BNEL φ BLEZL φ BGTZL Φ
3 011 β β β β SPECIAL2 δ JALX ε ε *
6 110 LL LWC1 LWC2 θ PREF β LDC1 LDC2 θ β
7 111 SC SWC1 SWC2 θ * β SDC1 SDC2 θ β

Table 2: MIPS32 SPECIAL Opcode Encoding of the Function Field
function bits 2..0
bits 5..3 0 1 2 3 4 5 6 7
000 001 010 011 100 101 110 111
2 010 MFHI MTHI MFLO MTLO β * β β
3 011 MULT MULTU DIV DIVU β β β β
5 101 * * SLT SLTU β β β β
7 111 β * β β β * β β

Check the FAQ page for updates on the assignment.