How Computers Calculate - the ALU

How Computers Calculate - the ALU: Crash Course Computer Science #5

英文

Hi, I’m Carrie Ann and this is Crash Course Computer Science.

So last episode, we talked about how numbers can be represented in binary. Representing Like, 00101010 is 42 in decimal.

Representing and storing numbers is an important function of a computer, but the real goal is computation, or manipulating numbers in a structured and purposeful way, like adding two numbers together.

These operations are handled by a computer’s Arithmetic and Logic Unit, but most people call it by its street name: the ALU.

The ALU is the mathematical brain of a computer.

When you understand an ALU’s design and function, you’ll understand a fundamental part of modern computers. It is THE thing that does all of the computation in a computer, so basically everything uses it.

First though, look at this beauty.

This is perhaps the most famous ALU ever, the Intel 74181.

When it was released in 1970, It was the first complete ALU that fit entirely inside of a single chip - Which was a huge engineering feat at the time.

So today we’re going to take those Boolean logic gates we learned about last week to build a simple ALU circuit with much of the same functionality as the 74181.

And over the next few episodes we’ll use this to construct a computer from scratch. So it’s going to get a little bit complicated, but I think you guys can handle it.

An ALU is really two units in one -- there’s an arithmetic unit and a logic unit.

Let's start with the arithmetic unit, which is responsible for handling all numerical operations in a computer, like addition and subtraction. It also does a bunch of other simple things like add one to a number, which is called an increment operation, but we’ll talk about those later.

Today, we’re going to focus on the pièce de résistance, the crème de la crème of operations that underlies almost everything else a computer does - adding two numbers together. We could build this circuit entirely out of individual transistors, but that would get confusing really fast.

So instead as we talked about in Episode 3 – we can use a high-level of abstraction and build our components out of logic gates, in this case: AND, OR, NOT and XOR gates.

The simplest adding circuit that we can build takes two binary digits, and adds them together.

So we have two inputs, A and B, and one output, which is the sum of those two digits.

Just to clarify: A, B and the output are all single bits.

There are only four possible input combinations.

The first three are: 0+0 = 0 1+0 = 1 0+1 = 1

Remember that in binary, 1 is the same as true, and 0 is the same as false.

So this set of inputs exactly matches the boolean logic of an XOR gate, and we can use it as our 1-bit adder.

But the fourth input combination, 1 + 1, is a special case. 1 + 1 is 2 (obviously) but there’s no 2 digit in binary, so as we talked about last episode, the result is 0 and the 1 is carried to the next column. So the sum is really 10 in binary.

Now, the output of our XOR gate is partially correct - 1 plus 1, outputs 0.

But, we need an extra output wire for that carry bit.

The carry bit is only “true” when the inputs are 1 AND 1, because that's the only time when the result (two) is bigger than 1 bit can store… and conveniently we have a gate for that! An AND gate, which is only true when both inputs are true, so we’ll add that to our circuit too.

And that's it. This circuit is called a half adder. It's not that complicated - just two logic gates - but let’s abstract away even this level of detail and encapsulate our newly minted half adder as its own component, with two inputs - bits A and B - and two outputs, the sum and the carry bits.

This takes us to another level of abstraction… heh… I feel like I say that a lot.

I wonder if this is going to become a thing.

Anyway, If you want to add more than 1 + 1 we’re going to need a “Full Adder.” That half-adder left us with a carry bit as output.

That means that when we move on to the next column in a multi-column addition, and every column after that, we are going to have to add three bits together, no two.

A full adder is a bit more complicated - it takes three bits as inputs: A, B and C. So the maximum possible input is 1 + 1 + 1, which equals 1 carry out 1, so we still only need two output wires: sum and carry.

We can build a full adder using half adders. To do this, we use a half adder to add A plus B just like before – but then feed that result and input C into a second half adder.

Lastly, we need a OR gate to check if either one of the carry bits was true.

That’s it, we just made a full adder! Again,we can go up a level of abstraction and wrap up this full adder as its own component. It takes three inputs, adds them, and outputs the sum and the carry, if there is one.

Armed with our new components, we can now build a circuit that takes two, 8-bit numbers – Let’s call them A and B – and adds them together.

Let’s start with the very first bit of A and B, which we’ll call A0 and B0. At this point, there is no carry bit to deal with, because this is our first addition. So we can use our half adder to add these two bits together. The output is sum0. Now we want to add A1 and B1 together.

It's possible there was a carry from the previous addition of A0 and B0, so this time we need to use a full adder that also inputs the carry bit. We output this result as sum1.

Then, we take any carry from this full adder, and run it into the next full adder that handles A2 and B2. And we just keep doing this in a big chain until all 8 bits have been added.

Notice how the carry bits ripple forward to each subsequent adder. For this reason, this is called an 8-bit ripple carry adder. Notice how our last full adder has a carry out.

If there is a carry into the 9th bit, it means the sum of the two numbers is too large to fit into 8-bits.

This is called an overflow.

In general, an overflow occurs when the result of an addition is too large to be represented by the number of bits you are using.

This can usually cause errors and unexpected behavior.

Famously, the original PacMan arcade game used 8 bits to keep track of what level you were on.

This meant that if you made it past level 255 – the largest number storablein 8 bits – to level 256, the ALU overflowed.

This caused a bunch of errors and glitches making the level unbeatable.

The bug became a rite of passage for the greatest PacMan players.

So if we want to avoid overflows, we can extend our circuit with more full adders, allowing us to add 16 or 32 bit numbers. This makes overflows less likely to happen, but at the expense of more gates. An additional downside is that it takes a little bit of time for each of the carries to ripple forward.

Admittedly, not very much time, electrons move pretty fast, so we’re talking about billionths of a second, but that’s enough to make a difference in today’s fast computers.

For this reason, modern computers use a slightly different adding circuit called a ‘carry-look-ahead’ adder which is faster, but ultimately does exactly the same thing-- adds binary numbers.

The ALU’s arithmetic unit also has circuits for other math operations and in general these 8 operations are always supported.

And like our adder, these other operations are built from individual logic gates.

Interestingly, you may have noticed that there are no multiply and divide operations.

That's because simple ALUs don’t have a circuit for this, and instead just perform a series of additions.

Let’s say you want to multiply 12 by 5.

That’s the same thing as adding 12 to itself 5 times. So it would take 5 passes through the ALU to do this one multiplication. And this is how many simple processors, like those in your thermostat, TV remote, and microwave, do multiplication.

It’s slow, but it gets the job done.

However, fancier processors, like those in your laptop or smartphone, have arithmetic units with dedicated circuits for multiplication.

And as you might expect, the circuit is more complicated than addition -- there’s no magic, it just takes a lot more logic gates – which is why less expensive processors don’t have this feature.

Ok, let’s move on to the other half of the ALU: the Logic Unit.

Instead of arithmetic operations, the Logic Unit performs… well... logical operations, like AND, OR and NOT, which we’ve talked about previously.

It also performs simple numerical tests, like checking if a number is negative.

For example, here’s a circuit that tests if the output of the ALU is zero.

It does this using a bunch of OR gates to see if any of the bits are 1.

Even if one single bit is 1, we know the number can’t be zero and then we use a final NOT gate to flip this input so the output is 1 only if the input number is 0.

So that’s a high level overview of what makes up an ALU. We even built several of the main components from scratch, like our ripple adder.

As you saw, it’s just a big bunch of logic gates connected in clever ways.

Which brings us back to that ALU you admired so much at the beginning of the episode.

The Intel 74181.

Unlike the 8-bit ALU we made today, the 74181 could only handle 4-bit inputs, which means YOU BUILT AN ALU THAT’S LIKE TWICE AS GOOD AS THAT SUPER FAMOUS ONE. WITH YOUR MIND! Well.. sort of. We didn’t build the whole thing… but you get the idea.

The 74181 used about 70 logic gates, and it couldn’t multiply or divide.

But it was a huge step forward in miniaturization, opening the doors to more capable and less expensive computers.

This 4-bit ALU circuit is already a lot to take in, but our 8-bit ALU would require hundreds of logic gates to fully build and engineers don’t want to see all that complexity when using an ALU, so they came up with a special symbol to wrap it all up, which looks like a big ‘V’. Just another level of abstraction!

Our 8-bit ALU has two inputs, A and B, each with 8 bits. We also need a way to specify what operation the ALU should perform, for example, addition or subtraction.

For that, we use a 4-bit operation code.

We’ll talk about this more in a later episode, but in brief, 1000 might be the command to add, while 1100 is the command for subtract. Basically, the operation code tells the ALU what operation to perform. And the result of that operation on inputs A and B is an 8-bit output.

ALUs also output a series of Flags, which are 1-bit outputs for particular states and statuses.

For example, if we subtract two numbers, and the result is 0, our zero-testing circuit, the one we made earlier, sets the Zero Flag to True (1). This is useful if we are trying to determine if two numbers are are equal.

If we wanted to test if A was less than B, we can use the ALU to calculate A subtract B and look to see if the Negative Flag was set to true.

If it was, we know that A was smaller than B.

And finally, there’s also a wire attached to the carry out on the adder we built, so if there is an overflow, we’ll know about it. This is called the Overflow Flag.

Fancier ALUs will have more flags, but these three flags are universal and frequently used.

In fact, we’ll be using them soon in a future episode.

So now you know how your computer does all its basic mathematical operations digitally with no gears or levers required.

We’re going to use this ALU when we construct our CPU two episodes from now.

But before that, our computer is going to need some memory! We'll talk about that next week.

中文

嗨,我是CarrieAnne,这里是十分钟速成课:计算机科学

上集,我们谈了如何用二进制表示数字,比如,二进制的“00101010”是十进制的“42”,表示并存储数字是计算机的重要功能

但真正的目标是计算,或者说是以有意义的方式处理数字,比如将两个数字相加,这些操作由计算机的“算术逻辑单元“处理,但大多数人会简称它:ALU

ALU是计算机的数学大脑,等你理解了ALU的设计和功能之后,你就理解了现代计算机的基石

ALU就是计算机里负责所有运算的,所以基本上,其他所有部件也用到了它,先来看看这个神奇的东西

这可能是最著名的ALU,英特尔74181,1970年发布时,它是第一个完全封装在单个芯片内的完整ALU,这在当时是惊人的工程壮举

今天我们要用上周学的布尔逻辑门,来构建一个简单的ALU电路,功能和74181相同。然后接下来几集,我们会用它从头做出一台电脑,所以会有点复杂,但我觉得你们搞的定。

ALU有2个单元,1个算术单元和1个逻辑单元,让我们从算术单元开始,它负责计算机里的所有数字操作,比如加减法,它还做一些其他简单事,比如给某个数字+1,这叫增量运算,我们之后会说

今天的重点是一切的根本-"将两个数字相加"

我们可以用单个晶体管一个个拼,把这个电路做出来,但很快就会复杂的难以理解,所以与其用晶体管,我们会像第3集谈到的那样

-用更高层次的抽象,也就是用逻辑门来做,我们会用到AND,OR,NOT和XOR逻辑门,最简单的加法电路,就是拿2个bit加在一起（bit就是0或者1）有2个输入:A和B,1个输出:就是两个数字的和需要说清的是:A,B,输出,这3个都是单个Bit（0或1）

只有四种可能的组合,前三个是:0+0=0,1+0=1,0+1=1,记住二进制里,1与true相同,0与false相同

所以这组输入和输出,与XOR门的逻辑完全一样,,我们可以把XOR用作1位加法器（adder）

但第四个输入组合,1+1,是个特例1+1是2（显然）但二进制里没有2,所以正如上集说的,结果是0。1进到下一位,所以它的和是二进制的“10”

XOR门的输出,只对了一部分,1加1,输出0,但我们需要一根额外的线代表进位,只有当输入是1和1时,进位才是“true”,因为这是唯一一个情况,1个Bit存不下结果,方便的是,我们刚好有个逻辑门能做这个事！

AND门,只有当两个输入都为“true”,输出才为“true”,所以我们把它加到电路中,就这样了。这个电路叫“半加器”。

没那么复杂-就两个逻辑门而已- 让我们把这个抽象化,把“半加器”封装成一个单独组件

两个输入,A和B都是1位-两个输出“总和”与“进位”,这就进入了另一层抽象,我好像提了好多次这事,说不定会变成一个传统什么的。

总之,如果你想处理大过“1+1”的情况,就需要“全加器”（fulladder）,半加法器将进位作​​为输出,也就是说,我们算下一列时,

还有之后的每一列,我们得加3个位在一起,并不是2个,全加器复杂了一点点 -有3个Bit输入:A,B,C 所以最大的可能输入是1+1+1

“总和”1“进位”1,所以需要两条输出线:“总和”“进位”, 我们可以用半加器做全加器。我们先用半加器将A和B相加,就像之前一样,然后把C输入到第二个半加器,最后用一个OR门检查进位是不是true。就这样,我们做出了一个全加器！

我们可以再提升一层抽象,把这个全加器作为独立的组件,全加器会把A,B,C三个输入加起来,然后输出“总和”以及“进位”,如果有进位的话,现在有了新组件,我们可以做个电路相加两个8Bit,叫他们A和B好了,然后把它们相加。

我们从A和B的第一位开始,叫A0和B0好了,我们不需要处理任何进位,因为这是第一次加法,所以我们可以用半加器来加,输出叫sum0好了,现在要加A1和B1

因为A0和B0的结果有可能进位,所以这次要用全加器,除了A1和B1,还要连上进位,我们把这个结果叫做sum1,然后,把这个全加器的进位,连到下个全加器的输入,处理A2和B2,然后依次类推,把8个bit都搞定。

注意每个进位是怎么连到下一个全加器的。所以这个叫做"8位脉动进位加法器"注意最后一个全加器有“进位”的输出,如果第9位有进位,代表着2个数字的和太大了,超过了8位,这叫“溢出”（overflow）

一般来说,“溢出”的意思是,两个数相加的和太大了,超过了你用来表示的位数,会导致错误和不可预计的结果。

著名的例子是,吃豆人用8bit存目前的关卡,如果你玩到了第256关（8位bit最大能表示255）,ALU会溢出,造成一连串错误和乱码,使得该关卡无法进行,这个bug成了厉害的吃豆人玩家的代表

如果想避免溢出,我们可以加更多全加器,然后相加16或32位数字。这使得溢出更难发生,但代价是要用更多逻辑门,另外一个缺点是,每次进位都要一点时间向前移动,当然时间不久,因为电子移动的很快,但在如今的电脑里,量级是每秒数十亿次,就会有影响。

现代计算机用了稍微不同的加法电路,叫做“超前进位加法器”,它更快,做的事情是一样的-把二进制数相加

ALU的算术单元,也能做一些其他数学运算,一般来说,这8个操作都是支持的,就像加法器一样,这些操作也是由逻辑门构成的。

有趣的是,你可能注意到没有乘法和除法,因为简单的ALU没有专门的电路来处理,而是把乘法用多次加法来实现,假设你想用“12”乘5,这和把“12”加5次是一样的,所以需要5次ALU操作来实现这个乘法

这就是许多简单的处理器,比如恒温器,电视遥控器和微波炉,做乘法的方法,慢是慢,但是搞的定。

然而笔记本和手机有更好的处理器,有专门做乘法的算术单元,正如你想的那样,乘法电路比加法复杂-没什么魔法,只是更多逻辑门,这就是为什么便宜的处理器没这个功能

好了,我们现在讲ALU的另一半:逻辑单元,逻辑单元不执行算术,执行的是逻辑操作,比如之前讨论过的AND,OR和NOT操作

它也执行简单的数值测试,比如检查一个数字是不是负数,例如,这里是个检查ALU的输出是否为0的电路,它用一堆OR门来检查其中一位是否为1,哪怕只有一个Bit(位)是1,

我们就知道那个数字肯定不是0,然后用一个NOT门取反,所以只有输入的数字为0时,输出才为1。

以上就是ALU的一个高层次概括。

我们甚至从头开始做了几个主要组件,比如脉动进位加法器,正如你看到的,只是一大堆逻辑门用巧妙的方式连在一起。

让我们回到视频开始时的ALU,英特尔74181,和我们今天做的8位ALU不同,74181只能处理4位输入,也就是说,你刚做了一个比英特尔74181好两倍的APU,其实差不多啦..

虽然我们没有从头到尾的做出来,但你已经理解了整体概念。

74181用了大约70个逻辑门,但不能执行乘除,但它在小型化方面迈出了一大步,打开了更强大更便宜电脑的大门

4位ALU已经需要很多逻辑门了,但我们的8位ALU会需要数百个逻辑门,工程师不想在用ALU时去管那些复杂性,所以想了一个特殊的符号来代表它,看起来像一个大“V”,这只是另一个层次的抽象！

我们的8位ALU有两个输入,A和B,每个都是8位(bits),我们还需要一种方法指定ALU应该执行什么操作,例如加法或减法,为此,我们用4Bit的操作代码。

我们之后的某一集会再说这个,简言之,“1000”可能会代表加法命令,而“1100”代表减法命令,基本上,操作代码会告诉ALU执行什么操作,输入A和B的操作结果是8位输出,ALU还输出一系列标志（Flag）,代表特定状态的1位（bit）输出

例如,如果我们相减两个数字,结果为0,我们的零测试电路（前面做的）会将零标志设为True（1）确定两个数字是否相等时非常有用

如果想测A是否小于B,可以用ALU来算A减B,看负标志是否为true,如果是true,我们就知道A小于B

最后,还有一条线连到加法器的进位,所以如果有溢出,我们就能知道,这叫溢出标志

高级的ALU有更多标志,但这3个标志是ALU普遍用的,事实上,我们未来某集会用到它们,现在你知道了电脑是怎么在没有齿轮或杠杆的情况下进行运算的

在接下来两集中,我们会用这个ALU来做CPU,但在此之前,我们的电脑会需要一些“记忆”！

我们下周再谈这个话题。