Description

• Build and test a pipelined MIPS CPU that implements a subset of the MIPS instruction set.
• Handle hazards through forwarding and stalling.

Description

In this lab, you will use Logisim to design and test a pipelined MIPS CPU that implements a subset of the MIPS instruction set, along with data hazard resolution. Make sure to use the given circuit for this assignment, as the Register File included implements internal forwarding, while previous versions do not.

Details

Your CPU must implement all instructions from Lab 3. Specifically, you must implement:

AND, ANDI, ADD, ADDI, OR, ORI, SUB, SLT, SLTU*, XOR, LW, SW, BEQ, J, JAL, JR, SLL, SRL

As with the previous labs, the instructions for SLTU are incorrect in the given MIPS PDF.

The instructions should read:

If rs < rt with an unsigned comparison, put 1 into rd. Otherwise put 0 into rd.

The control signals for the ALU are identical to Lab 3, and are reposted here for your convenience:

Operation	ALUCtl3	ALUCtl2	ALUCtl1	ALUCtl0
OR	0	0	0	0
SLTU	0	0	0	1
SLT	0	0	1	0
ADD	0	0	1	1
SUB	0	1	0	0
XOR	0	1	0	1
AND	0	1	1	0
…
SLR	1	1	1	0
SLL	1	1	1	1

Your CPU should not have any branch delay slots, and should use a branch not taken strategy for branch prediction. You may implement your control signals using any method you prefer. You can use combinational logic, microcode, or a combination of the two.

Hazards

As you have learned in lecture, pipelining a CPU introduces the possibilities of hazards. Your CPU must be able to handle all possible hazards. Your CPU must use forwarding where possible, and resort to stalling only where necessary. Below is a subset of the possible hazards you may encounter. This means that, while all possible hazards may not be listed here, your CPU must still be able to handle all possible hazards.

1. Read After Write (RAW) hazards. Your CPU must perform forwarding on both ALU inputs to prevent Read After Write hazards. Your CPU must handle the hazards in the following code segments without stalling.

ADD $4, $5, $6	ADD $4, $5, $6	ADD $4, $5, $6	ADD $4, $5, $6
ADD $7, $4, $4	ADD $8, $9, $10	ADD $8, $9, $10	LW $8, 0($4)
	ADD $7, $4, $4	ADD $7, $4, $8

2. Load Use Your CPU must handle load-use hazards through stalling and forwarding. You may only stall when necessary. If you stall when forwarding would work, you will lose points.

LW $8, 0($4)	LW $8, 0($4)
ADD $10, $9, $8	ADD $4, $5, $6
	ADD $10, $9, $8

3. Store Word (SW) hazards. Your CPU must handle all Read After Write hazards associated with SW using forwarding. You may need to stall in certain cases, as well.

ADD $4, $5, $6	LW $4, 0($0)	LW $4, 0($0)
SW $4, 0($4)	SW $4, 10($0)	SW $5, 10($4)

4. Control Flow Read After Write hazards can also occur with the BEQ and JR instructions.

The following hazards must be solved with forwarding.

ADD $4, $5, $6	ADD $4, $5, $6	LW $10, 0($0)	LW $10, 0($0)
ADD $8, $9, $10	ADD $8, $9, $10	ADD $4, $5, $6	ADD $4, $5, $6
BEQ $0, $4, BranchAddr	JR $4	ADD $8, $9, $10	ADD $8, $9, $10
		BEQ $0, $10, BranchAddr	JR $10

The following hazards should be resolved with stalls.

ADD $4, $5, $6			ADD $4, $5, $6	LW $10, 0($0)
BEQ $0, $4, BranchAddr			JR $4	ADD $4, $5, $6
				BEQ $0, $10, BranchAddr
	LW $10, 0($0)	LW $10, 0($0)			LW $10, 0($0)
	ADD $4, $5, $6	BEQ $0, $10, BranchAddr			JR $10
	JR $10

Branch Prediction

In order to reduce the number of stall cycles in our CPU, we will be using a branch not taken prediction strategy. This means that, if a branch is taken, we will need to provide hardware to squash the incorrectly predicted instructions. For example:

BEQ $0, $0, BranchAddr
ADD $1, $1, $1	This instruction must be squashed.

The number of instructions that must be squashed is dependent on where in the pipeline you evaluate your branch condition. Jump instructions can be viewed as branches that are always taken and therefore are able to have their “branch” conditions evaluated in the Decode stage.