The ALU, the swiss knife of every cpu
Today the author wants to introduce an important part of every cpu: The arithmetic logic unit (ALU), we already know about some functions presented in the blog posts before. In this post we want to close the gaps systematically. Time for a short recap: The logic functions 'and','or','not' and 'xor' were introduced, also the arithmetic functions 'add' and 'sub' for integers were shown. Now we want to build most of those functionalities in one unit, the 1-bit alu cell.
| Function | description | Ainvert | Binvert | Operation |
|---|---|---|---|---|
and |
a & b |
0 |
0 |
00 |
or |
a | b |
0 |
0 |
01 |
add |
a + b |
0 |
0 |
10 |
sub |
a - b |
0 |
1 |
10 |
slt |
a < b |
0 |
1 |
11 |
nor |
a nor b |
1 |
1 |
00 |
nand |
a nand b |
1 |
1 |
01 |
A 1-bit ALU cell
To keep things simple we implement an ALU for 1 bit, which then can be adapted to every bitwidth simply by repitition. We introduce an implementation designed by Hennessey and Peterson, quoted from the popular book Computer Organization and Design (RISC-V) Edition by Hennessey and Patterson.
The implementation will support the fundamental operations 'and','or', 'add' and 'sub'. As we already learned the subtraction can be realised two’s complement: Inverting the input B and setting the carry-in to one.
Construct an n-bit ALU
The 1bit ALU-cell we created in the first section, can be chained to an n-bit width-alu. The last ALU-cell in the chain, differs a bit from the regular cell as it also includes an overflow-detection circuit. We will get to it later in the article.
Set-less-than
We want the complete ALU to support another fundamental instruction set-less-than (slt), necessary to allow branch-operations later on. For this operation the addional input 'less' is designed. So the ALU supports an instruction that in C looks like:
(a < b)? 1 : 0
This can be simply implemented by subtracting b from a, and testing if the value is less than zero. In the implementation, every alu-cell in the chain but the least-significant-bit, gets a zero on the 'less' input. The first alu-cell gets the result of the last one, which is representing the most-significant-bit. As the msb also represents the sign bit, we can simply route as input to the least-significant and we are done. This is - however - not true, in case the subtraction might result in an overflow.
Also, we add a nor-gate with inputs from all result bits to detect zero.
Overflow Detection
The last 1-bit ALU cell in the chain has another output 'overflow', to indicate an overflow of the addition of two integer values. The encourages the inclined reader to derive the truth table and circuit as an exercise.
For a two’s complement interpretation overflow occurs in two cases:
-
Two positive numbers are added, the result becomes negative
-
Two negative number are added, the result becomes positive
The truth table for overflow is as follows (original source can be found here)
| Binv | a(n-1) | b(n-1) | c(n-1) | OF |
|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
The circuit generated by Logisim is accordingly:
Multiplexer & Demultiplexer
To select one line out of multiple sources we need another key component, the multiplexer. We can find multiplexer in multiple places, however in an ALU it used to select one of the logic or arithmetic operations, we will see that later.
The demultiplexer- as the name suggest- does the exact opposite task and distributes signal on one line (input) to one of multiple outputs, depending on the selection bit(s).
Multiplexer in complementary Pass-Transistor Logic
We show and implement the multiplexer in pass-transistor-logic, as this is the most resource-efficient design…
