# ECE 271 ALU Demo ## 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 - `x`: 16 bit signed integer - `y`: 16 bit signed integer ### Control Signals - `zx`: Conditionally set `x` to zero - `nx`: Conditionally invert `x` (after possibly zeroing) - `zy`: Conditionally set `y` to zero - `ny`: Conditionally invert `y` (after possibly zeroing) - `fn`: Function to perform: 0 = AND, 1 = ADD - `no`: Conditionally invert ALU output #### Control Signals in Detail - The zero control signals `zx` and `zy` will set the `x` or `y` input busses to `0x0000` when high, or leave the busses as given when low. For example, if `x` is `0x1234` and `zx` is high, `x` will be set to `0x0000`. Otherwise, if `zx` is low, `x` remains at `0x1234`. - The inversion control signals `nx` and `ny` invert the `x` or `y` busses when high, or leave the busses as given when low. For example, if `x` is `0x1234` and `nx` is high, `x` will be set to `0xEDCB`. Otherwise, if `nx` is low, `x` remains at `0x1234`.Note that this process follows the conditional zeroing, so if both `zx` and `nx` are high, `x` will first be zeroed then inverted, resulting in `x` holding the value `0xFFFF`. This is useful behavior. - The function selection signal `fn` selects the operation performed. If `fn` is low, the ALU evaluates the expression `x & y`. Otherwise, if `fn` is high, the ALU evaluates the expression `x + y`. - The final control signal, `no`, conditionally inverts the ALU result. When `no` is high, output is inverted. When `no` is low, output is unchanged. #### Control Signals at a Glance TLDR: The following operations are executed sequentially - `if (zx) x <- 0` - `if (nx) x <- ~x` - `if (zy) y <- 0` - `if (ny) y <- ~y` - `if (fn) out <- x+y, else out <- x&y` - `if (no) out <- ~out` ## 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 - `zr`: high when `out` is exactly equal to zero (`0x0000`), low otherwise. - `ng`: high when `out` is negative in two's complement (bit 15 is set), low otherwise - `ov`: high when addition results in an overflow (carry out). Low if no overflow or if `fn` selects AND operation. ## 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`](https://web.engr.oregonstate.edu/~yockeyq/repo/ece_271_alu_demo/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](https://www.nand2tetris.org/) 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.