Building and Extending a 32-Bit ALU

Overview

In this lab you will examine a working 32-bit Arithmetic Logic Unit (ALU) built in the Digital circuit simulator, verify its correctness using built-in test cases, and then extend it with new operations and status flags. By the end of the lab, you will have a deeper understanding of how combinational logic components are composed to form the computational heart of a processor.

Part 0: Setup

Download and untar Digital simulator with the commands below.

cd ~/cs224
wget --no-check-certificate https://cs224.cs.vassar.edu/labs/Digital.tar
tar xvf Digital.tar
cd Digital

Note: the simulator is a Java package, so you can run the simulator on your own computer. See the github repo for details on how to download and install.

After you have downloaded the simulator, run the simulator and complete the tutorial. If the tutorial doesn’t automatically start for you, run it with the View->Start Tutorial menu option.

 ./Digital.sh

After you have completed the tutorial, get the starter ALU code.

wget --no-check-certificate https://cs224.cs.vassar.edu/labs/ALU_32bit.dig

You can then run it in the simulator.

./Digital.sh ALU_32bit.dig

Part 1: Understand the Starter ALU

The provided ALU supports four operations selected by a 2-bit control signal ALUOp:

ALUOp	Operation	Description
00	ADD	Result = A + B
01	SUB	Result = A − B (two’s complement)
10	AND	Result = A & B
11	OR	Result = A \| B

Examine the circuit and answer the following questions in your written response file, answers.txt.

Q1. Explain how the ALU in the lab is different from the one we went over in lecture.

Run the built-in tests

In Digital, go to Simulation->Run Tests or click on the button with the green arrow.
All 15 test vectors should pass (green). You can click on any of the tests to see the trace of that test’s input and output.
Now add a test of your choice and rerun the tests.
Change one of the tests so it doesn’t pass.

Q2. What does a failed test look like?

Q3. The test case 0xFFFFFFFF + 0x00000001 expects a result of 0x00000000 with the Zero flag set. Explain why the 32-bit result wraps to zero. What does the CarryOut signal indicate in this case?

Q4. Coming out of the ALUOp signal is a black bar. What does this component called and why is it needed? If you are not sure what a component does, try hovering over it with your mouse.

Q5. When running a simulation, the multiplexers (MUXes) have a dot next to one of the inputs, what does the dot signify? If your not sure, try clicking on various test cases and see how the dot changes with the different cases.

Part 2: Extend the ALU

You will now add new operations to the ALU. This requires modifying the ALUOp encoding to use 3 bits (supporting up to 8 operations) and replacing the 4:1 output multiplexer with an 8:1 multiplexer.

Step-by-step guide for the modifications

Widen ALUOp to 3 bits. Select the ALUOp input, open its attributes, and change Bits from 2 to 3. Update the splitter accordingly. Note: you can’t edit a componet while a simulation is running. Stop the simulation by pressing the red square button.
Replace the output MUX. Delete the existing 4:1 multiplexer. Insert a new Multiplexer component, set its Selector Bits to 3 and its data Bits to 32. Reconnect the existing four operation outputs to inputs 0–3 of the new MUX, and wire ALUOp to the selector.
Add new operations to inputs 4–7 of the MUX as described below. While you are adding operations, you will want to add temporary inputs to get your simulator to run.

New operation table

ALUOp	Operation	Description
000	ADD	A + B (unchanged)
001	SUB	A − B (unchanged)
010	AND	A & B (unchanged)
011	OR	A \| B (unchanged)
100	XOR	A ⊕ B
101	NOR	~(A \| B)
110	SLT	Set on Less Than
111	SLTU	Set on Less Than Unsigned

Add XOR (ALUOp = 100)

Add a 32-bit XOR gate with inputs A and B. Connect its output to input 4 of the output MUX. Add tests to test out your new functionality.

Add NOR (ALUOp = 101)

Add a 32-bit NOR gate. Connect the result to input 5 of the output MUX. Add tests to test out your new functionality.

Add Set on Less Than (ALUOp = 110)

SLT is used in processors to support comparison-based branching. The result should be 0x00000001 if A < B (signed comparison), and 0x00000000 otherwise.

Hint: Look around in the Components menu. The part you are looking for is called a Comparator.

Since the result needs to be 32 bits, you’ll need to add a splitter/combiner part. Set bits 31-1 to 0, combining it with the CarryOut output set to bit 0.

Add Set on Less Than Unsigned (ALUOp = 111)

The comparator you added for the SLT instruction works by subtracting A from B (A - B) and looking at the result. Since we already have an ALU, let’s take advantage of that by using the ALU to implement SLTU. Wire up the SLTU operation using the existing adder in the circuit. When A < B, a subtraction will not generate a CarryOut bit. When A >= B, there will be a CarryOut bit, so the result in this case will be the not of CarryOut bit.

Write test cases

Add test vectors to the existing Testcase component that cover your new operations by right-clicking on the green Test box. Make sure your tests include at least the following:

XOR: At least 3 test vectors, including one where A = B (result should be 0, Zero flag set).
NOR: At least 2 test vectors.
SLT: At least 4 test vectors, including a case with positive A < positive B, negative A < positive B
SLTU: At least 4 test vectors, including a case with positive A < positive B, negative A < positive B

Run all tests and verify everything passes.

Tips

Save often. Digital does not auto-save.
Test incrementally. After adding each new operation, run the tests before moving on. It’s much easier to debug one new gate than three at once.
Hover over components to see their pin names and descriptions. This is especially helpful for the adder’s carry-in and carry-out pins.
If a wire turns red during simulation, you have a conflict (two outputs driving the same wire). Check for accidentally connected outputs.

Submission

Upload your ALU_32bit.dig and answers.txt files to Gradescope.