Group Project 2 - Fully Pipelined MIPS

This is cumulative. Both Table A and Table B instructions are required.

CS3410 Spring 2015

Work-in-progress Circuit Due: 11:59pm, Monday, March 16, 2015

Final Design Due: 11:59pm, Thursday, March 26, 2015

Late Policy: Start early, don't be late.

You must work in the same group for this project as for the last.

Overview

In this project you will extend and complete the processor design you started in project 1. Your basic execution loop from the previous assignment should contain most of the major components, with the exception of RAM for the load/store instructions. For this project we will use a split-memory "Harvard" architecture design: The Program ROM will store a read-only copy of the instructions, and a separate RAM will be used to store data for the program's execution. You will now implement all the other instructions mentioned in the last project project, including load/stores, jumps and branches.

You should reuse most or all of your work from project 1. This means updating the circuit circuit to handle the new instructions, revising the documentation to discuss any changes or addition to the datapath and control logic, and expanding your test program. This includes, of course, fixing anything that was broken or incomplete from the first project (ask the staff for help if needed — we will not be posting a solution, but neither do we want to penalize you twice for mistakes in project 1).

Important:Consult the MIPS Handbook and make sure that all aspects of each of the instructions is implemented exactly as specified in the handbook, except where noted here.

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.

What to Implement

Implement all of the instructions in Table B. You should have already decoded all these instructions in project 1. You may have to add additional decoding logic for any new control signals you introduce, as for the memory stage and for the PC update.

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

Our testing programs will include a mixture of all the instructions from projects 1 and 2, so you must ensure that the instructions from project 1 are correctly implemented as well.

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 Tables A and B.

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.

Delay slot. You must properly implement the branch/jump delay slot, so that the instruction immediately following a branch or jump is always executed, and any relative addresses or significant bits for the PC update are based on the that address and not the address of the jump instruction itself.

Memory load hazard. Memory operations should not have delay slot, but instead use stalling to avoid hazards. That is, you should introduce a bubble in the pipeline after a memory operation, but only if a hazard is detected.

RAM. The cs3410.jar Logisim library on the course web site includes a MIPS RAM component for your memory stage (see the description below). Logisim does not support RAM components large enough to cover a full 32-bit (4GB) address space. The largest RAM component contains 64MB of data using 24-bit-wide word-addresses. Our tests will rely on memory addresses in the lowest 1MB of the address space, so your your processor should contain at least 1MB of RAM placed at the lowest addresses. That is, reads and writes to byte-addresses in the range 0x00000000 to 0x000fffff should work as expected.
Important: Writes to addresses that not backed by any RAM should have no effect, and the address space should not "wrap around" after 1MB.

For the adventurous. Instead of having a single RAM component backing the low part of the address space, you can add multiple RAM components to cover various convenient pieces of the address space. For instance, to support the conventional MIPS program layout, put a second RAM to cover a few MB of address space near addresses 0x10000000 for program data, and a third RAM to cover addresses just under 0x80000000 for the stack. Or you can redirect reads and writes at certain addresses to some of Logisim's input/output devices. It is actually fairly trivial to make writes at addresses just above 0x80000000 write coordinate and color pixel data to an LCD screen component or ASCII characters to a TTY component. Similarly you can make reads at some designated unused address read from a Logisim Keyboard, Joystick, or other input component. Bonus points if you can code pong to go with an LCD.

Processor Components

As in project 1, build your MIPS processor as a single Logisim circuit file. Continue to use the same cs3410.jar library that we provided. Do not use Logisim's Project > Load Library > Logisim Library command to import circuits from other Logisim files.

Your top-level circuit must be named either "MIPS" or "MIPS32" (case-sensitive).

Your processor should have only one instance of each of these components: Register File, MIPS Program ROM, and ALU.

The restriction on incrementers has been relaxed since project 1: You may now use more than one incrementer, although incrementing PC by 4 should still be done with one incrementer rather than four.

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 from both project 1 and project 2. As before, 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.

We would also like you to test your program on a complex computation. A hailstone sequence is defined as follows: start at any positive integer n; if n is even, divide it by 2 to get n/2; else triple it and add one to get 3n+1; then repeat with the new number. You will implement the hailstone function, which counts how many steps it takes for the hailstone sequence to converge to 1 from a given starting point. For instance, hailstone(40) returns 8 because the sequence starting at 40 converges in 8 steps: 40, 20, 10, 5, 16, 8, 4, 2, 1. And hailstone(31) returns 106 due to its long and chaotic sequence: 31, 94, 47, 142, 71, 214, ..., 3077, 9232, 4616, 2308, 1154, 577, ..., 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

There are several ways to compute the hailstone function. You will implement all three of the methods below (please do not submit MIPS code with any form of main method).