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
`A`32Data to use for Input A in the ALU operation
`B`32Data to use for Input B in the ALU operation
`ALUSel`4Selects which operation the ALU should perform (see the list of operations with corresponding switch values below)
Output NameBit WidthDescription
`ALUResult`32Result 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`

• 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-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 appendix 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
`ReadIndex1`5Determines which register's value is sent to the `ReadData1` output
`ReadIndex2`5Determines which register's value is sent to the `ReadData2` output
`WriteIndex`5The register to write to on the next rising edge of the clock (if `RegWEn` is 1)
`WriteData`32The data to write into `rd` on the next rising edge of the clock (if `RegWEn` is 1)
`RegWEn`1Determines whether data is written to the register file on the next rising edge of the clock
`clk`1Clock input
Output NameBit WidthDescription
`ReadData1`32The value of the register identified by `ReadIndex1`
`ReadData2`32The value of the register identified by `ReadIndex2`
`ra`32The value of `ra` (`x1`)
`sp`32The value of `sp` (`x2`)
`t0`32The value of `t0` (`x5`)
`t1`32The value of `t1` (`x6`)
`t2`32The value of `t2` (`x7`)
`s0`32The value of `s0` (`x8`)
`s1`32The value of `s1` (`x9`)
`a0`32The 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.

• 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-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-x0.circ
``````

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
`Instruction`32The instruction being executed
`ImmSel`3Value determining how to reconstruct the immediate (you can ignore this for now)
Output NameBit WidthDescription
`Immediate`32Value 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!

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
`MemReadData`32Data at `MemAddress` from memory
`Instruction`32The instruction at memory address `ProgramCounter`
`clk`1Clock input
Output NameBit WidthDescription
`ra`32The value of `ra` (`x1`)
`sp`32The value of `sp` (`x2`)
`t0`32The value of `t0` (`x5`)
`t1`32The value of `t1` (`x6`)
`t2`32The value of `t2` (`x7`)
`s0`32The value of `s0` (`x8`)
`s1`32The value of `s1` (`x9`)
`a0`32The value of `a0` (`x10`)
`MemAddress`32The address in memory to read from or write to
`MemWriteData`32Data to write to memory
`MemWriteMask`4The write enable mask for writing data to memory
`ProgramCounter`32Address 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)

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!

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.

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`).

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.

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 appendix 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

``````

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
• `addi` (5)