计算

芯片

• 芯片：计算能源，有了芯片，设备通电后才可以计 算，有了计算，这些设备才能够实现更加复杂而精确的功能。
• 历史上是先有计算机，后有的芯片。世界上第一个芯片，也被称作集成电路。
• 芯片的计算能力来源于芯片内部的集成电路，集成电路大大减小了电路的体积，所有的元件都是用同一 块半导体材料制作而成，也就是把所有的电路都集成到了一个单一的硅片上。
• 摩尔定律：计算能力的发展

公理 & 不完备定理

• 可计算理论：图灵机
• 公理化体系和不完备性定理
• 德国著名数学家希尔伯特提出：这个世界可以建立一套完善的公理体系，由少数几个公理出发，推导出所有的定理和推论。这样就可以逐渐通过这种方法将世界上的万事万物都统一到一 个体系中。
• 计算机能力也是有边界的。哥德尔的不完备性定理，让大家看到了世界上还有大量不可计算的问题
• 图灵机和可计算理论：可计算性理论是计算机科学的理论基础之一
• 不可计算问题：如果素数是无穷的，那 么我们的计算就是无穷无尽的，所以这样的问题不可计算
• 停机问题:不能因为这个程序执行 了 10 年，从而得出它不会停止的结论。

计算能力的边界在哪里

• 解决问题往往需要消耗芯片的计算能力，这通常称作时间开销，另外解决问题还需要消耗内存，称作空间开销。
• 不是所有可以计算的问题都可以被解决，问题如果不能在多项式时间内找到答案，我们记为 NP 问题。

人工智能

• 包括停机问题、包括 NP 问题在内的很多问题，虽然不能解决，但可以努力让计算机的解决方案 超过人类的水平，这就是人工智能。
• 广义的 AI 还没有出现，现在出现的是在某个专业领域的 AI

图灵机 (理论 并没有被实现)

程序执行的原理：  第一，它清楚地定义了计算机能力的边界，也就是可计算理论； 第二，它定义了计算机由哪些部分组成，程序又是如何执行的。

1.图灵机拥有一条无限长的纸带，纸带上是一个格子挨着一个格子，格子中可以写字符，你可以把纸 带看作内存，而这些字符可以看作是内存中的数据或者程序。
2. 图灵机有一个读写头，读写头可以读取任意格子上的字符，也可以改写任意格子的字符。
3.读写头上面的盒子里是一些精密的零件，包括图灵机的存储、控制单元和运算单元。

• 图灵机如何执行程序：
  
  

冯诺依曼模型

约定了用二进制进行计算和存储，并且将计算机结构分成以下 5 个部分： 输入设备、输出设备、内存、中央处理器CPU、总线。

• 内存： 程序和数据被存储在一个被称作内存的线性排列存储区域。存储的数据单位是一个 二进制位，英文是 bit。最小的存储单位叫作字节，也就是 8 位，英文是 byte，每一个字节都对应一个 内存地址。内存地址由 0 开始编号. 内存都是随机存取器，也就是读取任何一个地址数据的速度是一样的，写入任何一个地址 数据的速度也是一样的。所有的数据都得要加载到内存中 才能够被CPU读取。 通常内存越大 系统越快， 因为系统都不用尝尝释放一些内存内部的数据。
• CPU:负责控制和计算。为了方便计算较大的数值，CPU 每次可以计算多个字节的数 据。
  如果 CPU 每次可以计算 4 个 byte，那么我们称作 32 位 CPU； 如果 CPU 每次可以计算 8 个 byte，那么我们称作 64 位 CPU。 这里的 32 和 64，称作 CPU 的位宽。因为一个 byte 最大的表示范围就是 0~255,32 位 CPU 能计算的最大整 数是 4294967295 (2³²)
• 控制单元和逻辑运算单元 CPU 中有一个控制单元专门负责控制 CPU 工作；还有逻辑运算单元专门负责计算。
• 寄存器: 寄存器就在 CPU 里，控制单元和逻辑运算单元非常近，因此速度很快。、

1. 通用寄存器:可给用户使用的，例如存放参数。
2. 特殊寄存器:特殊用途 ， 比如程序指针，就是一个特殊寄存器。它存储 了 CPU 要执行的下一条指令所在的内存地址。
3. 指令寄存器：指令被执行完成之前，指令都存储在这里

• 总线：用于CPU 、内存 和 其他设备连接,也需要通信.

1. 地址总线，专门用来指定 CPU 将要操作的内存地址。
2. 数据总线，用来读写内存中的数据。当 CPU 需要读写内存的时候，先要通过地址总线来指定内存地址，再通过数据总线来传输数据.
3. 控制总线:用来发送和接收关键信号.

• 输入、输出设备
  输入设备向计算机输入数据，计算机经过计算，将结果通过输出设备向外界传达。
• 线路位宽问题：数据通过线路传递 ， 通过操作电压 ， 低电压 0 ， 高电压 1，一个 bit 一个 bit 发送的方式，我们叫作串行。如果希望每次多传一些数据，就需要增加线路，也就 是需要并行 。
• 如果操作 4G 的内 存，那么就需要 32 条线，因为 2³² 是 4G。
• 64 位和 32 位的计算 ： 32 位宽的 CPU 最多操作 2³² 个内存地址，也就是 4G 内存地址。
• 64 位的 CPU 内部的逻辑计算单元 ，支持64位的数字计算 ，如果是32位，则需要通过算法 。32 位宽 CPU 最多操作 32 位宽的地址总线和数据总线

程序执行的过程

• 1.首先 CPU 读取 PC 指针指向的指令，将它导入指令寄存器。
  步骤 1：CPU 的控制单元操作地址总线指定需要访问的内存地址（简单理解，就是把 PC 指针中的值拷 贝到地址总线中）。
  步骤 2：CPU 通知内存设备准备数据（内存设备准备好了，就通过数据总线将数据传送给 CPU）。
  步骤 3：CPU 收到内存传来的数据后，将这个数据存入指令寄存器。
• 2.然后CPU 分析指令寄存器中的指令，确定指令的类型和参数。
• 3.如果是计算类型的指令，那么就交给逻辑运算单元计算；如果是存储类型的指令，那么由控制单元执 行。
• 4.PC 指针自增，并准备获取下一条指令。 比如在 32 位的机器上，指令是 32 位 4 个字节，需要 4 个内存地址存储，因此 PC 指针会自增 4。

过程注意

• 内存虽然是一个随机存取器，但是我们通常不会把指令和数据存在一起，这是为了安全起见。
• 程序指针也是一个寄存器， 64位CPU会提供 64位的寄存器，这样就可以使用更多内存地址，但是也会受到地址总线条数的限制，地址总线只有 40 条，那么可以寻址的范围就只有 1T，也就是 2⁴⁰。
• 从 PC 指针读取指令、到执行、再到下一条指令，构成了一个循环，这个不断循环的过程叫作CPU 的指令周期

a = 11 + 15 的执行过程

• 程序员写的程序a=11+15是字符串，CPU 不能执行字符串，只能执行指令，因此需要编译器，编译器的核心能力是翻译，它把一种程序翻译成另 一种程序语言。、
  

• 编译器通过分析，发现 11 和 15 是数据，因此编译好的程序启动时，会在内存中开辟出一个专门的区 域存这样的常数，这个专门用来存储常数的区域，就是数据段.

• 正文段 ： 将数据分别导入 R0 和 R1 寄存器 然后相加得到的数值 导入寄存器R2，store 指令将寄存器 R2 中的值存回数据区域中的 0x1108 位置。PC 指针先指向 0x200 位置，然后依次执行这 4 条指令

• 变量a实际再内存中是一个地址 ，助记符号。

指令

• 最左边的 6 位，叫作操作码，英文是 OpCode，100011 代表 load 指令；
• 中间的 4 位 0000是寄存器的编号，这里代表寄存器 R0；
• 后面的 22 位代表要读取的地址，也就是 0x100。
• 构造指令的过程，叫作指令的编码，通常由编译器完成；解析指令的过程，叫作指令的解码，由 CPU 完 成。由此可见 CPU 内部有一个循环（CPU 的指令周期）：

1. 首先 CPU 通过 PC 指针读取对应内存地址的指令，我们将这个步骤叫作 Fetch，就是获取的意思。
2. CPU 对指令进行解码，我们将这个部分叫作 Decode。
3. CPU 执行指令，我们将这个部分叫作 Execution。
4. CPU 将结果存回寄存器或者将寄存器存入内存，我们将这个步骤叫作 Store。 然后继续执行步骤1。

指令的类型

• 三种参数类型:寄存器、内存地址 、 数值(整数or 浮点),他们都是数字

• 指令从功能划分: I/O类型 、 计算类型 （最多处理俩个寄存器）、跳转类型（修改PC指针）、信号类型、闲置CPu的指令nop ， 执行后 CPU 会空转一个周期。

• 指令还有一个分法，就是寻址模式。

• 求和版本 ：add 俩个寄存器 、 add 寄存器 + 一个数值

• 同样是加载内存中的数据到寄存器的 load 指令: 直接加载一个内存地址 到寄存器 ， 称为直接寻址， 直接将 一个数值导入寄存器 ，寄存器寻址 ， 将一个寄存器的数值作为地址 再去加载这个地址，称为间接寻址

• 因此寻址模式是从指令如何获取数据的角度，对指令的一种分类，目的是给编写指令的人更多选择

• 指令的执行速度 : CPU 是用石英晶体产生的脉冲转化为时钟信号驱动的，每一次时钟信号高低电平的转换 就是一个周期，我们称为时钟周期。CPU 的主频，说的就是时钟信号的频率， 通常指令都需要 多个指令才可以进行完成的。

相比 32 位，64 位的优势是什么?

分类讨论

• 对于 CPU ，64位可以执行更大数字的运算 ， 64位CPU 可以寻址更大的内存空间.
• 对于程序 : 32 位指令在 64 位机器上执 行，困难不大，可以兼容。 如果是 64 位指令，在 32 位机器上执行就困难了。因为 32 位指令在 64 位机器执行的时候，需要的是一套兼容机制；但是 64 位指令在 32 位机器上执行，32 位的寄存 器都存不下指令的参数。
• 操作系统也是一种程序，如果是 64 位操作系统，也就是操作系统中程序的指令都是 64 位指令， 因此不能安装在 32 位机器上.

构造复杂程序

for 循环底层

求和1 ~100

// 指令设计者 设置了 jump指令 可以在程序之间进行跳转
loop : // 标签
jumo loop

• 上面我写指令的时候用到了 add/store 这些指令，它们叫作助记符，是帮助你记忆的。整体这段程序，我们就称作汇编程序.
• 不同CPU指令集不同， 现在使用比较多的是 RISC（精简指令集）和 CISC（复杂指令集）.

条件控制程序

• if - else 自上向下的执行逻辑 ， switch - case 精准匹配算法 switch-case 实现更多是依赖数学关系 . 如果有1000个case ， if最坏是999次

函数

对俩个数进行求和操作

关于参数的传递和 返回值传递给调用者 就需要栈这么一个数据结构

• 栈指针（Stack Pointer， SP）指向栈顶 （也就是下一个可以写入的位置）。每次将数据写入栈时，就把数据写到栈指针指向的位置，然后将 SP 的值增加 (32位自增4，64位自增8),SP 指向 0x100 位置，而 0x100 位置还没有数据.

计算俩个数的和 
jump add
SP ++ 
load $(SP - 12) -> R0 
load $(SP - 8) -> R1
load R0 R1 R2
store R2 -> $(SP-4)

• 但是存在一个问题 ， 就是没有存储PC指针的值，没办法跳转回去。
• 栈不可以被无限使用，11和 15 作为参数，计算出了结果 26，那么它们就可以清空了。
  
  

class 实现

• class 会分成两个部分，一部分是数据（也称作属性），另一部分是函数（也称 作方法）。构造函数会为class分配内存。执行：1. 首先把返回值和返回地址压栈； 2. 然后压栈参数； 3. 最后执行跳转。 class 会用到this 指针，为函数的第一个参数压栈。

存储器分级策略

寄存器（Register）

寄存器紧挨着 CPU 的控制单元和逻辑计算单元。数量通常在几十到几百之间，32 位 CPU 中大多数寄存器可以存储 4 个字节； 64 位 CPU 中大多数寄存器可以存储 8 个字节。寄存机的访问速度非常快，一般要求在半个 CPU 时钟周期内完成读写

存储器分级

一般情况下存储器分为寄存器，l1 cache，l2 cache, l3 cache ，内存，SSD/磁盘。从左到右，距离CPU逐渐变远，读取速度逐渐减低，空间逐渐增大。
L1 cache（2 ~4 cpu时钟周期），l2 cache(10 - 20cpu时钟周期）, l3 cache（20 - 60cpu时钟周期）

内存

内存的主要材料是半导体硅，是插在主板上工作的。因为它的位置距离 CPU 有一段距离，所以需要用总 线和 CPU 连接,内存速度大概在 200~300 个 CPU 周期之间

SSD 和硬盘

SSD 也叫固态硬盘，结构和内存类似，但是它的优点在于断电后数据还在。内存、寄存器、缓存断电后数据就消失了。内存的读写速度比 SSD 大概快 10~1000 倍

寄存器分级的查询顺序

当 CPU 需要内存中某个数据的时候，如果寄存器中有这个数据，我们可以直接使用；如果寄存器中没有 这个数据，我们就要先查询 L1 缓存；L1 中没有，再查询 L2 缓存；L2 中没有再查询 L3 缓存；L3 中没 有，再去内存中拿。

缓存条目

缓存可以看作是双列结构，分别存储着内存地址和对应的值。想要快速的定位缓存条目可以通过对内存地址的编号进行取余(类似hash算法)快速定位缓存条目位置。

• 指令预读: 通过对于指令的预读，使得读取指令的速度跟的上指令的执行速度。减少指令从内存中的读取次数(更耗时)，其实就是批处理。
• 缓存的命中: l1的缓存命中率约为80%，l1 l2 l3缓存加在一块命中率高达95%。
• 缓存置换: 当缓存满了之后，再读取数据到缓存将置换掉之前的缓存。

SSD、内存和 L1 Cache 相比速度差多少倍？

• 内存比 SSD 快 10~1000 倍，L1 Cache 比内存快 100 倍左右。因此 L1 Cache 比 SSD 快 了 1000~100000 倍。所以你有没有发现 SSD 的潜力很大，好的 SSD 已经接近内存了，只不过造价还略高。

练习题详解

可不可以构造一段程序证明停机问题无解?如果可以，请用自己熟悉的语言写出这段程序。

设存在一个函数 willStop，它只有一个参数 func，willStop 可以判断任意函数 func 是否会停止
会停止返回true 
func willStop(func){ 
	//...
}


function wrappedWillStop() { 
	if( willStop(wrappedWillStop) ) {
	 while(true){} // 如果函数会停机  则执行死循环
	 //willStop这样的函数肯定是无法被实现的；也就是停机问题无解
	} else {
	 return
	}
}

wrappedWillStop()  //调用函数

CPU 中有没有求对数的指令？如果没有那么程序如何去计算？

CPU 没有提供很复杂的指令，但是这里有很多算法可以降低我们的时间开销,可以利用指数对数逆运算

1 位的 CPU 能操作多大的内存空间？

• 无限大。 比如说，地址总线 40 位，说明 CPU 上有 40 个引脚接了地址总线。CPU 只有 1 位，因此操作这 40 个 引脚可以分成 40 步。每次设置 1 根引脚的电平是 0 还是 1。所以本身 CPU 多少位和能操作多少位地址 总线，没有本质联系。但是如果需要分步操作，效率会低，需要多次操作，不如一次完成来得划算。 因 此我们今天的设计通常不拿 32 位 CPU 操作 40 位地址总线，而是用 64 位 CPU 操作。

构造复杂的程序 : 将一个递归函数转成非递归函数的通用方法?

• 其实这道题目等同于递归的函数如何非递归表达？改写斐波那契数列第 N 项目。
  实现链接

假设有一个二维数组，总共有 1M 个条目，如果我们要遍历这个二维数组，应该逐行遍历还是 逐列遍历？

• 二维数组本质还是 1 维数组。只不过进行了脚标运算。比如说一个 N 行 M 列的数组，第 y 行 第 x 列的坐标是： x + y*M。因此当行坐标增加时，内存空间是跳跃的。列坐标增加时，内存空间是连 续的。
• 当 CPU 遍历二维数组的时候，会先从 CPU 缓存中取数据。
  关键因素在于现在的 CPU 设计不是每次读取一个内存地址，而是读取每次读取相邻的多个内存地址（内 存速度 200～300 CPU 周期，预读提升效率）
• 另一方面当读取内存地址跳跃较大的时候，会触发内存的页面置换。