深入理解计算机系统

参考资料

深入理解计算机系统

计算机系统漫游

科普一个简单程序的全生命周期
考虑到所有内容后续都会详叙, 在此不做展开
Amdahl 定律描述了改善任何过程的一般原则 (抓大头)

信息的表示和处理

位向量与计算机中的表示

字节是计算机中最小的可寻址内存单位
C 语言用编译时的不同的机器级代码表示类型, 生成的程序并不包含类型信息
字长决定的最重要的系统参数就是虚拟地址空间的最大大小
三个场景关注大小端
- 网络协议中, 数据在网络中传输时
- 汇编语言中
- C 语言的高级技巧
长度为 n 的位向量上 ^, ~, & 运算形成布尔环
- 用位向量编码集合子集是, ^, ~, & 恰为并集, 补集, 交集
我们一般对有符号数使用算术右移 (进行类型拓展时同理)
我们对位向量加上一个解释去表示类型

整数表示与运算

补码可以理解为最高位权为 \(-2^{n-1}\)
C 语言有无符号数转换只转换解释, 不转换位模式
- 比较时小心有符号数被强转为无符号数
无符号类型截断就是取模, 对有符号数进行类型转换时, 先解释为无符号数, 再取模, 再解释为有符号数
有符号数的相加也可以理解为无符号数的相加, 只是结果需要解释为有符号数
- 会出现正溢出和负溢出
无符号数与有符号数的加法逆元位模式一致
- 对位模式取反再加一
- 除了最小的有符号数没有加法逆元
无符号数与有符号数的乘法位模式一致
- 先看成无符号数, 相乘, 取模, 再解释为有符号数
C 语言有符号整数除法的结果是向零截断的
- 所以右移运算不能直接替代除法, 需要补偿
- 补偿方法为, 负数时, 先加上 \(2^k - 1\), 再右移
C 语言取模结果的符号与被除数 \(x\) 的符号一致
- 计算方法依旧一致, 先获得商 (向零截断), 再用被除数减去商乘以除数
- 所以这里有无符号数除法和取模的位模式存在差异

浮点数

\((-1)^s \times 2^e \times M\)
根据 \(E\) 的位模式, 将浮点数划分为以下几种
- 全为 \(0\) 非规格化
- 全为 \(1\) 时, \(M\) 的位模式全为 \(0\) 表示无穷大, 否则为 NaN
- 之间的数, 规格化

规格化数

\(E\) 的解释为 \(E = e - bias\), 其中 \(bias = 2^{k-1} - 1\) (偏置一半)
\(M\) 的解释为 \(M = 1 + \sum_{i=0}^{n-2} 2^{-i} \times M_i\) (\(1\) + 其位模式解释为小数点在开头的定点小数)

非规格化数

\(E\) 的解释为 \(E = 1 - bias\)
\(M\) 的解释为 \(M = \sum_{i=0}^{n-2} 2^{-i} \times M_i\) (小数点在开头的定点小数)
非规格化数用于表示 \(0\) 以及接近 \(0\) 的数
作用
- 使得非规格化数的最大值到规格化数的最小值之间的过渡更加平滑
- 并且单调, 使得浮点数的比较可以直接用位模式比较
- 实现逐渐下溢, 这保证了 x != y 时 x - y != 0

浮点数的舍入

向最近偶数舍入, 先向最近的整数, 若刚好位于两数中间, 则向偶数方向舍入 (默认, 为了减少统计误差)
向零舍入, 向上舍入, 向下舍入

浮点数的运算

大部分与整数运算一致
实数加法 / 乘法不具有结合律
浮点乘法在加法上不具备分配性
NaN 没有加法逆元

程序的机器级表示

X86-64 指令集

大部分略
任何为寄存器生成 \(32\) 位值的指令都会把该寄存器的高位部分置成 \(0\)
除数和余数是一个指令的两个结果
部分早期处理器将更新程序计数器作为执行一条指令的第一步
- 这使得相对寻址指令,实际生成的机器代码当中的相对值是基于下一条指令的

if (x > 0)
    y = 1;
else
    y = -1;

cmpq $0, x
jg .L1
movq $-1, y
jmp .L2
.L1:
movq $1, y
.L2:

这是编译器惯有的 if 翻译方法
当然, 相较于基于条件控制转移, 我们更喜欢基于条件数据传送 (显然它是包含条件控制转移的, 就是修改 PC)
- 也就是根据不同的条件返回不同的数据, 这样的话能有效利用流水线
- 有的时候也不得不用这个条件转移, 比如说条件控制转移的源位置可能不合法直接就段错误

while (x > 0)
    y++;

goto .L1
.L2:
incq y
.L1:
cmpq $0, x
jg .L2

这是编译器惯有的 while 翻译方法

cmpq $0, x
    jle .L_DONE     ; 如果初始条件 x <= 0，直接跳过循环
.L_LOOP:            ; 循环体开始
    incq y
    cmpq $0, x
    jg .L_LOOP      ; 如果 x > 0，跳回开头
.L_DONE:

guarded-do, 如果初始条件不成立就直接跳过循环, 否则把代码变换为 do-while 循环
for 循环, 就是简单包装一下, 就不详叙了
switch 语句, 就是根据不同的情况跳转到不同的标签 (详见编译原理)

过程

尽可能低代价的进行传递控制, 传递数据, 分配和释放内存
传递控制就保存一下当前的 PC, 然后跳转到目标地址
传递数据就直接用寄存器传递, 或者用运行时栈传递
分配和释放内存就直接用栈来实现
当所有的局部变量都可以保存在寄存器中, 而且该函数不会调用任何其他函数时, 函数就可能没有栈帧
栈帧也需要对齐

数据处理

有些时候, 局部数据必须存放在内存中
- 寄存器不足够存放所有的本地数据
- 对一个局部变量使用地址运算符
- 某些局部变量是数组或结构, 因此必须能够通过数组或结构引用被访问到
部分寄存器被划分为被调用者保存寄存器, 保证调用前后寄存器的值不变
- 其他的叫调用者保存寄存器, 调用者在调用前必须保存好它们的值 (如果需要), 调用后再恢复
因为栈向下增长, 所以栈上数组溢出时, 会覆盖上面的栈帧
为了处理变长数组, 编译器会记录栈帧底指针, 通过腾出一个被调用者保存寄存器来保存它
- 解决栈顶指针变化导致的偏移量失效
数组寻址时的简单加乘计算被集成进专门的单元中, 非常快
过程返回时小于 \(16\) 字节会用 \(1\) - \(2\) 个寄存器, 否则会调用拷贝
- 大对象现代编译器更喜欢做一个 RVO 优化, 传入一个调用者提供的内存地址, 被调用者直接在该地址上构造

浮点数机器语言

AVX 指令集
- 扩展了 \(256\) 位的向量寄存器
- 用于浮点数标量是仅使用 \(256\) 位中的低 \(32\) 或 \(64\) 位 (仅)
- \(256\) 位叫 YMM 寄存器
- 低 \(128\) 位叫 XMM 寄存器
GCC 在做单双精度转换时, 会复制一份原始值, 并行转换出两个结果
所有的 XMM 寄存器都是调用者保存
编译器会将浮点常量的二进制表示存储在内存的数据段中 (没有真立即数)
比较时如果任一操作数是 NaN, 会设置 PF

处理器体系结构

Y86-64 指令集

Y86-64 的指令集是 X86-64 的子集, 只处理 8 字节的整数操作
还有很多简化, 不详叙
pushq %rsp 压入减去 \(8\) 前的 %rsp (同 X86-64)
popq %rsp 不自动修改 %rsp
机器码
- 第一个字节为指令
- 可选第二个字节为两个寄存器
- 可选接下来 \(8\) 个字节常数 (小端)
状态码
- AOK 正常
- HLT 处理器执行了 halt 指令, 正常停机
- ADR 非法地址访问
- INS 非法指令

HCL (硬件控制语言)

具体形式还是比较简单的, 不详叙, 注意不要混淆编程语言
将很多的逻辑门组合成一个网, 就能构建计算块, 称为组合电路
- 每个逻辑门的输入必须连接系统输入 / 某个存储器单元的输出 / 某个逻辑门的输出
- 两个或多个逻辑门的输出不能连接在一起
- 这个网必须是无环的
多路复用器, 用所有控制输入组合的布尔表达式来选择数据输入的其中一个作为输出
- 有字级形式 -> 类似 switch
- HCL 中可以有允许不互斥的选择表达式, 但实际电路必须确保只有第一个满足的情况才会被选中
为了将组合电路时序化, 我们需要引入时钟信号
存储设备都是由同一个时钟控制的
- 时钟寄存器存储单个位或字, 时钟信号控制寄存器加载输入值
- 随机访问存储器存储多个字, 用地址来选择该读或该写哪个字 (包括内存与寄存器)
  - 寄存器文件属于随机访问存储器, 就是汇编中的寄存器
  - 寄存器文件有两个读端口和一个写端口, 可以同时读取两个寄存器 + 写入一个寄存器
  - 同时读写一个寄存器会读到一个变化

Y86-64 的顺序实现

我们构建一个非常简单的单周期指令硬件模型 SEQ
一条指令包括很多操作
- 取指, 根据 PC 取指令, 并计算下一条指令的 PC
- 译码, 从寄存器文件中读取操作数 (最多 \(2\) 个)
- 执行, 执行指令, 并设置条件码
- 访存, 读写内存 (我们不支持内存地址作为操作, 访存可以在执行后面)
- 写回, 将结果写回寄存器文件 (最多 \(2\) 个)
- 更新 PC
处理器从来不需要为了完成一条指令的执行而去读由该指令更新的状态
时钟控制程序寄存器与条件码寄存器就足够了
- 寄存器文件与内存当在组合逻辑里

流水线的通用实现

非流水线就是让电走一会, 然后放在寄存器里
- 把它拆成多阶段, 每个阶段都有自己的寄存器, 每个阶段的输出作为下一个阶段的输入
- 显著扩大了吞吐, 但因为寄存器的时间开销, 延迟也会变大
实际设计流水线时如何均匀划分是一个很大的问题 (短板效应)
流水线技术显然有一个问题, 带反馈的指令会导致流水线改变系统行为 (使用的寄存器的值可能还未准备好)

Y86-64 流水线实现

一个重要的改进是, 将之前每个时钟周期最后计算程序计数器, 改到在下一个周期的开头当中去计算
- 所以这回程序计数器连寄存器都没有了, 这种只保证可见, 不真正有实体的思想在底层还是很常见的, 比如说乱序执行
划分五级流水线, 并有五个流水线寄存器
- 计算 PC 的预测值
- F (Fetch) 保存 PC 的预测值
- 取指
- D (Decode) 保存刚刚取出的指令位
- 译码
- E (Execute) 保存译码后的数据
- 执行
- M (Memory) 保存执行结果
- 访存
- W (Write-back) 保存最终要写回寄存器文件的数据
- 写回
信号命名系统的重设计
- 大写前缀表示流水线寄存器 (上一周期产生并锁存的状态)
- 小写前缀表示当前阶段逻辑电路刚刚计算出来产生的信号
当指令 \(I\) 到达写回阶段时, 译码阶段正在处理指令 \(I+4\), 如果直接用译码器的输出，指令 \(I\) 的结果会被写入指令 \(I+4\) 指定的寄存器中
- 必须让目的寄存器 ID (dstE 和 dstM) 跟随指令一起流动
Select A 模块
- 没有指令会同时需要从寄存器读出的 valA 和 valP
- 所以去掉一个, 减少流水线寄存器的宽度 (流水线设计常见优化)
PC 的预测
- 由于执行一条指令的时候, 上一个指令还没结束, 不能确切知道下一个地址, 所以必须要分支预测
- 如果说存在跳转的话呢总是预测会发生跳转 (\(60%\) 成功率)
- 当分支预测失败的时候, 就取回正确的这个跳转值
- 特殊的是 ret 指令的下一条, 必须需要访存才能知道跳转到哪所以会直接等待
还有一种分支预测策略 (\(65%\) 成功率)
- 如果分支地址比下一条地址低就预测分支
- 因为循环往往是前向跳转的而且它通常会执行多次
部分处理器会有一个专门用来预测返回地址的硬件栈 (对程序员不可见)

流水线冒险

数据冒险指当下一条指令需要上一条指令计算出的结果叫做
控制冒险指处理器无法根据当前取出的指令确定下一条指令的地址
数据冒险解决方案
- 等待
  - 将指令阻塞在译码阶段
  - 向后续阶段插入气泡 (将流水线寄存器清零)
  - 非常慢
- 数据转发
  - 之前的指令写回之前, 就将结果转发给后续指令
  - 在后续指令的即将执行的时候, 多路选择器会检查 E / M / W 这三个流水线寄存器
  - 非常快
  - 这样就支持之前的指令在执行后到写回前直接转发结果给后续指令的执行前
- 但是, 如果两条指令紧紧跟随, 并且后续指令依赖于前一条指令的访存结果, 就不能转发
  - 暂停一周期即可
控制冒险解决方案
- ret 指令必须访存才能知道返回地址, 所以必须等待三周期才能执行
  - 等待虽然会使 F 寄存器中的值不变但是取指不会停止呀
  - 所以需要在 D 阶段插入三个气泡将取来的指令删掉
  - 当 ret 在 D 阶段, E 阶段是 pushq %rsp, D 流水线寄存器同时发生了冒险暂停和气泡, 先暂停, 然后气泡, 这是连 CSAPP 作者第一遍都写出 bug 的事情
- 条件跳转预测错误
  - 用气泡来取消后续指令
  - 浪费 2 个时钟周期

异常处理

流水线当中多个阶段同时出现异常显然是上报最深的
如果异常发生在错误预测的分支当中, 当然会消除这个异常
保证异常指令之后的所有指令都不能影响系统状态
实现方法
- 当检测到异常时, 作为状态码跟着指令流动, 最终在写回阶段处理 (实现了 1, 2)
- 同时立刻禁止全局的状态更新 (实现了 3)

未完成的工作

我们估算现在每周期能发射 \(1.27\) 条指令, 如果想进一步提升效率, 应该集中于更好的分支预测策略
多周期指令
- 真正的处理器中有很多指令需要多个周期才能执行完成
- 一个简单的解决方案是让这些指令在执行阶段停留多个周期
- 另一种方案是让这些指令在执行阶段完成后, 进入一个专门的多周期指令缓冲区
- 后续指令可以继续执行, 但是如果后续指令依赖于多周期指令的结果, 就必须等待
存储
- 我们简化了存储系统, 真实系统中有多级缓存
- 有些是只读的缓存, 有些是读写的缓存, 还有缓存的是虚拟地址到物理地址的翻译
- 如果降级到内存都找不到的话他可能在磁盘当中, 这会触发一个缺页异常 (因为需要数百万个周期, 等不起)

优化程序性能

用每元素周期数来衡量程序性能
- 元素指最小数据单元
妨碍优化因素
- 内存别名使用, 指针可能指向相同的内存位置
- 函数调用, 函数调用可能有副作用

消除妨碍编译器优化的障碍 (机器无关)

循环不变量应被提取到循环外部, 但编译器无法确定函数调用是否有副作用
每次获取数据时都进行边界检查可能会导致流水线预测错误
代码移动 / 循环不变量外提
- 消除了重复的函数调用
直接数据访问
- 消除了函数调用开销和边界检查
- 令人惊讶的是性能实际上并没有提升, 因为他压根就不是瓶颈
- 瓶颈在于你的循环内的每次复制都是往一个内存当中去写
引入临时变量
- 消除了每次循环内对同一内存位置的读写
- 并且这个优化看似很简单但实际上编辑器却没法帮你做
为什么编译器没法帮你做
- 因为编译器无法确定指针是否会指向相同的内存位置
- 也就是内存别名的问题
O2 优化的话, 那么你就会发现编辑器能帮你做一点小事
- 当他写回内存的时候不会再读取一次而是会使用上次写回的值

现代处理器

超标量与乱序执行
- 超标量: 每个时钟周期可以发射和执行多条指令
- 乱序执行: 只要数据准备好了, 指令就可以执行, 不必严格遵守代码编写的顺序
- 投机执行: 遇到分支时, 处理器不等待判断结果, 而是利用分支预测先猜一个方向执行下去
延迟与吞吐量
- 延迟: 完成一个运算需要的时间
- 吞吐量: 单位时间内可以完成多少个运算
- 优化的终极目标从延迟受限变成吞吐量受限
  - 也就是不因数据依赖而等待

机器相关的优化

循环展开
- 一次循环当中处理多个元素
- 减少循环控制开销, 但要更小心边界处理
- 增加指令级并行性, 但是依旧有数据依赖关系
提高并行性
- 多个累积变量, 满足结合率可以随便改变计算的顺序
- 重新结合变换, 先计算非数据依赖部分
使用 SIMD 指令
- 单指令多数据流, 一条指令操作多个数据
一些限制
- 寄存器数量有限
- 分支预测失败
  - 可以考虑让编辑器尽可能生成条件传送指令

内存性能

吞吐量大, 但是延迟高
- 数组操作就可以并行化利用吞吐量 (易预测的内存访问模式)
- 链表操作则受限于延迟
写操作通常看起来很快, 因为 CPU 使用了存储缓冲区 (而不是高速缓存 / 内存)
但写后读会导致严重的性能惩罚
- 因为读操作必须检查存储缓冲区, 看看有没有未写入的数据需要转发 (连转发都没有就更吓人了)
- 这会导致数据依赖链, 使得流水线停顿

存储器层次结构

读访问时间是局部性的一个函数

存储技术

存储器分类

SRAM 静态随机存取存储器
- 用六晶体管电路存储每一位数据
- 双稳态
- 用于高速缓存
DRAM 动态随机存取存储器
- 用电容存储每一位数据 (需要不停地刷新)
- DRAM 有 \(d\) 个超单元 (字), 每个超单元有 \(w\) 个 DRAM 单元 (位)
- 所有超单元按行列组织起来 (提高了延时但是降低了针脚数量)
- 内存控制器需要提供行列, 分别是 RAS 和 CAS 信号
  - RAS 行地址选通信号, 会把一整行的所有超单元都移动到内部行缓冲区
  - CAS 列地址选通信号, 会选择行缓冲区当中的某个超单元
- 用于主存
FPM DRAM 快速页面模式 DRAM
- 先提交一个行地址
- 不修改行地址情况下想要访问多列, 只需一直提交列地址就行 (一直都在行缓冲区里)
- EDO DRAM 扩展数据输出 DRAM, 允许在 CAS 信号频率更高
SDRAM 同步动态随机存取存储器
- 时钟同步, 可以在一个时钟周期内发出多个请求
- 更快
- DDR SDRAM 两个时钟沿作为控制信号
VRAM 视频随机存取存储器
- 双端口, 允许同时读写
- 输出本质上是缓冲区一直位移
- 用于图形适配器 (现代用 GDDR)
ROM 只读存储器
- 非易失性存储器
PRAM 可编程只读存储器
- 每个存储器有一个可被高电流熔断的熔丝
- 可以编程但只能写一次
EPROM 可擦除可编程只读存储器
- 可以用紫外线擦除
- 编程 \(1000\) 次
EEPROM 电可擦除可编程只读存储器
- 用电信号擦除
- 编程 \(100,000\) 次
flash 存储器
- 一种 EEPROM
- 擦除单位是块, 写入单位是字
- 用于固态硬盘

存储设备

数据流通过总线在 CPU 和 DRAM 之间传输
- 一次传输称为一次总线事务 (读或写)
- 一次读事务
  - CPU 发出读请求, 包括地址和控制信号到 IO 桥
  - IO 桥将地址翻译为 DRAM 地址, 并发出 RAS 和 CAS 信号
  - DRAM 将数据发送回 IO 桥
  - IO 桥将数据发送回 CPU
磁盘对外表现为若干个扇区, 每个扇区 \(512\) 字节 (磁盘控制器维护映射到盘面, 磁道, 扇区)
这些 IO 设备通过对应控制器 / 直连连接到 IO 总线
- IO 总线连接到 IO 桥
CPU 使用内存映射 IO 来向设备发送命令
- 地址空间中有一块地址是为与 IO 设备通信保留的 (端口)
- 一次磁盘读
  - 发送一个命令字与其他的参数到磁盘的端口
  - 指明应该读的逻辑块号
  - 指明应该存储磁盘扇区内容的主存地址
  - 磁盘控制器将逻辑块号映射为物理地址
  - DMA 将数据从磁盘传送到主存
  - 传送完成后, 磁盘控制器向 CPU 发送一个中断
SSD 的随机写很慢
- 想修改一个页, 必须先擦除整个块
- 而且经常会擦除有用的数据, 还得重新写回去

局部性

局部性就是程序重复访问相同 / 相邻的数据项集合的倾向 (时空)
循环体越小, 循环次数越多, 指令的局部性越好
重复引用相同的变量有很好的时间局部性
步长越小越好

存储器层次

每一层都保存着下一层取出的数据
- 寄存器, 字
- L1 缓存, 缓存行
- L2 缓存, 缓存行
- L3 缓存, 缓存行
- 主存, 磁盘块
- 磁盘, 远程网络服务器的文件
形式化的
- 数据总是以块大小为传送单元在 \(K\) 与 \(K + 1\) 层之间传输
  - 需要时, 先在 \(K\) 层查找, 找到就命中
  - 否则就从 \(K + 1\) 层取回一个块 (不命中)
  - 并且替换 \(K\) 层的一个块
- 一个空的缓存有时被称为冷缓存
  - 这时候不命中叫强制性不命中
- 缓存的块放在哪必须有一个映射策略
  - 有时候缓存没有满, 但是因为策略的冲突导致一直不命中, 就叫做冲突不命中
- 缓存太小导致当前阶段的工作集合大于缓存, 那么就是容量不命中

高速缓存存储器

定义: \((S, E, B, m)\)
- \(m\) 物理地址总线宽度
- \(S = 2^s\) 组数
- \(E\) 每个组中的行数 (相联度)
- \(B = 2^b\) 块大小 (每一行里存储的字节数)
- \(C = S \times E \times B\) 总容量 (只算数据区, 不标记位)
块是真正的数据单元, 行是包含数据块和元数据 (有效位, 标记位) 的容器, 组是行的集合
缓存时将内存地址作为 key, 切割成三段
- 标记, 存在行的元数据中
- 组索引, 用于选择组 (策略性)
- 块偏移, 用于选择块内字节 (策略性)

直接映射高速缓存

每个组只有一行
没有标记, 直接找就行
注意地址划分时用中间位做组索引
- 高位会破坏空间局部性 (临近的内存老是进一个组)
但是依旧会冲突不命中 (抖动)
- 解决办法是数组开大点

组相联高速缓存

一个组里有多个行
并行检查组内所有行的标记位
替换策略
- 随机
- LFU
- LRU

全相联高速缓存

只有一组, 所有行都在这一组里
没有组索引位, 地址只分两部分
极少发生冲突不命中
但硬件极贵且慢

写操作

要保证缓存和主存的数据一致
写命中
- 直写, 就是同时写缓存和主存
- 写回, 只写缓存, 并把该行标记为脏, 只有当这行被驱逐时, 才写回主存 (时间局部性)
写不命中
- 写分配, 先把块读入缓存, 然后再写 (空间局部性, 因为大概率马上会写旁边的字)
- 非写分配, 直接写主存, 不进缓存
一般来说, 写命中用写回, 写不命中用写分配

真实硬件

L1 缓存分为指令缓存和数据缓存
L2 / L3 缓存通常是统一缓存
参数选择
- 缓存越大命中率越高, 但越慢
- 块越大空间局部性越好, 但冲突不命中率也会增加 (因为行数变少), 传送时间也会增加, 一般是 \(64\) 字节
- 相连度越高冲突不命中率越低, 但硬件复杂且慢
  - L1 为了快, 相连度较低 (如 \(8\) 路)
  - L3 为了减少去主存的次数, 相连度较高 (如 \(16\) 路)

编写高速缓存友好的代码

让最常见的情况运行得快 (核心函数的关键循环)
尽量减小每个循环内部的缓存不命中数量
存储器山
- 用步长描述空间局部性
- 用工作集大小描述时间局部性
- 用读吞吐量描述性能
我们看到
- 工作集小于 \(32 KB\) 时,数据全在 L1 缓存, 读吞吐量极高 (\(~12 GB/s\))
- 工作集稍大 (\(< 256 KB\)) 时, 溢出到 L2 缓存, 读吞吐量掉一半
- 工作集更大 (\(< 8 MB\)) 时, 溢出到 L3 缓存
- 工作集极大时, 只能去主存拿数据, 读吞吐量跌入谷底 (\(~900 MB/s\))
- 步长越大 (跟块大小比), 读吞吐量越低
- 即使数据量很大, 只要步长为 \(1\), 读吞吐量依旧很高 (CPU 硬件预取发挥作用)
重新排列循环使步长为 \(1\)
分块以提高时间局部性
- 尽可能让工作集适应缓存大小
- 认可做一些算法上没意义的分治