Project 4: Processor Design

CS61C Spring 2013

Due Sunday, May 05th, 2012 at 11:59 PM

TA in charge: Alan Christopher

Based on original spec by Ben Sussman and Brian Zimmer, and modified spec of Albert Chae, Paul Pearce, Noah Johnson, Justin Hsia, Conor Hughes, Anirudh Todi, Ian Vonseggern, and Sung Roa Yoon.
Much thanks to Conor Hughes for an excellent assembler and autograder.

Post any questions or comments to Piazza.

This project spec is ridiculously long, but don't fret! We've spelled out many things in excruciating detail, so if you just take things one-by-one, it won't be as bad as it looks.

We are also providing a set of abridged project notes to look at. These will NOT substitute for reading through the actual project specs, but can be used as a quick reference later on.


Updates | Overview | Deliverables | ISA | Logisim | Testing | Submission

Updates and Clarifications


Updates | Overview | Deliverables | ISA | Logisim | Testing | Submission

Overview

In this project you will be using Logisim to create a 16-bit two-cycle processor. It is similar to MIPS, except that both the datapath and the instructions are 16-bits wide, it has only 4 registers, and memory addresses represent 16-bit words instead of 8-bit bytes (word-addressed instead of byte-addressed).

Please read this document CAREFULLY as there are key differences between the processor we studied in class and the processor you will be designing for this project.

Before you begin, copy the start kit to your home directory (and then possibly to your own machine):

    $ cp -r ~cs61c/proj/04 proj04

Pipelining

Your processor will have a 2-stage pipeline:

  1. Instruction Fetch: An instruction is fetched from the instruction memory.
  2. Execute: The instruction is decoded, executed, and committed (written back). This is a combination of the remaining stages of a normal MIPS pipeline.

You should note that data hazards do NOT pose a problem for this design, since all accesses to all sources of data happens only in a single pipeline stage. However, there are still control hazards 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 0x0006 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 pseudo-nop (In general 0x0000 is not a nop, but 0 + 0 == 0, so it works out when all the registers contain zero). We will allow you to depend on this behavior of Logisim. Remember to go to Simulate --> Reset Simulation (Ctrl+R) to reset your processor.


Updates | Overview | Deliverables | ISA | Logisim | Testing | Submission

Deliverables

Approach this project like you would any coding assignment: construct it piece by piece and test each component early and often!

Tidyness and readability will be a large factor in grading your circuit if there are any issues, so please make it as neat as possible! If we can't comprehend your circuit, you will probably receive no partial credit.

logisim divider

1) Register File [show]

2) Arithmetic Logic Unit (ALU) [show]

3) Processor [show]

3a) Data Memory [show]

3b) Output Devices [show]

4) Test Code [show]

*) Extra for Experts: NOT EXTRA CREDIT [show]


Updates | Overview | Deliverables | ISA | Logisim | Testing | Submission

Instruction Set Architecture (ISA)

You will be implementing a simple 16-bit processor with four registers ($r0-$r3). It will have separate data and instruction memory. Because this is a 16-bit architecture, our words are 16 bits wide, unlike the 32-bit MIPS ISA we have been studying in class. For the remainder of this document, a WORD refers to 16 bits. Each of the four registers is big enough to hold ONE word.

IMPORTANT: Because of the limitations of Logisim (and to make things simpler), our memories will be word-addressed (16 bits), unlike MIPS, which is byte-addressed (8 bits).

The instruction encoding is given below. Your processor will pull out a 16-bit value from instruction memory and determine the meaning of that instruction by looking at the opcode (the top four bits, which are bits 15-12). If the instruction is an R-type (i.e. opcode == 0), then you must also look at the funct field.

Notice how we do not use all 64 R-type instructions. Your project only has to work on these specified instructions. This way the project is shorter and easier.

15-12 11 10 9 8 7 6 5 4 3 2 1 0
0 rs rt rd funct See R-type Instructions
1 target address jal into $r3
2 target address j: jump to target address
3 rs unused jr:   PC = $rs
4 rs rt offset (signed) beq: branch if equal
5 rs rt immediate (signed) addi: $rt = $rs + imm
6 rs rt immediate (unsigned) andi: $rt = $rs & imm
7 rs rt immediate (unsigned) ori:  $rt = $rs | imm
8 rs rt offset (signed) bne: branch if not equal
9 rs rt immediate (signed) sw:   MEM[$rs+imm] = $rt
10 rs rt immediate (unsigned) lui:  $rt = imm << 8
11 rs rt immediate (signed) lw:   $rt = MEM[$rs + imm]
12 rs rt immediate (unsigned) disp: DISP[imm] = $rs

R-Type Instructions
funct Instruction
0 add:  $rd = $rs + $rt
1 sub:  $rd = $rs - $rt
2 sllv: $rd = $rs << $rt
3 srlv: $rd = $rs >> $rt (zero extend)
4 srav: $rd = $rs >> $rt (sign extend)
5 slt:  $rd = ($rs < $rt) ? 1 : 0
6 or:   $rd = $rs | $rt
7 and:  $rd = $rs & $rt
8 mulp8: $rd = {$rs[15:8] * $rt[15:8] , $rs[7:0] * $rt[7:0] }
9 divp8: $rd = {$rs[15:8] / $rt[15:8] , $rs[7:0] / $rt[7:0] }
10 addp8: $rd = {$rs[15:8] + $rt[15:8] , $rs[7:0] + $rt[7:0] }
11 subp8: $rd = {$rs[15:8] - $rt[15:8] , $rs[7:0] - $rt[7:0] }

Some specifics on selected instructions:

Shifting