CS61C Fall 2017 Project 2-2: CPU

TA: Alex Jing

Due Due 11/06 @ 23:59:59

NOTE: All important updates will be posted on Piazza thread. Please prioritize Piazza as the source of truth and check it regularly.


IMPORTANT INFO - PLEASE READ

Updates


Overview

In this project you will be using Logisim to implement a 32-bit two-cycle processor based on RISC-V. This project is meant to give you a better understanding of the actual RISC-V datapath. In fact, after this project you would have everything you needed to know in order to build a RISC-V CPU in Logisim that could understand your assembled and linked input from Project 1!

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). First, commit all changes that you had for part 1. Then, please fetch and merge the changes from the proj2-2 branch of the starter repo. For example, if you have set the proj2-starter remote link:

cd proj2-XXX-YYY                  # Go inside the project directory
git fetch proj2-starter
git merge proj2-starter/part2 -m "merge proj2-2 skeleton code"

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

git remote add proj2-starter https://github.com/61c-teach/fa17-proj2-starter.git

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

git remote rm proj2-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 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 7 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
t0 32 Driven with the contents of t0. FOR TESTING
t1 32 Driven with the contents of t1. FOR TESTING
a0 32 Driven with the contents of a0. 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.

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.

2) Pipelining

Your processor will have a 2-stage pipeline:

  1. Instruction Fetch: An instruction is fetched from the instruction memory. (Note: while you can, please do not calculate jump address in this stage. Instead, you should try to deal with the jump control hazard.)
  2. Execute: The instruction is decoded, executed, and committed (written back). This is a combination of the remaining stages of a normal five-stage RISC-V pipeline.

First, make sure you understand what hazards you will have 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.

2.5) Controls

You can probably guess that control signals will play a very large part in this project. Figuring out all of the control signals may seem intimidating. We suggest taking a look at Discussion 6 to get started, and to remember that there is not a definitive set of control signals--walk through the datapath with different types of instructions, and when you see a mux or other component think about what selector/enable value you will need for that instruction.

Additionally, implementing the control signals can be done in many ways, including implementing the corresponding truth tables and using comparators. Since you are welcome to use any built-in Logisim circuits, we suggest using whichever component makes the most sense to you, whether performing logical operations on instruction bits and/or comparing fields to certain values.

Lastly, before you go into implementation, one last piece of advice from me: Modularize, modularize, modularize!

3) The Instruction Set Architecture

Your CPU will support the instructions listed below. Most of the instructions should behave the same as the RISC-V you learned in class. If anything surprises you, it is likely that I made a mistake. Please make a Piazza post about it.

Instruction Formats

The Instructions

Instruction Type Opcode Funct3 Funct7/IMM Operation
add rd, rs1, rs2 R 0x33 0x0 0x00 R[rd] ← R[rs1] + R[rs2]
mul rd, rs1, rs2 0x0 0x01 R[rd] ← (R[rs1] * R[rs2])[31:0]
sub rd, rs1, rs2 0x0 0x20 R[rd] ← R[rs1] - R[rs2]
sll rd, rs1, rs2 0x1 0x00 R[rd] ← R[rs1] << R[rs2
mulh rd, rs1, rs2 0x1 0x01 R[rd] ← (R[rs1] * R[rs2])[63:32]
slt rd, rs1, rs2 0x2 0x00 R[rd] ← (R[rs1] < R[rs2]) ? 1 : 0 (signed)
xor rd, rs1, rs2 0x4 0x00 R[rd] ← R[rs1] ^ R[rs2]
div rd, rs1, rs2 0x4 0x01 R[rd] ← R[rs1] / R[rs2]
srl rd, rs1, rs2 0x5 0x00 R[rd] ← R[rs1] >> R[rs2]
or rd, rs1, rs2 0x6 0x00 R[rd] ← R[rs1] | R[rs2]
rem rd, rs1, rs2 0x6 0x01 R[rd] ← (R[rs1] % R[rs2]
and rd, rs1, rs2 0x7 0x00 R[rd] ← R[rs1] & R[rs2]
lb rd, offset(rs1) I 0x03 0x0 R[rd] ← SignExt(Mem(R[rs1] + offset, byte))
lh rd, offset(rs1) 0x1 R[rd] ← SignExt(Mem(R[rs1] + offset, half))
lw rd, offset(rs1) 0x2 R[rd] ← Mem(R[rs1] + offset, word)
addi rd, rs1, imm 0x13 0x0 R[rd] ← R[rs1] + imm
slli rd, rs1, imm 0x1 0x00 R[rd] ← R[rs1] << imm
slti rd, rs1, imm 0x2 R[rd] ← (R[rs1] < imm) ? 1 : 0
xori rd, rs1, imm 0x4 R[rd] ← R[rs1] ^ imm
srli rd, rs1, imm 0x5 0x00 R[rd] ← R[rs1] >> imm
ori rd, rs1, imm 0x6 R[rd] ← R[rs1] | imm
andi rd, rs1, imm 0x7 R[rd] ← R[rs1] & imm
sw rs2, offset(rs1) S 0x23 0x2 Mem(R[rs1] + offset) ← R[rs2]
beq rs1, rs2, offset SB 0x63 0x0 if(R[rs1] == R[rs2])
 PCPC + {offset, 1b'0}
blt rs1, rs2, offset 0x4 if(R[rs1] less than R[rs2] (signed))
 PCPC + {offset, 1b'0}
bltu rs1, rs2, offset 0x6 if(R[rs1] less than R[rs2] (unsigned))
 PCPC + {offset, 1b'0}
lui rd, offset U 0x37 R[rd] ← {offset, 12b'0}
jal rd, imm UJ 0x6f R[rd] ← PC + 4
PCPC + {imm, 1b'0}
jalr rd,rs, imm I 0x67 0x0 R[rd] ← PC + 4
PCR[rs] + {imm}

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

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 RISC-V programs and exercise your datapath in different ways. You can use Venus to convert RISC-V program into Machine code.

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 compare the behavior of your CPU to the output of Venus emulator (or even your project 1-2!).

Lastly, you may be wondering if you're implementation will rely on your ALU and RegFile from Project 2-1. You will be using your own implementations of the ALU and RegFile as you construct your datapath; however, for grading, we will test your CPU using both your versions of the ALU and RegFile as well as a staff version, and take the maximum score of the two.

Sanity tests and Auto-grader

To be released!

Submission

Files to submit:You will submit cpu.circ together with your alu.circ and regfile.circ.

There are two steps required to submit proj2-2. Failure to perform both steps will result in loss of credit:

  1. First, you must 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 your git repository. To submit, follow these instructions after logging into your -XXX-YYY class account:

    cd ~/proj2-XXX-YYY                             # Or where your shared git repo is
    submit proj2-2

    Once you type submit proj2-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.


  2. Additionally, you must submit proj2-2 to your Bitbucket repository:

    cd ~/proj2-XXX-YYY                            # Or where your shared git repo is
    git add -u                           
    git commit -m "project 2-2 submission"       # The commit message doesn't have to match exactly.
    git tag "proj2-2-sub"                        # The tag MUST be "proj2-2-sub". Failure to do so will result in loss of credit.
    git push origin proj2-2-sub                  # This tells git to push the commit tagged proj2-2-sub

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, but you will need to use the -f flag to tag and push to Bitbucket:

# Do everything as above until you get to tagging
git tag -f "proj2-2-sub"
git push -f origin proj2-2-sub

Note that in general, force pushes should be used with caution. They will overwrite your remote repository with information from your local copy. As long as you have not damaged your local copy in any way, this will be fine.

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 automatic grading script. For regrade, we will try to 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.