CS61C Summer 2014
Due Sunday, August 10, 2014 @ 23:59:59
TA: Kevin Liston
In this project, you will be implementing a 2-stage pipelined processor for the Ida 2 assembly language (a language designed specifically for this project!). It is absolutely necessary to thoroughly read the Ida 2 Manual to be able to complete this project, as there are substantial difference from familiar assembly languages such as MIPS.
You are allowed to complete this project with one partner, or by yourself. Make sure that if you work with a partner, only one of you submits the project. In the case of two submissions from you and your partner, there is no guarantee which one we will grade. Whoever submits must list their partner's login in the file PARTNER.txt before submitting (or leave it as is if you are working alone).
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. We have various tools at our disposal to detect plagiarism.
Before you begin, pull the skeleton files to your directory. Like before, you can reset the remote alias with the following commands:
cd ~/work git remote rm projects git remote add projects git@github.com:ucberkeley-cs61c/projects_su14.git
Then you can pull the skeleton files as usual:
cd ~/work git pull projects master
The following project files are given:
It is strongly recommended that you download Logisim and to run on your local machine while developing your processor to avoid overwhelming the instructional machines. The official version of Logisim we will be using for evaluation is v2.7.1.
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 examples of things to watch out for:
At first glance, you will notice that RUN.circ is filled with blue and undefined wire signals. These errors will not go away until you have completed most of, if not all six parts of this project.
It is also important to note the peculiar layout of the top-level RUN.circ circuit, which looks utterly unlike the familiar MIPS data path. 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 righthand one has the added benefit that each subcircuit can be evaluated independently from the rest.
This is exactly how the project files are laid out. The top-level circuit is RUN.circ, directly containing all other circuits, and wiring them together as necessary. The would-be top-level circuit CPU.circ is a subcircuit in the same way as A in the previous diagram is. Note that since it will not be graded in any capacity, RUN.circ should not be modified.
The ALU contains basically all arithmetic operations required to execute any instruction. The following table lists the required input and output interface of the ALU circuit.
Input | Bits | Purpose |
ALU_SOURCE_X | 32 | the x operand |
ALU_SOURCE_Y | 32 | the y operand |
ALU_OPERATION | 4 | has following meaning:
|
Output | Bits | Purpose |
LT | 1 | if x < y (signed) |
EQ | 1 | if x == y |
GT | 1 | if x > y (signed) |
ADD_OVERFLOW | 1 | if the result is an addition that involved signed overflow |
SUB_OVERFLOW | 1 | if the result is a subtraction that involved signed overflow |
DIV_BY_ZERO | 1 | if the result is a division that involved a 0 divisor |
ALU_RESULT | 32 | the result of the computation selected by ALU_OPERATION |
This is the general purpose register file, a circuit that contains every general purpose register. This file allows reading and writing to registers when needed. The following table lists the required input and output interface of the REG circuit.
Input | Bits | Purpose |
REG_1_READ | 4 | the first register to read |
REG_2_READ | 4 | the second register to read |
REG_3_WRITE | 4 | the third register to read and/or the register to write to |
REG_WRITE_VAL | 32 | the value to write into the REG_3_WRITE register |
REG_WRITE | 1 | if the REG_3_WRITE register should be written to |
CLOCK | 1 | the clock pulse (you may use registers in this circuit) |
Output | Bits | Purpose |
REG_1_VAL | 32 | the pre-update contents of the REG_1_READ register |
REG_2_VAL | 32 | the pre-update contents of the REG_2_READ register |
REG_3_VAL | 32 | the pre-update contents of the REG_3_WRITE register |
R00 - R15 | 32 | the pre-update content of each general register |
This unit contains the comparison result register, and logic to access and modify it. Be sure to review the way the comparison values work in the Ida 2 Manual. The following table lists the required input and output interface of the CMP circuit.
Input | Bits | Purpose |
CQ_QUERY | 3 | the comparison query from the current instruction |
LT | 1 | a "less than" result from the ALU (1 and only 1 of LT/EQ/GT will be on at any given time) |
EQ | 1 | an "equal to" result from the ALU (1 and only 1 of LT/EQ/GT will be on at any given time) |
GT | 1 | a "greater than" result from the ALU (1 and only 1 of LT/EQ/GT will be on at any given time) |
CR_WRITE | 1 | if the current instruction enables writing to the comparison register |
CLOCK | 1 | the clock pulse (you may use registers in this circuit) |
Output | Bits | Purpose |
CR_VAL | 3 | the current value of the comparison register (see the Ida 2 Manual for specifics) |
CQ_PASSED | 1 | if the comparison query passes for the current instruction |
This module contains logic to calculate and select the next program counter. The following table lists the required input and output interface of the NPC circuit.
Input | Bits | Purpose |
INSTRUCTION | 32 | the current instruction |
CURRENT_PC | 24 | the current program counter value |
JUMP_ADDRESS | 24 | the jump address component of the current instruction |
CQ_PASSED | 1 | if the INSTRUCTION passed its comparison test |
Output | Bits | Purpose |
NEXT_PC | 24 | the program counter to use to fetch the next instruction |
This unit contains the pipelining logic of the processor. You will be implementing a 2-stage pipeline, specifically including the following stages:
Note that data hazards are not present in this design, since every data access from any source occurs only in one pipeline stage. However, control hazards must still be accounted for. Ida 2 does not expose branch delay slots to software. In other words, the instruction immediately after a jump is not executed if the jump actually occurs. By the time you have figured out that a jump is in the execute stage, you have already accessed the instruction memory and possibly pulled out the wrong instruction. Thus you will need to kill the instruction being fetched if the instruction currently being executed is a taken jump (which is to say that jumps that are not taken should not cause a kill).
Instruction kills for this project must be accomplished by MUXing a nop into the instruction stream within this PIP.circ. The nop will then be sent into the execute stage (instead of using the fetched instruction). Notice that every Ida 2 instruction contains numerous possible nops (every instruction can be turned into a nop using the ?NO comparison). However, you must use an all-zero instruction (0x00000000) as the nop, for grading purposes.
All pipelining-related circuitry is contained within this single circuit, so switching back and forth between a one and two stage design should be trivial. A project that is pipelined runs almost identically to one that is not (due to how logisim handles timing). When pipelining, you will notice two things in particular. First, there will be a startup delay cycle. Second, when performing a halting loop, the processor will jump between two different lines indefinitely. These are both correct behaviors.
The following table lists the required input and output interface of the PIP circuit.
Input | Bits | Purpose |
INSTRUCTION_IN | 32 | the current instruction entering the pipeline barrier |
PC_IN | 24 | the current program counter associated with INSTRUCTION_IN |
CQ_PASSED | 1 | if INSTRUCTION_OUT passed its comparison test |
CLOCK | 1 | the clock pulse (you may use registers in this circuit) |
Output | Bits | Purpose |
INSTRUCTION_OUT | 32 | the instruction exiting the pipeline barrier |
PC_OUT | 24 | the program counter associated with INSTRUCTION_OUT (or undefined when INSTRUCTION_OUT is a bubble) |
The CPU contains all control logic. This file contains inputs and outputs shaped as if it contained every other circuit in this project. The function of these interfaces were defined previously. Essentially, the CPU contains instruction decoding and control signals. The CPU should function correctly, independent of your specific implementations of the rest of the circuits.
You will notice that the CPU also contains a memory module and instruction module, both actually located in RUN.circ. You do not need to modify or complete these modules, as they are done for you. However, so that you can use them correctly, here is the interface for the instruction memory module:
Input | Bits | Purpose |
JUMP_ADDRESS | 24 | an address to use in calculating the next program counter |
Output | Bits | Purpose |
INSTRUCTION | 32 | the instruction to execute |
CURRENT_PC | 24 | the program counter associated with INSTRUCTION |
And here is the interface for the data memory module:
Input | Bits | Purpose |
MEM_ADDR | 24 | an address to read from (and write to, if MEM_WRITE is enabled) |
MEM_IN | 32 | the data to write to memory at MEM_ADDR, if MEM_WRITE is enabled |
MEM_WRITE | 1 | if writing to memory is enabled |
Output | Bits | Purpose |
MEM_OUT | 32 | the contents of memory at MEM_ADDR |
Testing the individual components of your processor would involve checking that for every input, the output is as is expected. While this process is tedious, you should definitely devote some time to testing in this manner. However, once you've implemented your processor entirely, you can test its correctness by writing programs to run on it! Be sure to review the Ida 2 Manual thoroughly.
Once you have the assembler and a program to run, you can assemble Ida 2 files using the following command, which takes a list of files to batch assemble:
java -jar Assemble.jar fib.ida
After a hex file has been assembled, it can be loaded into a logisim instruction memory RAM unit. You might also want to load a similar hex file into the data memory RAM unit, or otherwise edit the data memory directly. Before running the processor, be sure to first reset the simulation, and then load the appropriate hex files.
The project skeleton provides you with a fib.ida fibonacci-calculating program to start your testing. You might also consider running bin.ida, which performs a binary search on the contents of data memory (which you can initialize with sorted.hex). If either of these tests fails miserably, you should try testing a much simpler program of your own design.
Please note that you are expected to fully test your processor, both as a whole and as individual circuits. Doing so is the only way for you to know if you completed everything correctly. This project is graded on correctness, and while it is split into 6 isolated parts (allowing for various partial credit), these parts are not worth equal amounts, as they are not equally difficult. Partial credit within each component varies as well.
This project has specifically been designed to be graded piecewise. Each individual file will be graded entirely in isolation of the others, which means that any problems in one file will only impact the portion of the grade allocated to that one part and none of the rest. However, this also means that diverging from any of the previously listed interface requirements for any circuit component will be penalized on both sides of the interface.
Because this project does not involve compiling code, there are several critical issues that might come up that should be noted. Note that these issues are each severe enough to receive substantial penalties during grading without consideration of intent, as many of these issues are comparable to submitting uncompilable code.
You can run the following command to check all six of your circuit files.
java -jar Check.jar
You can also test individual files as well.
java -jar Check.jar ALU.circ
This command will print either OKAY or FAIL for each of the required circuit files. It will also list the reason for failure, which would be one of the following critical errors:
Passing this check does not guarantee the absence of these or other errors in your project. However, you will definitely receive no credit for submitting a file that fails this check, without any leniency.
The following often result in an incorrect solution. While these issues are not explicitly checked for during grading, they are no less severe. Try to avoid all of these issues as they will likely (but not assuredly) break your solution.
There is a file named proj3.marker at the top of the skeleton. This file is used to locate your submission, so do not move it.
Also notice there is a file named PARTNER.txt. Please list your partner's login letters in this file, being careful not to change the formatting. If you are submitting, your partner's login should be listed, and if your partner is submitting, your own login should be listed. If you have no partner, you should leave this file as it is.
Only the following submitted files will be considered for grading:
Again, this means that none of your circuits may use other external circuits.
To submit this project, tag the commit you want to submit with the tag proj3, and push to your git repo. For reference, the following commands would submit the most recent commit in your local repository:
git status git tag proj3 -f git push --tags origin master
Don't be afraid to submit multiple times. You can move your tags around, so you can choose an older commit later on if you want, or a newer commit.
This project is due in its entirety on Sunday, August 10, 2014 @ 23:59:59.