Project 3: Processor Design

CS61C Summer 2014

Due Sunday, August 10, 2014 @ 23:59:59

TA: Kevin Liston

Updates

  1. Clarified that both ALU shift amounts should be determined by only the lower five bits of the second operand.
  2. Added the interface for the instruction memory to the CPU section.
  3. Clarified that in PIP.circ, PC_OUT is undefined when INSTRUCTION_OUT is a bubble.
  4. Added an additional testing program.
  5. Clarified some division fringe cases.
  6. Clarified "Set Upper" with a more straightforward notation: {A,B} means concatenate the bits of A to the upper end of the bits of B, so that for example {101, 011} = 101011
  7. Clarified the exclusiveness of the LT/EQ/GT signal inputs in CMP.circ.

Overview

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.

Getting Started

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:

  1. RUN.circ - wires all circuits together, contains all RAM memory, and runs the entire processor. Do not modify this file.
  2. CPU.circ - contains the control logic.
  3. REG.circ - contains the general purpose registers.
  4. ALU.circ - performs arithmetic operations.
  5. CMP.circ - handles comparison checking.
  6. NPC.circ - computes the next program counter.
  7. PIP.circ - contains the pipeline barrier.
  8. Assemble.jar - assembles Ida 2 code into Logisim hex files.
  9. fib.ida - a sample test program.
  10. Check.jar - checks your circuit files for incompatibilities.
  11. PARTNER.txt - contains your partner's login.
  12. proj3.marker - indicates that this is your project 3 submission.
  13. CheckSubmission.py - checks your submission.

Working With Logisim

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:

Circuit Organization

RUN

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.

Part 1: ALU

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.

InputBitsPurpose
ALU_SOURCE_X32the x operand
ALU_SOURCE_Y32the y operand
ALU_OPERATION4has following meaning:
  1. x << y[4:0]
  2. x >> y[4:0] (logical)
  3. x & y
  4. x | y
  5. x ^ y
  6. {y[15:0], x[15:0]}
  7. x * y (signed)
  8. x / y (signed)
  9. y - x
  10. x + y
  11. x + y
  12. x + y
  13. x + y
  14. x + y
  15. x + y
  16. x + y
NOTE: these operations should conform to the specifics enumerated in the Ida 2 Manual.
OutputBitsPurpose
LT1if x < y (signed)
EQ1if x == y
GT1if x > y (signed)
ADD_OVERFLOW1if the result is an addition that involved signed overflow
SUB_OVERFLOW1if the result is a subtraction that involved signed overflow
DIV_BY_ZERO1if the result is a division that involved a 0 divisor
ALU_RESULT32the result of the computation selected by ALU_OPERATION

Part 2: REG

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.

InputBitsPurpose
REG_1_READ4the first register to read
REG_2_READ4the second register to read
REG_3_WRITE4the third register to read and/or the register to write to
REG_WRITE_VAL32the value to write into the REG_3_WRITE register
REG_WRITE1if the REG_3_WRITE register should be written to
CLOCK1the clock pulse (you may use registers in this circuit)
OutputBitsPurpose
REG_1_VAL32the pre-update contents of the REG_1_READ register
REG_2_VAL32the pre-update contents of the REG_2_READ register
REG_3_VAL32the pre-update contents of the REG_3_WRITE register
R00 - R1532the pre-update content of each general register

Part 3: CMP

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.

InputBitsPurpose
CQ_QUERY3the comparison query from the current instruction
LT1a "less than" result from the ALU (1 and only 1 of LT/EQ/GT will be on at any given time)
EQ1an "equal to" result from the ALU (1 and only 1 of LT/EQ/GT will be on at any given time)
GT1a "greater than" result from the ALU (1 and only 1 of LT/EQ/GT will be on at any given time)
CR_WRITE1if the current instruction enables writing to the comparison register
CLOCK1the clock pulse (you may use registers in this circuit)
OutputBitsPurpose
CR_VAL3the current value of the comparison register (see the Ida 2 Manual for specifics)
CQ_PASSED1if the comparison query passes for the current instruction

Part 4: NPC

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.

InputBitsPurpose
INSTRUCTION32the current instruction
CURRENT_PC24the current program counter value
JUMP_ADDRESS24the jump address component of the current instruction
CQ_PASSED1if the INSTRUCTION passed its comparison test
OutputBitsPurpose
NEXT_PC24the program counter to use to fetch the next instruction

Part 5: PIP

This unit contains the pipelining logic of the processor. You will be implementing a 2-stage pipeline, specifically including the following stages:

  1. Instruction Fetch - an instruction is fetched from instruction memory
  2. Everything Else - the instruction is decoded, executed, data memory is touched, and then the results are written back

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.

InputBitsPurpose
INSTRUCTION_IN32the current instruction entering the pipeline barrier
PC_IN24the current program counter associated with INSTRUCTION_IN
CQ_PASSED1if INSTRUCTION_OUT passed its comparison test
CLOCK1the clock pulse (you may use registers in this circuit)
OutputBitsPurpose
INSTRUCTION_OUT32the instruction exiting the pipeline barrier
PC_OUT24the program counter associated with INSTRUCTION_OUT (or undefined when INSTRUCTION_OUT is a bubble)

Part 6: CPU

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:

InputBitsPurpose
JUMP_ADDRESS24an address to use in calculating the next program counter
OutputBitsPurpose
INSTRUCTION32the instruction to execute
CURRENT_PC24the program counter associated with INSTRUCTION

And here is the interface for the data memory module:

InputBitsPurpose
MEM_ADDR24an address to read from (and write to, if MEM_WRITE is enabled)
MEM_IN32the data to write to memory at MEM_ADDR, if MEM_WRITE is enabled
MEM_WRITE1if writing to memory is enabled
OutputBitsPurpose
MEM_OUT32the contents of memory at MEM_ADDR

Testing

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.

Grading Considerations

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.

Detectable Issues

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:

  1. does not match the reference - Involves adding, deleting, or moving any input or output pins. Doing this usually alters where these pins appear when the circuit is used. This is by far the easiest mistake to make, and it is also easy to fix. Simply obtain a fresh copy of the file and copy over everything except the input and output pins from your broken file.
  2. there is no "main" circuit - Involves renaming the main circuits within the submitted files. They should be named "main" internally. Changing this name makes it difficult to find the intended circuit for grading, especially if there are subcircuits.
  3. contains a clock pin - Involves using the special clock pins anywhere inside the submitted files. Thus if there is no input pin labeled as being a clock signal, then you are not supposed to use the clock in that particular circuit. Specifically, you will find it impossible to use the clock within the ALU.circ, NPC.circ, and CPU.circ files.
  4. contains a trigger not on the rising edge - Involves updating any component on something other than the rising edge of the clock. This option often causes other difficult to locate problems.
  5. contains an external file - Involves including external file circuits. Only the required files will be graded. Any files that attempt to link external files cannot be graded. Instead, use internal sub-circuits as appropriate.
  6. file does not exist - Involves missing a file. Files you do not submit will get no credit.
  7. file is unreadable - Involves a broken file format. This checking program only performs minimal assurance that your files are not broken. Opening your files in Logisim is a much safer check for this. Obviously, if Logisim cannot read your file, you will get no credit for it, even if this check does not say that it is unreadable.

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.

Undetectable Issues

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.

  1. Outputting unknowns or error signals (such as X/?/E). Your circuits should never do this for any output. If you see X/?/E symbols in outputs, or if you see red/blue/orange wires anywhere in your solutions, it might be incorrect, and is very likely to be heavily penalized!
  2. Gating the clock. This refers to plugging a clock signal into any component's input that is not explicitly labeled as a clock input. Gating the clock can cause problems similar to updating on the falling edge of the clock.
  3. Having any wires with unknowns, errors, or conflicting widths (these show up as X/E/? and red, blue, or orange wires). Wires such as these can cause unpredictable behavior. Again, if you see red/blue/orange wires anywhere in your solutions, it might function incorrectly!

Submission

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:

  1. CPU.circ
  2. REG.circ
  3. ALU.circ
  4. CMP.circ
  5. PIP.circ
  6. NPC.circ
  7. PARTNER.txt
  8. proj3.marker

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.