Journey to the centre of CPU: Building an ALU

Ever wondered how your cpu performs an operation as simple as multiplication or comparing two numbers and deciding which is greater.
We all know everything deep inside is binary and anything that happens in cpu is done with binary gates such as AND, OR, NOT, XOR etc.

Today we will discuss and see how a cpu can build an ALU to compare two numbers.

What is an ALU?

Think of an ALU as a combination of several primitive logic gates combined to perform one specific action.

It’s like assembling simple pieces in IKEA to build the furniture you want or assembling whatever sauces or veggies you like to create the subway you like.

let’s start with basics

AND - an operation which decides whether both the input are 1 or one of them is 0

OR - an operation which decides if either of the input is 1

NOT - an operation which negates the input (convert 0 to 1 and convert 1 to 0)

NAND - an operation which negates the output after performing AND operation

NOR - an operation which negates the output after performing OR operation

XOR - an operation which decides whether both the inputs are equal

Using these gates, one can build any combination which can perform almost any digital or arithmetic logic, in fact all the gates or operation can just be achieved with combination of NAND gates.

Let’s try building a simple operation unit which adds two bits and return us carry and sum

We have two numbers a and b both representing one single bit either 0 and 1.

In order to add two binary bits, we can’t expect cpu to just “add” like human, we have to explicitly define the operations that we need, for this let us list down all the possible cases and think of an operation which can be used to achieve the result.

Possible outcomes are

looking closely, we see sum is 1 when inputs are different and 0 when input it same, going back to basics, XOR gate emulates this behaviour, okay, so sum can be achieved by using XOR over both the inputs.

What about carry?
Notice how it is 1 only when both the inputs are 1, that means, drumroll, 🥁 🥁, AND gate.

YES, now we have a gate which can add two inputs and give us output, and this is how you build an ALU.
Combining different gates to achieve one specific function can be an example of a small ALU unit under large complex ALUs.
Typically standard ALUs contains more complex and bunch of different operations based on the inputs and several flags used to manipulate the inputs and outputs.

An ALU which compares two numbers are tells us which is bigger

Defining the input and output flags

Inputs - a, b

Possible flags - we will have three flags, x, y, z and depending on their values we will decide whether they are equal or which is greater.

x is 1 when a=b

y is 1when a<b

z is 1 when a>b

(NOT (a XOR b)) will return 1 when a is equal b

(a AND (NOT b)) will return 1 when 1 a is greater than b

((NOT a) AND b) will return 1 when b is greater than a

We will combine these gates and put into one unit, and map the output to different lines, x, y, z and whichever lights the bulb will tell us the about the comparison.

A more elaborative diagram of to compare 4 bit inputs

                     A[3] ──────┐
                                │
                     B[3] ──────┘──XOR──┐
                                        │
                     A[2] ──────┐       │
                                │       │
                     B[2] ──────┘──XOR──┴──AND──┐
                                        │      │
                     A[1] ──────┐       │      │
                                │       │      │
                     B[1] ──────┘──XOR──┴──AND──┴──AND──A_EQ_B
                                        │      │
                     A[0] ──────┐       │      │
                                │       │      │
                     B[0] ──────┘──XOR──┴──AND──┘

                     A[3] ──────┐
                                │
                     B[3] ──────┘──AND──┐
                                        │
                     A[2] ──────┐       │
                                │       │
                     B[2] ──────┘──XOR──┼──AND──┐
                                        │      │
                     A[1] ──────┐       │      │
                                │       │      │
                     B[1] ──────┘──XOR──┼──AND──┼──OR──A_GT_B
                                        │      │
                     A[0] ──────┐       │      │
                                │       │      │
                     B[0] ──────┘──XOR──┼──AND──┘
                                        │
                                A_EQ_B──┘──NOT──A_LT_B

If we observe, it is just smaller 1 bit comparators combined to build a bigger one and that’s how an ALU is made.

Literally like lego pieces.

In real world, ALUs are more complex but fundamentals remain the same.

CPUs are fascinating piece of tech and in later parts of these posts, we will uncover how RAMs are made.

Until then, keep processing.

Cheers