CS61C Summer 2016 Project 3-2: CPU

TA: Steven Ho

Due Monday, August 1st, 2016 @ 11:59 PM

Updates and Clarifications


IMPORTANT INFO - PLEASE READ


Overview

In this project you will be using Logisim to implement a simple 32-bit two-cycle processor. Throughout the implementation of this project, we'll be making design choices that make it compatible with machine code outputs from MARS and your Project 2! When you're done, you'll be able to run MIPS code through your assembler and linker, and then on your very own CPU :D

In part II, you will complete a 2-stage pipelined processor!

0) Obtaining the Files

We have added the CPU template (cpu.circ) and harness (run.circ), the data memory module (mem.circ), and a basic assembler (assembler.py) to help you test your CPU. The only file you will turn in for grading is cpu.circ. Please fetch and merge the changes from the proj3-2 branch of the starter repo. For example, if you have set the proj3-starter remote link:

cd <proj3 directory>                  # Go inside the project directory
git fetch proj3-starter
git merge proj3-starter/proj3-2 -m "merge proj3-2 skeleton code"

If you do not have the proj3-starter remote link from part I, you can run:

git remote add proj3-starter https://github.com/cs61c-summer2016/proj3-starter.git

If you do have some other incorrect value for the proj3-starter remote link, delete it first by running:

git remote rm proj3-starter

1) Getting Started - Processor

We have provided a skeleton for your processor in cpu.circ. Your processor will contain an instance of your ALU and Register File, as well as a memory unit provided in your starter kit. You are also responsible for constructing the entire datapath and control from scratch. Your completed processor should implement the ISA detailed below in the section Instruction Set Architecture (ISA) using a two-cycle pipeline, specified below.

Your processor will get its program from the processor harness run.circ. Your processor will output the address of an instruction, and accept the instruction at that address as an input. Inspect run.circ to see exactly what's going on. (This same harness will be used to test your final submission, so make sure your CPU fits in the harness before submitting your work!) Your processor has 2 inputs that come from the harness:

Input Name Bit Width Description
INSTRUCTION 32 Driven with the instruction at the instruction memory address identified by the FETCH_ADDRESS (see below).
CLOCK 1 The input for the clock. As with the register file, this can be sent into subcircuits (e.g. the CLK input for your register file) or attached directly to the clock inputs of memory units in Logisim, but should not otherwise be gated (i.e., do not invert it, do not AND it with anything, etc.).

Your processor must provide 6 outputs to the harness:

Output Name Bit Width Description
$s0 32 Driven with the contents of $s0. FOR TESTING
$s1 32 Driven with the contents of $s1. FOR TESTING
$s2 32 Driven with the contents of $s2. FOR TESTING
$ra 32 Driven with the contents of $ra. FOR TESTING
$sp 32 Driven with the contents of $sp. FOR TESTING
FETCH_ADDRESS 32 This output is used to select which instruction is presented to the processor on the INSTRUCTION input.

ONE MORE THING: In addition to these inputs and outputs, you also need to have an LED unit which lights up to signify signed overflow. This indicator should be wired to the signed overflow port of your ALU. This should be viewable in your main circuit.

Just like in part I, be careful not to move the input or output pins! You should ensure that your processor is correctly loaded by a fresh copy of run.circ before you submit. You can download a fresh copy from the starter repo website.

1.5) Getting Started - Memory

The memory unit is already fully implemented for you! Here's a quick summary of its inputs and outputs:

Output Name In- or Out-put? Bit Width Description
A: ADDR In 32 Address to read/write to in Memory
D: WRITE DATA In 32 Value to be written to Memory
En: WRITE ENABLE In 1 Equal to one on any instructions that write to memory, and zero otherwise
Clock In 1 Driven by the clock input to cpu.circ
D: READ DATA Out 32 Driven by the data stored at the specified address.

One important caveat is that the memory is only 64 MB in size, due to the limitations of Logisim's built-in memory block. If you try to read or write addresses greater than or equal to 226, they will alias to lower addresses. That is, the address 226 + X will appear to be the same as X.

2) Pipelining

Your processor will have a 2-stage pipeline:

  1. Instruction Fetch: An instruction is fetched from the instruction memory.
  2. Execute: The instruction is decoded, executed, and committed (written back). This is a combination of the remaining stages of a normal MIPS pipeline.

You should note that data hazards do NOT pose a problem for this design, since all accesses to all sources of data happens only in a single pipeline stage. However, there are still control hazards to deal with. Our ISA does not expose branch delay slots to software. This means that the instruction immediately after a branch or jump is not necessarily executed if the branch is taken. This makes your task a bit more complex. By the time you have figured out that a branch or jump is in the execute stage, you have already accessed the instruction memory and pulled out (possibly) the wrong instruction. You will therefore need to "kill" instructions that are being fetched if the instruction under execution is a jump or a taken branch. Instruction kills for this project MUST be accomplished by MUXing a nop into the instruction stream and sending the nop into the Execute stage instead of using the fetched instruction. Notice that 0x00000000 is a nop instruction; please use this, as it will simplify grading and testing. You should only kill if a branch is taken (do not kill otherwise), but do kill on every type of jump.

Because all of the control and execution is handled in the Execute stage, your processor should be more or less indistinguishable from a single-cycle implementation, barring the one-cycle startup latency and the branch/jump delays. However, we will be enforcing the two-pipeline design. If you are unsure about pipelining, it is perfectly fine (maybe even recommended) to first implement a single-cycle processor. This will allow you to first verify that your instruction decoding, control signals, arithmetic operations, and memory accesses are all working properly. From a single-cycle processor you can then split off the Instruction Fetch stage with a few additions and a few logical tweaks. Some things to consider:

You might also notice a bootstrapping problem here: during the first cycle, the instruction register sitting between the pipeline stages won't contain an instruction loaded from memory. How do we deal with this? It happens that Logisim automatically sets registers to zero on reset; the instruction register will then contain a nop. We will allow you to depend on this behavior of Logisim. Remember to go to Simulate --> Reset Simulation (Ctrl+R) to reset your processor.

3) Instruction Set Architecture (ISA)

Your CPU will support the instructions listed below. In all of the instructions you recognize from MIPS, the instruction format, opcode, funct, and register numbers should be taken directly from your greensheet. Notice that not all of the native MIPS functions are listed in the CORE INSRUCTION SET section of the greensheet - you may also need to look in the ARITHMETIC CORE INSTRUCTION SET section, and in the OPCODES, BASE CONVERSION, ASCII SYMBOLS table on the back! There will also be an instruction that is foreign to MIPS: specifications for this new instruction will follow the table, as well as clarifications on some other selected instructions.

Instruction Format
Add add $rd, $rs, $rt
Add Immediate addi $rt, $rs, immediate
Add Immediate Unsigned addiu $rt, $rs, immediate
Add Unsigned addu $rd, $rs, $rt
And and $rd, $rs, $rt
And Immediate andi $rt, $rs, immediate
Branch on Equal beq $rs, $rt, label
Branch on Not Equal bne $rs, $rt, label
Branch on Overflow NEW! bov $rs, $rt, label
Jump j label
Jump and Link jal label
Jump Register jr $rs
Jump and Link Register jalr $rs
Load Upper Immediate lui $rt, immediate
Load Word lw $rt, offset($rs)
Or or $rd, $rs, $rt
Or Immediate ori $rt, $rs, immediate
Set Less Than slt $rd, $rs, $rt
Set Less Than Immediate slti $rt, $rs, immediate
Set Less Than Immediate Unsigned sltiu $rt, $rs, immediate
Set Less Than Unsigned sltu $rd, $rs, $rt
Shift Left Logical sll $rd, $rt, shamt
Shift Right Arithmetic sra $rd, $rt, shamt
Shift Right Logical srl $rd, $rt, shamt
Store Word sw $rt, offset($rs)
Sub sub $rd, $rs, $rt
Sub Unsigned subu $rd, $rs, $rt

Branch on Overflow (bov)

This instruction is similar in nature to the other branch instructions but checks for overflow rather than equality:

Jump and Link (jal) and Jump and Link Register (jalr)

Since we only have a 2 staged pipeline, it does not make sense to store PC + 8 in $ra on a jal/jalr instruction! Instead we will store PC + 4

Logisim Notes

If you are having trouble with Logisim, RESTART IT and RELOAD your circuit! Don't waste your time chasing a bug that is not your fault. However, if restarting doesn't solve the problem, it is more likely that the bug is a flaw in your project. Please post to Piazza about any crazy bugs that you find and we will investigate.

Things to Look Out For

Logisim's Combinational Analysis Feature

Logisim offers some functionality for automating circuit implementation given a truth table, or vice versa. Though not disallowed (enforcing such a requirement is impractical), use of this feature is discouraged. Remember that you will not be allowed to have a laptop running Logisim on the final.


Testing

make p2

In order to run a very short and simple sequence of instructions on your CPU, you can run make p2 from your project 3 directory. Note: This test assumes you have pipelined the CPU, so you should run this after you've implemented pipelining.

Option 1: Manual Checking

For part 2, it is somewhat difficult to provide small unit tests such as the ones from part 1 since you are completing the full datapath. As such, the best approach would be to write short MIPS programs and exercise your datapath in different ways. To facilitate this, we have provided you with a rudimentary MIPS assembler that functions similarly to your project 2. To assemble a MIPS file, simply run the assembler with python and pass in your input file as follows:

vim test.s  # create your assembly file. Remember to only use the instructions provide in the ISA above
python assembler.py test.s # This will generate an output file named test.hex
python assembler.py test.s -v # Same as above, but also provides some verbose output on command line.
    

Note: the assembler has only been tested with python 2.7, so it may be easier to run it remotely off of the hive* servers if you haven't set up your python environments.

Once you have generated the machine code, you'll have to load it into the instruction memory unit in run.circ and begin execution. To do so, first open run.circ and locate the Instruction Memory Unit.

Click on the memory module and then, in the left sidebar, click on the "(Click to edit)" option next to "Contents". This will bring up a hex editor with the option to open a previously created hex file. This is where we load the file outputted by the assembler earlier.

Once you've loaded the machine code you can tick the clock manually and watch your CPU execute your program! You can double click on the CPU using the poke tool to take a look at how your datapath is behaving under the given input. You can also fire up MARS at the same time and step through your code there simultaneously. This will allow you to compare the expected behaviour, as seen in MARS, with the behaviour your circuit is exhibiting. Of course, this approach is not valid for the new instructions - for those you'll have to rely solely on your own test assembly code.

Option 2: Analyzing Final Register Values

We have provided you with a Python testing script that takes in MIPS assembly code and runs that code on your cpu.circ. Then it will print out the values that are in the five debugging registers after the code has completed execution.

IMPORTANT: You should only run this script after you have made sure that make p2 runs successfully and after you have implemented pipelining. Otherwise, the registers will be one cycle off.

We have written a sample MIPS test file sample_reg_check.s inside the tests subdirectory. In order to run it on your cpu.circ, you simply run:

python see_output.py tests/sample_reg_check.s
    

Note: The python command may differ if you are using Linux or Windows. An example of the output is below:

ONE MORE IMPORTANT NOTE: The MIPS files you make for testing must include a "dummy" line at the end of the program's execution in order for you to see all of your register outputs correctly. This is because the addition of the pipeline causes the script to stop running the cpu.circ one cycle early. Thus, make sure you add a dummy line so that you see the true values that are in the registers after executing your test file.

After running the script, you can manually go through the circuit with the instructions already loaded by looking at a circuit called test.circ in the folder containing see_output.py. This way you can check what is in your testing registers at every step of the execution.

Keep in mind that the assembler.py that we have provided is not able to parse pseudoinstructions or uncommon instructions, so do not include them in your test MIPS files. You will need to rely on Testing Option 1 in order to test the instructions that can't be parsed.

Submission

The only file you will turn in for grading is cpu.circ. Since this project is done solo and you are not required to submit your repository for this project, there is just one step required to submit proj3-2. You only need to submit using the standard unix submit program on the instructional servers. This assumes that you followed the earlier instructions and did all of your work inside of the git repository that you created when you started proj3-1. To submit, follow these instructions after logging into your cs61c-XX class account:

cd <proj3 repo directory>
submit proj3-2

Once you type submit proj3-2, follow the prompts generated by the submission system. It will tell you when your submission has been successful and you can confirm this by looking at the output of glookup -t.

Resubmitting

If you need to re-submit, you can follow the same set of steps that you would if you were submitting for the first time.

Deliverables

cpu.circ

We will be using our own versions of the *-harness.circ and run.circ files, so you do not need to submit those. In addition, you should not depend on any changes you make to those files.

Grading

This project will be graded in large part by an autograder. Readers will also glance at your circuits. If some of your tests fail the readers will look to see if there is a simple wiring problem. If they can find one, they will give you the new score from the autograder minus a deduction based on the severity of the wiring problem. For this reason, neatness is a small part of your grade - please try to make your circuits neat and readable.

Regrade Requests

Due to the nature of Logisim being very difficult and time-consuming to open, understand, and edit, the regrading policy will be much stricter than it was for project 3-1. The penalty for asking for a regrade is a 15% reduction of your final score, whether or not your changes work/improve your score. Your suggested changes must be minor and you cannot add any logic. You may not ask me to add gates, registers, wires, etc. You may ask me to change the gate options, extend wires, or edit tunnel names. We expect you to submit a finished project, not something that has minor errors. Lastly, you can only ask for a regrade once, so use it wisely. The deadline for a regrade will be announced shortly.