Project 4: Processor Design

CS61C Fall 2014

TAs: Kevin Liston, Matthew Griffin

Due: Sunday, December 7, 2014 @ 23:59:59

Updates

Overview

In this project, you will be implementing a processor for the Ida Assembly assembly language (a language designed specifically for this project!). It is absolutely necessary to thoroughly read the Ida Assembly Manual to be able to complete this project.

Piazza Etiquette

Before getting started, please note that it is not okay to make public piazza posts that contain images of your solution or contain non-trivial implementation details.

Make sure any questions you ask publicly do not give away any implementation details. The entire point of this project is to implement a CPU, so asking how to implement something, or asking if a given implementation idea is correct is not okay! If you must ask these sort of questions, ask them privately. Do not answer questions with implementation details either. We may penalize students who give away non-trivial implementation details! Err on the side of caution here, and make the post private if you are unsure.

You can, of course, ask for clarification of the instructions, but either avoid mentioning specific implementation details, or make your question private. And as usual, we will not debug your entire project over piazza.

Getting Started

You are required to complete this project with one partner. You are not allowed to show or share your project files with any other student, friend, and such, except for your project partner. This also includes files you write specifically for testing purposes, even if they are not part of the tests you will be turning in. We have various tools at our disposal to detect plagiarism.

Before you begin, pull the skeleton files to your directory:

mkdir ~/proj4 cp -r ~cs61c/proj/04/* ~/proj4

The following project files are given:

This project has 2 parts. Part 1 is fairly light, involving writing various test cases to use for part 2. Part 2 is much more involved, requiring you to implement cpu.circ in its entirety. These parts can be completed in any order, but completing part 1 first is suggested. Both parts are due together as one single submission on Sunday, December 7, 2014 @ 23:59:59

Before you begin, be aware that part 1 is worth substantially less than part 2, so allocate your time accordingly. However, completing part 1 will allow you to test part 2 more conclusively.

Part 1: Writing Test Cases

Assembling Programs

For this part, you will be writing simple Ida programs that you can use to test your CPU implementation in the next part. Given a simple Ida program (.ida file), you can then assemble your program into a Logisim-compatible hex file (.hex file). To assemble an Ida program, you can run the following command.

java -jar Ida.jar -a tests/program.ida

To assemble all Ida programs in the test directory, you can run the following command instead.

java -jar Ida.jar -a tests/*.ida

The assembler with print any errors it encounters while assembling. A valid program will have no errors printed while being assembled. For example, we have the following Ida program to assemble. Notice the mistake of using two immediate values.

ADD $t0 0 33

The assembler would then output the following error upon attempting to assemble the program.

EXPECTED REGISTER
   | 
   | tests/bad.ida | LINE 2 | COLUMN 9
   | ---------------------------------
   | 
   | ADD $t0 0 33
   |         ^

We can fix the error by changing 0 to a register, $0.

ADD $t0 $0 33

This program will now assemble without any errors, and generate a hex file as output. Note that the assembler will usually create a hex file even if it prints errors! While it is not important for the scope of this project, you can examine the hex output of the assembler. For example, the hex file for this program would have the following contents.

v2.0 raw
0 6b000021

Note that 6b000021 is the assembled version of the given instruction. The assembler aways injects a NOP instruct of value 0 to the start of the assembled program. This should not affect anything for you. Finally, v2.0 raw is just a piece of header information that Logisim uses.

Executing Programs

We have provided you with a CPU emulator, which you can use to run your program. This emulator will print the contents of the CPU registers after completion, formatted in hexadecimal, signed decimal, and unsigned decimal.

java -jar Ida.jar -e tests/program.hex

For example, upon executing a blank program, you would see the following verbose output.

|- R --|--- HEX ----|- UNSIGNED -|-- SIGNED ---|
  $jc  = 0x00000000 =          0 =           0
  $sp  = 0x00000000 =          0 =           0
  $fp  = 0x4A624BF2 = 1247955954 =  1247955954
  $v0  = 0xBAACF956 = 3131898198 = -1163069098
  $v1  = 0xA15ED9AD = 2707347885 = -1587619411
  $ra  = 0x43920192 = 1133642130 =  1133642130
  $a0  = 0xF8914257 = 4170269271 =  -124698025
  $a1  = 0xE07D14FE = 3766293758 =  -528673538
  $a2  = 0x51915328 = 1368478504 =  1368478504
  $a3  = 0xC41B674D = 3290130253 = -1004837043
  $a4  = 0xE003C4A7 = 3758343335 =  -536623961
  $t0  = 0x5795EDD8 = 1469443544 =  1469443544
  $t1  = 0xEE73F091 = 4000575633 =  -294391663
  $t2  = 0x1B1C2649 =  454829641 =   454829641
  $t3  = 0x970AFC14 = 2534079508 = -1760887788
  $t4  = 0xCCE8BC13 = 3437804563 =  -857162733
  $t5  = 0xBD58E4A2 = 3176719522 = -1118247774
  $t6  = 0xB868E3F0 = 3093881840 = -1201085456
  $t7  = 0x3DF2DEDF = 1039326943 =  1039326943
  $t8  = 0x1911C313 =  420594451 =   420594451
  $t9  = 0x7BA4F208 = 2074407432 =  2074407432
  $t10 = 0x4C8B8CF0 = 1284214000 =  1284214000
  $t11 = 0x7E47874C = 2118616908 =  2118616908
  $t12 = 0xAF8C2426 = 2945197094 = -1349770202
  $t13 = 0xFD9DDB86 = 4254980998 =   -39986298
  $t14 = 0x88811F00 = 2290163456 = -2004803840
  $t15 = 0x8213B2CD = 2182329037 = -2112638259
  $t16 = 0xA3B4DC5B = 2746539099 = -1548428197
  $t17 = 0xD7E800FE = 3622306046 =  -672661250
  $t18 = 0x34FE9313 =  889099027 =   889099027
  $t19 = 0x48AA1870 = 1219106928 =  1219106928

These values are the initial values of every register in the register file. We will assume these registers will always have these specific initial values at the start of your programs. You can write tests that are easier to read by zeroing out all registers at the beginning.

There is one final thing to note about the emulator. Consider executing the following program, which is an infinite loop.

repeat: J @repeat

The emulator will give the following warning, and refuse to complete.

"program.hex" -- program was cut off and skipped; consider making it shorter

This happens because programs you run are going to be limited to exactly 0x600 clock ticks. If your programs do not terminate before that time, they will not run in the emulator. This can be avoided by writing shorter tests, or tests that have shorter iterations.

If you run into error messages complaining about a java.lang.OutOfMemoryError, try running the jar with a larger heap space, for example by using the max heap space setting -Xmx256m, and initial heap space setting -Xms256m. For example, this sets the heap space to 256 MB.

java -Xmx256m -Xms256m -jar Ida.jar -e tests/program.hex

Proving Broken CPUs

We have given a special command that will run every test case in the tests directory against a series of broken CPUs. Your task is to write test cases that prove each broken CPU is actually broken (that is to say, prove each broken CPU does not match the reference emulator). Note that these broken CPUs are also implemented as emulators, so you will have no way to find out how they are broken except for writing tests. The following command will run all of the broken CPUs each on all of your test cases.

java -jar Ida.jar -t

This will produce output for each broken CPU, telling which cases passed and failed. You want your cases to fail, meaning that the broken CPU does not match the correct emulator. You will see output for each broken CPU such as the following. In this case, broken CPU 13 was proven as broken due to test case 2.

Running test cases on CPU: "BROKEN_CPU_13".
PASS -- "testcase1.hex".
FAIL -- "testcase2.hex".
PASS -- "testcase3.hex".
PASS -- "testcase4.hex".
PASS -- "testcase5.hex".
+1, broken CPU was proven.

There are 20 broken CPUs. To receive full credit, you must design exactly 5 test cases that prove at least 10 of the broken CPUs are actually broken. There is no extra credit for proving more (but it is to your advantage, to better test your own CPU in part 2). You can (and should) write more than 5 test cases to narrow down the broken CPU's errors, but when submitting, only the following files will be collected.

We recommend writing as many test cases as needed, and then before submitting, merging test cases into fewer files. The more small test cases you have, the easier testing your part 2 CPU will be! Again, note that you only need to prove 10 out of the 20 broken CPUs as broken to receive full credit, and you will receive no additional credit for proving more than 10.

Note that test cases that exceed clock tick 0x600 on the emulator cannot prove a broken CPU. However, some test cases that do not exceed clock tick 0x600 on the emulator might exceed clock tick 0x600 on one of the broken CPUs (think about why!), and in this case, that CPU would be proven as broken.

Part 2: Designing the CPU

For this part of the project, you will be completing cpu.circ in Logisim, such that it matches the behavior described in the Ida Assembly Manual, as closely as possible. To get you started, here is a simplified diagram of what you will be building. In this diagram, the parts we have completed for you in run.circ are highlighted in red. Everything else, you must design for yourself!

Again, instruction memory and the register file have already been provided inside of run.circ. You are responsible for implementing everything else, and your solution should all go inside of cpu.circ.

It is also important to note the peculiar layout of the top-level run.circ circuit. Observe the following diagram. On the left, circuit A has two subcircuits: B and C. On the right, a new circuit D has three subcircuits: A, B, and C. Note that these are equivalent, though the left circuit is run from A's perspective, and the right circuit is run from D's perspective. Here, D would be run.circ, and A would be cpu.circ.

The cpu.circ circuit is essentially inside-out. The outputs of this circuit are actually the inputs of the register file and instruction memory. Likewise, the outputs of instruction memory and the register file are the inputs of the CPU.

Design Considerations

Here are a few notes:

Several Logisim components are banned, and the verification program that is discussed later will tell you if you used one of the banned components. We are allowing only the following components:

If you want to use new sub-components, you should define them with names beginning with the prefix "u_" (lowercase 'u' and an underscore), for example:

Working With Logisim

We have provided you with a copy of Logisim, but you can download it yourself if you prefer (Logisim). In any case, please do not run Logisim remotely. The official version of Logisim we will be using for evaluation is v2.7.1. Since we have provided you with a copy of Logisim, you might want to run it from the terminal. By doing this, whenever Logisim has an error, you will be notified by error messages in the terminal.

When working with Logisim, be wary of red wires (error signals), blue wires (unknown signals), and orange wires (wires with conflicting widths). You can use the poke tool to poke wires to check their values, and trace the source of problems in the wiring. Here are some common examples of things to watch out for:

If your file inexplicably is filled with unknown signals (blue wires and X's everywhere) or if the circuits suddenly vanish, just save the file and reopen it to fix the error. No data should be lost in doing so.

Testing

You can run the tests you wrote previously to verify that your solution is correct, by running the following verification program.

java -jar Ida.jar -v

This will list whether each test case passed or failed. Your project will ultimately be graded in a similar fashion, so if your tests are comprehensive enough, you can almost guarantee a high score. Your CPU is graded on correctness of the register file contents, near clock tick 0x600.

You will see a series of outputs such as this, which tells you whether the register contents of the emulator and of your own Logisim CPU match at clock tick 0x600, after running the given test case. Unlike before, you want your test cases to pass (because you probably do not want your CPU to be proven as broken).

Test case: "testcase3.hex".
Running emulator.
Running Logisim.
PASS -- "testcase3.hex".
+1, CPU passed the test.

You might notice that the verification program also displays some information about checking your CPU. You might get an error such as the following.

Checking CPU file.
FAIL -- "cpu.circ" -- does not match the reference (input or output pins differ).

The verification mode also scans your cpu.circ file for common issues that would cause it to malfunction. These serious issues include:

If the verification program reports your cpu.circ file does not match the reference, you will need to download a fresh blank copy of the file, and paste your solution into it (but not copying over your input and output pins). Logisim is hugely finicky about input and output pins. Moving one by mistake, and then undoing the move will often break the circuit.

Submissions that fail this verification test will receive no credit! There will be no leniency on this policy (even if the mistake is minuscule), so you have been warned!

Debugging

Simply knowing a test failed does not help fix a bug hidden deep in your CPU. Fortunately, there are a few debugging options available.

You can run the emulator to display human-readable output with the following command:

java -jar Ida.jar -e program.hex

This will print the expected value of all of the registers at clock tick number 0x600, and can thus be used to debug your program.

Next, you can run your own CPU solution to display human-readable output with the following command:

java -jar Ida.jar -l program.hex

Like the emulator, this will print the value of all of the registers at clock tick number 0x600. You can compare the results with the emulator's results to see which registers were affected.

Finally, you can manually run your CPU to debug it step-by-step. Ultimately, this is your best debugging option, as you can poke at your CPU's wires and follow the paths of data. First, open run.circ (make sure to reset the simulation if the file is already open). Then load a hex program file into the instruction memory module.

You can step through tick-by-tick to figure out where various issues might occur in your implementation. Unfortunately, you cannot step through the emulator.

Submission

When you are done with the project, make sure you have the following files ready for submission. Even if you did not use all 5 test cases, you will still need to submit all of these files. Note that these are the only files the submission system will accept. Further note that you are submitting the assembled test cases here, and they must be in the same folder as the CPU (just copy them up a directory). Also, it is worth it to run the verification program one last time before submitting.

When you are ready, submit in the usual way. When you submit, make sure to list the correct partner! If you accidentally list the wrong partner, make sure to let us know before the due date, even if you resubmit with the correct partner. If you submit with the wrong partner listed, and also do not let us know before the due date, your grade on this project might be penalized!

submit proj4

This project is due in its entirety on Sunday, December 7, 2014 @ 23:59:59.

Grading

The part 1 test cases will be graded using the same test case mode of the program that we have provided you. The part 1 score will be whatever number of the 20 broken CPUs you prove, capped at a value of 10.

The part 2 CPU file will be graded using the same verification mode of the program that we have provided you. This means that your project should match the behavior of the emulation software instead of matching the Ida Assembly Manual. We do not anticipate any differences between the emulator and the manual, but if there are any differences, we will side with the emulator. We may update the emulator if bugs are found before the due date and announce the changes, however, we will not modify the emulator during the last 4 days before the project due date. In short: if you run enough test cases, and the verification program says you passed them all, and you double check your results during the last 4 days of the project, you will likely get a high grade.