Crash Course Computer Science 学习笔记
0 Preview
Carrie Anne Philbin 是个好老师。（树莓派基金会教育总监）
1 Early Computing
1.1 早期计算设备
- 算盘（abacus）。
- 星盘（astrolabe），可计算船只在海上的经纬度。
- 计算尺（slide rule），数学运算辅助工具。
- 各种时钟。
1.2 计算机发展史
“At each increase of knowledge, as well as on the contrivance of every new tool, human labour becomes abridged.” —— Charles Babbage
-
查尔斯·巴贝奇（Charles Babbage）是一个需要被铭记的计算机先驱和天才。
-
计算机最早是一种职业，就是算数的。
“I have read the truest computer of times, and the best arithmetician that ever breathed, and he reduceth thy dayes into a short number” —— Richard Braithwait, 1613.
-
莱布尼茨乘法器（Stepped Reckoner），一种类似于计算器的设备，通过齿轮运转。
“… it is beneath the dignity of excellent men to waste their time in calculation when any peasant could do the work just as accurately with the aid of a machine.” —— Leibniz
-
预计算表（Pre-Computed Table），就是一堆预先计算好的结果，像字典一样，可以查询。典型应用：射程表。
-
差分机（https://en.wikipedia.org/wiki/Difference_engine），由查尔斯·巴贝奇研发的自动化数学机器，可计算多项式、近似对数、三角函数，可储存结果，还可以输出结果。
-
分析机（Analytical Engine），由查尔斯·巴贝奇设计的一种机械式通用计算机，包含了数学逻辑单元、控制流程、条件分支、循环、内置缓存，还可以获取输入输出，已达到图灵完备级别。
-
埃达·洛夫莱斯（Ada Lovelace）为差分机编写了假想程序。
“A new, a vast, and a powerful language is developed for the future use of analysis.” —— Ada Lovelace
-
19世纪末，计算设备被用于科学和工程领域，但未触及商业。直到1890年左右的美国人口普查，数据太多而无法通过人力计算按时完成。政府找到赫尔曼·何乐礼（Herman Hollerith），发明了打孔卡片制表机（Tabulation Machine）。他随后建立表机器公司（Tabulating Machine Company），这家公司后来于1924年与其它机械制造商合并，成为了国际商业机器股份有限公司（IBM）。
2 Electronic Computing
2.1 电子机械计算机
-
哈佛马克1号（https://en.wikipedia.org/wiki/Harvard_Mark_I），用于同盟国。
-
继电器（Relay）：电控机械开关。【注：这里指的是电磁继电器】
- 继电器中有一根控制线（control wire），决定电路的开或关。
- 控制线（control wire）连接着继电器里的线圈。
- 给控制线（control wire）通电，电流流过线圈，产生磁场，吸引电路闭合。
- 不通电，在弹簧作品下，电路断开。
参考 -
继电器可以连接其他电路或齿轮，完成计算任务。
-
继电器有质量，所以不能快速打开或关闭。
-
机械结构易损坏。
-
又大又热吸引昆虫。1947年9月，操作员从故障继电器上取出一只死蛾子。（Bug的由来）
“From then on, when anything went wrong with a computer, we said it had bugs in it.” —— Grace Hopper
2.2 电子计算机
电子元器件的知识本不复杂，但是由于其自身发展的历史原因，名称前后复用，虽然材料、制作等已经完全不同了，容易引起混乱。简而言之，现在去搜索到的N极管，基本都是指晶体管，也就是硅元素物质，虽然叫“管”，但是既没有玻璃，也不是管状，英文名称可以很好区分，中文名有点乱。早期的N极管，是真空管，有玻璃也是管状。
-
巨人1号（Colossus Mk 1）是第一个大规模使用真空管的计算机。
-
- 晶体管也有二极管，三极管，与上文的功能相同，材料不同。
- 晶体管虽然叫“管”，但其实不是管状，也没有玻璃，是由掺杂的硅做的。
- 二级晶体管，又简称二极管，也叫PN结。
-
三极晶体管，又简称三极管，也叫双极性晶体管。
-
可以看作两个二极管的组合。
-
有两个电极（electrode），C极和E极，和一个控制线（control wire）。
-
控制线（control wire）连接门电极（gate electrode），即B极。B极不给电流，不通电，电流越大，通过的电流也越大，有放大功能。
-
- 晶体管比真空管效率高，不易坏，还可以做得很小。
3 Boolean Logic & Logic Gates
3.1 逻辑门：
-
NOT（三角符号）
-
AND（D型符号）
-
OR（飞船符号）
-
XOR（异或）（飞船 + 笑脸符号）
xor
3.2 用晶体管表示逻辑门
-
NOT Gate
not_gate -
AND gate
and_gate -
OR Gate
or_gate
4 Representing Numbers and Letters with Binary
5 How Computers Calculate - the ALU
5.1 ALU——Arithmetic & Logic Unit
5.2 Arithmetic Part
-
算术部分（Arithmetic Part）：执行数学操作
-
异或——>半加法器——>全加法器（一层一层的封装与抽象）
XOR–>Half_Adder–>Full_Adder -
8位加法器
8-bits_adder -
减法：将减数取反，再 + 1，再与被减数相加。
- 举例：
- 5 - 1 = 4；
- 5 -> 101；
- 1-> 001；
- 1 取反 -> 110；
- 取反 + 1 -> 111；
- 101 + 111 -> (1)100；
- 举例：
-
上述的加法器，叫行波加法器。优点是直观简单，缺点是速度慢，因为进位（Carry）需要一层层计算，最后才能确定。
-
现在高级的设备用的是超前进位加法器（Carry-Look-Ahead-Adder），基本原理是进位（Carry）其实在两个加数已知的情况下，可以直接得出，不需要等一级一级的计算结果。
- ALU可以做这些事
- 低端ALU不能直接乘或者除，没有专门的电路来处理。
5.3 Logic Part
-
逻辑部分（Logic Unit）：执行逻辑操作，以及简单数值测试
check_0 -
ALU的抽象
alu_abstraction
6 Registers and RAM
6.1 存储输入的值
-
关键：把输出作为输入返回。
-
一个只能存储0的电路
store_0 -
一个只能储存1的电路
store_1 -
与或锁（add-or latch）：可以写入（Set）或者重置（Reset）。
add-or_latch -
门锁（gated latch）：有一个输入与一个控制。控制打开保存输入，控制关闭保留之前的输入。
gated_latch -
记录一下自己画的过程留作纪念
process -
这里缺少了读取的电路，补充一下。这里画的逻辑没问题，但是实际中，输入输出数据线复用了一条，这个软件我不知道如何操作才能实现这样的效果
write_and_read_datar 参考
6.2 寄存器（Register）
-
一组门锁（gated latch）组成寄存器（register），门锁数量叫做位宽。
-
8位寄存器
-
把8个门锁（gated latch）并排放置，用一根线连接所有的控制线。
-
打开控制线，输入8位的数字。
-
关闭控制线，数据已存储。
8-bit_register
-
6.3 内存
6.3.1 内存布局
-
并排放置不可取，在门锁多的情况下线太多，太占空间，而且不能精准的操作某一个存储单元。
-
使用网格矩阵。
16_latch_matrix -
这张网格矩阵的单元放大图值得好好看，看不懂没法理解为什么16X16需要35根线。
写数据
读数据 -
详解：
- 网格矩阵形成了一个二维坐标系，任何一点（即那个单个的存储单元），如果需要被定位到，需要X轴的线，和Y轴的线，同时被激活。
- 也是这16+16=32根线，组成了门锁矩阵。把这两根线，称为定位线 / 寻址线。
- 把这两根线，用与（AND）门连接，那么只有同时为1，最终结果才会为1，这个与（AND）之后的线，我们称为激活线（自己造的名字）。
- 在寄存器部分。我们已经知道，一个存储单元需要一个控制线，一个数据线才能写入+储存数据，这里还要加一个读取线，用来读数据。那么就是写入控制线，读取控制线，数据传输线，一共3条线。
- 并排放置的话，写入控制线，读取控制线，共用一个的情况，一次可以操作一排存储单元，如果要操作单个，就需要更多的线。
- 现在变成了网格矩阵，那么把之前的激活线与写入控制线，读取控制线，数据传输线各自用与（AND）门连接，如图所示，三条线即可以共用。因为激活线每次只会激活一个存储单元，其他的存储单元的激活线是0，与三条线与（AND）结果还是0，不影响。
- 所以一共需要16(X轴定位线) + 16(Y轴定位线) + 1(写入控制线) + 1(读取控制线) + 1(数据传输线) = 35 根线。
6.3.2 静态随机存取器（Static Random Access Memory - SRAM）
-
多路复用器（Multiplexer）：
-
我们现在学习的内存，是16 X 16 = 256 bits，那么经纬度地址就是0 - 15，可以用一个4位2进制数表示。
-
多路复用器，可以让我们用一个4位2进制数表示10进制的0 - 15，即找到我们需要的存储单元。
multiplexer
-
-
把多路复用器（Multiplexer）与存储单元结合到一起，再抽象起来，变成一块完整的大存储单元（一个存储单元可以存1比特，这个整合到一起的可以存256比特，即32字节）。
32-bytes_memory -
把8个大存储单元并列起来，每次给8个大存储单元相同的地址，就可以储存8比特，即1字节，一共可以存储256字节。
256-bytes_memory -
再把并列起来的大存储单元抽象，看作一个整体，称为内存（SRAM）。
SRAM
6.3.3 一个问题探究
一个问题：我们已经知道了内存的原理，并且把数据存放在内存。那么有一个问题，CPU如何知道我们需要的值，在内存的哪里？换言之，如果我们计算 2 + 3 = 5，然后我们现在需要5，并把5存在内存里，CPU怎么知道哪个地址的值，就是我们需要的5？
答案：CPU并不知道，是我们的程序告诉它的。
详解：这个问题之所以困扰我很久（几小时）的原因，是我在学习硬件的时候，忽略了软件的存在。CPU等硬件是很呆的，它本身不知道自己要干嘛，它不会自己去计算 2 + 3 的，是我们写的软件告诉它这么做的。
图解：
- 在真实程序中，程序并不会像图里一样，与CPU你来我往，而是把所有指令按顺序发给CPU，称为指令集。所以，变量与地址的维护，是由程序完成的，CPU只负责接命令干活，这也是为什么各个视频教程里，讲到CPU与内存的时候，都是从地址出发，因为CPU实际上已经拿到地址了
- 程序对变量与地址的维护，就是另一个话题了，实质是程序对内存的管理，例如Java中的内存模型，是对内存的抽象。
7 The Central Processing Unit (CPU)
7.1 把这两个视频结合到一起看，就会很清晰：
7.2 CPU 组成：控制单元（Control Unit）+ 运算单元（Arithmetic Unit）
7.2.1 控制单元（Control Unit）：
- 操作控制器（Operation Controller）
- 时序产生器（Timing Generator）
- 程序计数器（Program Counter）
- 地址寄存器（Instruction Address Register）
- 指令译码器（Instruction Decoder）
- 指令寄存器（Instruction Register）
- 等等等等
7.2.2 运算单元（Arithmetic Unit）：
- 运算逻辑单元（ALU）
- 寄存器（Register） / 数据寄存器 / 缓冲寄存器（Data Register）
- 累加器（Accumulator）
- 状态寄存器（Status Register）
- 等等等等
7.2.3 CPU工作步骤：
-
指令由两部分组成：指令码（表示这条指令要干啥） + 操作数（要操作的数字或地址，可没有）。
-
获取阶段（Fetch Phase）
- 程序计数器（Program Counter）把指令地址给地址寄存器（Instruction Address Register）。
- 地址寄存器（Instruction Address Register）去内存（其实不一定就是内存，方便理解不展开）中取到这条指令（Instruction），交给指令寄存器（Instruction Register）。
- 指令寄存器（Instruction Register）把指令交给指令译码器（Instruction Decoder）。
-
解析阶段（Decode Phase）
- 指令译码器（Instruction Decoder）解析指令，其实是与CPU指令集比对。
-
执行阶段（Execute Phase）
-
假设这条指令的操作数是一个地址，那么指令译码器（Instruction Decoder）会把地址交给地址寄存器（Instruction Address Register）。
-
地址寄存器（Instruction Address Register）去内存取到数据，交给寄存器（Register） / 数据寄存器 / 缓冲寄存器（Data Register）。
-
流程结束，地址寄存器（Instruction Address Register）+1。
-
-
重复获取阶段（Fetch Phase）
-
重复解析阶段（Decode Phase）：指令为+1操作。
-
重复执行阶段（Execute Phase）
-
寄存器（Register）把数据给运算逻辑单元（ALU）。
-
操作控制器（Operation Controller）发出一个+1操作信号给运算逻辑单元（ALU）。
-
ALU +1 之后，把结果放到累加器（Accumulator）。
注：累加器（Accumulator）实质也是一个寄存器（Register），所以Carrie Anne的视频里，用寄存器A、B来将流程也没毛病。
-
-
流程结束，地址寄存器（Instruction Address Register）+1。
7.2.4 再来看这个架构图就会很清晰了。
8 Instructions & Programs
8.1 指令集实质是对电路计算的提升与抽象，程序实质是对指令集的提升与抽象。
8.2 几个信概念：
- 指令长度（Instruction Length）
- 可变长度指令（Variable Length Instruction）
- 立即值（Immediate Value）
8.3 Intel 4004 指令集
9 Advanced CPU Designs
9.1 提升CPU性能的若干方式
- 早期：提升晶体管（transistor）质量。
- 增加额外电路组成，用来处理常规指令集需要长时间处理的内容，例如图形、视频编码解码、加密解密等。
- 增加额外指令集，同时保留过去的指令集，用于向下兼容性（Backwards Compatibility）。
- 增加高速缓存（Cache）。
- 缓存命中（Cache Hit）。
- 缓存未击中（Cache Miss）。
- 缓存一致性问题：每一个缓存存储单元有一个脏位（Dirty Bit），用来标记是否需要同步缓存与内存数据。
- 指令流水线（Instruction Pipelining）：实质就是并行（parallelize）处理几个指令。
- 指令之间的互相依赖问题。
- 低端处理器：根据下一条指令判断是否暂停流水线（Pipeline Stall）。
- 高端处理器：乱序执行（out-of-order execution）——根据依赖动态重排序指令顺序。
- 条件指令（Conditional） / 跳跃指令（Jump）
- 低端处理器：暂停流水线（Pipeline Stall）等待最终结果。
- 高端处理器：
- 分析预测（Branch Predicting）——预测后续的指令执行。
- 推测执行（Speculative Execution）——直接分析预测（Branch Predicting）中预测的路径，再根据最终结果调整，是否需要流水线冲洗（Pipeline Flush）。
- 指令之间的互相依赖问题。
- 超标量（Superscalar）
- 多核CPU