基础篇

计算机的基本硬件组成

image.png

第一,广。组成原理中的概念非常多,每个概念的信息量也非常大。比如想要理解 CPU 中的算术逻辑单元(也就是 ALU)是怎么实现加法的,需要牵涉到如何把整数表示成二进制,还需要了解这些表示背后的电路、逻辑门、CPU 时钟、触发器等知识。

第二,深。组成原理中的很多概念,阐述开来就是计算机学科的另外一门核心课程。比如,计算机的指令是怎么从你写的 C、Java 这样的高级语言,变成计算机可以执行的机器码的?如果我们展开并深入讲解这个问题,就会变成《编译原理》这样一门核心课程。

第三,学不能致用。学东西是要拿来用的,但因为这门课本身的属性,很多人在学习时,常常沉溺于概念和理论中,无法和自己日常的开发工作联系起来,以此来解决工作中遇到的问题,所以,学习往往没有成就感,就很难有动力坚持下去。

早年,要自己组装一台计算机,要先有三大件,CPU、内存和主板。

在这三大件中,我们首先要说的是 CPU,它是计算机最重要的核心配件,全名你肯定知道,叫中央处理器(Central Processing Unit)。为什么说 CPU 是“最重要”的呢?因为计算机的所有“计算”都是由 CPU 来进行的。自然,CPU 也是整台计算机中造价最昂贵的部分之一。

第二个重要的配件,就是内存(Memory)。你撰写的程序、打开的浏览器、运行的游戏,都要加载到内存里才能运行。程序读取的数据、计算得到的结果,也都要放在内存里。内存越大,能加载的东西自然也就越多。

存放在内存里的程序和数据,需要被 CPU 读取,CPU 计算完之后,还要把数据写回到内存。然而 CPU 不能直接插到内存上,反之亦然。于是,就带来了最后一个大件——主板(Motherboard)。

主板是一个有着各种各样,有时候多达数十乃至上百个插槽的配件。我们的 CPU 要插在主板上,内存也要插在主板上。主板的芯片组(Chipset)和总线(Bus)解决了 CPU 和内存之间如何通信的问题。芯片组控制了数据传输的流转,也就是数据从哪里到哪里的问题。总线则是实际数据传输的高速公路。因此,总线速度(Bus Speed)决定了数据能传输得多快。

有了三大件,只要配上电源供电,计算机差不多就可以跑起来了。但是现在还缺少各类输入(Input)/ 输出(Output)设备,也就是我们常说的 I/O 设备。如果你用的是自己的个人电脑,那显示器肯定必不可少,只有有了显示器我们才能看到计算机输出的各种图像、文字,这也就是所谓的输出设备。

同样的,鼠标和键盘也都是必不可少的配件。这样我才能输入文本,写下这篇文章。它们也就是所谓的输入设备。

还有一个很特殊的设备,就是显卡(Graphics Card)。现在,使用图形界面操作系统的计算机,无论是 Windows、Mac OS 还是 Linux,显卡都是必不可少的。有人可能要说了,我装机的时候没有买显卡,计算机一样可以正常跑起来啊!那是因为,现在的主板都带了内置的显卡。如果你用计算机玩游戏,做图形渲染或者跑深度学习应用,你多半就需要买一张单独的显卡,插在主板上。显卡之所以特殊,是因为显卡里有除了 CPU 之外的另一个“处理器”,也就是 GPU(Graphics Processing Unit,图形处理器),GPU 一样可以做各种“计算”的工作。

鼠标、键盘以及硬盘,这些都是插在主板上的。作为外部 I/O 设备,它们是通过主板上的南桥(SouthBridge)芯片组,来控制和 CPU 之间的通信的。“南桥”芯片的名字很直观,一方面,它在主板上的位置,通常在主板的“南面”。另一方面,它的作用就是作为“桥”,来连接鼠标、键盘以及硬盘这些外部设备和 CPU 之间的通信。

有了南桥,自然对应着也有“北桥”。是的,以前的主板上通常也有“北桥”芯片,用来作为“桥”,连接 CPU 和内存、显卡之间的通信。不过,随着时间的变迁,现在的主板上的“北桥”芯片的工作,已经被移到了 CPU 的内部,所以你在主板上,已经看不到北桥芯片了。

冯·诺依曼体系结构

我们手机里只有 SD 卡(Secure Digital Memory Card)这样类似硬盘功能的存储卡插槽,并没有内存插槽、CPU 插槽这些东西。没错,因为手机尺寸的原因,手机制造商们选择把 CPU、内存、网络通信,乃至摄像头芯片,都封装到一个芯片,然后再嵌入到手机主板上。这种方式叫 SoC,也就是 System on a Chip(系统芯片)。

而所有的计算机程序,也都可以抽象为从输入设备读取输入信息,通过运算器和控制器来执行存储在存储器里的程序,最终把结果输出到输出设备中。而我们所有撰写的无论高级还是低级语言的程序,也都是基于这样一个抽象框架来进行运作的。

image.png

  • 图灵机是一种思想模型(计算机的基本理论基础),是一种有穷的、构造性的问题的问题求解思路,图灵认为凡是能用算法解决的问题也一定能用图灵机解决;
  • 冯诺依曼提出了“存储程序”的计算机设计思想,并“参照”图灵模型设计了历史上第一台电子计算机,即冯诺依曼机。

计算机组成原理知识地图

image.png

CPU

什么是性能?时间的倒数

计算机的性能,其实和我们干体力劳动很像,好比是我们要搬东西。对于计算机的性能,我们需要有个标准来衡量。这个标准中主要有两个指标。

第一个是响应时间(Response time)或者叫执行时间(Execution time)。想要提升响应时间这个性能指标,你可以理解为让计算机“跑得更快”。

第二个是吞吐率(Throughput)或者带宽(Bandwidth),想要提升这个指标,你可以理解为让计算机“搬得更多”。

过去几年流行的手机跑分软件,就是把多个预设好的程序在手机上运行,然后根据运行需要的时间,算出一个分数来给出手机的性能评估。而在业界,各大 CPU 和服务器厂商组织了一个叫作 SPEC(Standard Performance Evaluation Corporation)的第三方机构,专门用来指定各种“跑分”的规则。

SPEC 提供的 CPU 基准测试程序,就好像 CPU 届的“高考”,通过数十个不同的计算程序,对于 CPU 的性能给出一个最终评分。这些程序丰富多彩,有编译器、解释器、视频压缩、人工智能国际象棋等等,涵盖了方方面面的应用场景。感兴趣的话,你可以点击这个链接看看。

其次,即使我们已经拿到了 CPU 时间,我们也不一定可以直接“比较”出两个程序的性能差异。即使在同一台计算机上,CPU 可能满载运行也可能降频运行,降频运行的时候自然花的时间会多一些。

除了 CPU 之外,时间这个性能指标还会受到主板、内存这些其他相关硬件的影响。所以,我们需要对“时间”这个我们可以感知的指标进行拆解,把程序的 CPU 执行时间变成 CPU 时钟周期数(CPU Cycles)和 时钟周期时间(Clock Cycle)的乘积。

程序的 CPU 执行时间 =CPU 时钟周期数×时钟周期时间

我们先来理解一下什么是时钟周期时间。你在买电脑的时候,一定关注过 CPU 的主频。比如我手头的这台电脑就是 Intel Core-i7-7700HQ 2.8GHz,这里的 2.8GHz 就是电脑的主频(Frequency/Clock Rate)。这个 2.8GHz,我们可以先粗浅地认为,CPU 在 1 秒时间内,可以执行的简单指令的数量是 2.8G 条

2.0GHz意味着每秒钟它会产生20亿个时钟脉冲信号,每个时钟信号周期为0.5纳秒

如果想要更准确一点描述,这个 2.8GHz 就代表,我们 CPU 的一个“钟表”能够识别出来的最小的时间间隔。就像我们挂在墙上的挂钟,都是“滴答滴答”一秒一秒地走,所以通过墙上的挂钟能够识别出来的最小时间单位就是秒。

而在 CPU 内部,和我们平时戴的电子石英表类似,有一个叫晶体振荡器(Oscillator Crystal)的东西,简称为晶振。我们把晶振当成 CPU 内部的电子表来使用。晶振带来的每一次“滴答”,就是时钟周期时间

对于 CPU 时钟周期数,我们可以再做一个分解,把它变成“指令数×每条指令的平均时钟周期数(Cycles Per Instruction,简称 CPI)”。不同的指令需要的 Cycles 是不同的,加法和乘法都对应着一条 CPU 指令但是乘法需要的 Cycles 就比加法要多,自然也就慢。在这样拆分了之后,我们的程序的 CPU 执行时间就可以变成这样三个部分的乘积。

**程序的 CPU 执行时间 = 指令数 × CPI × Clock Cycle Time **

  • Clock Cycle Time 一次晶振时间,时钟周期
  • CPI,每条指令的平均时钟周期数(Cycles Per Instruction,简称 CPI),加法和乘法都对应着一条 CPU 指令,乘法需要的 Cycles 就比加法要多

因此,如果我们想要解决性能问题,其实就是要优化这三者。

  1. 时钟周期时间,就是计算机主频,这个取决于计算机硬件。我们所熟知的摩尔定律就一直在不停地提高我们计算机的主频。比如说,我最早使用的 80386 主频只有 33MHz,现在手头的笔记本电脑就有 2.8GHz,在主频层面,就提升了将近 100 倍。
  2. 每条指令的平均时钟周期数 CPI,就是一条指令到底需要多少 CPU Cycle。在后面讲解 CPU 结构的时候,我们会看到,现代的 CPU 通过流水线技术(Pipeline),让一条指令需要的 CPU Cycle 尽可能地少。因此,对于 CPI 的优化,也是计算机组成和体系结构中的重要一环。
  3. 指令数,代表执行我们的程序到底需要多少条指令、用哪些指令。这个很多时候就把挑战交给了编译器。同样的代码,编译成计算机指令时候,就有各种不同的表示方式。

功耗:CPU 的“人体极限”

于是,从 1978 年 Intel 发布的 8086 CPU 开始,计算机的主频从 5MHz 开始,不断提升。1980 年代中期的 80386 能够跑到 40MHz,1989 年的 486 能够跑到 100MHz,直到 2000 年的奔腾 4 处理器,主频已经到达了 1.4GHz。而消费者也在这 20 年里养成了“看主频”买电脑的习惯。当时已经基本垄断了桌面 CPU 市场的 Intel 更是夸下了海口,表示奔腾 4 所使用的 CPU 结构可以做到 10GHz,颇有一点“大力出奇迹”的意思。

然而,计算机科学界从来不相信“大力出奇迹”。奔腾 4 的 CPU 主频从来没有达到过 10GHz,最终它的主频上限定格在 3.8GHz。这还不是最糟的,更糟糕的事情是,大家发现,奔腾 4 的主频虽然高,但是它的实际性能却配不上同样的主频。想要用在笔记本上的奔腾 4 2.4GHz 处理器,其性能只和基于奔腾 3 架构的奔腾 M 1.6GHz 处理器差不多。

一个 3.8GHz 的奔腾 4 处理器,满载功率是 130 瓦。这个 130 瓦是什么概念呢?机场允许带上飞机的充电宝的容量上限是 100 瓦时。如果我们把这个 CPU 安在手机里面,不考虑屏幕内存之类的耗电,这个 CPU 满载运行 45 分钟,充电宝里面就没电了。而 iPhone X 使用 ARM 架构的 CPU,功率则只有 4.5 瓦左右。

我们的 CPU,一般都被叫作超大规模集成电路(Very-Large-Scale Integration,VLSI)。这些电路,实际上都是一个个晶体管组合而成的。CPU 在计算,其实就是让晶体管里面的“开关”不断地去“打开”和“关闭”,来组合完成各种运算和功能。

想要计算得快,一方面,我们要在 CPU 里,同样的面积里面,多放一些晶体管,也就是增加密度;另一方面,我们要让晶体管“打开”和“关闭”得更快一点,也就是提升主频。而这两者,都会增加功耗,带来耗电和散热的问题。

我们会在 CPU 上面抹硅脂、装风扇,乃至用上水冷或者其他更好的散热设备,就好像在工厂里面装风扇、空调,发冷饮一样。但是同样的空间下,装上风扇空调能够带来的散热效果也是有极限的。

因此,在 CPU 里面,能够放下的晶体管数量和晶体管的“开关”频率也都是有限的。一个 CPU 的功率,可以用这样一个公式来表示:

功耗 ~= 1/2 ×负载电容×电压的平方×开关频率×晶体管数量

  • 增加晶体管可以增加硬件能够支持的指令数量,增加数字通路的位数,以及利用好电路天然的并行性,从硬件层面更快地实现特定的指令,所以增加晶体管也是常见的提升cpu性能的一种手段。
  • 电压的问题在于两个,一个是电压太低就会导致电路无法联通,因为不管用什么作为电路材料,都是有电阻的,所以没有办法无限制降低电压,另外一个是对于工艺的要求也变高了,成本也更贵啊。

那么,为了要提升性能,我们需要不断地增加晶体管数量。同样的面积下,我们想要多放一点晶体管,就要把晶体管造得小一点。这个就是平时我们所说的提升“制程”。从 28nm 到 7nm,相当于晶体管本身变成了原来的 1/4 大小。这个就相当于我们在工厂里,同样的活儿,我们要找瘦小一点的工人,这样一个工厂里面就可以多一些人。我们还要提升主频,让开关的频率变快,也就是要找手脚更快的工人。

但是,功耗增加太多,就会导致 CPU 散热跟不上,这时,我们就需要降低电压。这里有一点非常关键,在整个功耗的公式里面,功耗和电压的平方是成正比的。这意味着电压下降到原来的 1/5,整个的功耗会变成原来的 1/25。

事实上,从 5MHz 主频的 8086 到 5GHz 主频的 Intel i9,CPU 的电压已经从 5V 左右下降到了 1V 左右。这也是为什么我们 CPU 的主频提升了 1000 倍,但是功耗只增长了 40 倍。比如说,我写这篇文章用的是 Surface Go,在这样的轻薄笔记本上,微软就是选择了把电压下降到 0.25V 的低电压 CPU,使得笔记本能有更长的续航时间。

这就引出了我们在进行性能优化中,常常用到的一个经验定律,阿姆达尔定律(Amdahl’s Law)。这个定律说的就是,对于一个程序进行优化之后,处理器并行运算之后效率提升的情况。具体可以用这样一个公式来表示:

优化后的执行时间 = 受优化影响的执行时间 / 加速倍数 + 不受影响的执行时间

在“摩尔定律”和“并行计算”之外,在整个计算机组成层面,还有这样几个原则性的性能提升方法。

  1. 加速大概率事件。最典型的就是,过去几年流行的深度学习,整个计算过程中,99% 都是向量和矩阵计算,于是,工程师们通过用 GPU 替代 CPU,大幅度提升了深度学习的模型训练过程。本来一个 CPU 需要跑几小时甚至几天的程序,GPU 只需要几分钟就好了。Google 更是不满足于 GPU 的性能,进一步地推出了 TPU。后面的文章,我也会为你讲解 GPU 和 TPU 的基本构造和原理。
  2. 通过流水线提高性能。现代的工厂里的生产线叫“流水线”。我们可以把装配 iPhone 这样的任务拆分成一个个细分的任务,让每个人都只需要处理一道工序,最大化整个工厂的生产效率。类似的,我们的 CPU 其实就是一个“运算工厂”。我们把 CPU 指令执行的过程进行拆分,细化运行,也是现代 CPU 在主频没有办法提升那么多的情况下,性能仍然可以得到提升的重要原因之一。我们在后面也会讲到,现代 CPU 里是如何通过流水线来提升性能的,以及反面的,过长的流水线会带来什么新的功耗和效率上的负面影响。
  3. 通过预测提高性能。通过预先猜测下一步该干什么,而不是等上一步运行的结果,提前进行运算,也是让程序跑得更快一点的办法。典型的例子就是在一个循环访问数组的时候,凭经验,你也会猜到下一步我们会访问数组的下一项。后面要讲的“分支和冒险”、“局部性原理”这些 CPU 和存储系统设计方法,其实都是在利用我们对于未来的“预测”,提前进行相应的操作,来提升我们的程序性能。

指令和运算

CPU指令

我们就从平时用的电脑、手机这些设备来说起。这些设备的 CPU 到底有哪些指令呢?这个还真有不少,我们日常用的 Intel CPU,有 2000 条左右的 CPU 指令,实在是太多了,所以我没法一一来给你讲解。不过一般来说,常见的指令可以分成五大类。

第一类是算术类指令。我们的加减乘除,在 CPU 层面,都会变成一条条算术类指令。

第二类是数据传输类指令。给变量赋值、在内存里读写数据,用的都是数据传输类指令。

第三类是逻辑类指令。逻辑上的与或非,都是这一类指令。

第四类是条件分支类指令。日常我们写的“if/else”,其实都是条件分支类指令。

最后一类是无条件跳转指令。写一些大一点的程序,我们常常需要写一些函数或者方法。在调用函数的时候,其实就是发起了一个无条件跳转指令。

你可能一下子记不住,或者对这些指令的含义还不能一下子掌握,这里我画了一个表格,给你举例子说明一下,帮你理解、记忆。

image.png

我们说过,不同的 CPU 有不同的指令集,也就对应着不同的汇编语言和不同的机器码。为了方便你快速理解这个机器码的计算方式,我们选用最简单的 MIPS 指令集,来看看机器码是如何生成的。

MIPS 是一组由 MIPS 技术公司在 80 年代中期设计出来的 CPU 指令集。就在最近,MIPS 公司把整个指令集和芯片架构都完全开源了。想要深入研究 CPU 和指令集的同学,我这里推荐一些资料,你可以自己了解下。

image.png

R 指令是一般用来做算术和逻辑操作,里面有读取和写入数据的寄存器的地址。如果是逻辑位移操作,后面还有位移操作的位移量,而最后的功能码,则是在前面的操作码不够的时候,扩展操作码表示对应的具体指令的。

I 指令,则通常是用在数据传输、条件分支,以及在运算的时候使用的并非变量还是常数的时候。这个时候,没有了位移量和操作码,也没有了第三个寄存器,而是把这三部分直接合并成了一个地址值或者一个常数。

J 指令就是一个跳转指令,高 6 位之外的 26 位都是一个跳转后的地址。

add $t0,$s2,$s1

我以一个简单的加法算术指令 add t0,s1, $s2, 为例,给你解释。为了方便,我们下面都用十进制来表示对应的代码。

对应的 MIPS 指令里 opcode 是 0,rs 代表第一个寄存器 s1 的地址是 17,rt 代表第二个寄存器 s2 的地址是 18,rd 代表目标的临时寄存器 t0 的地址,是 8。因为不是位移操作,所以位移量是 0。把这些数字拼在一起,就变成了一个 MIPS 的加法指令。

为了读起来方便,我们一般把对应的二进制数,用 16 进制表示出来。在这里,也就是 0X02324020。这个数字也就是这条指令对应的机器码。

image.png

回到开头我们说的打孔带。如果我们用打孔代表 1,没有打孔代表 0,用 4 行 8 列代表一条指令来打一个穿孔纸带,那么这条命令大概就长这样:

image.png

image.png

一个 CPU 里面会有很多种不同功能的寄存器。我这里给你介绍三种比较特殊的。

一个是 PC 寄存器(Program Counter Register),我们也叫指令地址寄存器(Instruction Address Register)。顾名思义,它就是用来存放下一条需要执行的计算机指令的内存地址。

第二个是指令寄存器(Instruction Register),用来存放当前正在执行的指令。

第三个是条件码寄存器(Status Register),用里面的一个一个标记位(Flag),存放 CPU 进行算术或者逻辑计算的结果。

除了这些特殊的寄存器,CPU 里面还有更多用来存储数据和内存地址的寄存器。这样的寄存器通常一类里面不止一个。我们通常根据存放的数据内容来给它们取名字,比如整数寄存器、浮点数寄存器、向量寄存器和地址寄存器等等。有些寄存器既可以存放数据,又能存放地址,我们就叫它通用寄存器。

实际上,一个程序执行的时候,CPU 会根据 PC 寄存器里的地址,从内存里面把需要执行的指令读取到指令寄存器里面执行,然后根据指令长度自增,开始顺序读取下一条指令。可以看到,一个程序的一条条指令,在内存里面是连续保存的,也会一条条顺序加载。

$ gcc -g -c test.c
$ objdump -d -M intel -S test.o 

image.png

编译链接

GCC 预处理、编译、汇编、链接.

9EEB42F4-31F5-4A88-8D70-C17B3F0695B2.png

实际上,“C 语言代码 - 汇编代码 - 机器码” 这个过程,在我们的计算机上进行的时候是由两部分组成的。

第一个部分由编译(Compile)、汇编(Assemble)以及链接(Link)三个阶段组成。在这三个阶段完成之后,我们就生成了一个可执行文件。

第二部分,我们通过装载器(Loader)把可执行文件装载(Load)到内存中。CPU 从内存中读取指令和数据,来开始真正执行程序。

image.png

你会发现,可执行代码 dump 出来内容,和之前的目标代码长得差不多,但是长了很多。因为在 Linux 下,可执行文件和目标文件所使用的都是一种叫 ELF(Execuatable and Linkable File Format)的文件格式,中文名字叫可执行与可链接文件格式,这里面不仅存放了编译成的汇编指令,还保留了很多别的数据。

比如我们过去所有 objdump 出来的代码里,你都可以看到对应的函数名称,像 add、main 等等,乃至你自己定义的全局可以访问的变量名称,都存放在这个 ELF 格式文件里。这些名字和它们对应的地址,在 ELF 文件里面,存储在一个叫作符号表(Symbols Table)的位置里。符号表相当于一个地址簿,把名字和地址关联了起来。

image.png

ELF 文件格式把各种信息,分成一个一个的 Section 保存起来。ELF 有一个基本的文件头(File Header),用来表示这个文件的基本属性,比如是否是可执行文件,对应的 CPU、操作系统等等。除了这些基本属性之外,大部分程序还有这么一些 Section:

  1. 首先是.text Section,也叫作代码段或者指令段(Code Section),用来保存程序的代码和指令;
  2. 接着是.data Section,也叫作数据段(Data Section),用来保存程序里面设置好的初始化数据信息;
  3. 然后就是.rel.text Secion,叫作重定位表(Relocation Table)。重定位表里,保留的是当前的文件里面,哪些跳转地址其实是我们不知道的。比如上面的 link_example.o 里面,我们在 main 函数里面调用了 add 和 printf 这两个函数,但是在链接发生之前,我们并不知道该跳转到哪里,这些信息就会存储在重定位表里;
  4. 最后是.symtab Section,叫作符号表(Symbol Table)。符号表保留了我们所说的当前文件里面定义的函数名称和对应地址的地址簿。

链接器会扫描所有输入的目标文件,然后把所有符号表里的信息收集起来,构成一个全局的符号表。然后再根据重定位表,把所有不确定要跳转地址的代码,根据符号表里面存储的地址,进行一次修正。最后,把所有的目标文件的对应段进行一次合并,变成了最终的可执行代码。这也是为什么,可执行文件里面的函数调用的地址都是正确的。

image.png

链接可以分动、静,共享运行省内存

我们上一节解决程序装载到内存的时候,讲了很多方法。说起来,最根本的问题其实就是内存空间不够用。如果我们能够让同样功能的代码,在不同的程序里面,不需要各占一份内存空间,那该有多好啊!就好比,现在马路上的共享单车,我们并不需要给每个人都造一辆自行车,只要马路上有这些单车,谁需要的时候,直接通过手机扫码,都可以解锁骑行。

这个思路就引入一种新的链接方法,叫作动态链接(Dynamic Link)。相应的,我们之前说的合并代码段的方法,就是静态链接(Static Link)。

在动态链接的过程中,我们想要“链接”的,不是存储在硬盘上的目标文件代码,而是加载到内存中的共享库(Shared Libraries)。顾名思义,这里的共享库重在“共享“这两个字。

这个加载到内存中的共享库会被很多个程序的指令调用到。在 Windows 下,这些共享库文件就是.dll 文件,也就是 Dynamic-Link Libary(DLL,动态链接库)。在 Linux 下,这些共享库文件就是.so 文件,也就是 Shared Object(一般我们也称之为动态链接库)。这两大操作系统下的文件名后缀,一个用了“动态链接”的意思,另一个用了“共享”的意思,正好覆盖了两方面的含义。

image.png

不过,要想要在程序运行的时候共享代码,也有一定的要求,就是这些机器码必须是“地址无关”的。也就是说,我们编译出来的共享库文件的指令代码,是地址无关码(Position-Independent Code)。换句话说就是,这段代码,无论加载在哪个内存地址,都能够正常执行。如果不是这样的代码,就是地址相关的代码。

image.png

对于所有动态链接共享库的程序来讲,虽然我们的共享库用的都是同一段物理内存地址,但是在不同的应用程序里,它所在的虚拟内存地址是不同的。我们没办法、也不应该要求动态链接同一个共享库的不同程序,必须把这个共享库所使用的虚拟内存地址变成一致。如果这样的话,我们写的程序就必须明确地知道内部的内存地址分配。

那么问题来了,我们要怎么样才能做到,动态共享库编译出来的代码指令,都是地址无关码呢?

动态代码库内部的变量和函数调用都很容易解决,我们只需要使用相对地址(Relative Address)就好了。各种指令中使用到的内存地址,给出的不是一个绝对的地址空间,而是一个相对于当前指令偏移量的内存地址。因为整个共享库是放在一段连续的虚拟内存地址中的,无论装载到哪一段地址,不同指令之间的相对地址都是不变的。

PLT 和 GOT,动态链接的解决方案

要实现动态链接共享库,也并不困难,和前面的静态链接里的符号表和重定向表类似,还是和前面一样,我们还是拿出一小段代码来看一看。

首先,lib.h 定义了动态链接库的一个函数 show_me_the_money。

// lib.h
#ifndef LIB_H
#define LIB_H

void show_me_the_money(int money);

#endif

lib.c 包含了 lib.h 的实际实现。

// lib.c
#include <stdio.h>


void show_me_the_money(int money)
{
    printf("Show me USD %d from lib.c \n", money);
}

然后,show_me_poor.c 调用了 lib 里面的函数。

// show_me_poor.c
#include "lib.h"
int main()
{
    int money = 5;
    show_me_the_money(money);
}

最后,我们把 lib.c 编译成了一个动态链接库,也就是 .so 文件。

$ gcc lib.c -fPIC -shared -o lib.so
$ gcc -o show_me_poor show_me_poor.c ./lib.so

你可以看到,在编译的过程中,我们指定了一个 -fPIC 的参数。这个参数其实就是 Position Independent Code 的意思,也就是我们要把这个编译成一个地址无关代码。

然后,我们再通过 gcc 编译 show_me_poor 动态链接了 lib.so 的可执行文件。在这些操作都完成了之后,我们把 show_me_poor 这个文件通过 objdump 出来看一下。

$ objdump -d -M intel -S show_me_poor
    
……
0000000000400540 <show_me_the_money@plt-0x10>:
  400540:       ff 35 12 05 20 00       push   QWORD PTR [rip+0x200512]        # 600a58 <_GLOBAL_OFFSET_TABLE_+0x8>
  400546:       ff 25 14 05 20 00       jmp    QWORD PTR [rip+0x200514]        # 600a60 <_GLOBAL_OFFSET_TABLE_+0x10>
  40054c:       0f 1f 40 00             nop    DWORD PTR [rax+0x0]

0000000000400550 <show_me_the_money@plt>:
  400550:       ff 25 12 05 20 00       jmp    QWORD PTR [rip+0x200512]        # 600a68 <_GLOBAL_OFFSET_TABLE_+0x18>
  400556:       68 00 00 00 00          push   0x0
  40055b:       e9 e0 ff ff ff          jmp    400540 <_init+0x28>
……
0000000000400676 <main>:
  400676:       55                      push   rbp
  400677:       48 89 e5                mov    rbp,rsp
  40067a:       48 83 ec 10             sub    rsp,0x10
  40067e:       c7 45 fc 05 00 00 00    mov    DWORD PTR [rbp-0x4],0x5
  400685:       8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]
  400688:       89 c7                   mov    edi,eax
  40068a:       e8 c1 fe ff ff          call   400550 <show_me_the_money@plt>
  40068f:       c9                      leave  
  400690:       c3                      ret    
  400691:       66 2e 0f 1f 84 00 00    nop    WORD PTR cs:[rax+rax*1+0x0]
  400698:       00 00 00 
  40069b:       0f 1f 44 00 00          nop    DWORD PTR [rax+rax*1+0x0]
……

我们还是只关心整个可执行文件中的一小部分内容。你应该可以看到,在 main 函数调用 show_me_the_money 的函数的时候,对应的代码是这样的:

call   400550 <show_me_the_money@plt>

这里后面有一个 @plt 的关键字,代表了我们需要从 PLT,也就是程序链接表(Procedure Link Table)里面找要调用的函数。对应的地址呢,则是 400550 这个地址。

那当我们把目光挪到上面的 400550 这个地址,你又会看到里面进行了一次跳转,这个跳转指定的跳转地址,你可以在后面的注释里面可以看到,GLOBAL_OFFSET_TABLE+0x18。这里的 GLOBAL_OFFSET_TABLE,就是我接下来要说的全局偏移表。

  400550:       ff 25 12 05 20 00       jmp    QWORD PTR [rip+0x200512]        # 600a68 <_GLOBAL_OFFSET_TABLE_+0x18>
  

在动态链接对应的共享库,我们在共享库的 data section 里面,保存了一张全局偏移表(GOT,Global Offset Table)。虽然共享库的代码部分的物理内存是共享的,但是数据部分是各个动态链接它的应用程序里面各加载一份的。所有需要引用当前共享库外部的地址的指令,都会查询 GOT,来找到当前运行程序的虚拟内存里的对应位置。而 GOT 表里的数据,则是在我们加载一个个共享库的时候写进去的。

不同的进程,调用同样的 lib.so,各自 GOT 里面指向最终加载的动态链接库里面的虚拟内存地址是不同的。

这样,虽然不同的程序调用的同样的动态库,各自的内存地址是独立的,调用的又都是同一个动态库,但是不需要去修改动态库里面的代码所使用的地址,而是各个程序各自维护好自己的 GOT,能够找到对应的动态库就好了。

image.png

我们的 GOT 表位于共享库自己的数据段里。GOT 表在内存里和对应的代码段位置之间的偏移量,始终是确定的。这样,我们的共享库就是地址无关的代码,对应的各个程序只需要在物理内存里面加载同一份代码。而我们又要通过各个可执行程序在加载时,生成的各不相同的 GOT 表,来找到它需要调用到的外部变量和函数的地址。

这是一个典型的、不修改代码,而是通过修改“地址数据”来进行关联的办法。它有点像我们在 C 语言里面用函数指针来调用对应的函数,并不是通过预先已经确定好的函数名称来调用,而是利用当时它在内存里面的动态地址来调用。

字符集和字符编码

ASCII 码只表示了 128 个字符,一开始倒也堪用,毕竟计算机是在美国发明的。然而随着越来越多的不同国家的人都用上了计算机,想要表示譬如中文这样的文字,128 个字符显然是不太够用的。于是,计算机工程师们开始各显神通,给自己国家的语言创建了对应的字符集(Charset)和字符编码(Character Encoding)。

字符集,表示的可以是字符的一个集合。比如“中文”就是一个字符集,不过这样描述一个字符集并不准确。想要更精确一点,我们可以说,“第一版《新华字典》里面出现的所有汉字”,这是一个字符集。这样,我们才能明确知道,一个字符在不在这个集合里面。比如,我们日常说的 Unicode,其实就是一个字符集,包含了 150 种语言的 14 万个不同的字符。

而字符编码则是对于字符集里的这些字符,怎么一一用二进制表示出来的一个字典。我们上面说的 Unicode,就可以用 UTF-8、UTF-16,乃至 UTF-32 来进行编码,存储成二进制。所以,有了 Unicode,其实我们可以用不止 UTF-8 一种编码形式,我们也可以自己发明一套 GT-32 编码,比如就叫作 Geek Time 32 好了。只要别人知道这套编码规则,就可以正常传输、显示这段代码。

image.png

同样的文本,采用不同的编码存储下来。如果另外一个程序,用一种不同的编码方式来进行解码和展示,就会出现乱码。这就好像两个军队用密语通信,如果用错了密码本,那看到的消息就会不知所云。在中文世界里,最典型的就是“手持两把锟斤拷,口中疾呼烫烫烫”的典故。

电路与运算

可以说,电报是现代计算机的一个最简单的原型。它和我们现在使用的现代计算机有很多相似之处。我们通过电路的“开”和“关”,来表示“1”和“0”。就像晶体管在不同的情况下,表现为导电的“1”和绝缘的“0”的状态。

image.png

其实加法器就是想一个办法把这三排开关电路连起来

image.png

讲与、或、非门的时候,我们很容易就能和程序里面的“AND(通常是 & 符号)”“ OR(通常是 | 符号)”和“ NOT(通常是 ! 符号)”对应起来。可能你没有想过,为什么我们会需要“异或(XOR)”,这样一个在逻辑运算里面没有出现的形式,作为一个基本电路。其实,异或门就是一个最简单的整数加法,所需要使用的基本门电路

算完个位的输出还不算完,输入的两位都是 11 的时候,我们还需要向更左侧的一位进行进位。那这个就对应一个与门,也就是有且只有在加数和被加数都是 1 的时候,我们的进位才会是 1。

所以,通过一个异或门计算出个位,通过一个与门计算出是否进位,我们就通过电路算出了一个一位数的加法。于是,我们把两个门电路打包,给它取一个名字,就叫作半加器(Half Adder)。

image.png

全加器

你肯定很奇怪,为什么我们给这样的电路组合,取名叫半加器(Half Adder)?莫非还有一个全加器(Full Adder)么?你猜得没错。半加器可以解决个位的加法问题,但是如果放到二位上来说,就不够用了。我们这里的竖式是个二进制的加法,所以如果从右往左数,第二列不是十位,我称之为“二位”。对应的再往左,就应该分别是四位、八位。

二位用一个半加器不能计算完成的原因也很简单。因为二位除了一个加数和被加数之外,还需要加上来自个位的进位信号,一共需要三个数进行相加,才能得到结果。但是我们目前用到的,无论是最简单的门电路,还是用两个门电路组合而成的半加器,输入都只能是两个 bit,也就是两个开关。那我们该怎么办呢?

实际上,解决方案也并不复杂。我们用两个半加器和一个或门,就能组合成一个全加器。第一个半加器,我们用和个位的加法一样的方式,得到是否进位 X 和对应的二个数加和后的结果 Y,这样两个输出。然后,我们把这个加和后的结果 Y,和个位数相加后输出的进位信息 U,再连接到一个半加器上,就会再拿到一个是否进位的信号 V 和对应的加和后的结果 W。

image.png

image.png

int add(int a,int b)
{
    int carry,add;
    do{
        add=a^b;
        carry=(a&b)<<1;
        a=add;
        b=carry;
    }while(carry!=0);
    return add;
}

有了全加器,我们要进行对应的两个 8 bit 数的加法就很容易了。我们只要把 8 个全加器串联起来就好了。个位的全加器的进位信号作为二位全加器的输入信号,二位全加器的进位信号再作为四位的全加器的进位信号。这样一层层串接八层,我们就得到了一个支持 8 位数加法的算术单元。如果要扩展到 16 位、32 位,乃至 64 位,都只需要多串联几个输入位和全加器就好了。

image.png

image.png

顺序乘法的实现过程

十进制中的 13 乘以 9,计算的结果应该是 117。我们通过转换成二进制,然后列竖式的办法,来看看整个计算的过程是怎样的。

image.png

在 13×9 这个例子里面,被乘数 13 表示成二进制是 1101,乘数 9 在二进制里面是 1001。最右边的个位是 1,所以个位乘以被乘数,就是把被乘数 1101 复制下来。因为二位和四位都是 0,所以乘以被乘数都是 0,那么保留下来的都是 0000。乘数的八位是 1,我们仍然需要把被乘数 1101 复制下来。不过这里和个位位置的单纯复制有一点小小的差别,那就是要把复制好的结果向左侧移三位,然后把四位单独进行乘法加位移的结果,再加起来,我们就得到了最终的计算结果。

对应到我们之前讲的数字电路和 ALU,你可以看到,最后一步的加法,我们可以用上一讲的加法器来实现。乘法因为只有“0”和“1”两种情况,所以可以做成输入输出都是 4 个开关,中间用 1 个开关,同时来控制这 8 个开关的方式,这就实现了二进制下的单位的乘法。

我们可以用一个开关来决定,下面的输出是完全复制输入,还是将输出全部设置为 0

image.png

至于位移也不麻烦,我们只要不是直接连线,把正对着的开关之间进行接通,而是斜着错开位置去接就好了。如果要左移一位,就错开一位接线;如果要左移两位,就错开两位接线。

把对应的线路错位连接,就可以起到位移的作用

image.png

这样,你会发现,我们并不需要引入任何新的、更复杂的电路,仍然用最基础的电路,只要用不同的接线方式,就能够实现一个“列竖式”的乘法。而且,因为二进制下,只有 0 和 1,也就是开关的开和闭这两种情况,所以我们的计算机也不需要去“背诵”九九乘法口诀表,不需要单独实现一个更复杂的电路,就能够实现乘法。

为了节约一点开关,也就是晶体管的数量。实际上,像 13×9 这样两个四位数的乘法,我们不需要把四次单位乘法的结果,用四组独立的开关单独都记录下来,然后再把这四个数加起来。因为这样做,需要很多组开关,如果我们计算一个 32 位的整数乘法,就要 32 组开关,太浪费晶体管了。如果我们顺序地来计算,只需要一组开关就好了。

我们先拿乘数最右侧的个位乘以被乘数,然后把结果写入用来存放计算结果的开关里面,然后,把被乘数左移一位,把乘数右移一位,仍然用乘数去乘以被乘数,然后把结果加到刚才的结果上。反复重复这一步骤,直到不能再左移和右移位置。这样,乘数和被乘数就像两列相向而驶的列车,仅仅需要简单的加法器、一个可以左移一位的电路和一个右移一位的电路,就能完成整个乘法。

乘法器硬件结构示意图

image.png

你看这里画的乘法器硬件结构示意图。这里的控制测试,其实就是通过一个时钟信号,来控制左移、右移以及重新计算乘法和加法的时机。我们还是以计算 13×9,也就是二进制的 1101×1001 来具体看。

image.png

这个计算方式虽然节约电路了,但是也有一个很大的缺点,那就是慢。

你应该很容易就能发现,在这个乘法器的实现过程里,我们其实就是把乘法展开,变成了“加法 + 位移”来实现。我们用的是 4 位数,所以要进行 4 组“位移 + 加法”的操作。而且这 4 组操作还不能同时进行。因为下一组的加法要依赖上一组的加法后的计算结果,下一组的位移也要依赖上一组的位移的结果。这样,整个算法是“顺序”的,每一组加法或者位移的运算都需要一定的时间。

所以,最终这个乘法的计算速度,其实和我们要计算的数的位数有关。比如,这里的 4 位,就需要 4 次加法。而我们的现代 CPU 常常要用 32 位或者是 64 位来表示整数,那么对应就需要 32 次或者 64 次加法。比起 4 位数,要多花上 8 倍乃至 16 倍的时间。

换个我们在算法和数据结构中的术语来说就是,**这样的一个顺序乘法器硬件进行计算的时间复杂度是 O(N)**。这里的 N,就是乘法的数里面的位数。

并行加速方法

前面顺序乘法器硬件的实现办法,就好像体育比赛里面的单败淘汰赛。只有一个擂台会存下最新的计算结果。每一场新的比赛就来一个新的选手,实现一次加法,实现完了剩下的还是原来那个守擂的,直到其余 31 个选手都上来比过一场。如果一场比赛需要一天,那么一共要比 31 场,也就是 31 天。

image.png

加速的办法,就是把比赛变成像世界杯足球赛那样的淘汰赛,32 个球队捉对厮杀,同时开赛。这样一天一下子就淘汰了 16 支队,也就是说,32 个数两两相加后,你可以得到 16 个结果。后面的比赛也是一样同时开赛捉对厮杀。只需要 5 天,也就是 O(log2N) 的时间,就能得到计算的结果。但是这种方式要求我们得有 16 个球场。因为在淘汰赛的第一轮,我们需要 16 场比赛同时进行。对应到我们 CPU 的硬件上,就是需要更多的晶体管开关,来放下中间计算结果。

通过并联更多的 ALU,加上更多的寄存器,我们也能加速乘法

image.png

电路并行

上面我们说的并行加速的办法,看起来还是有点儿笨。我们回头来做一个抽象的思考。之所以我们的计算会慢,核心原因其实是“顺序”计算,也就是说,要等前面的计算结果完成之后,我们才能得到后面的计算结果。

最典型的例子就是我们上一讲讲的加法器。每一个全加器,都要等待上一个全加器,把对应的进入输入结果算出来,才能算下一位的输出。位数越多,越往高位走,等待前面的步骤就越多,这个等待的时间有个专门的名词,叫作门延迟(Gate Delay)。

每通过一个门电路,我们就要等待门电路的计算结果,就是一层的门电路延迟,我们一般给它取一个“T”作为符号。一个全加器,其实就已经有了 3T 的延迟(进位需要经过 3 个门电路)。而 4 位整数,最高位的计算需要等待前面三个全加器的进位结果,也就是要等 9T 的延迟。如果是 64 位整数,那就要变成 63×3=189T 的延迟。这可不是个小数字啊!

除了门延迟之外,还有一个问题就是时钟频率。在上面的顺序乘法计算里面,如果我们想要用更少的电路,计算的中间结果需要保存在寄存器里面,然后等待下一个时钟周期的到来,控制测试信号才能进行下一次移位和加法,这个延迟比上面的门延迟更可观。

那么,我们有什么办法可以解决这个问题呢?实际上,在我们进行加法的时候,如果相加的两个数是确定的,那高位是否会进位其实也是确定的。对于我们人来说,我们本身去做计算都是顺序执行的,所以要一步一步计算进位。但是,计算机是连结的各种线路。我们不用让计算机模拟人脑的思考方式,来连结线路。

那怎么才能把线路连结得复杂一点,让高位和低位的计算同时出结果呢?怎样才能让高位不需要等待低位的进位结果,而是把低位的所有输入信号都放进来,直接计算出高位的计算结果和进位结果呢?

我们只要把进位部分的电路完全展开就好了。我们的半加器到全加器,再到加法器,都是用最基础的门电路组合而成的。门电路的计算逻辑,可以像我们做数学里面的多项式乘法一样完全展开。在展开之后呢,我们可以把原来需要较少的,但是有较多层前后计算依赖关系的门电路,展开成需要较多的,但是依赖关系更少的门电路。

我在这里画了一个示意图,展示了一下我们加法器。如果我们完全展开电路,高位的进位和计算结果,可以和低位的计算结果同时获得。这个的核心原因是电路是天然并行的,一个输入信号,可以同时传播到所有接通的线路当中。

C4 是前 4 位的计算结果是否进位的门电路表示

image.png

如果一个 4 位整数最高位是否进位,展开门电路图,你会发现,我们只需要 3T 的延迟就可以拿到是否进位的计算结果。而对于 64 位的整数,也不会增加门延迟,只是从上往下复制这个电路,接入更多的信号而已。看到没?我们通过把电路变复杂,就解决了延迟的问题。

这个优化,本质上是利用了电路天然的并行性。电路只要接通,输入的信号自动传播到了所有接通的线路里面,这其实也是硬件和软件最大的不同。

无论是这里把对应的门电路逻辑进行完全展开以减少门延迟,还是上面的乘法通过并行计算多个位的乘法,都是把我们完成一个计算的电路变复杂了。而电路变复杂了,也就意味着晶体管变多了。

之前很多同学在我们讨论计算机的性能问题的时候,都提到,为什么晶体管的数量增加可以优化计算机的计算性能。实际上,这里的门电路展开和上面的并行计算乘法都是很好的例子。我们通过更多的晶体管,就可以拿到更低的门延迟,以及用更少的时钟周期完成一个计算指令

浮点数的不精确性

你可以在 Linux 下打开 Python 的命令行 Console,也可以在 Chrome 浏览器里面通过开发者工具,打开浏览器里的 Console,在里面输入“0.3 + 0.6”,然后看看你会得到一个什么样的结果。

>>> 0.3 + 0.6
0.8999999999999999

不知道你有没有大吃一惊,这么简单的一个加法,无论是在 Python 还是在 JavaScript 里面,算出来的结果居然不是准确的 0.9,而是 0.8999999999999999 这么个结果。这是为什么呢?

定点数的表示

有一个很直观的想法,就是我们用 4 个比特来表示 0~9 的整数,那么 32 个比特就可以表示 8 个这样的整数。然后我们把最右边的 2 个 0~9 的整数,当成小数部分;把左边 6 个 0~9 的整数,当成整数部分。这样,我们就可以用 32 个比特,来表示从 0 到 999999.99 这样 1 亿个实数了。

image.png

这种用二进制来表示十进制的编码方式,叫作BCD 编码(Binary-Coded Decimal)。其实它的运用非常广泛,最常用的是在超市、银行这样需要用小数记录金额的情况里。在超市里面,我们的小数最多也就到分。这样的表示方式,比较直观清楚,也满足了小数部分的计算。

不过,这样的表示方式也有几个缺点。

第一,这样的表示方式有点“浪费”。本来 32 个比特我们可以表示 40 亿个不同的数,但是在 BCD 编码下,只能表示 1 亿个数,如果我们要精确到分的话,那么能够表示的最大金额也就是到 100 万。如果我们的货币单位是人民币或者美元还好,如果我们的货币单位变成了津巴布韦币,这个数量就不太够用了。

第二,这样的表示方式没办法同时表示很大的数字和很小的数字。我们在写程序的时候,实数的用途可能是多种多样的。有时候我们想要表示商品的金额,关心的是 9.99 这样小的数字;有时候,我们又要进行物理学的运算,需要表示光速,也就是 3×108 这样很大的数字。那么,我们有没有一个办法,既能够表示很小的数,又能表示很大的数呢?

浮点数的表示

答案当然是有的,就是你可能经常听说过的浮点数(Floating Point),也就是 float 类型。

在计算机里,我们也可以用一样的办法,用科学计数法来表示实数。浮点数的科学计数法的表示,有一个 IEEE 的标准,它定义了两个基本的格式。一个是用 32 比特表示单精度的浮点数,也就是我们常常说的 float 或者 float32 类型。另外一个是用 64 比特表示双精度的浮点数,也就是我们平时说的 double 或者 float64 类型。

双精度类型和单精度类型差不多,这里,我们来看单精度类型,双精度你自然也就明白了。

image.png

第一部分是一个符号位,用来表示是正数还是负数。我们一般用 s 来表示。在浮点数里,我们不像正数分符号数还是无符号数,所有的浮点数都是有符号的。

接下来是一个 8 个比特组成的指数位。我们一般用 e 来表示。8 个比特能够表示的整数空间,就是 0~255。我们在这里用 1~254 映射到 -126~127 这 254 个有正有负的数上。因为我们的浮点数,不仅仅想要表示很大的数,还希望能够表示很小的数,所以指数位也会有负数。

7277BB65-A362-48BE-9E15-D7E497F5ED3B.png

我们可以做一个简单的实验,用一个循环相加 2000 万个 1.0f,最终的结果会是 1600 万左右,而不是 2000 万。这是因为,加到 1600 万之后的加法因为精度丢失都没有了。这个代码比起上面的使用 2000 万来加 1.0 更具有现实意义。

public class FloatPrecision {
  public static void main(String[] args) {
    float sum = 0.0f;
    for (int i = 0; i < 20000000; i++) {
      float x = 1.0f;
      sum += x;      
    }
    System.out.println("sum is " + sum);   
  }  
}

对应的输出结果是:

sum is 1.6777216E7

面对这个问题,聪明的计算机科学家们也想出了具体的解决办法。他们发明了一种叫作Kahan Summation的算法来解决这个问题。算法的对应代码我也放在文稿中了。从中你可以看到,同样是 2000 万个 1.0f 相加,用这种算法我们得到了准确的 2000 万的结果。

public class KahanSummation {
  public static void main(String[] args) {
    float sum = 0.0f;
    float c = 0.0f;
    for (int i = 0; i < 20000000; i++) {
      float x = 1.0f;
      float y = x - c;
      float t = sum + y;
      c = (t-sum)-y;
      sum = t;      
    }
    System.out.println("sum is " + sum);   
  }  
}

其实这个算法的原理其实并不复杂,就是在每次的计算过程中,都用一次减法,把当前加法计算中损失的精度记录下来,然后在后面的循环中,把这个精度损失放在要加的小数上,再做一次运算。

处理器

指令 + 运算

指令周期(Instruction Cycle)

前面讲计算机机器码的时候,我向你介绍过 PC 寄存器、指令寄存器,还介绍过 MIPS 体系结构的计算机所用到的 R、I、J 类指令。如果我们仔细看一看,可以发现,计算机每执行一条指令的过程,可以分解成这样几个步骤。

  1. Fetch(取得指令),也就是从 PC 寄存器里找到对应的指令地址,根据指令地址从内存里把具体的指令,加载到指令寄存器中,然后把 PC 寄存器自增,好在未来执行下一条指令。
  2. Decode(指令译码),也就是根据指令寄存器里面的指令,解析成要进行什么样的操作,是 R、I、J 中的哪一种指令,具体要操作哪些寄存器、数据或者内存地址。
  3. Execute(执行指令),也就是实际运行对应的 R、I、J 这些特定的指令,进行算术逻辑操作、数据传输或者直接的地址跳转。

这样的步骤,其实就是一个永不停歇的“Fetch - Decode - Execute”的循环,我们把这个循环称之为指令周期(Instruction Cycle)。

在取指令的阶段,我们的指令是放在存储器里的,实际上,通过 PC 寄存器和指令寄存器取出指令的过程,是由控制器(Control Unit)操作的。指令的解码过程,也是由控制器进行的。一旦到了执行指令阶段,无论是进行算术操作、逻辑操作的 R 型指令,还是进行数据传输、条件分支的 I 型指令,都是由算术逻辑单元(ALU)操作的,也就是由运算器处理的。不过,如果是一个简单的无条件地址跳转,那么我们可以直接在控制器里面完成,不需要用到运算器。

image.png

除了 Instruction Cycle 这个指令周期,在 CPU 里面我们还会提到另外两个常见的 Cycle。一个叫 Machine Cycle,机器周期或者 CPU 周期。CPU 内部的操作速度很快,但是访问内存的速度却要慢很多。每一条指令都需要从内存里面加载而来,所以我们一般把从内存里面读取一条指令的最短时间,称为 CPU 周期

对于一个指令周期来说,我们取出一条指令,然后执行它,至少需要两个 CPU 周期。取出指令至少需要一个 CPU 周期,执行至少也需要一个 CPU 周期,复杂的指令则需要更多的 CPU 周期。

建立数据通路

第一类叫操作元件,也叫组合逻辑元件(Combinational Element),其实就是我们的 ALU。在前面讲 ALU 的过程中可以看到,它们的功能就是在特定的输入下,根据下面的组合电路的逻辑,生成特定的输出。

第二类叫存储元件,也有叫状态元件(State Element)的。比如我们在计算过程中需要用到的寄存器,无论是通用寄存器还是状态寄存器,其实都是存储元件。

我们通过数据总线的方式,把它们连接起来,就可以完成数据的存储、处理和传输了,这就是所谓的建立数据通路了。

下面我们来说控制器。它的逻辑就没那么复杂了。我们可以把它看成只是机械地重复“Fetch - Decode - Execute“循环中的前两个步骤,然后把最后一个步骤,通过控制器产生的控制信号,交给 ALU 去处理。

组合逻辑电路和时序逻辑电路

上一讲,我们看到,要能够实现一个完整的 CPU 功能,除了加法器这样的电路之外,我们还需要实现其他功能的电路。其中有一些电路,和我们实现过的加法器一样,只需要给定输入,就能得到固定的输出。这样的电路,我们称之为组合逻辑电路(Combinational Logic Circuit)。

但是,光有组合逻辑电路是不够的。你可以想一下,如果只有组合逻辑电路,我们的 CPU 会是什么样的?电路输入是确定的,对应的输出自然也就确定了。那么,我们要进行不同的计算,就要去手动拨动各种开关,来改变电路的开闭状态。这样的计算机,不像我们现在每天用的功能强大的电子计算机,反倒更像古老的计算尺或者机械计算机,干不了太复杂的工作,只能协助我们完成一些计算工作。

这样,我们就需要引入第二类的电路,也就是时序逻辑电路(Sequential Logic Circuit)。时序逻辑电路可以帮我们解决这样几个问题。

第一个就是自动运行的问题。时序电路接通之后可以不停地开启和关闭开关,进入一个自动运行的状态。这个使得我们上一讲说的,控制器不停地让 PC 寄存器自增读取下一条指令成为可能。

第二个是存储的问题。通过时序电路实现的触发器,能把计算结果存储在特定的电路里面,而不是像组合逻辑电路那样,一旦输入有任何改变,对应的输出也会改变。

第三个本质上解决了各个功能按照时序协调的问题。无论是程序实现的软件指令,还是到硬件层面,各种指令的操作都有先后的顺序要求。时序电路使得不同的事件按照时间顺序发生。

时钟信号的硬件实现

想要实现时序逻辑电路,第一步我们需要的就是一个时钟。我在第 3 讲说过,CPU 的主频是由一个晶体振荡器来实现的,而这个晶体振荡器生成的电路信号,就是我们的时钟信号。

实现这样一个电路,和我们之前讲的,通过电的磁效应产生开关信号的方法是一样的。只不过,这里的磁性开关,打开的不再是后续的线路,而是当前的线路。

在下面这张图里你可以看到,我们在原先一般只放一个开关的信号输入端,放上了两个开关。一个开关 A,一开始是断开的,由我们手工控制;另外一个开关 B,一开始是合上的,磁性线圈对准一开始就合上的开关 B。

于是,一旦我们合上开关 A,磁性线圈就会通电,产生磁性,开关 B 就会从合上变成断开。一旦这个开关断开了,电路就中断了,磁性线圈就失去了磁性。于是,开关 B 又会弹回到合上的状态。这样一来,电路接通,线圈又有了磁性。我们的电路就会来回不断地在开启、关闭这两个状态中切换。

开关 A 闭合(也就是相当于接通电路之后),开关 B 就会不停地在开和关之间切换,生成对应的时钟信号

image.png

这个不断切换的过程,对于下游电路来说,就是不断地产生新的 0 和 1 这样的信号。如果你在下游的电路上接上一个灯泡,就会发现这个灯泡在亮和暗之间不停切换。这个按照固定的周期不断在 0 和 1 之间切换的信号,就是我们的时钟信号(Clock Signal)。这个不断切换的过程,对于下游电路来说,就是不断地产生新的 0 和 1 这样的信号。如果你在下游的电路上接上一个灯泡,就会发现这个灯泡在亮和暗之间不停切换。这个按照固定的周期不断在 0 和 1 之间切换的信号,就是我们的时钟信号(Clock Signal)

时钟信号示意图

image.png

这种电路,其实就相当于把电路的输出信号作为输入信号,再回到当前电路。这样的电路构造方式呢,我们叫作反馈电路(Feedback Circuit)。

接下来,我们还会看到更多的反馈电路。上面这个反馈电路一般可以用下面这个示意图来表示,其实就是一个输出结果接回输入的反相器(Inverter),也就是我们之前讲过的非门。

image.png

通过 D 触发器实现存储功能

有了时钟信号,我们的系统里就有了一个像“自动门”一样的开关。利用这个开关和相同的反馈电路,我们就可以构造出一个有“记忆”功能的电路。这个有记忆功能的电路,可以实现在 CPU 中用来存储计算结果的寄存器,也可以用来实现计算机五大组成部分之一的存储器。

image.png

这样一个电路,我们称之为触发器(Flip-Flop)。接通开关 R,输出变为 1,即使断开开关,输出还是 1 不变。接通开关 S,输出变为 0,即使断开开关,输出也还是 0。也就是,当两个开关都断开的时候,最终的输出结果,取决于之前动作的输出结果,这个也就是我们说的记忆功能

这里的这个电路是最简单的 RS 触发器,也就是所谓的复位置位触发器(Reset-Set Flip Flop) 。对应的输出结果的真值表,你可以看下面这个表格。可以看到,当两个开关都是 0 的时候,对应的输出不是 1 或者 0,而是和 Q 的上一个状态一致。

image.png

再往这个电路里加两个与门和一个小小的时钟信号,我们就可以实现一个利用时钟信号来操作一个电路了。这个电路可以帮我们实现什么时候可以往 Q 里写入数据。

我们看看下面这个电路,这个在我们的上面的 R-S 触发器基础之上,在 R 和 S 开关之后,加入了两个与门,同时给这两个与门加入了一个时钟信号 CLK 作为电路输入。

这样,当时钟信号 CLK 在低电平的时候,与门的输入里有一个 0,两个实际的 R 和 S 后的与门的输出必然是 0。也就是说,无论我们怎么按 R 和 S 的开关,根据 R-S 触发器的真值表,对应的 Q 的输出都不会发生变化。

只有当时钟信号 CLK 在高电平的时候,与门的一个输入是 1,输出结果完全取决于 R 和 S 的开关。我们可以在这个时候,通过开关 R 和 S,来决定对应 Q 的输出。

image.png

如果这个时候,我们让 R 和 S 的开关,也用一个反相器连起来,也就是通过同一个开关控制 R 和 S。只要 CLK 信号是 1,R 和 S 就可以设置输出 Q。而当 CLK 信号是 0 的时候,无论 R 和 S 怎么设置,输出信号 Q 是不变的。这样,这个电路就成了我们最常用的 D 型触发器。用来控制 R 和 S 这两个开关的信号呢,我们视作一个输入的数据信号 D,也就是 Data,这就是 D 型触发器的由来。

把 R 和 S 两个信号通过一个反相器合并,我们可以通过一个数据信号 D 进行 Q 的写入操作

image.png

一个 D 型触发器,只能控制 1 个比特的读写,但是如果我们同时拿出多个 D 型触发器并列在一起,并且把用同一个 CLK 信号控制作为所有 D 型触发器的开关,这就变成了一个 N 位的 D 型触发器,也就可以同时控制 N 位的读写。

CPU 里面的寄存器可以直接通过 D 型触发器来构造。我们可以在 D 型触发器的基础上,加上更多的开关,来实现清 0 或者全部置为 1 这样的快捷操作。

电路的输出信号不单单取决于当前的输入信号,还要取决于输出信号之前的状态。最常见的这个电路就是我们的 D 触发器,它也是我们实际在 CPU 内实现存储功能的寄存器的实现方式。

PC 寄存器所需要的计数器

我们常说的 PC 寄存器,还有个名字叫程序计数器。下面我们就来看看,它为什么叫作程序计数器。

有了时钟信号,我们可以提供定时的输入;有了 D 型触发器,我们可以在时钟信号控制的时间点写入数据。我们把这两个功能组合起来,就可以实现一个自动的计数器了。

加法器的两个输入,一个始终设置成 1,另外一个来自于一个 D 型触发器 A。我们把加法器的输出结果,写到这个 D 型触发器 A 里面。于是,D 型触发器里面的数据就会在固定的时钟信号为 1 的时候更新一次。

image.png

这样,我们就有了一个每过一个时钟周期,就能固定自增 1 的自动计数器了。这个自动计数器,可以拿来当我们的 PC 寄存器。事实上,PC 寄存器的这个 PC,英文就是 Program Counter,也就是程序计数器的意思。

每次自增之后,我们可以去对应的 D 型触发器里面取值,这也是我们下一条需要运行指令的地址。前面第 5 讲我们讲过,同一个程序的指令应该要顺序地存放在内存里面。这里就和前面对应上了,顺序地存放指令,就是为了让我们通过程序计数器就能定时地不断执行新指令。

在最简单的情况下,我们需要让每一条指令,从程序计数,到获取指令、执行指令,都在一个时钟周期内完成。如果 PC 寄存器自增地太快,程序就会出错。因为前一次的运算结果还没有写回到对应的寄存器里面的时候,后面一条指令已经开始读取里面的数据来做下一次计算了。这个时候,如果我们的指令使用同样的寄存器,前一条指令的计算就会没有效果,计算结果就错了。

在这种设计下,我们需要在一个时钟周期里,确保执行完一条最复杂的 CPU 指令,也就是耗时最长的一条 CPU 指令。这样的 CPU 设计,我们称之为单指令周期处理器(Single Cycle Processor)

很显然,这样的设计有点儿浪费。因为即便只调用一条非常简单的指令,我们也需要等待整个时钟周期的时间走完,才能执行下一条指令。在后面章节里我们会讲到,通过流水线技术进行性能优化,可以减少需要等待的时间,这里我们暂且说到这里。

读写数据所需要的译码器

现在,我们的数据能够存储在 D 型触发器里了。如果我们把很多个 D 型触发器放在一起,就可以形成一块很大的存储空间,甚至可以当成一块内存来用。像我现在手头这台电脑,有 16G 内存。那我们怎么才能知道,写入和读取的数据,是在这么大的内存的哪几个比特呢?

于是,我们就需要有一个电路,来完成“寻址”的工作。这个“寻址”电路,就是我们接下来要讲的译码器。

在现在实际使用的计算机里面,内存所使用的 DRAM,并不是通过上面的 D 型触发器来实现的,而是使用了一种 CMOS 芯片来实现的。不过,这并不影响我们从基础原理方面来理解译码器。在这里,我们还是可以把内存芯片,当成是很多个连在一起的 D 型触发器来实现的。

如果把“寻址”这件事情退化到最简单的情况,就是在两个地址中,去选择一个地址。这样的电路,我们叫作 2-1 选择器。我把它的电路实现画在了这里。

我们通过一个反相器、两个与门和一个或门,就可以实现一个 2-1 选择器。通过控制反相器的输入是 0 还是 1,能够决定对应的输出信号,是和地址 A,还是地址 B 的输入信号一致。

image.png

一个反向器只能有 0 和 1 这样两个状态,所以我们只能从两个地址中选择一个。如果输入的信号有三个不同的开关,我们就能从 23,也就是 8 个地址中选择一个了。这样的电路,我们就叫 3-8 译码器。现代的计算机,如果 CPU 是 64 位的,就意味着我们的寻址空间也是 2^64,那么我们就需要一个有 64 个开关的译码器。

image.png

所以说,其实译码器的本质,就是从输入的多个位的信号中,根据一定的开关和电路组合,选择出自己想要的信号。除了能够进行“寻址”之外,我们还可以把对应的需要运行的指令码,同样通过译码器,找出我们期望执行的指令,也就是在之前我们讲到过的 opcode,以及后面对应的操作数或者寄存器地址。只是,这样的“译码器”,比起 2-1 选择器和 3-8 译码器,要复杂的多。

建立数据通路,构造一个最简单的 CPU

D 触发器、自动计数以及译码器,再加上一个我们之前说过的 ALU,我们就凑齐了一个拼装一个 CPU 必须要的零件了。下面,我们就来看一看,怎么把这些零件组合起来,才能实现指令执行和算术逻辑计算的 CPU。

image.png

  1. 首先,我们有一个自动计数器。这个自动计数器会随着时钟主频不断地自增,来作为我们的 PC 寄存器。
  2. 在这个自动计数器的后面,我们连上一个译码器。译码器还要同时连着我们通过大量的 D 触发器组成的内存。
  3. 自动计数器会随着时钟主频不断自增,从译码器当中,找到对应的计数器所表示的内存地址,然后读取出里面的 CPU 指令。
  4. 读取出来的 CPU 指令会通过我们的 CPU 时钟的控制,写入到一个由 D 触发器组成的寄存器,也就是指令寄存器当中。
  5. 在指令寄存器后面,我们可以再跟一个译码器。这个译码器不再是用来寻址的了,而是把我们拿到的指令,解析成 opcode 和对应的操作数。
  6. 当我们拿到对应的 opcode 和操作数,对应的输出线路就要连接 ALU,开始进行各种算术和逻辑运算。对应的计算结果,则会再写回到 D 触发器组成的寄存器或者内存当中。

这样的一个完整的通路,也就完成了我们的 CPU 的一条指令的执行过程。在这个过程中,你会发现这样几个有意思的问题。

CPU指令周期和流水线

愿得一心人,白首不相离:单指令周期处理器

快速执行完成的指令,需要等待满一个时钟周期,才能执行下一条指令

image.png

所以,在单指令周期处理器里面,无论是执行一条用不到 ALU 的无条件跳转指令,还是一条计算起来电路特别复杂的浮点数乘法运算,我们都等要等满一个时钟周期。在这个情况下,虽然 CPI 能够保持在 1,但是我们的时钟频率却没法太高。因为太高的话,有些复杂指令没有办法在一个时钟周期内运行完成。那么在下一个时钟周期到来,开始执行下一条指令的时候,前一条指令的执行结果可能还没有写入到寄存器里面。那下一条指令读取的数据就是不准确的,就会出现错误。

image.png

到这里你会发现,这和我们之前第 3 讲和第 4 讲讲时钟频率时候的说法不太一样。当时我们说,一个 CPU 时钟周期,可以认为是完成一条简单指令的时间。为什么到了这里,单指令周期处理器,反而变成了执行一条最复杂的指令的时间呢?

这是因为,无论是 PC 上使用的 Intel CPU,还是手机上使用的 ARM CPU,都不是单指令周期处理器,而是采用了一种叫作指令流水线(Instruction Pipeline)的技术。

无可奈何花落去,似曾相识燕归来:现代处理器的流水线设计

其实,CPU 执行一条指令的过程和我们开发软件功能的过程很像。

如果我们想开发一个手机 App 上的功能,并不是找来一个工程师,告诉他“你把这个功能开发出来”,然后他就吭哧吭哧把功能开发出来。真实的情况是,无论只有一个工程师,还是有一个开发团队,我们都需要先对开发功能的过程进行切分,把这个过程变成“撰写需求文档、开发后台 API、开发客户端 App、测试、发布上线”这样多个独立的过程。每一个后面的步骤,都要依赖前面的步骤。

我们的指令执行过程也是一样的,它会拆分成“取指令、译码、执行”这样三大步骤。更细分一点的话,执行的过程,其实还包含从寄存器或者内存中读取数据,通过 ALU 进行运算,把结果写回到寄存器或者内存中。

image.png

这样一来,我们就不用把时钟周期设置成整条指令执行的时间,而是拆分成完成这样的一个一个小步骤需要的时间。同时,每一个阶段的电路在完成对应的任务之后,也不需要等待整个指令执行完成,而是可以直接执行下一条指令的对应阶段。

这就好像我们的后端程序员不需要等待功能上线,就会从产品经理手中拿到下一个需求,开始开发 API。这样的协作模式,就是我们所说的指令流水线。这里面每一个独立的步骤,我们就称之为流水线阶段或者流水线级(Pipeline Stage)。

五级的流水线,就表示我们在同一个时钟周期里面,同时运行五条指令的不同阶段。这个时候,虽然执行一条指令的时钟周期变成了 5,但是我们可以把 CPU 的主频提得更高了。我们不需要确保最复杂的那条指令在时钟周期里面执行完成,而只要保障一个最复杂的流水线级的操作,在一个时钟周期内完成就好了。

如果某一个操作步骤的时间太长,我们就可以考虑把这个步骤,拆分成更多的步骤,让所有步骤需要执行的时间尽量都差不多长。这样,也就可以解决我们在单指令周期处理器中遇到的,性能瓶颈来自于最复杂的指令的问题。像我们现代的 ARM 或者 Intel 的 CPU,流水线级数都已经到了 14 级。

虽然我们不能通过流水线,来减少单条指令执行的“延时”这个性能指标,但是,通过同时在执行多条指令的不同阶段,我们提升了 CPU 的“吞吐率”。在外部看来,我们的 CPU 好像是“一心多用”,在同一时间,同时执行 5 条不同指令的不同阶段。在 CPU 内部,其实它就像生产线一样,不同分工的组件不断处理上游传递下来的内容,而不需要等待单件商品生产完成之后,再启动下一件商品的生产过程。

超长流水线的性能瓶颈

既然流水线可以增加我们的吞吐率,你可能要问了,为什么我们不把流水线级数做得更深呢?为什么不做成 20 级,乃至 40 级呢?这个其实有很多原因,我在之后几讲里面会详细讲解。这里,我先讲一个最基本的原因,就是增加流水线深度,其实是有性能成本的。

我们用来同步时钟周期的,不再是指令级别的,而是流水线阶段级别的。每一级流水线对应的输出,都要放到流水线寄存器(Pipeline Register)里面,然后在下一个时钟周期,交给下一个流水线级去处理。所以,每增加一级的流水线,就要多一级写入到流水线寄存器的操作。虽然流水线寄存器非常快,比如只有 20 皮秒(ps,10−12 秒)。

image.png

但是,如果我们不断加深流水线,这些操作占整个指令的执行时间的比例就会不断增加。最后,我们的性能瓶颈就会出现在这些 overhead 上。如果我们指令的执行有 3 纳秒,也就是 3000 皮秒。我们需要 20 级的流水线,那流水线寄存器的写入就需要花费 400 皮秒,占了超过 10%。如果我们需要 50 级流水线,就要多花费 1 纳秒在流水线寄存器上,占到 25%。这也就意味着,单纯地增加流水线级数,不仅不能提升性能,反而会有更多的 overhead 的开销。所以,设计合理的流水线级数也是现代 CPU 中非常重要的一点。

“主频战争”带来的超长流水线

我们在第 3 讲里讲过,我们其实并不能简单地通过 CPU 的主频,就来衡量 CPU 乃至计算机整机的性能。因为不同的 CPU 实际的体系架构和实现都不一样。同样的 CPU 主频,实际的性能可能差别很大。所以,在工业界,更好的衡量方式通常是,用 SPEC 这样的跑分程序,从多个不同的实际应用场景,来衡量计算机的性能。

但是,跑分对于消费者来说还是太复杂了。在 Pentium 4 的 CPU 面世之前,绝大部分消费者并不是根据跑分结果来判断 CPU 的性能的。大家判断一个 CPU 的性能,通常只看 CPU 的主频。而 CPU 的厂商们也通过不停地提升主频,把主频当成技术竞赛的核心指标。

Intel 一向在“主频战争”中保持领先,但是到了世纪之交的 1999 年到 2000 年,情况发生了变化。

1999 年,AMD 发布了基于 K7 架构的 Athlon 处理器,其综合性能超越了当年的 Pentium III。2000 年,在大部分 CPU 还在 500~850MHz 的频率下运行的时候,AMD 推出了第一代 Athlon 1000 处理器,成为第一款 1GHz 主频的消费级 CPU。在 2000 年前后,AMD 的 CPU 不但性能和主频比 Intel 的要强,价格还往往只有 Intel 的 2/3。

在巨大的外部压力之下,Intel 在 2001 年推出了新一代的 NetBurst 架构 CPU,也就是 Pentium 4 和 Pentium D。Pentium 4 的 CPU 有个最大的特点,就是高主频。2000 年的 Athlon 1000 的主频在当时是最高的,1GHz,然而 Pentium 4 设计的目标最高主频是 10GHz。

image.png

为了达到这个 10GHz,Intel 的工程师做出了一个重大的错误决策,就是在 NetBurst 架构上,使用超长的流水线。这个超长流水线有多长呢?我们拿在 Pentium 4 之前和之后的 CPU 的数字做个比较,你就知道了。

Pentium 4 之前的 Pentium III CPU,流水线的深度是 11 级,也就是一条指令最多会拆分成 11 个更小的步骤来操作,而 CPU 同时也最多会执行 11 条指令的不同 Stage。随着技术发展到今天,你日常用的手机 ARM 的 CPU 或者 Intel i7 服务器的 CPU,流水线的深度是 14 级。

可以看到,差不多 20 年过去了,通过技术进步,现代 CPU 还是增加了一些流水线深度的。那 2000 年发布的 Pentium 4 的流水线深度是多少呢?答案是 20 级,比 Pentium III 差不多多了一倍,而到了代号为 Prescott 的 90 纳米工艺处理器 Pentium 4,Intel 更是把流水线深度增加到了 31 级。

要知道,增加流水线深度,在同主频下,其实是降低了 CPU 的性能。因为一个 Pipeline Stage,就需要一个时钟周期。那么我们把任务拆分成 31 个阶段,就需要 31 个时钟周期才能完成一个任务;而把任务拆分成 11 个阶段,就只需要 11 个时钟周期就能完成任务。在这种情况下,31 个 Stage 的 3GHz 主频的 CPU,其实和 11 个 Stage 的 1GHz 主频的 CPU,性能是差不多的。事实上,因为每个 Stage 都需要有对应的 Pipeline 寄存器的开销,这个时候,更深的流水线性能可能还会更差一些。

我在上一讲也说过,流水线技术并不能缩短单条指令的响应时间这个性能指标,但是可以增加在运行很多条指令时候的吞吐率。因为不同的指令,实际执行需要的时间是不同的。我们可以看这样一个例子。我们顺序执行这样三条指令。

  • 一条整数的加法,需要 200ps。
  • 一条整数的乘法,需要 300ps。
  • 一条浮点数的乘法,需要 600ps。

如果我们是在单指令周期的 CPU 上运行,最复杂的指令是一条浮点数乘法,那就需要 600ps。那这三条指令,都需要 600ps。三条指令的执行时间,就需要 1800ps。

如果我们采用的是 6 级流水线 CPU,每一个 Pipeline 的 Stage 都只需要 100ps。那么,在这三个指令的执行过程中,在指令 1 的第一个 100ps 的 Stage 结束之后,第二条指令就开始执行了。在第二条指令的第一个 100ps 的 Stage 结束之后,第三条指令就开始执行了。这种情况下,这三条指令顺序执行所需要的总时间,就是 800ps。那么在 1800ps 内,使用流水线的 CPU 比单指令周期的 CPU 就可以多执行一倍以上的指令数。

虽然每一条指令从开始到结束拿到结果的时间并没有变化,也就是响应时间没有变化。但是同样时间内,完成的指令数增多了,也就是吞吐率上升了。

image.png

新的挑战:冒险和分支预测

那到这里可能你就要问了,这样看起来不是很好么?Intel 的 CPU 支持的指令集很大,我们之前说过有 2000 多条指令。有些指令很简单,执行也很快,比如无条件跳转指令,不需要通过 ALU 进行任何计算,只要更新一下 PC 寄存器里面的内容就好了。而有些指令很复杂,比如浮点数的运算,需要进行指数位比较、对齐,然后对有效位进行移位,然后再进行计算。两者的执行时间相差二三十倍也很正常。

既然这样,Pentium 4 的超长流水线看起来很合理呀,为什么 Pentium 4 最终成为 Intel 在技术架构层面的大失败呢?

第一个,自然是我们在第 3 讲里讲过的功耗问题。提升流水线深度,必须要和提升 CPU 主频同时进行。因为在单个 Pipeline Stage 能够执行的功能变简单了,也就意味着单个时钟周期内能够完成的事情变少了。所以,只有提升时钟周期,CPU 在指令的响应时间这个指标上才能保持和原来相同的性能。

同时,由于流水线深度的增加,我们需要的电路数量变多了,也就是我们所使用的晶体管也就变多了。

主频的提升和晶体管数量的增加都使得我们 CPU 的功耗变大了。这个问题导致了 Pentium 4 在整个生命周期里,都成为了耗电和散热的大户。而 Pentium 4 是在 2000~2004 年作为 Intel 的主打 CPU 出现在市场上的。这个时间段,正是笔记本电脑市场快速发展的时间。在笔记本电脑上,功耗和散热比起台式机是一个更严重的问题了。即使性能更好,别人的笔记本可以用上 2 小时,你的只能用 30 分钟,那谁也不爱买啊!

更何况,Pentium 4 的性能还更差一些。这个就要我们说到第二点了,就是上面说的流水线技术带来的性能提升,是一个理想情况。在实际的程序执行中,并不一定能够做得到。

还回到我们刚才举的三条指令的例子。如果这三条指令,是下面这样的三条代码,会发生什么情况呢?

int a = 10 + 5; // 指令1
int b = a * 2; // 指令2
float c = b * 1.0f; // 指令3

我们会发现,指令 2,不能在指令 1 的第一个 Stage 执行完成之后进行。因为指令 2,依赖指令 1 的计算结果。同样的,指令 3 也要依赖指令 2 的计算结果。这样,即使我们采用了流水线技术,这三条指令执行完成的时间,也是 200 + 300 + 600 = 1100 ps,而不是之前说的 800ps。而如果指令 1 和 2 都是浮点数运算,需要 600ps。那这个依赖关系会导致我们需要的时间变成 1800ps,和单指令周期 CPU 所要花费的时间是一样的。

这个依赖问题,就是我们在计算机组成里面所说的冒险(Hazard)问题。这里我们只列举了在数据层面的依赖,也就是数据冒险。在实际应用中,还会有结构冒险、控制冒险等其他的依赖问题。

对应这些冒险问题,我们也有在乱序执行、分支预测等相应的解决方案。我们在后面的几讲里面,会详细讲解对应的知识。

但是,我们的流水线越长,这个冒险的问题就越难一解决。这是因为,同一时间同时在运行的指令太多了。如果我们只有 3 级流水线,我们可以把后面没有依赖关系的指令放到前面来执行。这个就是我们所说的乱序执行的技术。比方说,我们可以扩展一下上面的 3 行代码,再加上几行代码。

CPU冒险

任何一本讲解 CPU 的流水线设计的教科书,都会提到流水线设计需要解决的三大冒险,分别是结构冒险(Structural Hazard)、数据冒险(Data Hazard)以及控制冒险(Control Hazard)。

这三大冒险的名字很有意思,它们都叫作 hazard(冒险)。喜欢玩游戏的话,你应该知道一个著名的游戏,生化危机,英文名就叫 Biohazard。的确,hazard 还有一个意思就是“危机”。那为什么在流水线设计里,hazard 没有翻译成“危机”,而是要叫“冒险”呢?

在 CPU 的流水线设计里,固然我们会遇到各种“危险”情况,使得流水线里的下一条指令不能正常运行。但是,我们其实还是通过“抢跑”的方式,“冒险”拿到了一个提升指令吞吐率的机会。流水线架构的 CPU,是我们主动进行的冒险选择。我们期望能够通过冒险带来更高的回报,所以,这不是无奈之下的应对之举,自然也算不上什么危机了。

事实上,对于各种冒险可能造成的问题,我们其实都准备好了应对的方案。这一讲里,我们先从结构冒险和数据冒险说起,一起来看看这些冒险及其对应的应对方案。

结构冒险:为什么工程师都喜欢用机械键盘?

我们先来看一看结构冒险。结构冒险,本质上是一个硬件层面的资源竞争问题,也就是一个硬件电路层面的问题。

CPU 在同一个时钟周期,同时在运行两条计算机指令的不同阶段。但是这两个不同的阶段,可能会用到同样的硬件电路。

最典型的例子就是内存的数据访问。请你看看下面这张示意图,其实就是第 20 讲里对应的 5 级流水线的示意图。

可以看到,在第 1 条指令执行到访存(MEM)阶段的时候,流水线里的第 4 条指令,在执行取指令(Fetch)的操作。访存和取指令,都要进行内存数据的读取。我们的内存,只有一个地址译码器的作为地址输入,那就只能在一个时钟周期里面读取一条数据,没办法同时执行第 1 条指令的读取内存数据和第 4 条指令的读取指令代码。

同一个时钟周期,两个不同指令访问同一个资源

image.png

类似的资源冲突,其实你在日常使用计算机的时候也会遇到。最常见的就是薄膜键盘的“锁键”问题。常用的最廉价的薄膜键盘,并不是每一个按键的背后都有一根独立的线路,而是多个键共用一个线路。如果我们在同一时间,按下两个共用一个线路的按键,这两个按键的信号就没办法都传输出去。

这也是为什么,重度键盘用户,都要买贵一点儿的机械键盘或者电容键盘。因为这些键盘的每个按键都有独立的传输线路,可以做到“全键无冲”,这样,无论你是要大量写文章、写程序,还是打游戏,都不会遇到按下了键却没生效的情况。

“全键无冲”这样的资源冲突解决方案,其实本质就是增加资源。同样的方案,我们一样可以用在 CPU 的结构冒险里面。对于访问内存数据和取指令的冲突,一个直观的解决方案就是把我们的内存分成两部分,让它们各有各的地址译码器。这两部分分别是存放指令的程序内存和存放数据的数据内存。

这样把内存拆成两部分的解决方案,在计算机体系结构里叫作哈佛架构(Harvard Architecture),来自哈佛大学设计Mark I 型计算机时候的设计。对应的,我们之前说的冯·诺依曼体系结构,又叫作普林斯顿架构(Princeton Architecture)。从这些名字里,我们可以看到,早年的计算机体系结构的设计,其实产生于美国各个高校之间的竞争中。

不过,我们今天使用的 CPU,仍然是冯·诺依曼体系结构的,并没有把内存拆成程序内存和数据内存这两部分。因为如果那样拆的话,对程序指令和数据需要的内存空间,我们就没有办法根据实际的应用去动态分配了。虽然解决了资源冲突的问题,但是也失去了灵活性。

现代 CPU 架构,借鉴了哈佛架构,在高速缓存层面拆分成指令缓存和数据缓存

image.png

不过,借鉴了哈佛结构的思路,现代的 CPU 虽然没有在内存层面进行对应的拆分,却在 CPU 内部的高速缓存部分进行了区分,把高速缓存分成了指令缓存(Instruction Cache)和数据缓存(Data Cache)两部分。

内存的访问速度远比 CPU 的速度要慢,所以现代的 CPU 并不会直接读取主内存。它会从主内存把指令和数据加载到高速缓存中,这样后续的访问都是访问高速缓存。而指令缓存和数据缓存的拆分,使得我们的 CPU 在进行数据访问和取指令的时候,不会再发生资源冲突的问题了。

数据冒险:三种不同的依赖关系

结构冒险是一个硬件层面的问题,我们可以靠增加硬件资源的方式来解决。然而还有很多冒险问题,是程序逻辑层面的事儿。其中,最常见的就是数据冒险。

数据冒险,其实就是同时在执行的多个指令之间,有数据依赖的情况。这些数据依赖,我们可以分成三大类,分别是先写后读(Read After Write,RAW)、先读后写(Write After Read,WAR)和写后再写(Write After Write,WAW)。下面,我们分别看一下这几种情况。

先写后读(Read After Write)

我们先来一起看看先写后读这种情况。这里有一段简单的 C 语言代码编译出来的汇编指令。这段代码简单地定义两个变量 a 和 b,然后计算 a = a + 2。再根据计算出来的结果,计算 b = a + 3。

int main() {
   0:   55                      push   rbp
   1:   48 89 e5                mov    rbp,rsp
  int a = 1;
   4:   c7 45 fc 01 00 00 00    mov    DWORD PTR [rbp-0x4],0x1
  int b = 2;
   b:   c7 45 f8 02 00 00 00    mov    DWORD PTR [rbp-0x8],0x2
  a = a + 2;
  12:   83 45 fc 02             add    DWORD PTR [rbp-0x4],0x2
  b = a + 3;
  16:   8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]
  19:   83 c0 03                add    eax,0x3
  1c:   89 45 f8                mov    DWORD PTR [rbp-0x8],eax
}
  1f:   5d                      pop    rbp
  20:   c3                      ret  

你可以看到,在内存地址为 12 的机器码,我们把 0x2 添加到 rbp-0x4 对应的内存地址里面。然后,在紧接着的内存地址为 16 的机器码,我们又要从 rbp-0x4 这个内存地址里面,把数据写入到 eax 这个寄存器里面。

所以,我们需要保证,在内存地址为 16 的指令读取 rbp-0x4 里面的值之前,内存地址 12 的指令写入到 rbp-0x4 的操作必须完成。这就是先写后读所面临的数据依赖。如果这个顺序保证不了,我们的程序就会出错。

这个先写后读的依赖关系,我们一般被称之为数据依赖,也就是 Data Dependency。

再等等:通过流水线停顿解决数据冒险

除了读之后再进行读,你会发现,对于同一个寄存器或者内存地址的操作,都有明确强制的顺序要求。而这个顺序操作的要求,也为我们使用流水线带来了很大的挑战。因为流水线架构的核心,就是在前一个指令还没有结束的时候,后面的指令就要开始执行。

所以,我们需要有解决这些数据冒险的办法。其中最简单的一个办法,不过也是最笨的一个办法,就是流水线停顿(Pipeline Stall),或者叫流水线冒泡(Pipeline Bubbling)。

流水线停顿的办法很容易理解。如果我们发现了后面执行的指令,会对前面执行的指令有数据层面的依赖关系,那最简单的办法就是“再等等”。我们在进行指令译码的时候,会拿到对应指令所需要访问的寄存器和内存地址。所以,在这个时候,我们能够判断出来,这个指令是否会触发数据冒险。如果会触发数据冒险,我们就可以决定,让整个流水线停顿一个或者多个周期。

image.png

我在前面说过,时钟信号会不停地在 0 和 1 之前自动切换。其实,我们并没有办法真的停顿下来。流水线的每一个操作步骤必须要干点儿事情。所以,在实践过程中,我们并不是让流水线停下来,而是在执行后面的操作步骤前面,插入一个 NOP 操作,也就是执行一个其实什么都不干的操作。

image.png

这个插入的指令,就好像一个水管(Pipeline)里面,进了一个空的气泡。在水流经过的时候,没有传送水到下一个步骤,而是给了一个什么都没有的空气泡。这也是为什么,我们的流水线停顿,又被叫作流水线冒泡(Pipeline Bubble)的原因。

NOP 操作和指令对齐

要想理解操作数前推技术,我们先来回顾一下,第 5 讲讲过的,MIPS 体系结构下的 R、I、J 三类指令,以及第 20 讲里的五级流水线“取指令(IF)- 指令译码(ID)- 指令执行(EX)- 内存访问(MEM)- 数据写回(WB) ”。

在 MIPS 的体系结构下,不同类型的指令,会在流水线的不同阶段进行不同的操作。

我们以 MIPS 的 LOAD,这样从内存里读取数据到寄存器的指令为例,来仔细看看,它需要经历的 5 个完整的流水线。STORE 这样从寄存器往内存里写数据的指令,不需要有写回寄存器的操作,也就是没有数据写回的流水线阶段。至于像 ADD 和 SUB 这样的加减法指令,所有操作都在寄存器完成,所以没有实际的内存访问(MEM)操作。

image.png

有些指令没有对应的流水线阶段,但是我们并不能跳过对应的阶段直接执行下一阶段。不然,如果我们先后执行一条 LOAD 指令和一条 ADD 指令,就会发生 LOAD 指令的 WB 阶段和 ADD 指令的 WB 阶段,在同一个时钟周期发生。这样,相当于触发了一个结构冒险事件,产生了资源竞争。

image.png

所以,在实践当中,各个指令不需要的阶段,并不会直接跳过,而是会运行一次 NOP 操作。通过插入一个 NOP 操作,我们可以使后一条指令的每一个 Stage,一定不和前一条指令的同 Stage 在一个时钟周期执行。这样,就不会发生先后两个指令,在同一时钟周期竞争相同的资源,产生结构冒险了。

image.png

流水线里的接力赛:操作数前推

通过 NOP 操作进行对齐,我们在流水线里,就不会遇到资源竞争产生的结构冒险问题了。除了可以解决结构冒险之外,这个 NOP 操作,也是我们之前讲的流水线停顿插入的对应操作。

但是,插入过多的 NOP 操作,意味着我们的 CPU 总是在空转,干吃饭不干活。那么,我们有没有什么办法,尽量少插入一些 NOP 操作呢?不要着急,下面我们就以两条先后发生的 ADD 指令作为例子,看看能不能找到一些好的解决方案。

add $t0, $s2,$s1
add $s2, $s1,$t0

这两条指令很简单。

  1. 第一条指令,把 s1 和 s2 寄存器里面的数据相加,存入到 t0 这个寄存器里面。
  2. 第二条指令,把 s1 和 t0 寄存器里面的数据相加,存入到 s2 这个寄存器里面。

因为后一条的 add 指令,依赖寄存器 t0 里的值。而 t0 里面的值,又来自于前一条指令的计算结果。所以后一条指令,需要等待前一条指令的数据写回阶段完成之后,才能执行。就像上一讲里讲的那样,我们遇到了一个数据依赖类型的冒险。于是,我们就不得不通过流水线停顿来解决这个冒险问题。我们要在第二条指令的译码阶段之后,插入对应的 NOP 指令,直到前一天指令的数据写回完成之后,才能继续执行。

这样的方案,虽然解决了数据冒险的问题,但是也浪费了两个时钟周期。我们的第 2 条指令,其实就是多花了 2 个时钟周期,运行了两次空转的 NOP 操作。

image.png

不过,其实我们第二条指令的执行,未必要等待第一条指令写回完成,才能进行。如果我们第一条指令的执行结果,能够直接传输给第二条指令的执行阶段,作为输入,那我们的第二条指令,就不用再从寄存器里面,把数据再单独读出来一次,才来执行代码。

我们完全可以在第一条指令的执行阶段完成之后,直接将结果数据传输给到下一条指令的 ALU。然后,下一条指令不需要再插入两个 NOP 阶段,就可以继续正常走到执行阶段。

image.png

这样的解决方案,我们就叫作操作数前推(Operand Forwarding),或者操作数旁路(Operand Bypassing)。其实我觉得,更合适的名字应该叫操作数转发。这里的 Forward,其实就是我们写 Email 时的“转发”(Forward)的意思。不过现有的经典教材的中文翻译一般都叫“前推”,我们也就不去纠正这个说法了,你明白这个意思就好。

转发,其实是这个技术的逻辑含义,也就是在第 1 条指令的执行结果,直接“转发”给了第 2 条指令的 ALU 作为输入。另外一个名字,旁路(Bypassing),则是这个技术的硬件含义。为了能够实现这里的“转发”,我们在 CPU 的硬件里面,需要再单独拉一根信号传输的线路出来,使得 ALU 的计算结果,能够重新回到 ALU 的输入里来。这样的一条线路,就是我们的“旁路”。它越过(Bypass)了写入寄存器,再从寄存器读出的过程,也为我们节省了 2 个时钟周期。

操作数前推的解决方案不但可以单独使用,还可以和流水线冒泡一起使用。有的时候,虽然我们可以把操作数转发到下一条指令,但是下一条指令仍然需要停顿一个时钟周期。

比如说,我们先去执行一条 LOAD 指令,再去执行 ADD 指令。LOAD 指令在访存阶段才能把数据读取出来,所以下一条指令的执行阶段,需要在访存阶段完成之后,才能进行。

image.png

总的来说,操作数前推的解决方案,比流水线停顿更进了一步。流水线停顿的方案,有点儿像游泳比赛的接力方式。下一名运动员,需要在前一个运动员游玩了全程之后,触碰到了游泳池壁才能出发。而操作数前推,就好像短跑接力赛。后一个运动员可以提前抢跑,而前一个运动员会多跑一段主动把交接棒传递给他。

填上空闲的 NOP:上菜的顺序不必是点菜的顺序

但是这个“阻塞”很多时候是没有必要的。因为尽管你的代码生成的指令是顺序的,但是如果后面的指令不需要依赖前面指令的执行结果,完全可以不必等待前面的指令运算完成。

a = b + c
d = a * e
x = y * z

计算里面的 x ,却要等待 a 和 d 都计算完成,实在没啥必要。所以我们完全可以在 d 的计算等待 a 的计算的过程中,先把 x 的结果给算出来。

在流水线里,后面的指令不依赖前面的指令,那就不用等待前面的指令执行,它完全可以先执行。

image.png

可以看到,因为第三条指令并不依赖于前两条指令的计算结果,所以在第二条指令等待第一条指令的访存和写回阶段的时候,第三条指令就已经执行完成了。

这样的解决方案,在计算机组成里面,被称为乱序执行(Out-of-Order Execution,OoOE)。乱序执行,最早来自于著名的 IBM 360。相信你一定听说过《人月神话》这本软件工程届的经典著作,它讲的就是 IBM 360 开发过程中的“人生体会”。而 IBM 360 困难的开发过程,也少不了第一次引入乱序执行这个新的 CPU 技术。

CPU 里的“线程池”:理解乱序执行

使用乱序执行技术后,CPU 里的流水线就和我之前给你看的 5 级流水线不太一样了。我们一起来看一看下面这张图。

image.png

  1. 在取指令和指令译码的时候,乱序执行的 CPU 和其他使用流水线架构的 CPU 是一样的。它会一级一级顺序地进行取指令和指令译码的工作。
  2. 在指令译码完成之后,就不一样了。CPU 不会直接进行指令执行,而是进行一次指令分发,把指令发到一个叫作保留站(Reservation Stations)的地方。顾名思义,这个保留站,就像一个火车站一样。发送到车站的指令,就像是一列列的火车。
  3. 这些指令不会立刻执行,而要等待它们所依赖的数据,传递给它们之后才会执行。这就好像一列列的火车都要等到乘客来齐了才能出发。
  4. 一旦指令依赖的数据来齐了,指令就可以交到后面的功能单元(Function Unit,FU),其实就是 ALU,去执行了。我们有很多功能单元可以并行运行,但是不同的功能单元能够支持执行的指令并不相同。就和我们的铁轨一样,有些从上海北上,可以到北京和哈尔滨;有些是南下的,可以到广州和深圳。
  5. 指令执行的阶段完成之后,我们并不能立刻把结果写回到寄存器里面去,而是把结果再存放到一个叫作重排序缓冲区(Re-Order Buffer,ROB)的地方。
  6. 在重排序缓冲区里,我们的 CPU 会按照取指令的顺序,对指令的计算结果重新排序。只有排在前面的指令都已经完成了,才会提交指令,完成整个指令的运算结果。
  7. 实际的指令的计算结果数据,并不是直接写到内存或者高速缓存里,而是先写入存储缓冲区(Store Buffer 面,最终才会写入到高速缓存和内存里。

可以看到,在乱序执行的情况下,只有 CPU 内部指令的执行层面,可能是“乱序”的。只要我们能在指令的译码阶段正确地分析出指令之间的数据依赖关系,这个“乱序”就只会在互相没有影响的指令之间发生。

有了乱序执行,我们重新去执行上面的 3 行代码。

a = b + c
d = a * e
x = y * z

里面的 d 依赖于 a 的计算结果,不会在 a 的计算完成之前执行。但是我们的 CPU 并不会闲着,因为 x = y * z 的指令同样会被分发到保留站里。因为 x 所依赖的 y 和 z 的数据是准备好的, 这里的乘法运算不会等待计算 d,而会先去计算 x 的值。

如果我们只有一个 FU 能够计算乘法,那么这个 FU 并不会因为 d 要等待 a 的计算结果,而被闲置,而是会先被拿去计算 x。

在 x 计算完成之后,d 也等来了 a 的计算结果。这个时候,我们的 FU 就会去计算出 d 的结果。然后在重排序缓冲区里,把对应的计算结果的提交顺序,仍然设置成 a -> d -> x,而计算完成的顺序是 x -> a -> d。

在这整个过程中,整个计算乘法的 FU 都没有闲置,这也意味着我们的 CPU 的吞吐率最大化了。

整个乱序执行技术,就好像在指令的执行阶段提供一个“线程池”。指令不再是顺序执行的,而是根据池里所拥有的资源,以及各个任务是否可以进行执行,进行动态调度。在执行完成之后,又重新把结果在一个队列里面,按照指令的分发顺序重新排序。即使内部是“乱序”的,但是在外部看起来,仍然是井井有条地顺序执行。

乱序执行,极大地提高了 CPU 的运行效率。核心原因是,现代 CPU 的运行速度比访问主内存的速度要快很多。如果完全采用顺序执行的方式,很多时间都会浪费在前面指令等待获取内存数据的时间里。CPU 不得不加入 NOP 操作进行空转。而现代 CPU 的流水线级数也已经相对比较深了,到达了 14 级。这也意味着,同一个时钟周期内并行执行的指令数是很多的。

而乱序执行,以及我们后面要讲的高速缓存,弥补了 CPU 和内存之间的性能差异。同样,也充分利用了较深的流水行带来的并发性,使得我们可以充分利用 CPU 的性能。

控制冒险(Control Harzard)

在遇到了控制冒险之后,我们的 CPU 具体会怎么应对呢?除了流水线停顿,等待前面的 jmp 指令执行完成之后,再去取最新的指令,还有什么好办法吗?当然是有的。我们一起来看一看。

缩短分支延迟

第一个办法,叫作缩短分支延迟。回想一下我们的条件跳转指令,条件跳转指令其实进行了两种电路操作。

第一种,是进行条件比较。这个条件比较,需要的输入是,根据指令的 opcode,就能确认的条件码寄存器。

第二种,是进行实际的跳转,也就是把要跳转的地址信息写入到 PC 寄存器。无论是 opcode,还是对应的条件码寄存器,还是我们跳转的地址,都是在指令译码(ID)的阶段就能获得的。而对应的条件码比较的电路,只要是简单的逻辑门电路就可以了,并不需要一个完整而复杂的 ALU。

所以,我们可以将条件判断、地址跳转,都提前到指令译码阶段进行,而不需要放在指令执行阶段。对应的,我们也要在 CPU 里面设计对应的旁路,在指令译码阶段,就提供对应的判断比较的电路。

这种方式,本质上和前面数据冒险的操作数前推的解决方案类似,就是在硬件电路层面,把一些计算结果更早地反馈到流水线中。这样反馈变得更快了,后面的指令需要等待的时间就变短了。

不过只是改造硬件,并不能彻底解决问题。跳转指令的比较结果,仍然要在指令执行的时候才能知道。在流水线里,第一条指令进行指令译码的时钟周期里,我们其实就要去取下一条指令了。这个时候,我们其实还没有开始指令执行阶段,自然也就不知道比较的结果。

分支预测

所以,这个时候,我们就引入了一个新的解决方案,叫作分支预测(Branch Prediction)技术,也就是说,让我们的 CPU 来猜一猜,条件跳转后执行的指令,应该是哪一条。

最简单的分支预测技术,叫作“假装分支不发生”。顾名思义,自然就是仍然按照顺序,把指令往下执行。其实就是 CPU 预测,条件跳转一定不发生。这样的预测方法,其实也是一种静态预测技术。就好像猜硬币的时候,你一直猜正面,会有 50% 的正确率。

如果分支预测是正确的,我们自然赚到了。这个意味着,我们节省下来本来需要停顿下来等待的时间。如果分支预测失败了呢?那我们就把后面已经取出指令已经执行的部分,给丢弃掉。这个丢弃的操作,在流水线里面,叫作 Zap 或者 Flush。CPU 不仅要执行后面的指令,对于这些已经在流水线里面执行到一半的指令,我们还需要做对应的清除操作。比如,清空已经使用的寄存器里面的数据等等,这些清除操作,也有一定的开销。

所以,CPU 需要提供对应的丢弃指令的功能,通过控制信号清除掉已经在流水线中执行的指令。只要对应的清除开销不要太大,我们就是划得来的。

image.png

动态分支预测

上面的静态预测策略,看起来比较简单,预测的准确率也许有 50%。但是如果运气不好,可能就会特别差。于是,工程师们就开始思考,我们有没有更好的办法呢?比如,根据之前条件跳转的比较结果来预测,是不是会更准一点?

而同样的策略,我们一样可以放在分支预测上。这种策略,我们叫一级分支预测(One Level Branch Prediction),或者叫 1 比特饱和计数(1-bit saturating counter)。这个方法,其实就是用一个比特,去记录当前分支的比较情况,直接用当前分支的比较情况,来预测下一次分支时候的比较情况。

只用一天下雨,就预测第二天下雨,这个方法还是有些“草率”,我们可以用更多的信息,而不只是一次的分支信息来进行预测。于是,我们可以引入一个状态机(State Machine)来做这个事情。

这个状态机里,我们一共有 4 个状态,所以我们需要 2 个比特来记录对应的状态。这样这整个策略,就可以叫作 2 比特饱和计数,或者叫双模态预测器(Bimodal Predictor)。

第一种方案,类似我们的操作数前推,其实是在改造我们的 CPU 功能,通过增加对应的电路的方式,来缩短分支带来的延迟。另外两种解决方案,无论是“假装分支不发生”,还是“动态分支预测”,其实都是在进行“分支预测”。只是,“假装分支不发生”是一种简单的静态预测方案而已。

在动态分支预测技术里,我给你介绍了一级分支预测,或者叫 1 比特饱和计数的方法。其实就是认为,预测结果和上一次的条件跳转是一致的。在此基础上,我还介绍了利用更多信息的,就是 2 比特饱和计数,或者叫双模态预测器的方法。这个方法其实也只是通过一个状态机,多看了一步过去的跳转比较结果。

这个方法虽然简单,但是却非常有效。在 SPEC 89 版本的测试当中,使用这样的饱和计数方法,预测的准确率能够高达 93.5%。Intel 的 CPU,一直到 Pentium 时代,在还没有使用 MMX 指令集的时候,用的就是这种分支预测方式。

image.png

多发射与超标量:同一时间执行的两条指令

其实只要我们把取指令和指令译码,也一样通过增加硬件的方式,并行进行就好了。我们可以一次性从内存里面取出多条指令,然后分发给多个并行的指令译码器,进行译码,然后对应交给不同的功能单元去处理。这样,我们在一个时钟周期里,能够完成的指令就不只一条了。IPC 也就能做到大于 1 了。

image.png

这种 CPU 设计,我们叫作多发射(Mulitple Issue)超标量(Superscalar)

什么叫多发射呢?这个词听起来很抽象,其实它意思就是说,我们同一个时间,可能会同时把多条指令发射(Issue)到不同的译码器或者后续处理的流水线中去。

在超标量的 CPU 里面,有很多条并行的流水线,而不是只有一条流水线。“超标量“这个词是说,本来我们在一个时钟周期里面,只能执行一个标量(Scalar)的运算。在多发射的情况下,我们就能够超越这个限制,同时进行多次计算。

image.png

你可以看我画的这个超标量设计的流水线示意图。仔细看,你应该能看到一个有意思的现象,每一个功能单元的流水线的长度是不同的。事实上,不同的功能单元的流水线长度本来就不一样。我们平时所说的 14 级流水线,指的通常是进行整数计算指令的流水线长度。如果是浮点数运算,实际的流水线长度则会更长一些。

超线程:Intel 多卖给你的那一倍 CPU

不知道是不是因为当时面临的竞争太激烈了,为了让 Pentium 4 的 CPU 在性能上更有竞争力一点,2002 年底,Intel 在的 3.06GHz 主频的 Pentium 4 CPU 上,第一次引入了超线程(Hyper-Threading)技术。

什么是超线程技术呢?Intel 想,既然 CPU 同时运行那些在代码层面有前后依赖关系的指令,会遇到各种冒险问题,我们不如去找一些和这些指令完全独立,没有依赖关系的指令来运行好了。那么,这样的指令哪里来呢?自然同时运行在另外一个程序里了。

比如,在一个物理 CPU 核心内部,会有双份的 PC 寄存器、指令寄存器乃至条件码寄存器。这样,这个 CPU 核心就可以维护两条并行的指令的状态。在外面看起来,似乎有两个逻辑层面的 CPU 在同时运行。所以,超线程技术一般也被叫作同时多线程(Simultaneous Multi-Threading,简称 SMT)技术。

不过,在 CPU 的其他功能组件上,Intel 可不会提供双份。无论是指令译码器还是 ALU,一个 CPU 核心仍然只有一份。因为超线程并不是真的去同时运行两个指令,那就真的变成物理多核了。超线程的目的,是在一个线程 A 的指令,在流水线里停顿的时候,让另外一个线程去执行指令。因为这个时候,CPU 的译码器和 ALU 就空出来了,那么另外一个线程 B,就可以拿来干自己需要的事情。这个线程 B 可没有对于线程 A 里面指令的关联和依赖。

SIMD:如何加速矩阵乘法?

在上面的 CPU 信息的图里面,你会看到,中间有一组信息叫作 Instructions,里面写了有 MMX、SSE 等等。这些信息就是这个 CPU 所支持的指令集。这里的 MMX 和 SSE 的指令集,也就引出了我要给你讲的最后一个提升 CPU 性能的技术方案,SIMD,中文叫作单指令多数据流(Single Instruction Multiple Data)。

我们先来体会一下 SIMD 的性能到底怎么样。下面是两段示例程序,一段呢,是通过循环的方式,给一个 list 里面的每一个数加 1。另一段呢,是实现相同的功能,但是直接调用 NumPy 这个库的 add 方法。在统计两段程序的性能的时候,我直接调用了 Python 里面的 timeit 的库。

$ python
>>> import numpy as np
>>> import timeit
>>> a = list(range(1000))
>>> b = np.array(range(1000))
>>> timeit.timeit("[i + 1 for i in a]", setup="from __main__ import a", number=1000000)
32.82800309999993
>>> timeit.timeit("np.add(1, b)", setup="from __main__ import np, b", number=1000000)
0.9787889999997788
>>>

从两段程序的输出结果来看,你会发现,两个功能相同的代码性能有着巨大的差异,足足差出了 30 多倍。也难怪所有用 Python 讲解数据科学的教程里,往往在一开始就告诉你不要使用循环,而要把所有的计算都向量化(Vectorize)。

有些同学可能会猜测,是不是因为 Python 是一门解释性的语言,所以这个性能差异会那么大。第一段程序的循环的每一次操作都需要 Python 解释器来执行,而第二段的函数调用是一次调用编译好的原生代码,所以才会那么快。如果你这么想,不妨试试直接用 C 语言实现一下 1000 个元素的数组里面的每个数加 1。你会发现,即使是 C 语言编译出来的代码,还是远远低于 NumPy。原因就是,NumPy 直接用到了 SIMD 指令,能够并行进行向量的操作。

而前面使用循环来一步一步计算的算法呢,一般被称为 SISD,也就是单指令单数据(Single Instruction Single Data)的处理方式。如果你手头的是一个多核 CPU 呢,那么它同时处理多个指令的方式可以叫作 MIMD,也就是多指令多数据(Multiple Instruction Multiple Dataa)。

为什么 SIMD 指令能快那么多呢?这是因为,SIMD 在获取数据和执行指令的时候,都做到了并行。一方面,在从内存里面读取数据的时候,SIMD 是一次性读取多个数据。

就以我们上面的程序为例,数组里面的每一项都是一个 integer,也就是需要 4 Bytes 的内存空间。Intel 在引入 SSE 指令集的时候,在 CPU 里面添上了 8 个 128 Bits 的寄存器。128 Bits 也就是 16 Bytes ,也就是说,一个寄存器一次性可以加载 4 个整数。比起循环分别读取 4 次对应的数据,时间就省下来了。

image.png

在数据读取到了之后,在指令的执行层面,SIMD 也是可以并行进行的。4 个整数各自加 1,互相之前完全没有依赖,也就没有冒险问题需要处理。只要 CPU 里有足够多的功能单元,能够同时进行这些计算,这个加法就是 4 路同时并行的,自然也省下了时间。

所以,对于那些在计算层面存在大量“数据并行”(Data Parallelism)的计算中,使用 SIMD 是一个很划算的办法。在这个大量的“数据并行”,其实通常就是实践当中的向量运算或者矩阵运算。在实际的程序开发过程中,过去通常是在进行图片、视频、音频的处理。最近几年则通常是在进行各种机器学习算法的计算。

而基于 SIMD 的向量计算指令,也正是在 Intel 发布 Pentium 处理器的时候,被引入的指令集。当时的指令集叫作 MMX,也就是 Matrix Math eXtensions 的缩写,中文名字就是矩阵数学扩展。而 Pentium 处理器,也是 CPU 第一次有能力进行多媒体处理。这也正是拜 SIMD 和 MMX 所赐。

异常的分类:中断、陷阱、故障和中止

我在前面说了,异常可以由硬件触发,也可以由软件触发。那我们平时会碰到哪些异常呢?下面我们就一起来看看。

第一种异常叫中断(Interrupt)。顾名思义,自然就是程序在执行到一半的时候,被打断了。这个打断执行的信号,来自于 CPU 外部的 I/O 设备。你在键盘上按下一个按键,就会对应触发一个相应的信号到达 CPU 里面。CPU 里面某个开关的值发生了变化,也就触发了一个中断类型的异常。

第二种异常叫陷阱(Trap)。陷阱,其实是我们程序员“故意“主动触发的异常。就好像你在程序里面打了一个断点,这个断点就是设下的一个”陷阱”。当程序的指令执行到这个位置的时候,就掉到了这个陷阱当中。然后,对应的异常处理程序就会来处理这个”陷阱”当中的猎物。

最常见的一类陷阱,发生在我们的应用程序调用系统调用的时候,也就是从程序的用户态切换到内核态的时候。我们在第 3 讲讲 CPU 性能的时候说过,可以用 Linux 下的 time 指令,去查看一个程序运行实际花费的时间,里面有在用户态花费的时间(user time),也有在内核态发生的时间(system time)。

我们的应用程序通过系统调用去读取文件、创建进程,其实也是通过触发一次陷阱来进行的。这是因为,我们用户态的应用程序没有权限来做这些事情,需要把对应的流程转交给有权限的异常处理程序来进行。

第三种异常叫故障(Fault)。它和陷阱的区别在于,陷阱是我们开发程序的时候刻意触发的异常,而故障通常不是。比如,我们在程序执行的过程中,进行加法计算发生了溢出,其实就是故障类型的异常。这个异常不是我们在开发的时候计划内的,也一样需要有对应的异常处理程序去处理。

故障和陷阱、中断的一个重要区别是,故障在异常程序处理完成之后,仍然回来处理当前的指令,而不是去执行程序中的下一条指令。因为当前的指令因为故障的原因并没有成功执行完成。

最后一种异常叫中止(Abort)。与其说这是一种异常类型,不如说这是故障的一种特殊情况。当 CPU 遇到了故障,但是恢复不过来的时候,程序就不得不中止了。

81E033D3-9A7F-45ED-A65D-6DC7815D3040.png

CISC和RISC

image.png

于是,从 Pentium Pro 时代开始,Intel 就开始在处理器里引入了微指令(Micro-Instructions/Micro-Ops)架构。而微指令架构的引入,也让 CISC 和 RISC 的分界变得模糊了。

image.png

在微指令架构的 CPU 里面,编译器编译出来的机器码和汇编代码并没有发生什么变化。但在指令译码的阶段,指令译码器“翻译”出来的,不再是某一条 CPU 指令。译码器会把一条机器码,“翻译”成好几条“微指令”。这里的一条条微指令,就不再是 CISC 风格的了,而是变成了固定长度的 RISC 风格的了。

这些 RISC 风格的微指令,会被放到一个微指令缓冲区里面,然后再从缓冲区里面,分发给到后面的超标量,并且是乱序执行的流水线架构里面。不过这个流水线架构里面接受的,就不是复杂的指令,而是精简的指令了。在这个架构里,我们的指令译码器相当于变成了设计模式里的一个“适配器”(Adaptor)。这个适配器,填平了 CISC 和 RISC 之间的指令差异。

不过,凡事有好处就有坏处。这样一个能够把 CISC 的指令译码成 RISC 指令的指令译码器,比原来的指令译码器要复杂。这也就意味着更复杂的电路和更长的译码时间:本来以为可以通过 RISC 提升的性能,结果又有一部分浪费在了指令译码上。针对这个问题,我们有没有更好的办法呢?

我在前面说过,之所以大家认为 RISC 优于 CISC,来自于一个数字统计,那就是在实际的程序运行过程中,有 80% 运行的代码用着 20% 的常用指令。这意味着,CPU 里执行的代码有很强的局部性。而对于有着很强局部性的问题,常见的一个解决方案就是使用缓存。

所以,Intel 就在 CPU 里面加了一层 L0 Cache。这个 Cache 保存的就是指令译码器把 CISC 的指令“翻译”成 RISC 的微指令的结果。于是,在大部分情况下,CPU 都可以从 Cache 里面拿到译码结果,而不需要让译码器去进行实际的译码操作。这样不仅优化了性能,因为译码器的晶体管开关动作变少了,还减少了功耗。

因为“微指令”架构的存在,从 Pentium Pro 开始,Intel 处理器已经不是一个纯粹的 CISC 处理器了。它同样融合了大量 RISC 类型的处理器设计。不过,由于 Intel 本身在 CPU 层面做的大量优化,比如乱序执行、分支预测等相关工作,x86 的 CPU 始终在功耗上还是要远远超过 RISC 架构的 ARM,所以最终在智能手机崛起替代 PC 的时代,落在了 ARM 后面。

ARM 和 RISC-V:CPU 的现在与未来

2017 年,ARM 公司的 CEO Simon Segards 宣布,ARM 累积销售的芯片数量超过了 1000 亿。作为一个从 12 个人起步,在 80 年代想要获取 Intel 的 80286 架构授权来制造 CPU 的公司,ARM 是如何在移动端把自己的芯片塑造成了最终的霸主呢?

ARM 这个名字现在的含义,是“Advanced RISC Machines”。你从名字就能够看出来,ARM 的芯片是基于 RISC 架构的。不过,ARM 能够在移动端战胜 Intel,并不是因为 RISC 架构。

到了 21 世纪的今天,CISC 和 RISC 架构的分界已经没有那么明显了。Intel 和 AMD 的 CPU 也都是采用译码成 RISC 风格的微指令来运行。而 ARM 的芯片,一条指令同样需要多个时钟周期,有乱序执行和多发射。我甚至看到过这样的评价,“ARM 和 RISC 的关系,只有在名字上”。

ARM 真正能够战胜 Intel,我觉得主要是因为下面这两点原因。

第一点是功耗优先的设计。一个 4 核的 Intel i7 的 CPU,设计的时候功率就是 130W。而一块 ARM A8 的单个核心的 CPU,设计功率只有 2W。两者之间差出了 100 倍。在移动设备上,功耗是一个远比性能更重要的指标,毕竟我们不能随时在身上带个发电机。ARM 的 CPU,主频更低,晶体管更少,高速缓存更小,乱序执行的能力更弱。所有这些,都是为了功耗所做的妥协。

第二点则是低价。ARM 并没有自己垄断 CPU 的生产和制造,只是进行 CPU 设计,然后把对应的知识产权授权出去,让其他的厂商来生产 ARM 架构的 CPU。它甚至还允许这些厂商可以基于 ARM 的架构和指令集,设计属于自己的 CPU。像苹果、三星、华为,它们都是拿到了基于 ARM 体系架构设计和制造 CPU 的授权。ARM 自己只是收取对应的专利授权费用。多个厂商之间的竞争,使得 ARM 的芯片在市场上价格很便宜。所以,尽管 ARM 的芯片的出货量远大于 Intel,但是收入和利润却比不上 Intel。

不过,ARM 并不是开源的。所以,在 ARM 架构逐渐垄断移动端芯片市场的时候,“开源硬件”也慢慢发展起来了。一方面,MIPS 在 2019 年宣布开源;另一方面,从 UC Berkeley 发起的RISC-V项目也越来越受到大家的关注。而 RISC 概念的发明人,图灵奖的得主大卫·帕特森教授从伯克利退休之后,成了 RISC-V 国际开源实验室的负责人,开始推动 RISC-V 这个“CPU 届的 Linux”的开发。可以想见,未来的开源 CPU,也多半会像 Linux 一样,逐渐成为一个业界的主流选择。如果想要“打造一个属于自己 CPU”,不可不关注这个项目。

GPU

这个对于图像进行实时渲染的过程,可以被分解成下面这样 5 个步骤:

  • 顶点处理(Vertex Processing)
  • 图元处理(Primitive Processing)
  • 栅格化(Rasterization)
  • 片段处理(Fragment Processing)
  • 像素操作(Pixel Operations)

解放图形渲染的 GPU

我们可以想一想,如果用 CPU 来进行这个渲染过程,需要花上多少资源呢?我们可以通过一些数据来做个粗略的估算。

在上世纪 90 年代的时候,屏幕的分辨率还没有现在那么高。一般的 CRT 显示器也就是 640×480 的分辨率。这意味着屏幕上有 30 万个像素需要渲染。为了让我们的眼睛看到画面不晕眩,我们希望画面能有 60 帧。于是,每秒我们就要重新渲染 60 次这个画面。也就是说,每秒我们需要完成 1800 万次单个像素的渲染。从栅格化开始,每个像素有 3 个流水线步骤,即使每次步骤只有 1 个指令,那我们也需要 5400 万条指令,也就是 54M 条指令。

90 年代的 CPU 的性能是多少呢?93 年出货的第一代 Pentium 处理器,主频是 60MHz,后续逐步推出了 66MHz、75MHz、100MHz 的处理器。以这个性能来看,用 CPU 来渲染 3D 图形,基本上就要把 CPU 的性能用完了。因为实际的每一个渲染步骤可能不止一个指令,我们的 CPU 可能根本就跑不动这样的三维图形渲染。

也就是在这个时候,Voodoo FX 这样的图形加速卡登上了历史舞台。既然图形渲染的流程是固定的,那我们直接用硬件来处理这部分过程,不用 CPU 来计算是不是就好了?很显然,这样的硬件会比制造有同样计算性能的 CPU 要便宜得多。因为整个计算流程是完全固定的,不需要流水线停顿、乱序执行等等的各类导致 CPU 计算变得复杂的问题。我们也不需要有什么可编程能力,只要让硬件按照写好的逻辑进行运算就好了。

那个时候,整个顶点处理的过程还是都由 CPU 进行的,不过后续所有到图元和像素级别的处理都是通过 Voodoo FX 或者 TNT 这样的显卡去处理的。也就是从这个时代开始,我们能玩上“真 3D”的游戏了。

image.png

不过,无论是 Voodoo FX 还是 NVidia TNT。整个显卡的架构还不同于我们现代的显卡,也没有现代显卡去进行各种加速深度学习的能力。这个能力,要到 NVidia 提出 Unified Shader Archicture 才开始具备。这也是我们下一讲要讲的内容。

Shader 的诞生和可编程图形处理器

不知道你有没有发现,在 Voodoo 和 TNT 显卡的渲染管线里面,没有“顶点处理“这个步骤。在当时,把多边形的顶点进行线性变化,转化到我们的屏幕的坐标系的工作还是由 CPU 完成的。所以,CPU 的性能越好,能够支持的多边形也就越多,对应的多边形建模的效果自然也就越像真人。而 3D 游戏的多边形性能也受限于我们 CPU 的性能。无论你的显卡有多快,如果 CPU 不行,3D 画面一样还是不行。

所以,1999 年 NVidia 推出的 GeForce 256 显卡,就把顶点处理的计算能力,也从 CPU 里挪到了显卡里。不过,这对于想要做好 3D 游戏的程序员们还不够,即使到了 GeForce 256。整个图形渲染过程都是在硬件里面固定的管线来完成的。程序员们在加速卡上能做的事情呢,只有改配置来实现不同的图形渲染效果。如果通过改配置做不到,我们就没有什么办法了。

这个时候,程序员希望我们的 GPU 也能有一定的可编程能力。这个编程能力不是像 CPU 那样,有非常通用的指令,可以进行任何你希望的操作,而是在整个的渲染管线(Graphics Pipeline)的一些特别步骤,能够自己去定义处理数据的算法或者操作。于是,从 2001 年的 Direct3D 8.0 开始,微软第一次引入了可编程管线(Programable Function Pipeline)的概念。

早期的可编程管线的 GPU,提供了单独的顶点处理和片段处理(像素处理)的着色器

image.png

一开始的可编程管线呢,仅限于顶点处理(Vertex Processing)和片段处理(Fragment Processing)部分。比起原来只能通过显卡和 Direct3D 这样的图形接口提供的固定配置,程序员们终于也可以开始在图形效果上开始大显身手了。

这些可以编程的接口,我们称之为 Shader,中文名称就是着色器。之所以叫“着色器”,是因为一开始这些“可编程”的接口,只能修改顶点处理和片段处理部分的程序逻辑。我们用这些接口来做的,也主要是光照、亮度、颜色等等的处理,所以叫着色器。

这个时候的 GPU,有两类 Shader,也就是 Vertex Shader 和 Fragment Shader。我们在上一讲看到,在进行顶点处理的时候,我们操作的是多边形的顶点;在片段操作的时候,我们操作的是屏幕上的像素点。对于顶点的操作,通常比片段要复杂一些。所以一开始,这两类 Shader 都是独立的硬件电路,也各自有独立的编程接口。因为这么做,硬件设计起来更加简单,一块 GPU 上也能容纳下更多的 Shader。

不过呢,大家很快发现,虽然我们在顶点处理和片段处理上的具体逻辑不太一样,但是里面用到的指令集可以用同一套。而且,虽然把 Vertex Shader 和 Fragment Shader 分开,可以减少硬件设计的复杂程度,但是也带来了一种浪费,有一半 Shader 始终没有被使用。在整个渲染管线里,Vertext Shader 运行的时候,Fragment Shader 停在那里什么也没干。Fragment Shader 在运行的时候,Vertext Shader 也停在那里发呆。

本来 GPU 就不便宜,结果设计的电路有一半时间是闲着的。喜欢精打细算抠出每一分性能的硬件工程师当然受不了了。于是,统一着色器架构(Unified Shader Architecture)就应运而生了。

既然大家用的指令集是一样的,那不如就在 GPU 里面放很多个一样的 Shader 硬件电路,然后通过统一调度,把顶点处理、图元处理、片段处理这些任务,都交给这些 Shader 去处理,让整个 GPU 尽可能地忙起来。这样的设计,就是我们现代 GPU 的设计,就是统一着色器架构。

有意思的是,这样的 GPU 并不是先在 PC 里面出现的,而是来自于一台游戏机,就是微软的 XBox 360。后来,这个架构才被用到 ATI 和 NVidia 的显卡里。这个时候的“着色器”的作用,其实已经和它的名字关系不大了,而是变成了一个通用的抽象计算模块的名字。

正是因为 Shader 变成一个“通用”的模块,才有了把 GPU 拿来做各种通用计算的用法,也就是 GPGPU(General-Purpose Computing on Graphics Processing Units,通用图形处理器)。而正是因为 GPU 可以拿来做各种通用的计算,才有了过去 10 年深度学习的火热。

image.png

现代 GPU 的三个核心创意

芯片瘦身

我们先来回顾一下,之前花了很多讲仔细讲解的现代 CPU。现代 CPU 里的晶体管变得越来越多,越来越复杂,其实已经不是用来实现“计算”这个核心功能,而是拿来实现处理乱序执行、进行分支预测,以及我们之后要在存储器讲的高速缓存部分。

而在 GPU 里,这些电路就显得有点多余了,GPU 的整个处理过程是一个流式处理(Stream Processing)的过程。因为没有那么多分支条件,或者复杂的依赖关系,我们可以把 GPU 里这些对应的电路都可以去掉,做一次小小的瘦身,只留下取指令、指令译码、ALU 以及执行这些计算需要的寄存器和缓存就好了。一般来说,我们会把这些电路抽象成三个部分,就是下面图里的取指令和指令译码、ALU 和执行上下文。

image.png

多核并行和 SIMT

这样一来,我们的 GPU 电路就比 CPU 简单很多了。于是,我们就可以在一个 GPU 里面,塞很多个这样并行的 GPU 电路来实现计算,就好像 CPU 里面的多核 CPU 一样。和 CPU 不同的是,我们不需要单独去实现什么多线程的计算。因为 GPU 的运算是天然并行的。

image.png

我们在上一讲里面其实已经看到,无论是对多边形里的顶点进行处理,还是屏幕里面的每一个像素进行处理,每个点的计算都是独立的。所以,简单地添加多核的 GPU,就能做到并行加速。不过光这样加速还是不够,工程师们觉得,性能还有进一步被压榨的空间。

我们在第 27 讲里面讲过,CPU 里有一种叫作 SIMD 的处理技术。这个技术是说,在做向量计算的时候,我们要执行的指令是一样的,只是同一个指令的数据有所不同而已。在 GPU 的渲染管线里,这个技术可就大有用处了。

无论是顶点去进行线性变换,还是屏幕上临近像素点的光照和上色,都是在用相同的指令流程进行计算。所以,GPU 就借鉴了 CPU 里面的 SIMD,用了一种叫作SIMT(Single Instruction,Multiple Threads)的技术。SIMT 呢,比 SIMD 更加灵活。在 SIMD 里面,CPU 一次性取出了固定长度的多个数据,放到寄存器里面,用一个指令去执行。而 SIMT,可以把多条数据,交给不同的线程去处理。

各个线程里面执行的指令流程是一样的,但是可能根据数据的不同,走到不同的条件分支。这样,相同的代码和相同的流程,可能执行不同的具体的指令。这个线程走到的是 if 的条件分支,另外一个线程走到的就是 else 的条件分支了。

于是,我们的 GPU 设计就可以进一步进化,也就是在取指令和指令译码的阶段,取出的指令可以给到后面多个不同的 ALU 并行进行运算。这样,我们的一个 GPU 的核里,就可以放下更多的 ALU,同时进行更多的并行运算了。

image.png

GPU 里的“超线程”

虽然 GPU 里面的主要以数值计算为主。不过既然已经是一个“通用计算”的架构了,GPU 里面也避免不了会有 if…else 这样的条件分支。但是,在 GPU 里我们可没有 CPU 这样的分支预测的电路。这些电路在上面“芯片瘦身”的时候,就已经被我们砍掉了。

所以,GPU 里的指令,可能会遇到和 CPU 类似的“流水线停顿”问题。想到流水线停顿,你应该就能记起,我们之前在 CPU 里面讲过超线程技术。在 GPU 上,我们一样可以做类似的事情,也就是遇到停顿的时候,调度一些别的计算任务给当前的 ALU。

和超线程一样,既然要调度一个不同的任务过来,我们就需要针对这个任务,提供更多的执行上下文。所以,一个 Core 里面的执行上下文的数量,需要比 ALU 多。

image.png

我们去看 NVidia 2080 显卡的技术规格,就可以算出,它到底有多大的计算能力。

2080 一共有 46 个 SM(Streaming Multiprocessor,流式处理器),这个 SM 相当于 GPU 里面的 GPU Core,所以你可以认为这是一个 46 核的 GPU,有 46 个取指令指令译码的渲染管线。每个 SM 里面有 64 个 Cuda Core。你可以认为,这里的 Cuda Core 就是我们上面说的 ALU 的数量或者 Pixel Shader 的数量,46x64 呢一共就有 2944 个 Shader。然后,还有 184 个 TMU,TMU 就是 Texture Mapping Unit,也就是用来做纹理映射的计算单元,它也可以认为是另一种类型的 Shader。

2080 Super 显卡有 48 个 SM,比普通版的 2080 多 2 个。每个 SM(SM 也就是 GPU Core)里有 64 个 Cuda Core,也就是 Shader

image.png

2080 的主频是 1515MHz,如果自动超频(Boost)的话,可以到 1700MHz。而 NVidia 的显卡,根据硬件架构的设计,每个时钟周期可以执行两条指令。所以,能做的浮点数运算的能力,就是:

(2944 + 184)× 1700 MHz × 2 = 10.06 TFLOPS

那么,最新的 Intel i9 9900K 的性能是多少呢?不到 1TFLOPS。而 2080 显卡和 9900K 的价格却是差不多的。所以,在实际进行深度学习的过程中,用 GPU 所花费的时间,往往能减少一到两个数量级。而大型的深度学习模型计算,往往又是多卡并行,要花上几天乃至几个月。这个时候,用 CPU 显然就不合适了。

今天,随着 GPGPU 的推出,GPU 已经不只是一个图形计算设备,更是一个用来做数值计算的好工具了。同样,也是因为 GPU 的快速发展,带来了过去 10 年深度学习的繁荣。

FPGA和ASIC

FPGA

image.png

这个,就是我们接下来要说的 FPGA,也就是现场可编程门阵列(Field-Programmable Gate Array)。看到这个名字,你可能要说了,这里面每个单词单独我都认识,放到一起就不知道是什么意思了。

没关系,我们就从 FPGA 里面的每一个字符,一个一个来看看它到底是什么意思。

  • P 代表 Programmable,这个很容易理解。也就是说这是一个可以通过编程来控制的硬件。
  • G 代表 Gate 也很容易理解,它就代表芯片里面的门电路。我们能够去进行编程组合的就是这样一个一个门电路。
  • A 代表的 Array,叫作阵列,说的是在一块 FPGA 上,密密麻麻列了大量 Gate 这样的门电路。
  • 最后一个 F,不太容易理解。它其实是说,一块 FPGA 这样的板子,可以在“现场”多次进行编程。它不像 PAL(Programmable Array Logic,可编程阵列逻辑)这样更古老的硬件设备,只能“编程”一次,把预先写好的程序一次性烧录到硬件里面,之后就不能再修改了。

这么看来,其实“FPGA”这样的组合,基本上解决了我们前面说的想要设计硬件的问题。我们可以像软件一样对硬件编程,可以反复烧录,还有海量的门电路,可以组合实现复杂的芯片功能。

FPGA 的解决方案很精巧,我把它总结为这样三个步骤。

第一,用存储换功能实现组合逻辑。在实现 CPU 的功能的时候,我们需要完成各种各样的电路逻辑。在 FPGA 里,这些基本的电路逻辑,不是采用布线连接的方式进行的,而是预先根据我们在软件里面设计的逻辑电路,算出对应的真值表,然后直接存到一个叫作 LUT(Look-Up Table,查找表)的电路里面。这个 LUT 呢,其实就是一块存储空间,里面存储了“特定的输入信号下,对应输出 0 还是 1”。

image.png

这里面的关键就在于,这个查表的办法,不只能够提供斐波那契数列。如果我们要有一个获得 N 的 5 次方的函数,一样可以先计算好,放在表里面进行查询。这个“查表”的方法,其实就是 FPGA 通过 LUT 来实现各种组合逻辑的办法。

第二,对于需要实现的时序逻辑电路,我们可以在 FPGA 里面直接放上 D 触发器,作为寄存器。这个和 CPU 里的触发器没有什么本质不同。不过,我们会把很多个 LUT 的电路和寄存器组合在一起,变成一个叫作逻辑簇(Logic Cluster)的东西。在 FPGA 里,这样组合了多个 LUT 和寄存器的设备,也被叫做 CLB(Configurable Logic Block,可配置逻辑块)。

我们通过配置 CLB 实现的功能有点儿像我们前面讲过的全加器。它已经在最基础的门电路上做了组合,能够提供更复杂一点的功能。更复杂的芯片功能,我们不用再从门电路搭起,可以通过 CLB 组合搭建出来。

image.png

第三,FPGA 是通过可编程逻辑布线,来连接各个不同的 CLB,最终实现我们想要实现的芯片功能。这个可编程逻辑布线,你可以把它当成我们的铁路网。整个铁路系统已经铺好了,但是整个铁路网里面,设计了很多个道岔。我们可以通过控制道岔,来确定不同的列车线路。在可编程逻辑布线里面,“编程”在做的,就是拨动像道岔一样的各个电路开关,最终实现不同 CLB 之间的连接,完成我们想要的芯片功能。

于是,通过 LUT 和寄存器,我们能够组合出很多 CLB,而通过连接不同的 CLB,最终有了我们想要的芯片功能。最关键的是,这个组合过程是可以“编程”控制的。而且这个编程出来的软件,还可以后续改写,重新写入到硬件里。让同一个硬件实现不同的芯片功能。从这个角度来说,FPGA 也是“软件吞噬世界”的一个很好的例子。

ASIC

于是,我们就考虑为这些有专门用途的场景,单独设计一个芯片。这些专门设计的芯片呢,我们称之为 ASIC(Application-Specific Integrated Circuit),也就是专用集成电路。事实上,过去几年,ASIC 发展得特别快。因为 ASIC 是针对专门用途设计的,所以它的电路更精简,单片的制造成本也比 CPU 更低。而且,因为电路精简,所以通常能耗要比用来做通用计算的 CPU 更低。而我们上一讲所说的早期的图形加速卡,其实就可以看作是一种 ASIC。

因为 ASIC 的生产制造成本,以及能耗上的优势,过去几年里,有不少公司设计和开发 ASIC 用来“挖矿”。这个“挖矿”,说的其实就是设计专门的数值计算芯片,用来“挖”比特币、ETH 这样的数字货币。

那么,我们能不能用刚才说的 FPGA 来做 ASIC 的事情呢?当然是可以的。我们对 FPGA 进行“编程”,其实就是把 FPGA 的电路变成了一个 ASIC。这样的芯片,往往在成本和功耗上优于需要做通用计算的 CPU 和 GPU。

那你可能又要问了,那为什么我们干脆不要用 ASIC 了,全都用 FPGA 不就好了么?你要知道,其实 FPGA 一样有缺点,那就是它的硬件上有点儿“浪费”。这个很容易理解,我一说你就明白了。

每一个 LUT 电路,其实都是一个小小的“浪费”。一个 LUT 电路设计出来之后,既可以实现与门,又可以实现或门,自然用到的晶体管数量,比单纯连死的与门或者或门的要多得多。同时,因为用的晶体管多,它的能耗也比单纯连死的电路要大,单片 FPGA 的生产制造的成本也比 ASIC 要高不少。

当然,有缺点就有优点,FPGA 的优点在于,它没有硬件研发成本。ASIC 的电路设计,需要仿真、验证,还需要经过流片(Tape out),变成一个印刷的电路版,最终变成芯片。这整个从研发到上市的过程,最低花费也要几万美元,高的话,会在几千万乃至数亿美元。更何况,整个设计还有失败的可能。所以,如果我们设计的专用芯片,只是要制造几千片,那买几千片现成的 FPGA,可能远比花上几百万美元,来设计、制造 ASIC 要经济得多。

实际上,到底使用 ASIC 这样的专用芯片,还是采用 FPGA 这样可编程的通用硬件,核心的决策因素还是成本。不过这个成本,不只是单个芯片的生产制造成本,还要考虑总体拥有成本(Total Cost of Ownership),也就是说,除了生产成本之外,我们要把研发成本也算进去。如果我们只制造了一片芯片,那么成本就是“这枚芯片的成本 + 为了这枚芯片建的生产线的成本 + 芯片的研发成本”,而不只是“芯片的原材料沙子的成本 + 生产的电费”。

单个 ASIC 的生产制造成本比 FPGA 低,ASIC 的能耗也比能实现同样功能的 FPGA 要低。能耗低,意味着长时间运行这些芯片,所用的电力成本也更低。

但是,ASIC 有一笔很高的 NRE(Non-Recuring Engineering Cost,一次性工程费用)成本。这个成本,就是 ASIC 实际“研发”的成本。只有需要大量生产 ASIC 芯片的时候,我们才能摊薄这份研发成本。

image.png

其实,在我们的日常软件开发过程中,也需要做同样的决策。很多我们需要的功能,可能在市面上已经有开源的软件可以实现。我们可以在开源的软件之上做配置或者开发插件,也可以选择自己从头开始写代码。

存储与I/O系统

存储器层次结构全景

而我们大脑中的记忆,就好比 CPU Cache(CPU 高速缓存,我们常常简称为“缓存”)。CPU Cache 用的是一种叫作 SRAM(Static Random-Access Memory,静态随机存取存储器)的芯片。

SRAM

SRAM 之所以被称为“静态”存储器,是因为只要处在通电状态,里面的数据就可以保持存在。而一旦断电,里面的数据就会丢失了。在 SRAM 里面,一个比特的数据,需要 6~8 个晶体管。所以 SRAM 的存储密度不高。同样的物理空间下,能够存储的数据有限。不过,因为 SRAM 的电路简单,所以访问速度非常快。

在 CPU 里,通常会有 L1、L2、L3 这样三层高速缓存。每个 CPU 核心都有一块属于自己的 L1 高速缓存,通常分成指令缓存和数据缓存,分开存放 CPU 使用的指令和数据。

L2 的 Cache 同样是每个 CPU 核心都有的,不过它往往不在 CPU 核心的内部。所以,L2 Cache 的访问速度会比 L1 稍微慢一些。而 L3 Cache,则通常是多个 CPU 核心共用的,尺寸会更大一些,访问速度自然也就更慢一些。

你可以把 CPU 中的 L1 Cache 理解为我们的短期记忆,把 L2/L3 Cache 理解成长期记忆,把内存当成我们拥有的书架或者书桌。 当我们自己记忆中没有资料的时候,可以从书桌或者书架上拿书来翻阅。这个过程中就相当于,数据从内存中加载到 CPU 的寄存器和 Cache 中,然后通过“大脑”,也就是 CPU,进行处理和运算。

DRAM

内存用的芯片和 Cache 有所不同,它用的是一种叫作 DRAM(Dynamic Random Access Memory,动态随机存取存储器)的芯片,比起 SRAM 来说,它的密度更高,有更大的容量,而且它也比 SRAM 芯片便宜不少。

DRAM 被称为“动态”存储器,是因为 DRAM 需要靠不断地“刷新”,才能保持数据被存储起来。DRAM 的一个比特,只需要一个晶体管和一个电容就能存储。所以,DRAM 在同样的物理空间下,能够存储的数据也就更多,也就是存储的“密度”更大。但是,因为数据是存储在电容里的,电容会不断漏电,所以需要定时刷新充电,才能保持数据不丢失。DRAM 的数据访问电路和刷新电路都比 SRAM 更复杂,所以访问延时也就更长。

image.png

为了弥补两者之间的性能差异,我们能真实地把 CPU 的性能提升用起来,而不是让它在那儿空转,我们在现代 CPU 中引入了高速缓存。

从 CPU Cache 被加入到现有的 CPU 里开始,内存中的指令、数据,会被加载到 L1-L3 Cache 中,而不是直接由 CPU 访问内存去拿。在 95% 的情况下,CPU 都只需要访问 L1-L3 Cache,从里面读取指令和数据,而无需访问内存。要注意的是,这里我们说的 CPU Cache 或者 L1/L3 Cache,不是一个单纯的、概念上的缓存(比如之前我们说的拿内存作为硬盘的缓存),而是指特定的由 SRAM 组成的物理芯片。

这里是一张 Intel CPU 的放大照片。这里面大片的长方形芯片,就是这个 CPU 使用的 20MB 的 L3 Cache。

现代 CPU 中大量的空间已经被 SRAM 占据,图中用红色框出的部分就是 CPU 的 L3 Cache 芯片

image.png

在这一讲一开始的程序里,运行程序的时间主要花在了将对应的数据从内存中读取出来,加载到 CPU Cache 里。CPU 从内存中读取数据到 CPU Cache 的过程中,是一小块一小块来读取数据的,而不是按照单个数组元素来读取数据的。这样一小块一小块的数据,在 CPU Cache 里面,我们把它叫作 Cache Line(缓存块)。

在我们日常使用的 Intel 服务器或者 PC 里,Cache Line 的大小通常是 64 字节。而在上面的循环 2 里面,我们每隔 16 个整型数计算一次,16 个整型数正好是 64 个字节。于是,循环 1 和循环 2,需要把同样数量的 Cache Line 数据从内存中读取到 CPU Cache 中,最终两个程序花费的时间就差别不大了。

总结一下,一个内存的访问地址,最终包括高位代表的组标记、低位代表的索引,以及在对应的 Data Block 中定位对应字的位置偏移量。

image.png

而内存地址对应到 Cache 里的数据结构,则多了一个有效位和对应的数据,由“索引 + 有效位 + 组标记 + 数据”组成。如果内存中的数据已经在 CPU Cache 里了,那一个内存地址的访问,就会经历这样 4 个步骤:

  1. 根据内存地址的低位,计算在 Cache 中的索引;
  2. 判断有效位,确认 Cache 中的数据是有效的;
  3. 对比内存访问地址的高位,和 Cache 中的组标记,确认 Cache 中的数据就是我们要访问的内存数据,从 Cache Line 中读取到对应的数据块(Data Block)
  4. 根据内存地址的 Offset 位,从 Data Block 中,读取希望读取到的字。

CPU 读取数据过程

TLB 和我们前面讲的 CPU 的高速缓存类似,可以分成指令的 TLB 和数据的 TLB,也就是 ITLB 和 DTLB。同样的,我们也可以根据大小对它进行分级,变成 L1、L2 这样多层的 TLB。

image.png

安全性与内存保护

进程的程序也好,数据也好,都要存放在内存里面。实际程序指令的执行,也是通过程序计数器里面的地址,去读取内存内的内容,然后运行对应的指令,使用相应的数据。

虽然我们现代的操作系统和 CPU,已经做了各种权限的管控。正常情况下,我们已经通过虚拟内存地址和物理内存地址的区分,隔离了各个进程。但是,无论是 CPU 这样的硬件,还是操作系统这样的软件,都太复杂了,难免还是会被黑客们找到各种各样的漏洞。

就像我们在软件开发过程中,常常会有一个“兜底”的错误处理方案一样,在对于内存的管理里面,计算机也有一些最底层的安全保护机制。这些机制统称为内存保护(Memory Protection)。我这里就为你简单介绍两个。

可执行空间保护

第一个常见的安全机制,叫可执行空间保护(Executable Space Protection)。

这个机制是说,我们对于一个进程使用的内存,只把其中的指令部分设置成“可执行”的,对于其他部分,比如数据部分,不给予“可执行”的权限。因为无论是指令,还是数据,在我们的 CPU 看来,都是二进制的数据。我们直接把数据部分拿给 CPU,如果这些数据解码后,也能变成一条合理的指令,其实就是可执行的。

这个时候,黑客们想到了一些搞破坏的办法。我们在程序的数据区里,放入一些要执行的指令编码后的数据,然后找到一个办法,让 CPU 去把它们当成指令去加载,那 CPU 就能执行我们想要执行的指令了。对于进程里内存空间的执行权限进行控制,可以使得 CPU 只能执行指令区域的代码。对于数据区域的内容,即使找到了其他漏洞想要加载成指令来执行,也会因为没有权限而被阻挡掉。

这个时候,黑客们想到了一些搞破坏的办法。我们在程序的数据区里,放入一些要执行的指令编码后的数据,然后找到一个办法,让 CPU 去把它们当成指令去加载,那 CPU 就能执行我们想要执行的指令了。对于进程里内存空间的执行权限进行控制,可以使得 CPU 只能执行指令区域的代码。对于数据区域的内容,即使找到了其他漏洞想要加载成指令来执行,也会因为没有权限而被阻挡掉。

地址空间布局随机化

为了防止入侵者通过缓冲区溢出进行攻击,linux系统实现了栈随机化技术。

第二个常见的安全机制,叫地址空间布局随机化(Address Space Layout Randomization)。

内存层面的安全保护核心策略,是在可能有漏洞的情况下进行安全预防。上面的可执行空间保护就是一个很好的例子。但是,内存层面的漏洞还有其他的可能性。

这里的核心问题是,其他的人、进程、程序,会去修改掉特定进程的指令、数据,然后,让当前进程去执行这些指令和数据,造成破坏。要想修改这些指令和数据,我们需要知道这些指令和数据所在的位置才行。

原先我们一个进程的内存布局空间是固定的,所以任何第三方很容易就能知道指令在哪里,程序栈在哪里,数据在哪里,堆又在哪里。这个其实为想要搞破坏的人创造了很大的便利。而地址空间布局随机化这个机制,就是让这些区域的位置不再固定,在内存空间随机去分配这些进程里不同部分所在的内存空间地址,让破坏者猜不出来。猜不出来呢,自然就没法找到想要修改的内容的位置。如果只是随便做点修改,程序只会 crash 掉,而不会去执行计划之外的代码。

关闭Linux 内存地址随机化机制, 禁用进程地址空间随机化.可以将进程的mmap的基址,stack和vdso页面地址固定下来. 可以通过设置kernel.randomize_va_space内核参数来设置内存地址随机化的行为.
目前randomize_va_space的值有三种,分别是[0,1,2]

  • 0 - 表示关闭进程地址空间随机化。
  • 1 - 表示将mmap的基址,stack和vdso页面随机化。
  • 2 - 表示在1的基础上增加栈(heap)的随机化。

总线

首先,CPU 和内存以及高速缓存通信的总线,这里面通常有两种总线。这种方式,我们称之为双独立总线(Dual Independent Bus,缩写为 DIB)。CPU 里,有一个快速的本地总线(Local Bus),以及一个速度相对较慢的前端总线(Front-side Bus)。

我们在前面几讲刚刚讲过,现代的 CPU 里,通常有专门的高速缓存芯片。这里的高速本地总线,就是用来和高速缓存通信的。而前端总线,则是用来和主内存以及输入输出设备通信的。有时候,我们会把本地总线也叫作后端总线(Back-side Bus),和前面的前端总线对应起来。而前端总线也有很多其他名字,比如处理器总线(Processor Bus)、内存总线(Memory Bus)。

image.png

CPU 里面的北桥芯片,把我们上面说的前端总线,一分为二,变成了三个总线。

我们的前端总线,其实就是系统总线。CPU 里面的内存接口,直接和系统总线通信,然后系统总线再接入一个 I/O 桥接器(I/O Bridge)。这个 I/O 桥接器,一边接入了我们的内存总线,使得我们的 CPU 和内存通信;另一边呢,又接入了一个 I/O 总线,用来连接 I/O 设备。

事实上,真实的计算机里,这个总线层面拆分得更细。根据不同的设备,还会分成独立的 PCI 总线、ISA 总线等等。

image.png

在物理层面,其实我们完全可以把总线看作一组“电线”。不过呢,这些电线之间也是有分工的,我们通常有三类线路。

  1. 数据线(Data Bus),用来传输实际的数据信息,也就是实际上了公交车的“人”。
  2. 地址线(Address Bus),用来确定到底把数据传输到哪里去,是内存的某个位置,还是某一个 I/O 设备。这个其实就相当于拿了个纸条,写下了上面的人要下车的站点。
  3. 控制线(Control Bus),用来控制对于总线的访问。虽然我们把总线比喻成了一辆公交车。那么有人想要做公交车的时候,需要告诉公交车司机,这个就是我们的控制信号。

尽管总线减少了设备之间的耦合,也降低了系统设计的复杂度,但同时也带来了一个新问题,那就是总线不能同时给多个设备提供通信功能。

我们的总线是很多个设备公用的,那多个设备都想要用总线,我们就需要有一个机制,去决定这种情况下,到底把总线给哪一个设备用。这个机制,就叫作总线裁决(Bus Arbitraction)。总线裁决的机制有很多种不同的实现,如果你对这个实现的细节感兴趣,可以去看一看 Wiki 里面关于裁决器的对应条目,这里我们就不多说了。

CPU 是如何控制 I/O 设备的?

无论是内置在主板上的接口,还是集成在设备上的接口,除了三类寄存器之外,还有对应的控制电路。正是通过这个控制电路,CPU 才能通过向这个接口电路板传输信号,来控制实际的硬件。

我们先来看一看,硬件设备上的这些寄存器有什么用。这里,我拿我们平时用的打印机作为例子。

image.png

  1. 首先是数据寄存器(Data Register)。CPU 向 I/O 设备写入需要传输的数据,比如要打印的内容是“GeekTime”,我们就要先发送一个“G”给到对应的 I/O 设备。
  2. 然后是命令寄存器(Command Register)。CPU 发送一个命令,告诉打印机,要进行打印工作。这个时候,打印机里面的控制电路会做两个动作。第一个,是去设置我们的状态寄存器里面的状态,把状态设置成 not-ready。第二个,就是实际操作打印机进行打印。
  3. 而状态寄存器(Status Register),就是告诉了我们的 CPU,现在设备已经在工作了,所以这个时候,CPU 你再发送数据或者命令过来,都是没有用的。直到前面的动作已经完成,状态寄存器重新变成了 ready 状态,我们的 CPU 才能发送下一个字符和命令。

当然,在实际情况中,打印机里通常不只有数据寄存器,还会有数据缓冲区。我们的 CPU 也不是真的一个字符一个字符这样交给打印机去打印的,而是一次性把整个文档传输到打印机的内存或者数据缓冲区里面一起打印的。不过,通过上面这个例子,相信你对 CPU 是怎么操作 I/O 设备的,应该有所了解了。

信号和地址:发挥总线的价值

搞清楚了实际的 I/O 设备和接口之间的关系,一个新的问题就来了。那就是,我们的 CPU 到底要往总线上发送一个什么样的命令,才能和 I/O 接口上的设备通信呢?

CPU 和 I/O 设备的通信,一样是通过 CPU 支持的机器指令来执行的。

如果你回头去看一看第 5 讲,MIPS 的机器指令的分类,你会发现,我们并没有一种专门的和 I/O 设备通信的指令类型。那么,MIPS 的 CPU 到底是通过什么样的指令来和 I/O 设备来通信呢?

答案就是,和访问我们的主内存一样,使用“内存地址”。为了让已经足够复杂的 CPU 尽可能简单,计算机会把 I/O 设备的各个寄存器,以及 I/O 设备内部的内存地址,都映射到主内存地址空间里来。主内存的地址空间里,会给不同的 I/O 设备预留一段一段的内存地址。CPU 想要和这些 I/O 设备通信的时候呢,就往这些地址发送数据。这些地址信息,就是通过上一讲的地址线来发送的,而对应的数据信息呢,自然就是通过数据线来发送的了。

而我们的 I/O 设备呢,就会监控地址线,并且在 CPU 往自己地址发送数据的时候,把对应的数据线里面传输过来的数据,接入到对应的设备里面的寄存器和内存里面来。CPU 无论是向 I/O 设备发送命令、查询状态还是传输数据,都可以通过这样的方式。这种方式呢,叫作内存映射IO(Memory-Mapped I/O,简称 MMIO)。

image.png

那么,MMIO 是不是唯一一种 CPU 和设备通信的方式呢?答案是否定的。精简指令集 MIPS 的 CPU 特别简单,所以这里只有 MMIO。而我们有 2000 多个指令的 Intel X86 架构的计算机,自然可以设计专门的和 I/O 设备通信的指令,也就是 in 和 out 指令。

Intel CPU 虽然也支持 MMIO,不过它还可以通过特定的指令,来支持端口映射 I/O(Port-Mapped I/O,简称 PMIO)或者也可以叫独立输入输出(Isolated I/O)。

其实 PMIO 的通信方式和 MMIO 差不多,核心的区别在于,PMIO 里面访问的设备地址,不再是在内存地址空间里面,而是一个专门的端口(Port)。这个端口并不是指一个硬件上的插口,而是和 CPU 通信的一个抽象概念。

无论是 PMIO 还是 MMIO,CPU 都会传送一条二进制的数据,给到 I/O 设备的对应地址。设备自己本身的接口电路,再去解码这个数据。解码之后的数据呢,就会变成设备支持的一条指令,再去通过控制电路去操作实际的硬件设备。对于 CPU 来说,它并不需要关心设备本身能够支持哪些操作。它要做的,只是在总线上传输一条条数据就好了。

这个,其实也有点像我们在设计模式里面的 Command 模式。我们在总线上传输的,是一个个数据对象,然后各个接受这些对象的设备,再去根据对象内容,进行实际的解码和命令执行。

image.png

这是一张我自己的显卡,在设备管理器里面的资源(Resource)信息。你可以看到,里面既有 Memory Range,这个就是设备对应映射到的内存地址,也就是我们上面所说的 MMIO 的访问方式。同样的,里面还有 I/O Range,这个就是我们上面所说的 PMIO,也就是通过端口来访问 I/O 设备的地址。最后,里面还有一个 IRQ,也就是会来自于这个设备的中断信号了。

理解 DMA,一个协处理器

其实 DMA 技术很容易理解,本质上,DMA 技术就是我们在主板上放一块独立的芯片。在进行内存和 I/O 设备的数据传输的时候,我们不再通过 CPU 来控制数据传输,而直接通过 DMA 控制器(DMA Controller,简称 DMAC)。这块芯片,我们可以认为它其实就是一个协处理器(Co-Processor)。

DMAC 最有价值的地方体现在,当我们要传输的数据特别大、速度特别快,或者传输的数据特别小、速度特别慢的时候。

比如说,我们用千兆网卡或者硬盘传输大量数据的时候,如果都用 CPU 来搬运的话,肯定忙不过来,所以可以选择 DMAC。而当数据传输很慢的时候,DMAC 可以等数据到齐了,再发送信号,给到 CPU 去处理,而不是让 CPU 在那里忙等待。

好了,现在你应该明白 DMAC 的价值,知道了它适合用在什么情况下。那我们现在回过头来看。我们上面说,DMAC 是一块“协处理器芯片”,这是为什么呢?

注意,这里面的“协”字。DMAC 是在“协助”CPU,完成对应的数据传输工作。在 DMAC 控制数据传输的过程中,我们还是需要 CPU 的。

除此之外,DMAC 其实也是一个特殊的 I/O 设备,它和 CPU 以及其他 I/O 设备一样,通过连接到总线来进行实际的数据传输。总线上的设备呢,其实有两种类型。一种我们称之为主设备(Master),另外一种,我们称之为从设备(Slave)。

想要主动发起数据传输,必须要是一个主设备才可以,CPU 就是主设备。而我们从设备(比如硬盘)只能接受数据传输。所以,如果通过 CPU 来传输数据,要么是 CPU 从 I/O 设备读数据,要么是 CPU 向 I/O 设备写数据。

这个时候你可能要问了,那我们的 I/O 设备不能向主设备发起请求么?可以是可以,不过这个发送的不是数据内容,而是控制信号。I/O 设备可以告诉 CPU,我这里有数据要传输给你,但是实际数据是 CPU 拉走的,而不是 I/O 设备推给 CPU 的。

image.png

不过,DMAC 就很有意思了,它既是一个主设备,又是一个从设备。对于 CPU 来说,它是一个从设备;对于硬盘这样的 IO 设备来说呢,它又变成了一个主设备。那使用 DMAC 进行数据传输的过程究竟是什么样的呢?下面我们来具体看看。

  1. 首先,CPU 还是作为一个主设备,向 DMAC 设备发起请求。这个请求,其实就是在 DMAC 里面修改配置寄存器。
  2. CPU 修改 DMAC 的配置的时候,会告诉 DMAC 这样几个信息:
    • 首先是源地址的初始值以及传输时候的地址增减方式。所谓源地址,就是数据要从哪里传输过来。如果我们要从内存里面写入数据到硬盘上,那么就是要读取的数据在内存里面的地址。如果是从硬盘读取数据到内存里,那就是硬盘的 I/O 接口的地址。
    • 我们讲过总线的时候说过,I/O 的地址可以是一个内存地址,也可以是一个端口地址。而地址的增减方式就是说,数据是从大的地址向小的地址传输,还是从小的地址往大的地址传输。
    • 其次是目标地址初始值和传输时候的地址增减方式。目标地址自然就是和源地址对应的设备,也就是我们数据传输的目的地。
    • 第三个自然是要传输的数据长度,也就是我们一共要传输多少数据。
  3. 设置完这些信息之后,DMAC 就会变成一个空闲的状态(Idle)。
  4. 如果我们要从硬盘上往内存里面加载数据,这个时候,硬盘就会向 DMAC 发起一个数据传输请求。这个请求并不是通过总线,而是通过一个额外的连线。
  5. 然后,我们的 DMAC 需要再通过一个额外的连线响应这个申请。
  6. 于是,DMAC 这个芯片,就向硬盘的接口发起要总线读的传输请求。数据就从硬盘里面,读到了 DMAC 的控制器里面。
  7. 然后,DMAC 再向我们的内存发起总线写的数据传输请求,把数据写入到内存里面。
  8. DMAC 会反复进行上面第 6、7 步的操作,直到 DMAC 的寄存器里面设置的数据长度传输完成。
  9. 数据传输完成之后,DMAC 重新回到第 3 步的空闲状态。

所以,整个数据传输的过程中,我们不是通过 CPU 来搬运数据,而是由 DMAC 这个芯片来搬运数据。但是 CPU 在这个过程中也是必不可少的。因为传输什么数据,从哪里传输到哪里,其实还是由 CPU 来设置的。这也是为什么,DMAC 被叫作“协处理器”。

image.png

最早,计算机里是没有 DMAC 的,所有数据都是由 CPU 来搬运的。随着人们对于数据传输的需求越来越多,先是出现了主板上独立的 DMAC 控制器。到了今天,各种 I/O 设备越来越多,数据传输的需求越来越复杂,使用的场景各不相同。加之显示器、网卡、硬盘对于数据传输的需求都不一样,所以各个设备里面都有自己的 DMAC 芯片了。

kafka - sendfile

image.png

image.png

应用篇

KV vs MQ VS 数据仓库

image.png

Cassandra:顺序写和随机读

作为一个分布式的 KV 数据库,Cassandra 的键一般被称为 Row Key。其实就是一个 16 到 36 个字节的字符串。每一个 Row Key 对应的值其实是一个哈希表,里面可以用键值对,再存入很多你需要的数据。

Cassandra 本身不像关系型数据库那样,有严格的 Schema,在数据库创建的一开始就定义好了有哪些列(Column)。但是,它设计了一个叫作列族(Column Family)的概念,我们需要把经常放在一起使用的字段,放在同一个列族里面。比如,DMP 里面的人口属性信息,我们可以把它当成是一个列族。用户的兴趣信息,可以是另外一个列族。这样,既保持了不需要严格的 Schema 这样的灵活性,也保留了可以把常常一起使用的数据存放在一起的空间局部性。

往 Cassandra 的里面读写数据,其实特别简单,就好像是在一个巨大的分布式的哈希表里面写数据。我们指定一个 Row Key,然后插入或者更新这个 Row Key 的数据就好了。

Cassandra 的写操作

image.png

Cassandra 解决随机写入数据的解决方案,简单来说,就叫作“不随机写,只顺序写”。对于 Cassandra 数据库的写操作,通常包含两个动作。第一个是往磁盘上写入一条提交日志(Commit Log)。另一个操作,则是直接在内存的数据结构上去更新数据。后面这个往内存的数据结构里面的数据更新,只有在提交日志写成功之后才会进行。每台机器上,都有一个可靠的硬盘可以让我们去写入提交日志。写入提交日志都是顺序写(Sequential Write),而不是随机写(Random Write),这使得我们最大化了写入的吞吐量。

内存的空间比较有限,一旦内存里面的数据量或者条目超过一定的限额,Cassandra 就会把内存里面的数据结构 dump 到硬盘上。这个 Dump 的操作,也是顺序写而不是随机写,所以性能也不会是一个问题。除了 Dump 的数据结构文件,Cassandra 还会根据 row key 来生成一个索引文件,方便后续基于索引来进行快速查询。

随着硬盘上的 Dump 出来的文件越来越多,Cassandra 会在后台进行文件的对比合并。在很多别的 KV 数据库系统里面,也有类似这种的合并动作,比如 AeroSpike 或者 Google 的 BigTable。这些操作我们一般称之为 Compaction。合并动作同样是顺序读取多个文件,在内存里面合并完成,再 Dump 出来一个新的文件。整个操作过程中,在硬盘层面仍然是顺序读写。

Cassandra 的读操作

image.png

当我们要从 Cassandra 读数据的时候,会从内存里面找数据,再从硬盘读数据,然后把两部分的数据合并成最终结果。这些硬盘上的文件,在内存里面会有对应的 Cache,只有在 Cache 里面找不到,我们才会去请求硬盘里面的数据。

如果不得不访问硬盘,因为硬盘里面可能 Dump 了很多个不同时间点的内存数据的快照。所以,找数据的时候,我们也是按照时间从新的往旧的里面找。

这也就带来另外一个问题,我们可能要查询很多个 Dump 文件,才能找到我们想要的数据。所以,Cassandra 在这一点上又做了一个优化。那就是,它会为每一个 Dump 的文件里面所有 Row Key 生成一个 BloomFilter,然后把这个 BloomFilter 放在内存里面。这样,如果想要查询的 Row Key 在数据文件里面不存在,那么 99% 以上的情况下,它会被 BloomFilter 过滤掉,而不需要访问硬盘。

这样,只有当数据在内存里面没有,并且在硬盘的某个特定文件上的时候,才会触发一次对于硬盘的读请求。