CS61C Fall 2018 Project 3-1 - CPU: ALU and RegFile

TAs: Sruthi Veeragandham, Sean Farhat

Getting Started

As with Projects 1 and 2, we will be creating a new project repository on GitHub Classroom and pulling the starter code from GitHub. You are welcome to complete the project alone or with a partner, but we really encourage you to work with a partner, especially for Project 3-2, which is much more involved than Project 3-1. If you don't have a partner and would like to find one, fill out this Google form and we will try to pair you with another student that has a relatively similar schedule and work preferences. It is fine to work on Project 3-1 without a partner and Project 3-2 with a partner, so feel free to fill out the form until Monday, November 12th, though obviously sooner is better!

Whether or not you have a partner, complete the Project 3 Repository Registration Form which will guide you through the necessary steps to create a repository for this project.

Once you've cloned your Github classroom repository, make sure to setup the starter code remote repository and pull to make sure all changes are up to date. Setting the starter repository as a remote and pulling the starter code is independent of setting up your Github classroom repository, so please add the starter as a remote and get started if you're having any trouble. A TA can help you with Github classroom if you post on Piazza or come to lab/office hours.

$ git remote add starter https://github.com/61c-teach/fa18-proj3-starter.git
$ git pull starter master


Important Information: Please Read!

Clarifications

Any clarifications about this project will be posted both here and on the Project 3-1 Index Post on Piazza. The post also has a small selection of particularly useful/insightful followups at the top that you might find useful to read through if you get stuck.

1:10PM 11/04 Re-pull the starter code--there have been some changes to the tests for RegFile. All changes were in the tests directory, so your RegFile and ALU will not be affected.

2:30AM 11/09 If you're having trouble using binary_to_hex_alu.py or binary_to_hex_regfile.py because your ALU or RegFile is outputting x's, you can re-pull the starter code for a small fix in these files that will print the x's for you so you can see where you're going wrong instead of erroring.

10:00AM 11/09 Another fix to tests, please re-pull the starter code!

Getting a merge conflict? If it's from pulling the starter code, first, open your .circ file in a text editor (Vim, gedit, Atom, Sublime, etc.). Ctrl-F for "HEAD", and every place it appears, you should remove the line ">>>>>>> HEAD", though leave in place the code below it. Then, scroll down to where you see "=======" and remove that line, plus everything between it and the number of the commit, including the commit number. To demonstrate, if you see this:

You should make it look like this:

Resources

The lectures that covered the material relevant to this project were Monday October 29 (Single Cycle Datapath I), Wednesday October 31 (Single Cycle Datapath II), and Friday November 2 (Single Cycle Control). The relevant reading from Patterson & Hennessey is Chapter 4.1 - 4.4.

Exercise 1: Arithmetic Logic Unit (ALU)

Your first task is to create an ALU that supports all the operations needed by the instructions in our ISA (which is described in further detail in the next section). Please note that we treat overflow as RISC-V does with unsigned instructions, meaning that we ignore overflow.

We have provided a skeleton of an ALU for you in alu.circ. It has three inputs:

Input Name Bit Width Description
A 32 Data to use for Input A in the ALU operation.
B 32 Data to use for Input B in the ALU operation.
ALUSel 4 Selects what operation the ALU should perform
(see the list of operations with corresponding switch values below).

... and one output:

Output Name Bit Width Description
Result 32 Result of the ALU Operation.

Below is the list of ALU operations for you to implement, along with their associated ALUSel values. All of them are required with the exception of mulh, which will take some extra effort to implement (but you're certainly up to the task!) You are allowed and encouraged to use built-in Logisim blocks to implement the arithmetic operations.

Switch Value Instruction
0 add: Result = A + B
1 and: Result = A & B
2 or: Result = A | B
3 xor: Result = A^B
4 srl: Result = (unsigned) A >> B
5 sra: Result = (signed) A >> B
6 sll: Result = A << B
7 slt: Result = (A < B) ? 1 : 0 Signed
8 divu: Result = (unsigned) A / B
9 remu: Result = (unsigned) A % B
10 mult: Result = (signed) A*B[31:0]
11 mulhu: Result = A*B[63:32]
12 sub : Result = A - B
13 bsel: Result = B
14 mulh: Result = (signed) A*B[63:32]

When implementing mul and mulh, notice that the multiply block has a "Carry Out" output (the adder block also has this, but you will not need this) located here:

Carry Out in Multiply Block

Experiment a bit with it, and see what you get for both the result and carryout with negative and positive 2's complement numbers. You should realize why we made mulh extra credit.

Hints:

NOTE: Your ALU must be able to fit in the provided harness alu_harness.circ. Follow the same instructions as the register file regarding rearranging inputs and outputs of the ALU. In particular, you should ensure that your ALU is correctly loaded by a fresh copy of alu_harness.circ before you submit.

Testing

When you run ./test.sh, the ALU tests will produce output in the tests/student_output directory. We've provided a python script called binary_to_hex_alu.py that can interpret this output in a readable format for you. To use it, do the following: (you may have to use "py" or "python3" as is appropriate on your machine)

$ cd tests
$ python binary_to_hex_alu.py PATH_TO_OUT_FILE

For example, to see reference_output/alu-add-ref.out in readable format, you would do this:

$ cd tests
$ python binary_to_hex_alu.py reference_output/alu-add-ref.out

If you want to see the difference between your output and the reference solution, put the readable outputs into new .out files and diff them. For example, for the alu-add test, take the following steps:

$ cd tests
$ python binary_to_hex_alu.py reference_output/alu-add-ref.out > alu-add-ref.out
$ python binary_to_hex_alu.py student_output/alu-add-student.out > alu-add-student.out
$ diff alu-add-ref.out alu-add-student.out

Exercise 2: Register File (RegFile)

As you learned in class, RISC-V architecture has 32 registers. However, in this project, You will only implement 9 of them (specified below) to save you some repetitive work. This means your rs1, rs2, and rd signals will still be 5-bit, but we will only test you on the specified registers.

Your RegFile should be able to write to or read from these registers specified in a given RISC-V instruction without affecting any other registers. There is one notable exception: your RegFile should NOT write to x0, even if an instruction try. Remember that the zero register should ALWAYS have the value 0x0. You should NOT gate the clock at any point in your RegFile: the clock signal should ALWAYS connect directly to the clock input of the registers without passing through ANY combinational logic.

The registers and their corresponding numbers are listed below.

Register # Register Name
x0 zero
x1 ra
x2 sp
x5 t0
x6 t1
x7 t2
x8 s0
x9 s1
x10 a0

You are provided with the skeleton of a register file in regfile.circ. The register file circuit has six inputs:

Input Name Bit Width Description
Clock 1 Input providing the clock. This signal can be sent into subcircuits 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.).
RegWEn 1 Determines whether data is written to the register file on the next rising edge of the clock.
Read Register 1 (rs1) 5 Determines which register's value is sent to the Read Data 1 output, see below.
Read Register 2 (rs2) 5 Determines which register's value is sent to the Read Data 2 output, see below.
Write Register (rd) 5 Determines which register to set to the value of Write Data on the next rising edge of the clock, assuming that RegWEn is a 1.
Write Data 32 Determines what data to write to the register identified by the Write Register input on the next rising edge of the clock, assuming that RegWEn is 1.

The register file also has the following outputs:

Output Name Bit Width Description
Read Data 1 32 Driven with the value of the register identified by the Read Register 1 input.
Read Data 2 32 Driven with the value of the register identified by the Read Register 2 input.
ra Value 32 Always driven with the value of ra (This is a DEBUG/TEST output.)
sp Value 32 Always driven with the value of sp (This is a DEBUG/TEST output.)
t0 Value 32 Always driven with the value of t0 (This is a DEBUG/TEST output.)
t1 Value 32 Always driven with the value of t1 (This is a DEBUG/TEST output.)
t2 Value 32 Always driven with the value of t2 (This is a DEBUG/TEST output.)
s0 Value 32 Always driven with the value of s0 (This is a DEBUG/TEST output.)
s1 Value 32 Always driven with the value of s1 (This is a DEBUG/TEST output.)
a0 Value 32 Always driven with the value of a0 (This is a DEBUG/TEST output.)

The DEBUG/TEST outputs are present for testing and debugging purposes. If you were implementing a real register file, you would omit those outputs. In our case, be sure they are included correctly--if they are not, you will not pass.

You can make any modifications to regfile.circ you want, but the outputs must obey the behavior specified above. In addition, your regfile.circ that you submit must fit into the regfile_harness.circ file we have provided for you. This means that you should take care not to move inputs or outputs. To verify changes you have made didn't break anything, you can open regfile_harness.circ and ensure there are no errors and that the circuit functions well. (The tests use a slightly modified copy of regfile_harness.circ.)

Hints:

Testing

When you run ./test.sh, the RegFile tests will produce output in the tests/student_output directory. We've provided a python script called binary_to_hex_regfile.py that can interpret this output in a readable format for you. To use it, do the following commands: (you may have to use "py" or "python3" as is appropriate on your machine)

$ cd tests
$ python binary_to_hex_regfile.py PATH_TO_OUT_FILE

For example, to see reference_output/regfile-x0-ref.out in readable format, you would do this:

$ cd tests
$ python binary_to_hex_regfile.py reference_output/regfile-x0-ref.out

If you want to see the difference between your output and the reference solution, put the readable outputs into new .out files and diff them. For example, for the regfile-x0 test, take the following steps:

$ cd tests
$ python binary_to_hex_regfile.py reference_output/regfile-x0-ref.out > regfile-x0-ref.out
$ python binary_to_hex_regfile.py student_output/regfile-x0-student.out > regfile-x0-student.out
$ diff regfile-x0-ref.out regfile-x0-student.out

Submission

Your final submission for this project will be on Gradescope. It is available now! Please upload your alu.circ and regfile.circ files. You must either add your partner onto your Gradescope team for this assignment, or submit separately. Every student should have their own submission. The autograder should not take more than 3 minutes to run.