CS 3410 Programming Assignment 1

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

Overview In the first and second programming assignments we will design and implement a subset of the MIPS32 architecture in Logisim. By the end of these two assignments 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 programming asssignments. Read this document entirely before implementing your assignment.

In PA 1 you will implement a skeleton framework of pipelining and partial functionality, and then in PA 2 you will complete the processor design. PA 1 will include: decoding all the instructions you will implement in both assignments, implementing a skeleton pipeline, correct implementation of arithmetic and logic operations, and appropriate handling to avoid hazards for these operations.

PA 2 will implement all the other instructions and all the appropriate hazard logic.

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.

Pipelining This version of your processor will be pipelined according to the MIPS standard, which specifies four stages:

Fetch
Arithmetic
Memory access
Write back

Refer to the MIPS standard, volume I, section 2.6.1 for details. Note that the book describes a five-stage pipeline, which is not what you will be implementing; stick to the standard where there are differences.

For this assignment, the memory stage of the pipeline will just be a passthrough doing nothing. In PA 2, you will add load and store memory operations and populate that part of the pipeline.

Also, while we will have a fully pipelined architecture, in this assignment, you will not implement the delay slot. That will be added in PA 2.

What to implement In PA 1 we will implement the basic execution loop for the processor, but only for the arithmetic and logic instructions (see Table A). 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, our 32-bit ALU (see below), and other components, along with the instruction decode logic and control circuits needed to connect them together.

Arithmetic and logic instructions must: fetch the instruction to execute from the program ROM, decode the instruction, select arguments from the register file, compute a result, store the result in the register file, and increment the program counter by 4.

Begin by connecting a register file, the ALU, and enough circuitry to implement a few arithmetic instructions. Over the course of the first two programming assignments you will implement a small subset of the MIPS ISA. It will ultimately include jumps, branches, load/store and math instructions, however in this assignment your processor must only correctly implement the instuctions in this table (Table A):

Table A
Immediate arithmetic	ADDIU, ANDI, ORI, XORI
Register arithmetic	ADDU, SUBU, AND, OR, XOR, NOR
Shifts (constant and variable) (PA 1)	SLL, SRL, SRA, SLLV, SRLV, SRAV
Immediate Load	LUI

Note that while LUI is not an arithmetic or logic operation we are including it in PA1 because despite its name, it isn't a load operation either (it doesn't use memory).

Furthermore, you will decode all the instructions in the following table (Table B). You will actually implement the functionality of these instructions in PA 2.

Table B
Jumps (with a delay slot)	J, JR, JAL, JALR
Branches (with a delay slot)	BEQ, BNE, BLEZ, BGTZ
Memory Load/Store	LW, SW

Our testing programs will include a mixture of all these instructions. When processing one of the instructions of Table B, your implementation is free to do anything as long as: 1) no value in the register file changes and 2) no output of an instruction you are required to implement changes. Think carefully about your decode logic to make sure this second condition works out.

Components you will need The cs310 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 HW1 (except for the comparison operators); and an "Incrementer (General)" for you to use to increment the PC. More detailed descriptions of these components can be found below.

We will use a split-memory design: The Program ROM will store a read-only copy of the instructions, and a separate Logisim RAM will be used to store data for the program's execution.

For this assignment, do not use your ALU from HW1. Instead, you are required to use the "Mips ALU" component included in the cs4310 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.)

It is important to use our ALU because your HW1 solution also includes doing comparisons using the adder (something you will not be doing in your pipelined implementation), and to make it easier to work in groups.

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

Tips and Suggestions

Do not replicate any components. There should be only one ALU.
The next instruction for the PC (PC+4) can be done with the incrementer we provide. How? You do not need to replicate the incrementer to achieve this.
Refer to the MIPS manual for a full specification of the MIPS ISA. You will need to refer to it often.

Testing Write a test program that fully tests all of the features you have implemented. 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.

What to submit Submit:

A single Logisim project file containing your processor.
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.
Turn in a block diagram of your processor showing all the major components and connections between them. Please label them. In your diagram, you do not, but can if you wish, draw internal components.
A written description of your decoding logic, specification for the control lines for each opcode, and truth tables for the control lines
Turn in a short description of each of the components in your processor

About the documentation: The point of all this documentation is to give you another avenue of communicating your intended design and implementation in the case your circuit has mistakes. For a well-designed, clearly labeled, completely correct solution, the circuit itself can serve as the documentation, but, otherwise, use the documentation to clarify and explain any parts of your circuit we might find confusing.

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 cs3410 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:

Assume traps or exceptions will not occur (i.e., do not implement them).

Logisim and cs3410 Library Guide

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

Loading the cs3410 library Select Project → Load Library → Jar Library.... Select cs3410.jar, and enter cs3410.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 rising 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 arithmetic and logic operations from HW1.
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.

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:

Immediate Arithmetic	ADDIU $12, $0, PC
Register Arithmetic	ADDU $13, $0, $20
Immediate Load	LUI $14, 0x123
Shifts	SLL $13, $13, 2 SLLV $15, $14, $3
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)

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

NB: Items in white are required for PA1 and PA2. Make sure to decode all of them.

Table 1: MIPS32 Encoding of the Opcode Field
opcode		bits 28..26 →
↓ bits 31..29		0	1	2	3	4	5	6	7
↓ bits 31..29		000	001	010	011	100	101	110	111
0	000	SPECIAL δ	REGIMM δ	J	JAL	BEQ	BNE	BLEZ	BGTZ
1	001	ADDI	ADDIU	SLTI	SLTIU	ANDI	ORI	XORI	LUI
2	010	COP0 δ	COP1 δ	COP2 θδ	COP3 θδ	BEQL φ	BNEL φ	BLEZL φ	BGTZL Φ
3	011	β	β	β	β	SPECIAL2 δ	JALX ε	ε	*
4	100	LB	LH	LWL	LW	LBU	LHU	LWR	β
5	101	SB	SH	SWL	SW	β	β	SWR	CACHE
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
↓ bits 5..3		000	001	010	011	100	101	110	111
0	000	SLL	MOVCI δ	SRL	SRA	SLLV	*	SRLV	SRAV
1	001	JR	JALR	MOVZ	MOVN	SYSCALL	BREAK	*	SYNC
2	010	MFHI	MTHI	MFLO	MTLO	β	*	β	β
3	011	MULT	MULTU	DIV	DIVU	β	β	β	β
4	100	ADD	ADDU	SUB	SUBU	AND	OR	XOR	NOR
5	101	*	*	SLT	SLTU	β	β	β	β
6	110	TGE	TGEU	TLT	TLTU	TEQ	*	TNE	*
7	111	β	*	β	β	β	*	β	β