ECE 271 ALU Demo

Quinn Yockey
25 November 2024

Background

This demo attempts to help bridge the gap between ECE 271 Digital Logic Design and ECE 375 Computer Organization & Assembly Language. This is done by constructing a very simple arithmetic logic unit (ALU). An ALU is used to perform all calculations in a computer, and is one of the main components of a computer's central processing unit (CPU).

The ALU presented in this demo is far less complex than an ALU in any microcontroller or computer you will ever use in practice. However, its simplicity allows for a much easier conceptual demonstration that covers the fundamentals behind how more advanced ALUs work.

Overview

The idea behind this ALU is to take two 16 bit inputs, process them according to a specified operation, and produce a 16 bit output. For the simple ALU, we will only concern ourselves with the simplest of operations: bitwise AND, bitwise OR, inversion, addition, and subtraction.

Inputs

The ALU has two 16 bit data inputs x and y, and 6 control signals. The control signals are also known collectively as the opcode, and they determine which operation the ALU will perform.

Data

Control Signals

Control Signals in Detail

Control Signals at a Glance

TLDR: The following operations are executed sequentially

Outputs

The ALU outputs a 16 bit value that is the result of the specified operation applied to the x and y inputs. It also includes 3 output signals, called "flags", that specify notable properties of the result.

Result

out: 16 bit computation result

Flags

Calculations

Using some trickery, this ALU can compute a variety of useful expressions. The most interesting are listed below, along with an example of how control signals can be configured to calculate the result.

Note that this ALU isn't highly optimized since multiple different configurations of control signals compute the same output. For example, the expression x can be computed by x + 0 or x & 0xFFFF.

Expression zx nx zy ny fn no
0 1 0 1 0 0 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
x 0 0 1 1 0 0
y 1 1 0 0 0 0
!x 0 0 1 1 0 1
!y 1 1 0 0 0 1
-x 0 0 1 1 1 1
-y 1 1 0 0 1 1
x + 1 0 1 1 1 1 1
y + 1 1 1 0 1 1 1
x - 1 0 0 1 1 1 0
y - 1 1 1 0 0 1 0
x + y 0 0 0 0 1 0
x - y 0 1 0 0 1 1
y - x 0 0 0 1 1 1
x & y 0 0 0 0 0 0
x | y 0 1 0 1 0 1

Simulation

The provided do file test_alu.do simulates some example use cases of the ALU that showcase its functionality.

Add Two Numbers

Using the opcode for x+y in the table above, we can set x and y to the values we want to add, and observe the result in the output of the ALU. In this example we chose 0x0020 (decimal 32) and 0x0047 (decimal 71), and we expect the ALU output to be their sum, 0x0067 (decimal 103).

Extract Low Byte

To extract the least-significant byte of a two-byte value, we can AND it with 0x00FF. This will zero the most-significant byte while allowing the least-significant byte to pass through. For example, running this low byte computation on 0x9D95 should return 0x0095.

0x9D95 & 0x00FF


  1001 1101 1001 0101 (0x9D95)
& 0000 0000 1111 1111 (0x00ff)
----------------------
  0000 0000 1001 0101 (0x0095)

Bitwise OR

Even though our operations listed are only AND and ADD, this ALU can also computer bitwise OR! This can be done by inverting both inputs and the output. This can be justified by directly applying DeMorgan's Law: x | y = ~(~x & ~y).

Suppose we have a value 0x5555 (0b0101_0101_0101_0101) and we want to make sure the lowest 6 bits are set high. This can be done by ORing the lowest 6 bits with 1 and the rest with 0. The computation looks like the following:

0x5555 | 0x003F


  0101 0101 0101 0101 (0x5555)
| 0000 0000 0011 1111 (0x003f)
----------------------
  0101 0101 0111 1111 (0x557f)

Compare Two Numbers

To compare two numbers with our ALU, we can subtract y from x and observe the values of the ALU flags.

Again we have to get creative since the ALU doesn't directly support subtraction, only addition. The mechanics of why this works aren't particularly important, but I will prove the operation is valid for the curious reader. Recall the two's complement negative of a number n is -n = ~n + 1 or -n = ~(n - 1) (Both expressions are equally valid). We could try to compute x + (-y), but that will result in a value that is 1 off. Instead, we can compute x - y with -((-x) + y). Simplifying the -x term: -(~x + 1 + y). This can be re-written as -((~x + y) + 1). Simplifying the negative on the outside: ~(((~x + y) + 1) - 1). The +1 and -1 cancel, so we get ~(~x + y). This can be computed setting the nx and no control signals.

We will create (limited) expressions that use the ALU flags to determine the relation between our two operands x and y, assuming both numbers are treated as signed integers.

Equal

First, equality is the easiest to check. After a subtraction, the zr (zero) flag will be high only if x and y are equal, because their difference should be zero. If the zr flag is low, then x is not equal to y.

Greater Than

If x is greater than y, then x - y should be positive and the sign bit should be cleared. x is greater than y if and only if zr and ng are both clear.

Less Than

If x is less than y, then x - y should be negative and the sign bit should be set. x is less than y if and only if zr is clear and ng is set.

This Model is Incomplete

While these rules work for signed inputs that don't produce overflow, they fall apart as soon as overflow is introduced. Proper handling of all comparisons including edge cases with overflow is beyond the scope of this demo, but I encourage those interested to try and derive a simple equation that accounts for overflow when determining relation between two signed integers. It is also worth mentioning that these rules do not work for unsigned integers. Finding these is another exercise left for the reader.

Signed Comparison Results

Comparison zr ng
Less 0 1
Equal 1 0
Greater 0 0

Conclusion

Thank you to all who attended my demo in person and asked questions! I hope this material will help ease the transition to Computer Organization and Assembly Language. For any questions about the material I presented, please feel free to drop by my office hours posted on the course calendar. I would also greatly appreciate any feedback you might have, which you can tell me in person or email to me at yockeyq@oregonstate.edu.

Inspiration

The ALU in this demo was heavily inspired by the ALU presented in the Nand2Tetris online course. This is an outstanding course I took (for free!) over a year and a half and has been an incredible resource in conceptualizing how computers work at all levels of abstraction. I would highly recommend Nand2Tetris for any students interested in digital logic design or computer architecture.

Files

The files used in this demo are freely available at my self-hosted project git repository.