Part A: addi
Lab 5 is required for Project 3A, and lectures 14-19, Discussions 6-7, and Homeworks 6-7 are highly recommended.
In this part, you will design a skeleton CPU that can execute the addi instruction.
Task 1: Arithmetic Logic Unit (ALU)
Fill in the ALU in alu.circ so that it can perform the required arithmetic calculations.
| 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 which operation the ALU should perform (see the list of operations with corresponding switch values below) |
| Output Name | Bit Width | Description |
|---|---|---|
ALUResult | 32 | Result of the ALU operation |
Below is the list of ALU operations for you to implement, along with their associated ALUSel values. add is already made for you. You are allowed and encouraged to use built-in Logisim components to implement the arithmetic operations.
| ALUSel Value | Instruction |
|---|---|
| 0 | add: Result = A + B |
| 1 | sll: Result = A << B[4:0] |
| 2 | slt: Result = (A < B (signed)) ? 1 : 0 |
| 3 | Unused |
| 4 | xor: Result = A ^ B |
| 5 | srl: Result = (unsigned) A >> B[4:0] |
| 6 | or: Result = A | B |
| 7 | and: Result = A & B |
| 8 | mul: Result = (signed) (A * B)[31:0] |
| 9 | mulh: Result = (signed) (A * B)[63:32] |
| 10 | Unused |
| 11 | mulhu: Result = (A * B)[63:32] |
| 12 | sub: Result = A - B |
| 13 | sra: Result = (signed) A >> B[4:0] |
| 14 | Unused |
| 15 | bsel: Result = B |
Some additional tips:
- When performing shifts, only the lower 5 bits of
Bare needed, because only shifts of up to 32 are supported. - The result of multiplying 2 32-bit numbers can be up to 64 bits of information, but we're limited to 32-bit data lines, so
mulhandmulhuare used to get the upper 32 bits of the product. TheMultipliercomponent has aCarry Outoutput, with the description: "the upper bits of the product". This might be particularly useful for certain multiply operations. - The comparator component might be useful for implementing instructions that involve comparing inputs.
- A multiplexer (MUX) might be useful when deciding between operation outputs. In other words, consider simply processing the input for all operations, and then outputting the one of your choice.
- The ALU tests for Part A only use ALUSel values for defined instructions, so your design doesn't need to worry about the unused values.
Testing
On your local machine, start by running bash test.sh in the 61c-proj3 directory on your local machine. This gives you an overview of the commands you can run for testing. In particular, bash test.sh part_a runs all the tests for Part A. You can also provide the name of a specific task to run all the tests for that particular task.
To test this task, on your local machine, run bash test.sh test_alu.
If you fail a test, the test runner will print the difference between the expected and actual output. To view the complete reference output (.ref file) and your output (.out file), you can use run bash test.sh format with the name of the output file. For this task:
Debugging
See the Testing and Debugging section for a more detailed debugging guide.
All the testing .circ circuit files are in the tests folder. These circuits feed a sequence of inputs to your ALU circuit (one per clock cycle) and records the outputs from your circuit.
In Logisim, open one of the testing circuits for this task:
tests/unit-alu/alu-add.circ
tests/unit-alu/alu-all.circ
tests/unit-alu/alu-logic.circ
tests/unit-alu/alu-mult.circ
tests/unit-alu/alu-shift.circ
tests/unit-alu/alu-slt-sub-bsel.circ
To view your circuit, right-click your ALU, and select View alu. To step through the inputs to your circuit at each time step, click File -> Manual Tick Full Cycle. As you step through the inputs, use the Poke Tool to check the values in each wire.
Note: Avoid making edits in the test circuit, as they may be lost!
Task 2: Register File (RegFile)
Fill in regfile.circ so that it contains 32 registers that can be written to and read from.
| Input Name | Bit Width | Description |
|---|---|---|
ReadIndex1 | 5 | Determines which register's value is sent to the ReadData1 output |
ReadIndex2 | 5 | Determines which register's value is sent to the ReadData2 output |
WriteIndex | 5 | The register to write to on the next rising edge of the clock (if RegWEn is 1) |
WriteData | 32 | The data to write into rd on the next rising edge of the clock (if RegWEn is 1) |
RegWEn | 1 | Determines whether data is written to the register file on the next rising edge of the clock |
clk | 1 | Clock input |
| Output Name | Bit Width | Description |
|---|---|---|
ReadData1 | 32 | The value of the register identified by ReadIndex1 |
ReadData2 | 32 | The value of the register identified by ReadIndex2 |
ra | 32 | The value of ra (x1) |
sp | 32 | The value of sp (x2) |
t0 | 32 | The value of t0 (x5) |
t1 | 32 | The value of t1 (x6) |
t2 | 32 | The value of t2 (x7) |
s0 | 32 | The value of s0 (x8) |
s1 | 32 | The value of s1 (x9) |
a0 | 32 | The value of a0 (x10) |
- The 8 constant output registers are included in the output of the
regfilecircuit for testing and debugging purposes. Make sure to connect these 8 output pins to their corresponding registers. - The
x0register should always contain the 0 value, even if an instruction tries writing to it.
Some additional tips:
- Take advantage of copy-paste! It might be a good idea to make one register completely and use it as a template for the others to avoid repetitive work. You can duplicate a selected component or group of components in Logisim using
Ctrl/Cmd + D. - The
Enablepin on the built-in register may come in handy.
Testing and Debugging
To test your function, in your local terminal, run bash test.sh test_regfile.
To view the reference output and your output, you can run these formatting commands:
To debug your circuit, open the following test circuits, click into your regfile circuit, and tick full cycles to step through inputs:
tests/unit-regfile/regfile-more-regs.circ
tests/unit-regfile/regfile-read-only.circ
tests/unit-regfile/regfile-read-write.circ
tests/unit-regfile/regfile-x0.circ
Task 3: Immediate Generator
For the rest of Part A, we will be creating just enough of the CPU to execute the addi instruction. In Part B, you will revisit these circuits and expand them to support more instructions.
Fill in the immediate generator in imm-gen.circ (not the imm_gen subcircuit in cpu.circ) so that it can generate immediates for the addi instruction. You can ignore other immediate types for now.
| Input Name | Bit Width | Description |
|---|---|---|
Instruction | 32 | The instruction being executed |
ImmSel | 3 | Value determining how to reconstruct the immediate (you can ignore this for now) |
| Output Name | Bit Width | Description |
|---|---|---|
Immediate | 32 | Value of the immediate in the instruction (assume the instruction is addi for now) |
Testing and Debugging
You'll have to complete the next task before debugging this one!
Task 4: Datapath
Fill in cpu.circ so that it contains a datapath for a single-cycle (not pipelined) processor that can execute the addi instruction.
Here are the inputs and outputs to the processor. You can leave most of them unchanged in this task, since they are not needed for the addi instruction.
| Input Name | Bit Width | Description |
|---|---|---|
MemReadData | 32 | Data at MemAddress from memory |
Instruction | 32 | The instruction at memory address ProgramCounter |
clk | 1 | Clock input |
| Output Name | Bit Width | Description |
|---|---|---|
ra | 32 | The value of ra (x1) |
sp | 32 | The value of sp (x2) |
t0 | 32 | The value of t0 (x5) |
t1 | 32 | The value of t1 (x6) |
t2 | 32 | The value of t2 (x7) |
s0 | 32 | The value of s0 (x8) |
s1 | 32 | The value of s1 (x9) |
a0 | 32 | The value of a0 (x10) |
MemAddress | 32 | The address in memory to read from or write to |
MemWriteData | 32 | Data to write to memory |
MemWriteMask | 4 | The write enable mask for writing data to memory |
ProgramCounter | 32 | Address of the Instruction input |
We know that trying to build a datapath from scratch might be intimidating, so the rest of this section offers more detailed guidance for creating your processor.
Recall the five stages for executing an instruction:
- Instruction Fetch (IF)
- Instruction Decode (ID)
- Execute (EX)
- Memory (MEM)
- Write Back (WB)
Task 4.1: Instruction Fetch
We have already provided a simple implementation of the program counter. It is a 32-bit register that increments by 4 on each clock cycle. The ProgramCounter is connected to IMEM (instruction memory), and the Instruction is returned from IMEM.
Nothing for you to implement in this sub-task!
Task 4.2: Instruction Decode
In this step, we need to break down the Instruction input and send the bits to the right subcircuits.
What type of instruction is addi? What are the different fields in the instruction, and which bits correspond to each field?
addi is an I-type instruction. The fields are:
imm [31-20]rs1 [19-15]funct3 [14-12]rd [11-7]opcode [6-0]
In Logisim, what tool would you use to split out different groups of bits?
Use the splitter to extract each of the 5 fields from the instruction.
Which fields should connect to the register file? Which inputs of the register file should they connect to?
The rs1 bits you split from the instruction should connect to ReadIndex1 on the regfile.
The rd bits you split from the instruction should connect to WriteIndex on the regfile.
I-type instructions don't have rs2 so we can ignore rs2 for now.
Remember to connect the clock to the register file!
What needs to be connected to the immediate generator?
Connect the Instruction to the immediate generator. Your immediate generator from the previous task should take the instruction and output the correct immediate for you.
Task 4.3: Execute
In this step, we will use the decoded instruction fields to compute the actual instruction.
What two data values (A and B) should the addi instruction input to the ALU?
Input A should be the ReadData1 from the regfile.
Input B should be the immediate from the immediate generator.
What ALUSel value should the instruction input to the ALU?
ALUSel selects which computation the ALU will perform. Since we only care about implementing addi for now, we can hard-code ALU to always select the add operation (ALUSel = 0b0000).
Task 4.4: Memory
The addi instruction doesn't use memory, so there's nothing for you to implement in this sub-task!
The memory stage is where the memory can be written to using store instructions and read from using load instructions. Because the addi instruction does not use memory, we do not have to worry about it for Part A. Please ignore the DMEM and leave its I/O pins undriven.
Task 4.5: Write Back
In this step, we will write the result of our addi instruction back into a register.
What data is the addi instruction writing, and where is the instruction writing this data to?
addi takes the result of the addition computation (from the ALU output) and writes it to the register rd.
Connect ALUResult to WriteData on the regfile.
Since the addi instruction always writes to a register, you can hard-wire RegWEn to 1 for now so that register writes are always enabled.
Testing and Debugging
See the Testing and Debugging section for a more detailed debugging guide.
To test your function, in your local terminal, run bash test.sh test_addi.
To view the reference output and your output, you can run these formatting commands:
To debug your circuit, open the following test circuits, click into your CPU circuit, and tick full cycles to step through inputs:
tests/integration-addi/addi-basic.circ
tests/integration-addi/addi-positive.circ
tests/integration-addi/addi-negative.circ
Submission and Grading
Submit your repository to the Project 3A assignment on Gradescope. The autograder tests for Part A are the same as the tests you are running locally. Part A is worth 20% of your overall Project 3 grade.
- ALU (7)
- RegFile (8)
addi(5)
Total: 20 points