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 NameBit WidthDescription
A32Data to use for Input A in the ALU operation
B32Data to use for Input B in the ALU operation
ALUSel4Selects which operation the ALU should perform (see the list of operations with corresponding switch values below)
Output NameBit WidthDescription
ALUResult32Result 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 ValueInstruction
0add: Result = A + B
1sll: Result = A << B[4:0]
2slt: Result = (A < B (signed)) ? 1 : 0
3Unused
4xor: Result = A ^ B
5srl: Result = (unsigned) A >> B[4:0]
6or: Result = A | B
7and: Result = A & B
8mul: Result = (signed) (A * B)[31:0]
9mulh: Result = (signed) (A * B)[63:32]
10Unused
11mulhu: Result = (A * B)[63:32]
12sub: Result = A - B
13sra: Result = (signed) A >> B[4:0]
14Unused
15bsel: Result = B

Some additional tips:

  • When performing shifts, only the lower 5 bits of B are 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 mulh and mulhu are used to get the upper 32 bits of the product. The Multiplier component has a Carry Out output, 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:

bash test.sh format tests/unit-alu/out/alu-add.ref
bash test.sh format tests/unit-alu/out/alu-add.out

bash test.sh format tests/unit-alu/out/alu-all.ref
bash test.sh format tests/unit-alu/out/alu-all.out

bash test.sh format tests/unit-alu/out/alu-logic.ref
bash test.sh format tests/unit-alu/out/alu-logic.out

bash test.sh format tests/unit-alu/out/alu-mult.ref
bash test.sh format tests/unit-alu/out/alu-mult.out

bash test.sh format tests/unit-alu/out/alu-shift.ref
bash test.sh format tests/unit-alu/out/alu-shift.out

bash test.sh format tests/unit-alu/out/alu-slt-sub-bsel.ref
bash test.sh format tests/unit-alu/out/alu-slt-sub-bsel.out

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 NameBit WidthDescription
ReadIndex15Determines which register's value is sent to the ReadData1 output
ReadIndex25Determines which register's value is sent to the ReadData2 output
WriteIndex5The register to write to on the next rising edge of the clock (if RegWEn is 1)
WriteData32The data to write into rd on the next rising edge of the clock (if RegWEn is 1)
RegWEn1Determines whether data is written to the register file on the next rising edge of the clock
clk1Clock input
Output NameBit WidthDescription
ReadData132The value of the register identified by ReadIndex1
ReadData232The value of the register identified by ReadIndex2
ra32The value of ra (x1)
sp32The value of sp (x2)
t032The value of t0 (x5)
t132The value of t1 (x6)
t232The value of t2 (x7)
s032The value of s0 (x8)
s132The value of s1 (x9)
a032The value of a0 (x10)
  • The 8 constant output registers are included in the output of the regfile circuit for testing and debugging purposes. Make sure to connect these 8 output pins to their corresponding registers.
  • The x0 register 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 Enable pin 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:

bash test.sh format tests/unit-regfile/out/regfile-more-regs.ref
bash test.sh format tests/unit-regfile/out/regfile-more-regs.out

bash test.sh format tests/unit-regfile/out/regfile-read-only.ref
bash test.sh format tests/unit-regfile/out/regfile-read-only.out

bash test.sh format tests/unit-regfile/out/regfile-read-write.ref
bash test.sh format tests/unit-regfile/out/regfile-read-write.out

bash test.sh format tests/unit-regfile/out/regfile-x0.ref
bash test.sh format tests/unit-regfile/out/regfile-x0.out

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 NameBit WidthDescription
Instruction32The instruction being executed
ImmSel3Value determining how to reconstruct the immediate (you can ignore this for now)
Output NameBit WidthDescription
Immediate32Value 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 NameBit WidthDescription
MemReadData32Data at MemAddress from memory
Instruction32The instruction at memory address ProgramCounter
clk1Clock input
Output NameBit WidthDescription
ra32The value of ra (x1)
sp32The value of sp (x2)
t032The value of t0 (x5)
t132The value of t1 (x6)
t232The value of t2 (x7)
s032The value of s0 (x8)
s132The value of s1 (x9)
a032The value of a0 (x10)
MemAddress32The address in memory to read from or write to
MemWriteData32Data to write to memory
MemWriteMask4The write enable mask for writing data to memory
ProgramCounter32Address 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:

  1. Instruction Fetch (IF)
  2. Instruction Decode (ID)
  3. Execute (EX)
  4. Memory (MEM)
  5. 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:

bash test.sh format tests/integration-addi/out/addi-basic.ref
bash test.sh format tests/integration-addi/out/addi-basic.out

bash test.sh format tests/integration-addi/out/addi-negative.ref
bash test.sh format tests/integration-addi/out/addi-negative.out

bash test.sh format tests/integration-addi/out/addi-positive.ref
bash test.sh format tests/integration-addi/out/addi-positive.out

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