CSAPP3e第六章(存储器层次结构)
第六章 存储器层次结构(摘要与注解)
这一章也很好理解, 重点解释一些不太好理解或者书上介绍不是很清楚的地方, 然后列大纲用于以后复习看。
(UPD 做完 cache lab 后: 还是不太好理解的, cache lab 难度不小)
存储器分类
当前存储技术主要可以做以下分类:
- RAM 随机访问储存器, 断电后数据会消失
- SRAM, 静态随机范围储存器, 例如 CPU 的
L1/L2/L3缓存, 每个单元是六晶体管电路 - DRAM, 动态随机范围存储器, 每个单元是一晶体管电路。我们常用的主存一般是双倍数据速率同步的 DRAM (Double Data-Rate DRAM), 这是 DDR 内存的实际传输情况一般要频率乘 2 (有的会用 MT/s 作单位, 除以 2 就是频率)
- SRAM, 静态随机范围储存器, 例如 CPU 的
- ROM, 名字不重要, 一般可以读也可以写, 非易失性的
- PROM, 可编程 ROM, 只能被编程一次
- EPROM, 可擦写可编程 ROM
- EEPROM, 电子可擦写可编程 ROM, 一般每个单元会在编程 \(10^5\) 次后失效
- 闪存, 基于 EEPROM, 我们用的固态硬盘中的颗粒就是这个
- 旋转磁盘
DRAM 中的数据访问
一个传统 DRAM 芯片中分为 \(d=r \times c\) 个超单元, 每个超单元由 \(w\) 个 DRAM 单元组成(即 \(w\) 位信息)
每个 DRAM 芯片都连接到内存控制器芯片, 读 \((r, c)\) 时会把第 \(r\) 行全部放入内部行缓冲区, 然后取这一行的第 \(c\) 列。
多个 DRAM 芯片封装到内存模块中。一个 \(64\) 位字被分割为几个部分存储到不同 DRAM 芯片中, 要读取某个地址的主存内容, 内存控制器会先将这个地址转换为超单元地址 \((r, c)\) 然后广播到所有 DRAM 芯片最终合成为一个整体。
旋转磁盘
- 盘面->磁道->扇区的概念
- 柱面的概念
- 为了各个磁道扇区数相对相同, 因此有了记录区的概念
- 逻辑块(可能是硬件或固件)和磁盘控制器的概念
- 旋转磁盘的读取时间分为三部分
- 寻道时间
- 旋转时间(近似等于寻道时间)
- 传送时间(和前两者相比可忽略)
固态硬盘(SSD)
由闪存芯片(主控芯片)、闪存翻译层(类似磁盘控制器)和闪存颗粒构成, 闪存颗粒包含多个块, 每个块包含多个页
数据是以页单位读写的, 另外 SSD 读比写快。
基于闪存, 闪存基于 EEPROM, 所以这玩意每个块也是 \(10^5\) 次擦写后失效。但是现代很多平均磨损处理逻辑处理得很好, 用户不太需要担心这个问题。
计算机体系中的各部分数据交流
各部分之间通信一般是通过总线(bus) 中传递数据流。我们常说的 PCI, PCIe 就是总线标准, USB 是 通用串行总线的缩写。
主存到CPU
CPU 有总线接口, 通过系统总线连接到I/O桥(很多修笔记本的弹幕里常常说的先干南桥的南桥就是I/O桥), I/O桥通过内存总线连接到主存。
寄存器的数据传递到主存(store)和主存的数据传递到寄存器(load) 都需要两次总线事务+一次额外操作, 可以回想一下。
CPU 向旋转磁盘(或其他I/O设备)发送指令
磁盘通过总线适配器(SCSI/SATA/NVMe)连接到I/O总线, I/O总线连接到I/O桥, 剩下就还是I/O桥通过系统总线与 CPU 链接。
CPU 通过内存映射I/O(Memory Mapped I/O) 向 I/O 设备发送指令。地址空间内有一块地址(称为 I/O Port, 个人觉得这个叫法很蠢)专门为与 I/O 设备通信保留的(一个设备可能映射到多个 I/O Port)。
CPU 通过总线向磁盘控制器发送 \((指令, src: 逻辑块, dest: 主存某地址)\), 然后 CPU 不会等待 I/O (因为很慢, 这个间隔有约 \(16ms/clock\) 次时钟周期), 由磁盘控制器读完数据后直接通过总线传送给主存(这个过程称作 Direct Memory Access, DMA), 然后传送完成时磁盘控制器通过 中断(Interrupt) 提示并打断 CPU 通知其数据已到达。
之前看到过一个视频说某个网吧有个 DMA 包间, 我第一反应就是这个 DMA
结果还真是这个 DMA, 通过 DMA 技术读主存, 在另一台设备上进行游戏作弊
只能说真想不到技术还能这么用学操作系统或者组成原理继续往后学(异常控制流那里)还会介绍 Interrupt 和另一种控制流 Trap 的机制, 个人觉得这里挺好玩的。
存储器体系解构的设计理念
程序的局部性原理
- 时间局部性: 一个位置的数据在一个时间范围内被多次访问
- 空间局部性: 一个时间范围内访问相邻的多个位置的数据
书中以不同步长的循环对比, 分析了不命中率 并比较其效率
简单来说, 如果对某个位置的访问的最近上一层循环的下标和这个位置的访问下标一致, 那么显而易见这部分肯定是步长为 1 的循环, 步长为 \(k\), 高速缓存块大小为 \(B\) 字节, 不命中率为 \(min(1, wordsize \times k / B)\), 模拟以下就懂了, 实际上就是缓存只有 \(B\) 字节不够用了导致的容量不命中(这里我为了连续性调整了原书介绍的顺序, 缓存命中的概念在下面说)
编写缓存友好的代码需要我们:
- 对局部变量的反复引用(编译器可以缓存到寄存器)
- 多重视循环的局部性(其实时间复杂度也是主要看循环(或递归))
- 步长为 \(1\) 的引用模式是好的
缓存
基于局部性原理, 很自然地就有缓存的概念了。既然我们知道某个数据可能被多次引用/某一个部分的数据可能连续引用, 那么我们只要把大块存储中的这一小块常常被引用的部分放到较快(也较贵较小)的存储器中就能以低成本很大程度上提升存取效率, 这就是缓存的概念。
下面我们来看计算机中真实的缓存是如何实现的。
我们在第二章的博客中用设计师的视角, 以目的论为工具自然地理解了补码的意义和原理, 这里我们同样用设计师的视角来看:
首先, 缓存肯定是把地址空间内某个地址的数据缓存到 cache 里的某个位置,
那么我们首先要面对的问题就是: 放到哪个位置?
由于我们只是把一部分的数据拿出来缓存起来(其实虚拟内存是全相联缓存,
博客写到第九章时会说), 所以读一个数据时肯定可能出现读不到的情况,
称为”缓存不命中”, 我们把可能出现的三种不命中类型分别命名为:
- 强制不命中/冷不命中: 缓存是空的, 自然读不到数据
- 冲突不命中: 这个位置上有其他的数据了, 不是我要的数据, 自然不能读
- 容量不命中: 缓存太小, 当前工作集太大
从上面的三种情况, 我们意识到一些事:
- 由于缓存一定是小于等于其缓存的内容的存储器大小(也就是下面存储器层次结构中较下层的存储器)的, 而原则上我们又要让”任何一个地址的数据都可以进缓存(毕竟你不能预测哪些地址具有优秀的性质)“, 所以我们需要给某一段地址分为一组, 这些地址都缓存到同一个位置然后给每个位置编上索引(Index), 所以出现了冲突不命中
- 由于会冲突不命中, 为了辨别这个缓存位置当前存的是这个分组内的哪个地址, 我们需要还需要根据这组地址的唯一特征作一个标记(Tag), 然后根据缓存中这个组中某一行当前的标记来看这一行存的是哪个地址
- 当然, 缓存本身也需要空间, 我们通过缓存的另一个唯一特征(并且是要求连续的特征)作为偏移量, 来区分同一行内的数据块的多个字节中哪一个是地址的缓存
还是第二章说过的那句话, 由于我们实际上不是设计师, 所以在经过一些思考后可以直接看答案。
首先是地址分组的索引和唯一标记\(^{[*]}\), 以 0x12345678 为例,
这个地址的二进制值是00010010001101000101011001111000:
| 标记(前 \(t = 11\) 位) | 组索引(中间 \(s = 11\) 位) | 块偏移(结尾 \(b = 10\) 位) |
|---|---|---|
00010010001 |
10100010101 |
1001111000 |
对于这个 \(n = 32\) 位地址来说, 地址空间大小为 \(N = 2^n = 2 ^ {32} = 4294967296\) 个字节
这样 0x12345678 就是索引为
10100010101 = 1301 的组, 带有
10010001标记的那一行, 偏移为 1001111000 = 632
同时我们也意识到, 标记为 \(t\) 位,
索引为 \(s\) 位, 块偏移 \(b\) 位的 \(t + s
+ b\) 位地址需要 \(S = 2^s\) 组,
每组(理想上)需要 \(E = 2^t\) 行, 能够存
\(B = 2^b\) 个地址的缓存, 一共能存储 $
C = S E B$ 个地址, 这里缓存总容量 \(C = 2^{32}
= 2^{t+s+b}\), 恰好容纳了所有 \(N\) 个字节的的地址.
当然这是一个理论情况, 一般缓存容量都不足以不冲突地容纳所有 \(N\) 个地址,
这主要表现在大部分缓存大小不会是 \(C =
2^n\)。事实上很少有和被缓存的数据块总和等大的缓存,
那样直接用缓存作为主存就可以了。
我们以每组的行数 \(E\)
作为因素分类:
- 直接映射高速缓存, \(E = 1\), 狠狠冲突, 但是很简单(没有组索引, 但需要类似的行号作为标记)
- 组相联高速缓存, \(1 < E < C/B, S = \frac{C}{E \times B}\) , 上面的例子就是组相联
- 全相联高速缓存, \(E = C/B, S = 1\) (只有一组不需要组索引)
注意, 全相联高速缓存不一定就不会冲突了(比如第九章博客里要说到的主存作为虚拟地址空间的缓存, 也会出现缺页牺牲的情况), 不冲突的缓存只有缓存容量 \(C = N\) 的一种情况(正如前面所说很稀少), 如果满足 \(S = 1, E = C / B\), 那就是一个全相联缓存(有些资料会描述为”所有地址可以存入缓存的任意一行”, 因为这里只有一个组, 不受限制), 但是如果缓存容量 \(C < N\) , 在一些替换策略下还是会发生冲突.
这样我们通过对地址的分类也得出了组织高速缓存本身的方法:
在查找一个地址的缓存时, 通过中间 \(s\) 位组索引找到属于哪个组, 再通过中间 \(t\) 位标记找到属于哪个行(如果没有就是冲突不命中了), 然后根据块偏移找到具体是块内哪个字节(缓存行和块的大小是一致的, 这是一一对应的概念)
\(^{[*]}\): 这里块偏移是要求连续所以是最后几位很好理解, 但为什么组索引不设置为头部的 \(s\) 位而是分配在中间呢? 这是因为如果是分配在头部, 连续的几个地址就回分配在同一组(比如设置为前两位的话,
0x1000,0x1001,0x1010,0x1011这连续四个就分配在同一组了), 而缓存每次不命中都会加载一整块相邻的地址, 我们希望相邻的地址分散到不同的组, 来让缓存加载整个地址空间上尽可能多的地址, 可以增加缓存效率
冲突不命中时的替换策略
- 直接映射高速缓存没有所谓的替换”策略”, 因为有特定的位置放置规则, 所以直接替换对应位置即可.
- 组相联高速缓存和组相联高速缓存有多种替换策略, 如
LRU(Least Recently Used), 替换一段时间内最后一次访问时间最久远的那一行LFU(Least Frequently Used), 替换一段时间内最不常访问的一行
- 这里书中提了下全相联高速缓存会用在虚拟内存映射系统的 TLB, 算是提前剧透一下后面的内容
写入数据
以上重点讲了读某个地址时找其对应缓存的策略,
但其实写入数据也不(不一定)是直接写入主存(除非是下面要说的非写分配),
而也是先进入缓存的.
常见的策略有:
- Write-through 直写, 直接把写入缓存的内容同步更新写入主存, 缺陷是每次直写都会引起总线流量
- Write-back 写回, 由于我们读地址的数据是先找缓存, 所以其实没什么必要保持主存一直是最新的数据, 但当一个缓存行被替换掉时就必须得更新主存了, 因为此时缓存里被替换掉的数据已经不存在了。这种被替换时才写回主存的叫这个名儿。
写不命中
写入数据先进缓存, 但缓存里没缓存到这个数据怎么办?
- Write-allocate: 加载我们要写的数据所在的这一整块进高速缓存, 然后根据上面的策略更新缓存, 试图利用局部性原理, 但缺陷和直写一样
- No-Write-allocate: 不管缓存, 直接写入主存
其他
L1 缓存由于有着接近寄存器文件的速度, 所以不仅有储存数据的
d-cache, 还有储存指令的 i-cache (d = data, i =
instruction), 这个 i-cache 的事之前在 rCore Camp 的秋令营接触过一点
这些已经在保持正确性和完整性的情况下基本概括并且有逻辑地解释了原书这部分的内容了, 除了有关 6.4.7 高速缓存参数 的性能影响这一节, 因为太好理解了就不作解释了
另外就是你看你学了这么多, 其实按原书的话说只学了缓存的皮毛,
绝望吗
其实组成原理这一整门课都是在学皮毛(), 毕竟这门课叫 ICS
(Introduction of Computer Science),
btw, 北大的那门 ICS 也是买的这门课(还是这本书来着)的版权,
Lab 也是 15213 的 Lab 改的
笔者在写这篇文章的时候记得几个月前北大的 ICS
课期末考试因为计算上无用地复杂在知乎上起节奏了 (
我就是因为这个所以没去北大(大雾
存储器层次结构
观察各种存储器的发展速度, 我们发现一定程度上存储器的速度可能会制约到芯片的效率, 成为计算机运算能力的瓶颈。加上较快的存储设备也一般比较昂贵, 所以我们发展了存储层次结构的概念:
其实我们在下一章学到地址空间与虚拟内存就会发现, 其实这里每一层都是对其下一层的缓存。
通过局部性原理和这样的一层缓存一层的层次结构, 我们有效提升了存储器对解决实际问题的效率, 使其不再成为制约芯片算力的瓶颈。
至于瓶颈这个事可以类比现在的显示芯片和屏幕, 现在
2K/2.5K/4K/8K 的屏幕迅猛发展,
但是现在顶级的显示处理器也无法带动 4K 下较为流畅的游戏运行,
一定程度上制约了屏幕的发展。然后 NVIDIA 和游戏厂商还在 DLSS
这种邪路上越走越远
存储器山
本书封面图, 用以直观展现高速缓存对程序性能的影响。
- 随着步长增大, 程序的空间局部性越来越差, 整体展现为一个平滑的斜坡。
- 随着数据大小的增大, 较小的(也是较高速的)缓存不能再容下整个数据块, 程序的时间局部性变差, 到一定大小后会缓存到存储层次结构中较低层(较慢)的缓存, 数据所以显示为一个平台一个平台往下掉
- 还有更多有趣的细节在书中有提
个人对这种数据可视化的浪漫其实无感, 但这张图例外, 确实很漂亮, 也很清晰。
这篇文章从 22:04:30 写到了 0:45:07,
虽然写的时候还没放赞助二维码,
但是如果你读到这的时候发现已经放了二维码能不能扫一杯咖啡钱(,
现在大一(好了现在是大二了)急需零花钱捏QAQ(但还是急需)