CS 3410 Programming Assignment 2

Instructor: Kavita Bala

PA2: Fully Pipelined MIPS Processor

Due: Wednesday, October 22nd, 2008, 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 PA 2 you will complete the processor design you started in PA 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 assignment, 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.

You will now implement all the other instructions including load/stores, jumps and branches. It is now required that you correctly implement the delay slot, which means that the instruction immediately following a jump is always executed, and any relative addresses or significant bits are based on that address and not the address of the jump instruction itself.

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

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 In PA 1, the memory stage of the pipeline was a passthrough doing nothing. In PA 2, you will add load and store memory operations and populate that part of the pipeline. You will now implement all of the instructions in Table B, that you had only decoded in the PA 1. You will assume there is a delay slot for the jump and branches. You will also add the insertion of a bubble in the pipeline for loads/stores (if needed).

Table B
Jumps (with a delay slot) J, JR, JAL, JALR
Branches (with a delay slot) BEQ, GNE, BLEZ, BGTZ
Memory Load/Store (with a stall in pipeline if needed) LW, SW

Our testing programs will include a mixture of all the instructions from PA 1 and PA 2.


Testing

  1. 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.
  2. We would also like you to test your program on a complex computation: Fibonacci. Fibonacci numbers are described as:
    • F(0) = 0, F(1) = 1
    • F(n) = F(n-1) + F(n-2)
    They can be computed in multiple ways. Here are 3 ways to code this computation.
    • Recursive Fibonacci: This is the easiest to write, but very slow to compute. We will only use this recursive evaluation for values of N less than 4 or 5 (higher values of N make Logisim unhappy).
            int fibonacci(int n) {
      if (n == 0) return 0;
      if (n == 1) return 1;

      return fibonacci (n-1) + fibonacci (n-2);
      }
    • Iterative Fibonacci: The same series can be computed iteratively as in this snippet of code.
            int fibonacci(int n) {
      int u = 0, v = 1, i, t;

      if (n == 0) return 0;
      if (n == 1) return 1;

      for(i = 2; i <= n; i++) {
      t = u + v;
      u = v;
      v = t;
      }
      return v;
      }
    • Memoization for Fibonacci: We can store the previously computed Fibonacci numbers in an array (memoization) and reuse them as needed. In this snippet of code we assume that we are going to compute at most F(10).
            int fibonacci (int n) {
      int F[10], i;

      /* setup the F array to initially be uninitialized, except for 0 and 1*/
      F[0] = 0; F[1] = 1; for (i = 2; i < 10; i++) {F[i] = -1;}

      if (n == 0) {return 0;}
      if (n == 1) {return 1;}

      return fib (n, F);
      }

      int fib (int n, int* array) {
      int a, b;

      /* Check if F[n-2] has already been computed */
      if (F[n-2] == -1) {
      a = fib (n-2, F);
      F[n-2] = a;
      } else {
      a = F[n-2];
      }

      /* Check if F[n-1] has already been computed */
      if (F[n-1] == -1) {
      b = fib (n-1, F);
      F[n-1] = b;
      } else {
      b = F[n-1];
      }
      return a+b;
      }
Turn in these three versions of Fibonacci (you will have to translate them into assembler code), and make sure your processor handles them correctly.

What to submit Submit:

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.

Tips and Suggestions


Logisim and cs3410 Library Guide

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:

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
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 β * β β β * β β

Check the FAQ page for updates on the assignment.