0:04

In this unit we're going to talk about a very important component of every

general purpose computer called ALU or the Arithmetic Logic Unit.

Back in 1945 the mathematician John Von Neumann wrote

a seminal paper in which he included a diagram or

a description of how general purpose computers can be built.

And this became to be known over the years as the Von Neumann Architecture.

Now, when you look at this diagram, you see that one key player in the diagram is

the central processing unit and within this CPU, yet

another important piece the ALU or the Arithmetic Logic Unit.

Now, if we obstruct the way all these details and focus only on the ALU

we can think of an abstraction which receives to multi-bit inputs.

We call them input one and input two, and

the third input is the function that has to be computed.

So the ALU computes the function and out comes the result of this computation.

Now, the function f is one out of a family of predetermined functions

that taken together define what this ALU is capable of doing.

Some of these functions are arithmetic and some of these functions are logical.

So for example common computations that ALU typically perform

are integer addition, integer multiplication, integer division.

1:37

There may be some logical operations like bit wise AND, bit wise OR and so on.

So there's a really interesting question, which is when you set out to build an ALU,

how much functionality do you want to build in this hardware device.

Well this is a classical hardware software trade off question, because if you choose

not to implement something in hardware you can always augment it later with software.

So if for some reason you decide that the ALU will not include multiplication or

division, presumably at a later point when you build your software layer

you will deal, you will complete this functionality with software.

2:19

All right, now so far everything that we said was true for

every ALU out there on any computer.

From now on we are going to focus on one specific example of an ALU, we call

it the Hack ALU because this is the ALU that will hum inside our hack computer.

This is the overall gate diagram, and

as we see the ALU has two 16-bit data inputs which we call x and y.

It outputs a single 16-bit output which we call out, which function to compute is

determined by six control bits that have strange names like zx and nx and so on.

We will explain these names in just a few minutes.

Based on these six control bits,

the ALU computes one out of the following 18 functions of interest.

And I call these functions functions of interest because in principle

the ALU can compute many more functions, but

we've decided to focus on these 18 functions only.

Now some of these functions are very simple,

like the constance of 01 minus 1, xy and so on.

And other functions are more involved and

interesting like x plus y, x and y, and so on.

Now as we see from the diagram, the ALU also computes

two 1-bit control outputs which are called zr and ng.

The role of these two control bits and the reason for

these names would become clear later in the unit.

So let's move on and focus on the output of the ALU from one side and

the control bits that caused the ALU to compute these outputs,

and they cause it using this truth table.

So this truth table gives you a complete functional specification of this ALU.

That is, if you want to compute a certain function

you can look it up on the right hand side of the table.

You can then read off the zeros and ones that correspond to this function.

You enter the zeros and ones into the control bits and boom,

using some sort of black magic, the ALU will compute the desired function.

4:45

So let me illustrate how the ALU works in action and

in order to do it, I'm going to use our HDL simulator.

So we can fire up the simulator,

we can load the built-in ALU chip and as a result,

we'll get this chip into the HDL window and

once we do that, notice that we also get some nice GUI.

And indeed, some of the built-in chips in our simulator have a GUI side effect

that helps the user, you to understand what goes on inside the respective chip.

So this is a diagram that we made up to help you

keep track of what happens inside the ALU.

So moving along, we begin testing.

As you can notice we have set the ALU inputs to two values, which are 30 and 20.

And we also set the control bits to 000111,

which if you look at the table that I showed you before,

what they mean is it's a directive that tells the ALU compute y-x.

So the next thing that we do,

is we have to tell the simulator to actually do something.

And we do it by clicking this calculator icon, and

this tells the LU to evaluate the chip logic on the given inputs.

So this is what happens next and then we can inspect the outputs and

if we do that indeed we see that the ALU came out with what was advertised,

which is minus 10, the result of y- x.

So it looks like the ALU at least in this example, works well.

6:33

Let me give you a second example,

which demonstrates the logical computational abilities of the ALU.

The first thing that I do is I tell the simulator to revert to

working with a Boolean formats rather than decimal formats which make it

much it much easier to enter zeros and

ones into the various inputs of the ALU, and that's what we do here.

So I picked up two arbitrary examples of 16-bit zeros and

ones values, I entered them.

And then I entered also the control bit values

000000 which happens to be the directive to compute x and y.

Once again, if you look at the truth table, you will see this role listed out.

And indeed after we click the calculator icon, which I've skipped in this example,

we see that the ALU actually computed bit wise in the operation,

and the result was the bit wise end of the two given inputs.

So so far, it seems like the ALU is functioning quite well,

at least in these two examples.

Well, we didn't say anything about how the ALU actually works.

Everything so far was kind of magic.

So now is the time to open up the black box and

understand how the ALU actually performs this magic.

8:03

So once again this is the gate diagram or the interface diagram of the ALU, and

I want to focus on the six control bits and explain the names and

operations of every one of these bits.

So if zx=1, what we want to do is set the x input to 0.

So irrespective of what x is it can be 17 or 19 or 5,003 or whatever.

We set it to zero that's what we do if the x is 1.

If nx is 1, we set the x input to not x this is Bitwise negation,

and also notice that these two things happen one after the other.

So for example, if zx equals 1 and nx equals 1,

first of all, we 0 the x input and then we negate it.

So we'll get 1, 1, 1, 1, 1, 1,

if this is indeed the values of these two control bits.

The same thing exactly happens with a y input using the zy and

ny directives if you will, then we have an f bit.

If f is 1, we compute x plus y.

If f is 0, we compute x and y.

Now, these are the processed x and y.

So before we do these computations, the x and

ys have already undergone these manipulations that we talked about before.

They became either zero or negator or nothing, maybe we didn't touch them, and

then we compute either addition or 16-bit ending.

Finally, we have the no bit.

If the no bit is 1, we negate the resulting output.

The output that we just computed and if no is 0, we leave it as is.

9:56

If we do all of these operations one after the other then

what comes out is the desired function.

And now that you understand these semantics,

you can actually look at the table and try to convince yourself.

You can actually prove that this table delivers the required results,

and I will demonstrate to you how we can do it.

So let's pick up one example, let's see how value computes not x.

So I look up not x in the right-hand side.

I see it right there, and then I look up the binary values of the six

control bits and I start simulating on paper what happens inside the ALU.

So in order to do it I have to come up with some arbitrary examples of x and y.

So I make up two values and I use 4-bits instead of 16 to make it less tedious.

So I have these two examples x and y arbitrarily chosen,

and then I look at the control bits.

Zx equals 0, and nx equals 0,

which means that we don't touch the x input, we leave it as is.

11:06

And then we move onto the y input and we see that zy equals 1,

so we 0 the y input and n y equals 1, so we negate it and

what we get is the result 1, 1, 1, 1.

Moving along f is 0 and if f is 0, we want to compute x and y.

So we compute x and y and we get 1, 1, 0, 0.

This is a bit wise end and finally, no is 1.

So we negate the result, and we get 0, 0, 1, 1.

Lo and behold, 0, 0, 1, 1 is exactly not of x.

If you look at the original x, which was 1, 1, 0, 0, we got not x.

So we have proved that this row in the truth

table performs as advertised, so to speak.

Moving along, we can take another example, and this will be the final example.

12:04

We look at y-x, an arithmetic operation and

once again we see the binary values, and we begin simulating them.

So once again, we start with two arbitrary examples of x and y.

I've chosen 2 and 7.

This is arithmetic operations so

it's easier to think about it then both in decimal and in binary.

So we have 2 and 7.

And if everything works well, we should get the result 5 because y- x,

7- 2, should give us 5.

So we see that zx is 0 and nx is 0, so we don't touch the x input, it remains as is.

And moving along, we see that zy is 0, so we don't touch the y input.

But ny is 1, which means that we have to negate it.

So 0, 1, 1, 1 became 1, 0, 0, 0.

Moving along, we see that f equals 1.

So we compute the addition, and if we add up x and y, we get 1, 0, 1, 0.

No also equals 1, so we negate the result and we get 0, 1, 0, 1.

And 1, 0, 1 represents 5, which is exactly what we wanted.

So once again you see that the ALU performed as specified and

many of you may still wonder how this magic actually happens.

We were told that we have to do subtraction and

actually we did addition, and we got the result that we expected.

Well we don't want to get too much into it, but if you go back and read or look

at the units where we discussed the two's complement method, you will understand

also the internal mechanics here, and why everything comes out as expected.

13:54

Now as we said earlier in the unit, the ALU also

computes an output to a 1-bit output control bits.

And these bits are called zr and ng, and

the role of these bits is to say something about

the main output of the ALU denoted out.

Specifically, if out equals 0, the ALU sets zr to 1.

Otherwise, the zr becomes 0, and

if out is negative then ng equals 1.

Otherwise, ng equals 0.

Now, you may ask yourself why do we need these two bits?

Well, this will become clear when we put together the overall computer

architecture in which these two bits play an important role.

I'd like to make a few end notes about the Hack ALU.

I hope that we have convinced you that it's a simple concept.

It is very elegant, and surprisingly it's also

extremely easy to implement and let me explain why.

If you remember what we do with ALU given all these control bits,

in some cases we have to set 16-bit values to 0s, easy.

In other case, we have to set it to 1, also very easy.

In some cases, we have to negate an incoming value.

We've done it before I think in project one.

We built a gate that does exactly 16-bit negation.

And in some other cases we have to compute either plus or end and

these two computations were already,

are already taken care of using the chips that you designed in previous projects.

So all together, there is very little to do.

Everything was done in one way or

another by existing chips that you have already developed.

So to sum up this is Leonardo da Vinci,

one of the greatest inventor's in history and

Leonardo said that simplicity is the ultimate sophistication.

And I hope that I convince you that the Hack ALU is both simple but

quite sophisticated.