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:

• A single Logisim project file containing your processor.
• A test program that 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.

  Test files containing MIPS assembly for the 3 different versions of fibonacci.

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

---

Tips and Suggestions

• Refer to the MIPS manual for a full specification of the MIPS ISA. You will need to refer to it often.
• 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.
• 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

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