Group Project 1 - Pipelined Mini-MIPS

CS3410 Spring 2011

Due: 11:59pm, Friday, March 04, 2011

Late Policy: no individual extensions, all partners need a Slip Day.

You must work in a group of two for this project and the next. You can change groups for the third and later projects.

Overview

In the first and second group projects we will 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 assignments.

In project 1 you will implement a functioning outline of the pipelined processor for a small set of instructions, including: decoding all the instructions you will encounter in projects 1 and 2, implementing most of the MIPS pipeline, correct implementation of arithmetic and logic operations, and simple hazard avoidance for these instructions. In project 2 you will implement all a more complete set of instructions, and add more complete 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 MIPS 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, and your submission should cite any significant sources of information you used. If you are unsure if it is okay to borrow from some other source, just ask the TAs. If you are hesitant to ask the TAs or to cite the source, then it is probably not okay. Plagiarism in any form will not be tolerated. It is also your responsibility to make sure your sources match the material we describe here (warning: the top Google hit for "MIPS reference" contains several inaccuracies).

MIPS Pipeline

You will implement a five-stage MIPS pipeline, which is the most common organization for MIPS and is similar to what is described in the book and in class:

  1. Fetch
  2. Decode
  3. Execute
  4. Memory
  5. Writeback

The MIPS standard, volume I, section 2.6, describe several possible MIPS pipelines, none of which exactly match the five-stage pipeline that we will implement.

Memory stage. For project 1, the memory stage of the pipeline will just be a passthrough doing nothing. In project 2 you will implement load and store memory operations and populate the memory stage part of the pipeline.

Delay slot. In this assignment you will not implement the branch/jump delay slot or memory load delay slot. That will be added in project 2.

What to Implement

Implement a five-stage pipelined MIPS processor in Logisim. Your design should contain a program counter, a read-only program memory (ROM), a register file, our ALU, and any other components needed, along with the instruction decode and control circuits needed to connect them all together. The pipeline should: fetch instructions to execute from the program ROM and increment the program counter by 4; decode each instruction; select arguments from the register file; compute results; do nothing in the memory stage; and store results back in the register file.

Your pipeline must correctly execute all of the instructions in Table A:

Table A
Immediate arithmetic ADDIU, ANDI, ORI, XORI, SLTI, SLTIU
Register arithmetic ADDU, SUBU, AND, OR, XOR, NOR, SLT, SLTU
Move MOVN, MOVZ
Shifts (constant and variable) SLL, SRL, SRA, SLLV, SRLV, SRAV
Immediate load LUI

Note that LUI doesn't access memory and so, despite its name, is more similar to an arithmetic or logic instruction than a memory load instruction.

Furthermore, your instruction decoding and control logic must correctly decode all the instructions in table B. You will implement the functionality of these instructions in project 2, so decoding them properly now will save you from having to completely re-implement your decoding and control logic later.

Table B
Jumps (with one delay slot) J, JR, JAL, JALR
Branches (with one delay slot) BEQ, BNE, BLEZ, BGTZ
Memory Load/Store (little endian) LW, LB, LBU, SW, SB

Our testing programs for project 1 will include a mixture of instructions from both Table A and Table B. 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) the execution of instructions from Table A are not interfered with in any way. Think carefully about your decode logic to make sure this second condition works out.

Deviation from the MIPS standard: You can ignore any MIPS instruction or feature not mentioned in this document, such as traps, exceptions, and system calls. You can also assume that your processor will never encounter anything but legal instructions from the lists above.

Refer to the MIPS manual, Volume 2, linked on the course web site for a full specification of what each of these operations does. Except where noted in here, the MIPS manual is the authoritative specification for this project: information you find elsewhere (e.g. Wikipedia or the book) doesn't count if it contradicts the MIPS manual.

Processor Components

Build your MIPS processor as a single Logisim circuit file. We provide a Logisim JAR library which you can load using Logisim's Project > Load Library > JAR Library command. This is the only Logisim library you should use. Do not use Logisim's Project > Load Library > Logisim Library command to import circuits from other Logisim files.

The cs3410.jar Logisim library contains several components you will need, such as a register file, an ALU, an incrementer, and a program memory. You must use these components where applicable, but you may only use one of each.

Register file. Don't attempt to create your own register file out of regular Logisim Registers. This one makes debugging and simulation much easier.

ALU. You must use the ALU from this library, rather than your ALU from homework 1. Your design may only contain one ALU.

MIPS Program ROM. We will implement a Harvard Architecture design: The Program ROM component will store a read-only copy of the program instructions, and (in project 2) you will use a separate Logisim RAM to store data. The Program ROM component can load and display MIPS assembly language, which helps with debugging and saves you from having to write test programs in machine language.

Incrementer. You must use one (and only one) of these to increment the PC. Note that the incrementer only computes +1, whereas the PC increments by 4.

Logisim components. You can additionally use any of the components that come with Logisim, such as a Register for the PC, multiplexers, and so on.

Testing

Write a test program in MIPS assembly 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 program that exercise all of the different instructions and features of your processor. The program should be well commented, indicating what it is doing and what results should be expected when running the program, so that the course staff is convinced of the correctness of your processor.

Documentation

Document your design. Include a block diagram showing all the major components in the processor (ALU, Register File, PC, pipeline registers, etc.), and the datapath connections between them. You need not completely draw wires for control logic signals, but should indicate which components take control inputs, and give names to all control signals. Overall, the diagram should be very similar to (and not much more complicated than) the diagrams used in lecture, but with labels for control signals and any relevant data signals. You should provide an explanation for any parts of your processor or any subcomponents that are unusual or potentially confusing.

Also include a description of your control and instruction decoding logic. For each control logic signal (or group of related control logic signals) you should provide (a) a brief description of what the signal does, e.g. what the values of the control signal mean; and (b) a truth table showing what value the signal takes for each possible opcode.

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 and nicely laid out, completely correct solution, a screenshot of the Logisim circuit itself can serve as a diagram, but, otherwise, use the documentation to clarify and explain any parts of your circuit we might find confusing.

What to Submit

Help and Hints

Help. Ask the instructor, TAs and consultants for help We also expect to see most students in office hours during the course of the project. Extra hours will be scheduled as needed.

Bugs. 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 a good idea 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.

Really, it shows. Do a pencil-and-paper design before implementing in Logisim. We will penalize poorly laid-out designs that are hard to understand.

What to do first. Don't wait to get started. However, because we are still covering pipelining and pipeline hazards in lecture, you probably will not want to start right in on the final design. The following order of operations might be sensible:

  1. Find a partner ASAP.
  2. Read the MIPS manual page for every instruction (some have unusual quirks).
  3. Start writing test programs, including code both with and without hazards.
  4. (After pipelining is covered in lecture) Design on paper, build in Logisim, and begin to test a pipelined CPU that doesn't handle pipeline hazards. Write the documentation as you go.
  5. (After pipeline hazards are covered in lecture) Modify the datapath and control logic to handle pipeline hazards.

cs3410 Component Library Guide

The cs3410 Component Library is available on the course web page.

Loading the cs3410 library From Project > Load Library > Jar Library... select the cs3410.jar file. Also, put cs3410.jar in the same folder with the .circ file. You should now have a new folder in your sidebar containing the following components:

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. When the clock is triggered, if WE is high, the data value at input W is stored in register rW. The register file can be configured to use rising clock edges as trigger (the default), falling edge, or to be level sensitive.


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 machine code instruction at the PC address, or an error if the PC is invalid. Reading addresses outside the range of code supplied by the assembly file will cause the ROM to output zero, which happens to encode a no-op in MIPS. The assembly language is in the format described below.


MIPS ALU. Computes a result as follows:

Op name C
----  ----------------------  --------------  
000xshift left C = B << Sa;
001xadd C = A + B
0100shift right logical C = B >>> Sa
0101shift right arithmetic C = B >> Sa
011xsubtract C = A - B
1000and C = A & B
1010or C = A | B
1100xor C = A ^ B
1110nor C = ~(A | B)
1001eq C = (A == B) ? 1 : 0
1011ne C = (A != B) ? 1 : 0
1101gtz C = (A > 0) ? 1 : 0
1111lez C = (A ≤ 0) ? 1 : 0

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

LCD Video. If WE is high on the rising edge of CLK, writes a pixel on the LCD screen at the location given by the 7-bit unsigned X and Y coordinates. The pixel color is specified by 16-bit RGB input (in 5-5-5 format). The RST input resets the LCD screen. With some cleverness, you can redirect memory writes to this device to let your program draw on the LCD screen. Logisim also comes with some interesting input and output devices which can be used similarly.



MIPS (subset) Assembly Syntax

The MIPS Program ROM component has a built-in assembler that 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 pound ('#') is a comment. In project 1, you will only use a few of the instructions listed here.

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. Most integer arguments (immediates, shift amounts, jump targets) can be specified in hex (i.e. 0x12ab), in decimal (i.e. 1234 or -1234), a label, or the special constant PC. The assembler will replace PC with the address of the instruction itself. Most constants have some restrictions: jump destinations must have the same upper 4 bits as the PC+4, and must be a multiple of 4; branch destinations must be a multiple of 4 and fit in a signed 18 bit immediate; etc. As a special case, when a branch target is specified symbolically as a label, the assembler will automatically subtract the current PC value to obtain a signed offset.

By default, the first instruction will be placed at address 0, and subsequent instructions are placed at at addresses 4, 8, 12, etc.

Assembler directives. The Program ROM assembler understands two standard MIPS assembler directives, .text and .word, both of which take integer (hex or decimal) arguments. For example, .text 0x50000000 will direct the assembler place subsequent instructions starting at address 0x50000000. And .word 0x24030005 directs the assembler to use the value 0x24030005 as the next machine instruction, which happens to be the machine code for ADDIU $3, $0, 5.

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 $5
JALR $31, $5
JALR $5
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)

Items in white are required for project 1 and project 2. 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
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
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 β * β β β * β β