05_ALU

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.

alu symbol

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.

1bit alu cell

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.

1bit alu cell with overflow

alu array with less

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.

alu array with 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.

1bit alu cell with overflow

For a two’s complement interpretation overflow occurs in two cases:

  1. Two positive numbers are added, the result becomes negative

  2. 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:

overflow detection gates

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.

multiplexer symbol

multiplexer principle

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

demultiplexer principle

Multiplexer in complementary Pass-Transistor Logic

We show and implement the multiplexer in pass-transistor-logic, as this is the most resource-efficient design…​

mux ptl

Last update: January 21, 2024