Building a MIPS Processor*

(*Well, a slightly simplified version that only supports the instructions lw, sw, beq, add, sub, and, or, and slt instructions.)

Introduction

In this lab you will do three things:

1.  Define the control logic for the datapath control signals

2.  Hookup the key parts of a MIPS processor to make a working datapath. 3.  Verify that your design works by running a simple program

What to turn in

1.  You are expected to turn in your completed mips-datapath-lab.circ file. You should rename it as: “ lastname-firstname-mips-datapath-lab.circ” before you turn it in to simplify grading.

2.  You are also required to turn in a pdf file in which you answer the ToDos found within this document (name is as “ lastname-firstname-mips-datapath-lab.pdf”).

Getting Started

Read the background material

Before you get started, we strongly recommend you read chapter 4.3 and 4.4 in the 5th edition  of  the  book  (Patterson  &  Hennessy, Computer  Organization and Design: The Hardware/Software Interface). This will both show you pictures of what you are to build and explain how it works.

Files and programs

You are provided with the following files in the mips-datapath-lab.zip archive:

.    mips-datapath-lab.circ: an eviscerated shell that is missing all the important parts of a MIPS processor

.    1234.mem: a hex memory file that contains the values 1, 2, 3, 4 in the first 4 words of memory

.    test-code.mem: a file that contains a simple test program for verifying your design

To use these files you will need to install Logisim on your computer. We trust that you are capable of using Google to figure this out. Note that you may have to install a Java runtime to run Logisim. This is quite safe as long as you do not enable Java in your web browser.

Using Logisim

We recommend you watch the Logisim tutorials online before starting this lab (check this one for example). The key things for you to know before starting are:

1.  How to wire up components in Logisim (drag with the arrow cursor) and how to add logic gates (click on them under “Gates” on the left).

2.  How to edit the insides of components in logisim (double-click) and go back to the top view (click on “mips” on the left).

3.  How to simulate in Logisim (choose “Simulation Enabled” and use the pointer cursor to change values).

4.  How the clock works in Logisim (choose “Tick Once” to execute one clock cycle).

Okay, so maybe they don’t look all that similar, but you should be able to identify the same overall shape (the big loop on the top is part of the next PC logic) and the key components: PC, instruction memory, control logic, registers, ALU control, ALU, and data memory.

You probably noticed that the only wires we’ve included for you are the clock (at the bottom), a simplified next PC logic path (at the top), resets for the PC and register files (the red buttons), and one hint for getting started: we hooked up the RegWrite output from the Control logic to the RegWrite input on the Register file. (Wasn’t that nice of us?) There are also several MUXes missing. Completing the datapath connections is the second part of this lab.

The first part of the lab is completing the control logic. That’s right: those lovely ovals labeled “Control” and “ALU Control” are not finished on the inside. You will need to figure out the logic that goes inside of them.

A closer look

Before we get started on the actual work for the lab, let’s take a slightly closer look at what you have. Right-click on the ALU and choose “View alu” or double-click on it in the hierarchy list on the left.

The ALU

Here you can see the ALU. It has two inputs (A and B) and calculates 6 functions:

All 6 functions are calculated all the time, but the MUX at the end selects the right one based on the ALU control inputs. You can see from the figure that if the input to ALU control is 0010=2, then it will select input 2 (the third one since it starts counting at 0) and the output will be A+B. Compare this to the ALU function table below and make sure it makes sense to you. In particular, make sure you understand how the “set on less than” is implemented, since you will use that kind of logic later in the lab.

Now go back to the main view (double click on “mips” on the left) and then take a closer look at the “Control” unit.

The Control unit

You can see that the control unit has 4 parts:

1.  The input: the instruction OpCode

2.  The “Type Decode” which takes in the OpCode and outputs whether the instruction is an R-format, lw, sw, or beq instruction.

3.  The “Control Decode” which takes in the type of instruction and outputs the correct control signals for the datapath.

The Control unit’s job is to decode the instruction OpCode to control all the parts of the datapath. To do this we break up the decoding into two parts: first we decode the instruction type, then we use the instruction type to decode the control signals. This simplifies each piece of logic, which is great since you have to build them. (In practice, a CAD package will decide exactly how to break up the logic to make it as fast as possible.)

Part 1: Finishing the Control Logic

Now we’ll get down to the real work of making the control logic work. There are three parts you will need to complete: the Type Decode unit, the Control Decode unit, and the ALU Control unit. Each one uses a slightly different way to generate its output, so stay awake!

Start by taking a look inside the “Type Decode” unit:

Well, this is what you’d expect: the inputs are the instruction type (on the left) and the control signals are the outputs (on the right). Now to generate this logic you can either stare really hard at the table below and figure it out yourself (which is fine) or you can use the built in “Combinatorial Analysis” tool in Logisim to build it for you.

(You spent a few minutes pondering the logic on the right before reading this paragraph, right?)

If you look at the logic on the right, the output is coming from a MUX (D). The MUX has constant values as inputs (0, 1, 2, 6, and 7). The MUX is driven by a priority encoder (Pri), which takes signals from the logic in the middle. What happens is that if one of the inputs to the priority encoder is true, the priority encoder will tell the MUX to select that input, which will output the constant.

To make this all work, you just need to build the logic that determines which input to the priority encoder should be true given the ALUOp and Funciton inputs on the left.

Also, ALU control bits based on ALUop and Func field are provided below:

The truth table for controlling the ALU is also shown below:

Notice the part we’ve already done for you in shading (the two combinations that give you a 0010 as the output). Try to write down what the logic should be for determining if the operation is 0010 before you read further. Look at the bits in the table and figure out what the conditions are.

(Really, try to do this before you read the next bit.)

Let’s take a look at the first row. We have:

.    ALUOp1=0, ALUOp0=0, and all Fs are X. So the logic here is:

.    Operation     should     be     0010     whenever     ALUOp1=0     AND      ALUOp0=0. (We don’t care about the Fs because they are Xs.)

Now look at the circuit that we gave you above:

The top half (A) is an AND gate that is ANDing (NOT ALUOp1) and (NOT ALUOp0). This means the output of that AND gate will be true when ALUOp1=0 AND ALUOp0=0. (Which is, not so surprisingly, exactly what we want.)

Now what about the second shaded row where the answer is 0010? Try to work that out before going on.

The second row is:

.    ALUOp1=0 AND ALUOp0=0 AND F3=0 AND F2=0 AND F1=0 AND F0=0

Now look at the rest of the circuit (C) we built for you:

This is exactly that!

Now we have two cases where the output should be 0010. We need a final OR gate (B) to make sure that the output will be 0010 if either is true:

The result of the OR gate is 1 whenever the output should be 0010. To make the output be 0010 that value goes into the priority encoder, which selects the right input from the MUX to send out the results.

Note that all of the entries have Xs for both F4 and F5. That means we never use their values. So if you find yourself wiring up either F4 or F5 here you’ve probably made a mistake.

Testing

Once you have built the circuit you need to test it. Do this the same way you did for the previous circuit and make sure that the correct signals are set for each type of instruction.

Part 2: Hooking Up the Datapath

Now that you’ve completed (and tested, right?) the control logic, it’s time to hook up the datapath. Use the figure from the book (or datapath lectures) and your understanding of how the MIPS processor works to complete the datapath we’ve provided. You should not delete anything we’ve put in there. (There are a whole bunch of “probes” that show you the values on wires which you’ll want for debugging.)

You will need to pay special attention to how the instruction is broken up for connecting the processor. Note how the output from the instruction memory is split into four parts and you can see which bits are in each part. Also note that another copy of the instruction is split up below for the immediate field. You need to make sure you know which part of the instruction goes where! You can click on the splitter to see how it is configured as well.

And a memory file that contains 1,2,3, and 4 in the first 4 words of the memory (1234.mem).

To use these files you need to right-click on the instruction memory and data memories and load the appropriate files.

Now before you start running the program, figure out what that code will do.

Write down for each cycle (until the program runs out of instructions) what value is in each used register and what value and register will be written to for each instruction. (This is incredibly helpful for debugging.)

Once you’ve figured out what the program will do and what value will be written back to the register file after each instruction, start your program. Enable simulation, click the “Reset Program” and “Zero Register File” buttons to clear them. And then choose “Tick Once” to advance through each instruction.

When you first start simulating your first instruction will be in the processor. Make sure everything is working. Check the inputs and outputs, the MUXes, the control bits. And finally, check that the value being written back into the register file and the register being written. (These are both displayed with probes in the file so you can see them as the processor runs.)

When your program runs out of instructions you can double-check the contents of the register file by opening it up.

Debugging tips

.    Don’t advance past the first instruction until it is working correctly.

.    Check that the values for all registers (selected register and data) are correct and that the ALU operation is correct.

.    Use the finger tool to see the values on wires in the processor.