【计算机系统架构】从0开始构建一台现代计算机|二进制、布尔运算和ALU|第2章

在这里插入图片描述

博主简介：努力学习的22级计算机科学与技术本科生一枚🌸

博主主页： @Yaoyao2024

往期回顾：【计算机系统架构】从0开始构建一台现代计算机|布尔代数和基础逻辑门|第一章

每日一言🌼: 勇敢的人，不是不落泪的人，而是愿意含着泪继续奔跑的人。
——《朗读者》

0、前言

一言以蔽之：利用上一模块中构建的芯片组，我们现在将着手构建一个加法器系列–专为数字加法而设计的芯片。然后，我们将向前迈出一大步，构建一个算术逻辑单元。算术逻辑单元设计用于执行一整套算术和逻辑运算，是计算机的计算大脑。在本课程的后半部，我们将使用 ALU 作为核心芯片，并在此基础上构建计算机的中央处理器（CPU）。由于所有这些芯片都以二进制数（0 和 1）为运算单位，因此我们将从二进制运算的总体概述开始本模块的学习，然后再深入学习 ALU 的构建。
关键概念：二进制数、二进制加法、二进制补法、半加法器、全加法器、n 位加法器、计数器、算术逻辑单元 (ALU)、组合逻辑。

1、二进制数

其实在上一章节，我们并没有讲到“数”的概念，以及“进制”的概念，我们只是有两个相反概念的布尔值1和0对他进行相应各种布尔逻辑运算（And,Or,Not)。

只通过上述这样一位一位的布尔逻辑运算，肯定和我们复杂的计算机还差的远。既然是计算机，”计算“必然要有数。如何通过仅有的0,1两个符号表示数呢？

我们可以将其进行组合：

通过将0,1进行组合，像99,20这样将0,1,2,3,4,5,6,7,8,9进行组合一样，表示不同的数。有多少种组合，即可表示多少个数。

于是，我们通过这种0,1进行组合来表示数（其实我们用到的十进制就是用10个符号进行组合来表示数的）：
在这里插入图片描述

1.1、进制的概念

首先，我们要清楚，对于我们的计数系统，每一个数字所在的位置合这个数字代表的意义有关：

为什么这么说呢？假设我们穿越到原始时代，使用木棍进行计数，一个木棍代表一个猎物，那么假如有11个猎物，你会怎么计数：

$11111111111$

OK我们会用11个木棍排在一起代表有几个猎物。

再看我们现在的技术系统，表示11个猎物是：11，咿呀？怎么只有”两个木棍"？,这是因为，这两个1的位置不同，代表的意思不同:

$11 = 1×10^1 + 1×10^0$

前一个1表示10，后一个1表示1。

而这种每个数字所在位置代表的实际个数就是进制。

只使用单个0~9进行表示最多能10个数（也就是“逢10进1），要想再多表示怎么办，给不同位置的数赋予不同的意义。

同样的只使用0,1最多只能表示2个数：0和1，要是想表示2怎么办？10（也就是“逢2进1），这个时候1表示的是满了的2，0表示单个的并没有。

这就是进制，因此只使用0,1且带有位置权值的计数系统则为二进制计数系统。

1.2、二进制转为十进制

我们都知道每一位的0,1代表什么意思，把这个位置的数✖对应该位置的权值即可化简出对应的10进制数。

在这里插入图片描述

1.3：二进制转10进制

1.4：固定位宽(Fixed word size)

如1.2，k的取值代表的计数01序列长度，也称为位宽，位宽不同，0,1序列所表示的数字最大限度就不同。

在计算机底层，一个整数的位宽当然不是无限的，而是固定的（通常是8bits)

在这里插入图片描述

但是，我们忽略了一点：负数（Negative Number)

但是也有方法解决，这个时候我们将0,1序列的最左边一个比特位设为符号位（看，这个位置的符号代表的含义变了哦），若位1则代表是负数，否则则是正数。

Tips: 不过在计算机内部负数到底是如何表示的呢? 仅仅是牺牲一个比特位作为符号位就够了吗？当然不是，关于负数在计算机内部的表示和存储会在第3节详细讲解。

2、二进制加法

上节我们讨论了如何使用0,1来构建我们的二进制计数系统，那么有了数字，这节我们来看看如何使用二进制数字进行基本的算术运算吧~

Addition
Substraction
Which is greater?
Multiplication
Division

在这里插入图片描述

首先，我们知道，基本的算数运算就是以上6种；但是，设计了加法的硬件部分，实现了两个数相加的底层逻辑，其他的也可以实现。为什么？
一言蔽之：实现了加法,其他运算也可以转换为加法运算

对于减法、比较大小两个运算，实现了加法，就可以实现减法: 减法可以转换为负数相加
那对于乘法、除法呢？这些不会去专门设计一个硬件电路去实现（当然在不考虑成本和效率的情况下，当然可以设计一个专门的芯片），因为它本身其实就是 循环加、循环减法，可以在计算机系统的 软件层次去编写库函数去实现（实际上后续也会讲到，是在操作系统的数学库函数里实现的）。

总而言之，所有 运算的根基就是加法，实现了加法，其他运算也就水到渠成。

那么我们下面就来看看计算机底层是如何实现加法运算的。

2.1：我们是如何做加法的

让我们回到小学一二年级，看看我们对十进制的加法是如何进行的：

在这里插入图片描述
那么对于二进制，计算其实也是一样的：从右往左，一位一位的计算，把当前两位相加得到当前位的结果和进位、下一位的结果和进位是由下两位以及进位相加得到。

在这里插入图片描述

2.2：溢出Overflow

但是，这样做有一个问题：最高位溢出Overflow

因为根据上文，我们知道，整数存储在计算机底层具有固定的位宽(Fixed Word Size)，因此如下图所示，当相加的两个二进制整数太大，导致结果表示超过了位宽，即叫做溢出：

那么这种情况下，计算机会怎么处理呢？抛出异常？报错？实际上计算机处理方法是：To Do Nothing. 没错，当两个整数相加，结果超过位宽，计算机只会截取并且保存从右到左固定位宽大小的数据而直接将其溢出的部分舍去。

🪧Tips：虽然这样看起来很不合理，因为对于程序员来说，你必须清楚你的计算是否会溢出以避免最终得到的结果不正确。但是，我个人认为，这种处理方法实际上为后面要讲到的负数运算提供了便利。

💁🏻‍♀️下面，我们来看看如何设计实现加法的硬件芯片吧，这将分为三个阶段，这是一个逐渐抽象的过程，从半加器到全加器再到真正的多位加法器，后者以前者为基础进行实现。

2.3：半加器HA（Half Adder：adds two bits)

半加器是考虑整输入只有两个待相加的比特位，输出结果为：当前位计算结果(sum) + 进位(carry)

在这里插入图片描述

对于只有2个bit位相加的逻辑我们可以使用真值表进行表示，随后确定半加器的芯片设计：
在这里插入图片描述

但是这种半加器的限制是，它没有考虑当前计算位的进位是多少（而默认为0)，而我们知道，实际计算过程中，除了要考虑当前位的两个数，还需要考虑上一位计算结果得到的进位，然后一起将这3个比特位的值相加得到最终结果以及进位。因此，我们需要能够相加3比特位的芯片👉🏼全加器。

2.4: 全加器FA（Full Adder：adds three bits)

在这里插入图片描述

事实上，全加器可以由2个半加器组合得到（这也是半加器名字的由来）：

在这里插入图片描述

2.5：加法器Adder（Adds two numbers）

多位加法，如下图，其实就是从右往左做单位全加：比如黄色方框两个数相加得到该位的结果以及进位，进位参与下一位的绿色方框的运算…依次进行。
在这里插入图片描述

实现起来也很简单，我们可以使用1个半加器+15个全加器串接，或者直接使用16个全加器串接即可：

在这里插入图片描述

3、负数

在前面其实讲二进制数的时候，其实提到过负数的表示：牺牲最高位的数据位，设为符号位，以区别负数。

但是计算机底层内部的负数表示与存储真的是这样吗？其实不是这么简单，因为如果简单的这样处理，会引发一些问题：

0000和1000表示0和-0，有两个0的存在，这样很不优雅（elegant)且会带来一些麻烦
减法和加法无法使用同一个硬件电路，需要明确得设计出两个不同的电路进行处理（因为即使用整数加上负数表示简繁，得出来的结果并不正确），很麻烦

所以，事实上，计算机底层的负数表示并不是上述那样，而是使用了二进制：补码（2’s Complement）的方法来表示负数，这种方法不仅使得正数和负数的表示十分方便和优雅，且在计算方面，减法和加法使用同一个加法电路即可完成，极大的降低了成本。

在这里插入图片描述

👉🏼最棒的一点就是，当我们使用上述“补码”的方式去表示负数时，当我们进行减法时，减法其实就是负数的加法，我们只需要使用一个加法芯片即可完成。

在这里插入图片描述
如上图，当我们计算-2-3时，因为14 = 2^4 - 2代表的就是-2，那么实际上这个表达式就是两个负数相加，那么我们将负数对应的二进制补码相加，得到的结果，也就是这个计算结果也是一个二进制补码，它表示的负数就是正确结果。（你看这里其实最高位被舍弃了，我们在讲正整数相加时如果溢出位被舍弃，得到的结果是不正确的，但是在减法这里，其实正是因为这个舍弃，得到的结果才是正确的，这也是为什么我在上文讲溢出的时候说，我认为溢出不报错的原因就是因为它其实在减法运算过程中起到了一定的作用！）。

嗯，上述讲解是不是感觉很神奇，用补码这种形式表示负数，进行负数的加法得到的结果也是正确结果的表达形式。那么下面来讲解一下，这是怎么发生的：

首先我们要明确一点的是，使用补码表示负数，即：

$x = 2^n - x$

也就是说，我们看到 $2^n-x$ , 那么它就是 $- x$ ，这点必须明确。

下面从2种情况来论证，当使用补码来表示负数时，那么减x就是加上-x:

下面假设a>0，b>0

1) a-b

$a - b = a + (-b) = a + (2^n-b) = 2^n - (b-a)$
$\begin{cases} & \text{ if b>a} 则(a-b)<0,结果为-(b-a)就是2^n - (b-a)\\ & \text{ if b<a} 则(a-b)>0,结果为a-b 就是-(b-a) \end{cases}$

2) -a-b

$a - b = (-a) + (-b) = (2^n-a) + (2^n-b) = 2^n - (b+a) = -(a+b)$

这里注意有一个关键就是 $2^n-a) + (2^n-b)= 2^n - (b+a)$ 这里为什么有一个2^n直接被丢掉了？你想的没错，这里就是两个负数最高位符号位都是1, 相加，溢出，直接丢了2^n。
在这里插入图片描述
所以综上论述，使用补码来表示二进制负数，是完全可以的。

但是现在还差一点，比如输入a和b(a>0,b>0),求a-b，为了能够实现上述的把减法转换为加上负数，我们还需要把b转为-b，即：输入x求-x的求补码电路设计：

在这里插入图片描述
如上图，我们的目标是求2^n-x，但这本身就是一个减法，直接求当然是行不通的，但是我们可以转换一下。

首先看到上述等式的后半部分： (2^n-1) - x，它本质是将正数x取反，我们前面一章已经学会了如何进行多线路的取反操作；再看到等式前面的+1，这就更简单啦，因为我们前面已经设计出来了加法电路。

综上，我们使用了已有的取反+加法电路，实现了求补码的操作；求补码操作是后续负数加法的基础，只有先得到这个负数的二进制补码表示才可以对其进行加法操作。

下面这个例子讲了如何求-4的补码:
在这里插入图片描述
很简单：

首先将其正数4的二进制位全部进行翻转
得到的结果+1

Tips: 其实到这里，老师并没有讲到什么原码、反码、补码的概念，其实说实话也没有必要了解了到这里的话，但是我发现国内讲负数这块和这门课老师讲的完全不同，这门课则是从为什么需要这么表示开始，讲到补码是专门位计算机表示负数的一种表示方法，非常有逻辑。而国内则是一开始上来就讲原、反、补，什么正数的原反补相同什么什么的，搞初学者晕头转向，最后记下来了吧，其实也不知道为什么要这样做。我前面在学习原反补的时候也专门写了一篇博客👉【C语言篇】移位操作符、位操作符详解–图解演示、例题讲解、经验总结

看完这节课我才明白，原码、反码，其实根本没有必要存在，计算机里面负数就一个补码，而正数也不存在什么原反补。原反补只能说是在计算负数的补码时候的一种方法吧！（这里也只是基于现在我的认知的一个了解，如果有错误请在评论区告诉我！）

4、ALU（算术逻辑单元）

4.1 介绍

ALU（Algorithm Logic Unit）是冯诺依曼计算机体系结构种的重要组成部分：
在这里插入图片描述

让我们聚焦到ALU，它具有两个多位输入input1,2、计算函数f，计算结果输出。其中计算函数f是一系列预先确定好的函数（算术运算、逻辑运算)种的一个，这些函数共同定义了ALU的功能。

⭐ALU该包含哪些函数？？！
💁🏻‍♀️事实上，ALU并不需要包含所有的运算函数；因为计算机系统分为硬件（Hardware）和软件（Software）两部分；比如当我们硬件中实现了加法，那么乘法、除法可以使用软件编写程序（乘法=循环➕，除法=循环➖）完成，这取决于你的取舍（设计特定的硬件肯定成本更高，但是运算起来速度快）。

本课程将设计一个简单的ALU（如下图）。

它有2个16位的输入位x、y
有1个16位的计算结果输出位out
有6个控制位，负责控制计算函数的选择
这个AL一共包含了16个运算函数
且有2个1bit位的输出zr、ng （稍后讨论）

关于控制位，给控制位输入特定的值，则会进行特定的运算：
在这里插入图片描述

4.2：工作原理

⭐1) 控制位介绍：

在这门课的ALU，具有6个控制位，它们表示对输入信号的处理；输入相同，控制位不同，产生的逻辑运算的结果就不同；输入不同，控制位相同，运算逻辑（即运算函数）不变。
在这里插入图片描述
下面这是整个ALU的逻辑运算表：

下面以!x这个运算举例，说明这确实是可行的：

🚨Tips：不知道在真正学习ALU的控制位进行控制从而进行不同函数运算之前，大家会不会像我一样认为，这个控制位就是类似于选择器的那个选择信号，数据一股脑输入之后，会进行所有运算，然后选择一个运算函数的运算结果进行输出：

但是实际的控制位并不是这种单纯的选择作用。它把一个大的选择分成很多细小的选择：对X取非、And还是Add…分成这种细小操作，然后用控制位对这些细小操作是否执行进行控制（我觉得是组合），从而组合而成一个特定的运算函数。我觉得这样做有很大一个好处就是基本芯片的复用，或者说还是计算机里的抽象思维，因为如果把Add和And这些芯片一个个单独写出来，其实它们有很多重复的基本操作（取非呀、置为0呀…)，于是把这些基础的操作单独提出来，然后使用控制位对其进行控制，选择，对这些基础操作进行组合，从而得到特定的操作函数。我相信如果是我上面图那样，每一个特定函数都写一个特定的芯片，这样的制造成本肯定比将基本的芯片进行提取，然后用控制位进行控制和选择高得多。

在这里插入图片描述

4.3：总结

在这里插入图片描述

5、项目Project02

5.1：半加器HalfAdder

在这里插入图片描述
半加器很简单了，两个输入，两个输出；分开来看Sum的运算逻辑就是异或Xor，Carry的运算逻辑则是And，把这两个结合即为半加器：

在这里插入图片描述

/**
 * Computes the sum of two bits.
 */
CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b 
        carry;  // Left bit of a + b

    PARTS:
     Replace this comment with your code.
    Xor(a = a, b = b, out = sum);
    And(a = a, b = b, out = carry);
}

5.2：全加器FullAdder

全加器也很简单，它可以由两个半加器组合而来：
在这里插入图片描述

/**
 * Computes the sum of three bits.
 */
CHIP FullAdder {
    IN a, b, c;  // 1-bit inputs
    OUT sum,     // Right bit of a + b + c
        carry;   // Left bit of a + b + c

    PARTS:
     Replace this comment with your code.
    HalfAdder(a= a, b= b, sum= s1, carry= c1);
    HalfAdder(a= s1, b= c, sum= sum, carry= c2);
    Or(a= c1, b= c2, out= carry);
}

5.3：16位加法器Add16

多位加法器也很简单，把16个全加器进行串接即可：
在这里插入图片描述

/**
 * 16-bit adder: Adds two 16-bit two's complement values.
 * The most significant carry bit is ignored.
 */
CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
     Replace this comment with your code.
    FullAdder(a= a[0], b= b[0], c= false, sum= out[0], carry= c1);
    FullAdder(a= a[1], b= b[1], c= c1, sum= out[1], carry= c2);
    FullAdder(a= a[2], b= b[2], c= c2, sum= out[2], carry= c3);
    FullAdder(a= a[3], b= b[3], c= c3, sum= out[3], carry= c4);
    FullAdder(a= a[4], b= b[4], c= c4, sum= out[4], carry= c5);
    FullAdder(a= a[5], b= b[5], c= c5, sum= out[5], carry= c6);
    FullAdder(a= a[6], b= b[6], c= c6, sum= out[6], carry= c7);
    FullAdder(a= a[7], b= b[7], c= c7, sum= out[7], carry= c8);
    FullAdder(a= a[8], b= b[8], c= c8, sum= out[8], carry= c9);
    FullAdder(a= a[9], b= b[9], c= c9, sum= out[9], carry= c10);
    FullAdder(a= a[10], b= b[10], c= c10, sum= out[10], carry= c11);
    FullAdder(a= a[11], b= b[11], c= c11, sum= out[11], carry= c12);
    FullAdder(a= a[12], b= b[12], c= c12, sum= out[12], carry= c13);
    FullAdder(a= a[13], b= b[13], c= c13, sum= out[13], carry= c14);
    FullAdder(a= a[14], b= b[14], c= c14, sum= out[14], carry= c15);
    FullAdder(a= a[15], b= b[15], c= c15, sum= out[15], carry= c16);
}

5.4：进位器Inc16

进器其实就是一个简易版的加法器，它的输出结果是输入值+1：

/**
 * 16-bit incrementer:
 * out = in + 1
 */
CHIP Inc16 {
    IN in[16];
    OUT out[16];

    PARTS:
     Replace this comment with your code.
    Add16(a = in, b[0] = true, b[1..15] = false, out = out);
}

Tips: Inc16在本次构建ALU时并不会使用，后续用到

5.5：算术逻辑单元ALU

在这里插入图片描述

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/2/ALU.hdl
/**
 * ALU (Arithmetic Logic Unit):
 * Computes out = one of the following functions:
 *                0, 1, -1,
 *                x, y, !x, !y, -x, -y,
 *                x + 1, y + 1, x - 1, y - 1,
 *                x + y, x - y, y - x,
 *                x & y, x | y
 * on the 16-bit inputs x, y,
 * according to the input bits zx, nx, zy, ny, f, no.
 * In addition, computes the two output bits:
 * if (out == 0) zr = 1, else zr = 0
 * if (out < 0)  ng = 1, else ng = 0
 */
// Implementation: Manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) sets x = 0        // 16-bit constant
// if (nx == 1) sets x = !x       // bitwise not
// if (zy == 1) sets y = 0        // 16-bit constant
// if (ny == 1) sets y = !y       // bitwise not
// if (f == 1)  sets out = x + y  // integer 2's complement addition
// if (f == 0)  sets out = x & y  // bitwise and
// if (no == 1) sets out = !out   // bitwise not

CHIP ALU {
    IN  
        x[16], y[16],  // 16-bit inputs        
        zx, // zero the x input?
        nx, // negate the x input?
        zy, // zero the y input?
        ny, // negate the y input?
        f,  // compute (out = x + y) or (out = x & y)?
        no; // negate the out output?
    OUT 
        out[16], // 16-bit output
        zr,      // if (out == 0) equals 1, else 0
        ng;      // if (out < 0)  equals 1, else 0

    PARTS:
     Replace this comment with your code.
    //processX:
    Mux16(a= x, b= false, sel= zx, out= zeroX);
    Not16(in= zeroX, out= notX);
    Mux16(a= zeroX, b= notX, sel= nx, out= nX);

    //processY
    Mux16(a= y, b= false, sel= zy, out= zeroY);
    Not16(in= zeroY, out= notY);
    Mux16(a= zeroY, b= notY, sel= ny, out= nY);

    //f
    Add16(a = nX, b = nY, out = addXY);
    And16(a = nX, b = nY, out = andXY);
    Mux16(a= andXY, b= addXY, sel= f, out= fXY);
    //outPut
    Not16(in= fXY, out= nFXY);
    Mux16(a= fXY, b= nFXY, sel= no, out= out,out[15]=ng, out[0..7]=outa, out[8..15]=outb);

    //zr
    Or8Way(in= outa, out= or1);
    Or8Way(in= outb, out= or2);
    Or(a= or1, b= or2, out= temp);
    Not(in= temp, out= zr);
}