CS61C Spring 2016 Lab 6 - CPU Project Prep

Setup

Copy the starter lab files as usual, from the directory: ~cs61c/labs/06

Exercises

The lab this week is intended to be pretty short. It consists of a pipelining exercise which you will need to check off like normal. After, we have created a guide to help you start out on the CPU project. We encourage you to stay at lab and work through the guide with your partner, asking the TA or lab assistants for help! This second part has no checkoff portion.

At the end, we have included an optional exercise demo-ing a feature in MARS called "MIPS X-RAY", which may be useful to conceptually understand the CPU project. There is also no checkoff for this portion.

Exercise 1: Pipelining

Assume that on power-on, registers initially contain zeros.

Consider the following 2-input FSM. Its next state and output is computed by multiplying the inputs and adding it to the current state.

Say the propogation delay of a adder block is 50ns, the propogation delay of a multiplication block is 55 ns, and the clk-to-q delay of a register is 5ns. Calculate the maximum clock rate at which this circuit can operate. Assume that the register setup time is negligible, and that both inputs come from clocked registers that receive their data from an outside source.

Checkoff

  • Show your TA the calculations you performed to find the maximum clock rate (non-pipelined).

We want to improve the performance of this circuit, and let it operate at a higher clock rate. To do so, we will divide up the multiplication and addition into two different pipeline stages; in the first pipeline stage, we will perform the multiplication of the two inputs. In the second pipeline stage, we will add the product to the state.

Our definition of "correctness" will be simple: we will consider the sequence of outputs from this circuit "correct" iff it corresponds to the sequence of outputs the non-pipelined version would emit, potentially with some leading zeros. For example, if for some sequence of inputs the non-pipelined version emits [3,5,1,2,4, ...], a correct circuit might emit the sequence of outputs [0,3,5,1,2,4, ...] for that same sequence of inputs.

For your convenience and to help standardize check-offs, we are providing a starting point in the files pipeline.circ and ROMdata (use the links or pull from ~cs61c/labs/07/). In pipeline.circ, the sub-circuit Non-pipelined is set up exactly as the figure above. The main circuit is set up to produce the output sequence [3,5,1,2,4,-1,0,0,...] on the non-pipelined version of this circuit. It is also a handy example of how to use memory from a file. The ROM block should be initialized to the proper data, but if it is zero-ed out, right-click it and choose "Load image..." and select ROMdata.

Note that we need a register to hold the intermediate value of the computation between pipeline stages. This is a general theme with pipelines.

  1. Complete the sub-circuit Pipelined. You will need to add a register to divide the multiplication and addition into separate pipeline stages.
  2. Calculate the maximum clock rate for the pipelined version of the circuit.
  3. When we talked about pipelining in lecture, we discussed that if a computation depends on the output of a previous computation, it's difficult to pipeline them and we often need to insert a pipeline "bubble" (or several) to ensure that the output of the first computation is ready to be an input to the second. Explain why inserting such "bubbles" is unnecessary for this particular circuit.

Checkoff

Exercise 2: CPU Project Guide

We know that starting off part 2 with a blank slate might be intimidating, so we want to guide you through how to think about this project by implementing a simple R-type instruction, add. Feel free to work with your lab partner through this guide, but make sure you have separate copies when you continue working on your project later. There is no checkoff associated with this exercise (you can check off after finishing the previous exercise, exercise 1).

Recall the five stages of the MIPS pipeline:

  1. Instruction Fetch
  2. Instruction Decode
  3. Execute
  4. Memory
  5. Write Back

This guide will help you work through each of these stages, as it pertains to the add instruction. Each section will contain questions for you to think through, pointers to important details, and references to lecture material - but won't tell you exactly how to implement it. You may need to read and understand each question before going to the next one, and you can see the answers by clicking on the question. During your implementation, feel free to place things in subcircuits as you see fit.

Stage 1: Instruction Fetch

The main thing we are concerned about in this stage is: how do we get the current instruction? From lecture, we know that all MIPS instructions are stored in the instruction memory, and each of these instructions can be accessed through an address.

  1. Which file in the project holds your instruction memory? How does it connect to your cpu.circ file?

    The instruction memory is the ROM module in run.circ. It provides an input into your CPU named "instruction" and takes an output named "fetch_addr".

  2. In your CPU, how would changing the address you output to fetch_address affect the instruction input? The instruction that run.circ outputs to your CPU should be the instruction at address fetch_address in instruction memory.
  3. How do you know what the fetch_address should be? (Hint: it is also known as PC) fetch_address is the address of the current instruction being executed, so it is saved in the PC register. For this project, it's fine for the PC to start at 0, and that is the default value for registers.
  4. For this project, does your PC hold an address of a byte or a word? If you look in run.circ, you will see that the address coming from your CPU will go through a splitter before entering the word-addressed memory module. This means that your PC should hold a byte address.
  5. For basic programs without any jumps or branches, how would the PC change from line to line? The PC must increment by 1 instruction in order to go to the next instruction, as the address held by the PC register represents what instruction to execute.
  6. We have provided the PC register in the cpu.circ file. Please implement the PC's behavior for simple programs - ignoring jumps and branches. You will have to add in the latter two in the project, but for now we are only concerned with being able to run strings of add instructions. Where should the output of the PC register go? Remember to connect the clock!

Stage 2: Instruction Decode

Now that we have our instruction coming from the instruction input, we have break it down in the Instruction Decode step, according to the MIPS Instruction Format you have learned.

  1. What type of instruction is add? What are the different bit fields and which bits are needed for each? R-type. funct: 0-5, shamt: 6-10, rd: 11-15, rt: 16-20, rs: 21-25, opcode: 26-31.
  2. In Logisim, what tool would you use to split out different groups of bits? Splitter!
  3. Please implement the instruction field decode stage using the instruction input. You should use tunnels to label and group the bits.
  4. Now we need to get the data from the corresponding registers, using the register file. Which instruction fields should be connected to the register file? Which inputs of the register file should it connect to? Instruction fields rs and rt will need to connect to read register 1 and 2.
  5. Please implement reading from the register file. You will have to bring in your register file from part 1 of the project. Remember to connect the clock!

Stage 3: Execute

The Execute stage, also known as the ALU stage, is where the computation of most instructions is performed. This is also where we will introduce the idea of using a Control Module.

  1. For the add instruction, what should be your inputs in to the ALU? Read Data 1 and 2 should go into ports A and B of the ALU.
  2. In the ALU, what is the purpose of the Switch, also called the ALU_ctr? What should you input for the add instruction? It chooses which operation the ALU should perform. For add, the switch value should be 5.
  3. Although it is possible for now to just put a constant as the switch input, why would this be infeasible as you need to implement more instructions? With more instructions, the input to the ALU might need to change, so you would need to have some sort of circuit that changes the switch depending on the instruction being executed.
  4. How would you know what the switch's value should be for R-type instructions? What about for I- and J-type instructions? The switch's value would depend on the funct code for R-type and the opcode for I- and J-type instructions. This gives us a motivation to create a subcircuit that instructs the ALU what to do, based on the opcode or funct - the Control Module.
  5. Please create a new subcircuit for the Control Module. This module will need to take in as inputs the opcode and funct, using these to output a value for the ALU Switch, depending on what the current instruction is. There are a few ways of doing this. As you implement more instructions, this circuit will have to expand and become more complex.
  6. Please bring in your ALU from part 1 of the project and connect the ALU inputs correctly. Do you need to connect the clock? Why or why not?

Stage 4: Memory

The memory stage is where the memory can be written to using store instructions and read from using load instructions. Because the add instruction does not use memory, we will not spend too much time here.

  1. Please bring in the MEM module that we provided. At this point, we cannot connect most of the inputs, as we don't know where they should come from. However, you can still connect the clock.

Stage 5: Write back

The write back stage is where the results of the operation is saved back to the registers. Although not all instructions will write back to the register file (can you think of some which do not?), the add instruction does.

  1. Looking at the entire ISA, what are some of the instructions that will write back to a register? Where in the datapath would it get the values? add is an example that will take the output from the ALU and write it back. lw will take the output from MEM and write it to a register. There are more not specified here.
  2. Let's create the write back phase so that it is able to write both ALU and MEM outputs to the Register File. However, we need to choose between the two of them, as only one wire can end up being an input to the register file. Bring a wire from both the ALU and MEM, and connect it to a 2-to-1 MUX.
  3. What should you use as the Select input to the MUX? What does the input depend on? This input should be able to choose between the two MUX inputs, ALU and MEM, which means that its value depends on which instruction is executing. This suggests that the input should originate from the Control Module, as the Control Module is responsible for figuring out which instruction is executing (using the opcode or funct).
  4. We now come to the second, and arguably more important, role of Control Modules - determining what values to output to the CPU, in order to control the path of execution. These values are called Control Signals.

    One example of this is the control signal that connects to the MUX from the previous step, which is commonly called MemToReg. MemToReg is true (on) for instructions that read from memory a value to write to the registers (load instructions) and false (off) for other instructions. When connected to the MUX, it should let the value from MEM continue through the MUX when it is on and let the value from the ALU to continue otherwise.

    You can find more control signals on the lecture slides, and you'll need to define some yourself. If you find yourself needing a MUX, it's very likely that you'll need to define a control signal for it.

  5. There are a few ways of implementing the Control so that it can translate the opcode/funct to the corresponding instruction and then set the control signals correctly. One way to do so is outlined in lecture, which uses "AND" logic and "OR" logic to accomplish both tasks. If you are unfamiliar with it, review the slide now and try implementing it for the add instruction and the MemToReg control signal.
  6. Now that we have the inputs to the MUX sorted out, we need to wire the output. Where should the output connect to? Because the output is the data that you want to write into the Register File, it should connect to the Write Data input on the Register File.
  7. There are two more inputs on the Register File which are important for writing data: Write Enable and Write Register. One of these will come from the Instruction Decode stage and the other one will be a new control signal that you need to design. Please finish off the Write Back stage by connecting the Write Data, Write Enable, and Write Register inputs on the Register File correctly.

If you have done all of the following steps correctly, you should have a processor that works for add instructions. For the rest of the project, you will be implementing more instructions in much of the same ways - connecting outputs to inputs, adding MUXes and other Logisim components, and defining new control signals. Hopefully, this will be an easier task now that you have a basic skeleton to work off of. Remember, the lecture slides have a lot of information already, and will help you to continue building on the circuits you have now. Good luck!

Special thanks to Julian Early and Steven Ho for testing and proofreading this lab!

Optional exercise: MIPS X-RAY

It turns out that MARS 4.5 has a new feature called MIPS X-RAY that will visualize the datapath while you are running your instruction. This might be useful for you for part 2 of the project! To run MARS 4.5 run the command mars-4.5. To open up this feature go under "Tools" and select "MIPS X RAY". It should open a window that looks like this:

We will use the file fib.s to see how each instruction goes through the datapath. Open fib.s and the MIPS X-RAY feature. You can connect the X-RAY to the instructions by pressing the "Connect to MIPS" button on the bottom left of the screen. Assemble the file by pressing the "Assemble" button on the upper left of the screen. You can then step through the code using the green "Step" button next to the "Assemble" button. The wires that are red signal that the control signal is on. You can also click on any control block to see what is going on inside of it. Play around with the feature, and the following questions will be based off what is going on in the control block.

Note: The X-RAY feature generalizes instructions to have the same opcode. You can see this in control with the instructions add and addi. For the questions below, base your soley on the logic of the control block.

Questions:

  • What do the bits BIT 0 - BIT 5 represent?
  • For what instruction or type of instructions is opALU0 active? What operation in the ALU does opALU0 represent?
  • For what instruction or type of instructions is opALU1 active?
  • For what instruction or type of instructions is ALUSrc active? What does this signal represent with respect to the input to the ALU?