内存管理

从社招角度来看，怎样才是一个 NB 的员工，就内存管理领域来看：

研一的时候其实看过《计算机体系结构：量化研究方法》，当时看的是英文版，个人感觉收获蛮大，算是我后来一切工作的基础。如今有机会继续从事这方面的工作，很大程度上可以归结为运气好。 现在需要深入研究内核的内存管理模块，所有书中有关内存的只是需要回顾一下，原来的笔记在这里。略显杂乱，看完之后没有进一步归纳总结，这里算是之前工作的进一步。

cache 结构

直接映射

组相联映射

全相连映射

PIPT 和 VIVT 的区别

在查询 cache 时，使用的是虚拟地址还是物理地址？不同处理器使用的不一样。

物理高速缓存

当处理器查询 MMU 和 TLB 并得到物理地址之后，使用物理地址查询 cache，这种 cache 称为物理高速缓存。使用这种 cache 的缺点就是慢，因为需要等 MMU 和 TLB 完成地址转化后才能查询 cache。

虚拟高速缓存

即使用虚拟地址来寻址。但是这会导致如下问题：

cache 分类

在查询 cache 时，根据使用虚拟地址还是物理地址来查询 tag 域或 index 域，我们可以将 cache 分成如下几类：

MESI 协议

目前处理器的 cache 结构一般是 L1 D-cache, L1-Icache, L2-cache 和共享的 L3-cache，在这些 cache 上会存在同一个数据的多个副本，因此需要 cache 一致性协议去维护不同数据副本之间的一致。

实现一个 cache 协议的关键就是跟中每一块共享内存的状态，这些状态用 bit 位表示，而这些 bit 位也保存在内存块中。cache 一致性协议可分为两类：

关于这两种协议的介绍，网上的资料大多不准确，建议看《量化研究方法》第五章。

目前广泛使用的是 MESI(Modified, Exclusive, Shared, Invalid)协议，一种总线监听协议。协议中的 4 中状态（这些状态是不是存储在 cache line 中）：

状态 说明
M 该 cache line 有效，数据已被修改，和内存中的数据不一致，数据只存在于该 cache line 中
E 该 cache line 有效，数据和内存中的一致，只存在于该 cache line 中
S 该 cache line 有效，数据和内存中的一致，多个 cache line 持有该数据副本
I 该 cache line 无效

MESI 协议在总线上的操作分为本地读写和总线操作。本地读写指的是本地 CPU 读写自己私有的 cache，总线读写是指 CPU 发送请求到总线上，所有的 CPU 都可以收到这个请求。MESI 的操作类型如下所示：

操作类型 描述
本地读（PrRd） 本地 CPU 读 cache line
本地写（PrWr） 本地 CPU 写 cache line
总线读（BusRd） 总线监听到一个来自其他 CPU 的读 cache line 请求。收到信号的 CPU 先检查自己的 cache line 中是否有该数据，然后广播应答信号
总线写（BusRdX） 总线监听到一个来自其他 CPU 的写 cache line 请求。收到信号的 CPU 先检查自己的 cache line 中是否有该数据，然后广播应答信号
总线更新（BusUpge） 总线监听到更新请求，请求其他 CPU 做一些操作。其他 CPU 收到请求后，若自己的 cache line 中是有该数据，则需要做无效 cache line 等操作
刷新（Flush） 总线监听到刷新请求。收到请求的 CPU 把自己的 cache line 数据写回 mm 中
刷新到总线（FlushOpt） 收到该请求的 CPU 会将 cache line 数据发送到总线上，这样发送请求的 CPU 就可以获取该 cache line 内容

下图为 MESI 协议中各个状态的转换关系。

img

cache 优化

3 种缺失率

一般采用缺失率来衡量不同缓存组织方式的优劣，可以将缺失率分为三个类别：

6 种基本优化方法

10 种高级优化方法

首先可以将这 10 中优化方法分为 5 类：

1. 小而简单的一级 cache 降低命中时间和功耗

L1 cache 的关键是快，要尽可能接近 CPU 的频率，同时考虑到功率的影响，L1 cache 不可能做的很大。下面两个图分别是 cache 大小，相连程度同相对访问时间的关系与 cache 大小，相连程度同耗能之间的关系。

quantitative-1.jpg

quantitative-2.jpg

2. 采用路预测缩短命中时间

路预测算法在 cache 中使用额外的 bit 来预测下一次 cache 访问的路。多路选择器会提前选择需要访问的 block，在访问时之做简单的 tag 比较。如果预测成功，那么下次访问的 cache 访问延迟就是快速命中时间（？），如果没有成功，那么多路选择器将会比较其他的 block，并修改路预测器，这需要额外的一个时钟周期。

模拟器的测试结果表明，在 2 路组相联中，路预测的成功率超过 90%，在 4 路组相连中超过 80%，并且在 I-cache 中的成功率高于 D-cache。对于高性能的处理器，设计预测失败时一个时钟周期的暂停时间是关键。

3. cache 访问的流水线化和 multibanks cache 以增加带宽

缓存访问的流水线化能够增加 cache 带宽，多组 cache 能够在一个时钟周期内进行多个访问。这两项优化技术最初是用在 L1 cache 上的，能够增加指令带宽，现在多组 cache 也用在 L2 和 L3 cache 上了，主要作为能耗管理（？）。

L1 cache 访问的流水线化可以支持高时钟频率（也就是将一次访问 cache 分成多个阶段，适用于多级流水线的处理器），但是也会增加访问延迟。例如采用了 I-cache 流水线化访问的奔腾系列处理器，在 90 年代中期一次访问是 1 个时钟周期，到 2000 年的奔腾 2 处理器，需要 2 个时钟周期，而现在的 Core i7 处理器，则需要 4 个时钟周期。但是高时钟频率会导致分支预测失败的代价非常大。目前大部分高性能处理器采用 3-4 级 cache 访问流水线。

处理 I-cache 访问流水线化要比 D-cache 简单，I-cache 可以依靠高效的分支预测技术一次读取多条指令，但是 D-cache 会有读、写同时进行的问题，所以将 cache 分成多个不同的 bank，每个 bank 都可以独立的响应访存操作。这一技术最开始是用在 DRAM 上的（确实，包括 SSD 都是分成多个 die 之类的，每个可以独立操作）。

在 L2 和 L3 cache 中，也会使用 multibanks 技术，这样如果没有在访问 bank 时造成冲突，就能够同时处理多个 L1 miss，这是支持下一种优化方法的关键技术。

4. 无阻塞 cache 以增加带宽

对于乱序多发射处理器而言，处理器需要能够在发生 D-cache miss 时继续执行，而不是阻塞。无阻塞 cache 就能够做到在发生 D-cache 时继续 cache hit，这样一方面能够减少 D-cache miss 时发生的性能损失（ CPU 阻塞），一方面降低了能耗。一般将这种优化称为 “hit under miss”。

更进一步的方式是 “hit under multiple miss” 或 “miss under miss”，大多数高性能处理器支持这些优化，如 Core 系列处理器。

通常来说，乱序发射处理器能够处理 L1 D-cache miss 而 L2 cache hit 的情况，但是无法处理很多低等级 cache miss 的情况。处理器处理 miss 次数的能力取决于如下几种情况：

虽然无阻塞 cache 能够提高性能，但是它们实现起来比较困难。有两个点需要注意：

所有无阻塞 cache 能够提高带宽，减小 miss 后的阻塞时间，因此能够降低执行时间和能耗，但是需要额外的逻辑单元，增加了硬件的复杂性。

5. 关键字优先和提前重启降低缺失代价

这一优化基于一个现象：处理器每次通常只需要一个 block(cache line?) 中的一个 word(16/32 bits)。因此这一优化做的是不等块中所有的信息都 load 到 cache 中就将请求的 word 发送给处理器并让其恢复工作。这里有两种具体的做法：

这种优化方式通常只在 large cache 设计中有效。

6. 合并缓冲区以降低缺失代价

无论采用写直法还是写通法，都需要用到 write buffer，在这两种方法中，数据都是先写入到 write buffer 中，然后由 write buffer 写入到内存或下一级 cache 中。

合并缓冲区的设计思想如下图所示：

quantitative-3.jpg

当 write buffer 中包含 modified block 时，在写入 buffer 前就可以检查新的数据地址是否符合原有的有效的 buffer entry。如果符合的话，将新的 block 与该 entry 合并。

这一优化技术能够提高内存利用率，因为 multiword writes 比 one word at a time 要快，而且这样 write buffer 能够存储更多的数据，降低延迟。

7. 编译优化降低缺失率

这是一种软件优化方法，硬件设计人员的最爱！目前有如下优化方式在编译器中应用广泛。

quantitative-4.jpg

quantitative-5.jpg

8. 硬件预取指令和数据降低 miss penalty 和缺失率

指令预取是由 cache 之外的硬件完成的。通常处理器在发生 cache miss 后会取两个 block（这里的 block 应该是指 cache line），一个是请求的 block，放置在 I-cache 中；一个是顺序的下一个 block，放置在 instruction stream buffer 中。当然，如果预取成功率低，那么会对性能造成消极的影响。

9. 编译器控制预取降低 miss penalty 和缺失率

和硬件预取类似，这个编译器完成的。编译器插入预取指令，其可分为两种方式：

这两种预取方式都可以分为 “faulting” 和 “nonfaulting”，也就是在预取时会不会发生虚拟地址异常或触发保护错。”nonfaulting” 预取就是到预取错误时不走异常流程，而是不进行任何操作（也就是说这条 load 指令变成了一条 no-ops 指令）。

最高效的预取是对于程序来说，预取操作是透明的，其不会改变寄存器和内存的内容，也不会导致异常。

控制预取能够生效的条件是 cache 在进行预取操作时能够继续向处理器发送指令和数据。我们来看一个简单的编译器插入预取指令的例子：

首先我们假设我们有一个 8KB 大小的直接映射的 cache，cache line 是 16 bytes（共有 512 个 cache line），采用写回法。下面的变量 a, b 都是 8 bytes 的双精度浮点类型。我们来计算一下总共会发生多少次 miss。

for (i = 0; i < 3; i = i + 1)
	for (j = 0; j < 100; j = j + 1)
		a[i][j] = b[j][0] * b[j + 1][0];

首先对数组 a 的访问会导致 miss。对 a 总共读取 3*100 次，因为每个 cache line 能够存放两个元素，且对 a 的访问是行相关的，那么会发生 3 * (100 / 2) = 150 次。对数组 b 的访问是列相关的，且每次访问 j, j+1 两个元素，所以会发生 100 + 1 = 101 次访问（另外 + 1 是因为第一次访问 b[0][0] 和 b[0][1] 都发生了 miss）（画图解释更清晰）。总共发生了 251 次 miss。

再来通过编译器预取优化一下：

for (j = 0; j < 100; j = j + 1) {
	prefetch(b[j + 7][0]);
	/* b(j,0) for 7 iterations later */
	prefetch(a[0][j + 7]);
	/* a(0,j) for 7 iterations later */
	a[0][j] = b[j][0] * b[j + 1][0];
}

for (i = 1; i < 3; i = i + 1){
	for (j = 0; j < 100; j = j + 1) {
		prefetch(a[i][j + 7]);
		/* a(i,j) for + 7 iterations */
		a[i][j] = b[j][0] * b[j + 1][0];
    }
}

这样的话，我们预取了从 a[0][7] 到 a[2][99] 和 b[7][0] 到 b[99][0] 的数据到 cache 中。剩下的元素：

所以最终的结果是用额外的 400 条预取指令减少了 232 次 cache miss。

然后我们来考虑一下每种指令的执行时间。

首先假设预取指令和处理器执行是重合的，不额外消耗时间。

优化前的循环每次循环为 7 个时钟周期，需要 3 * 100 * 7 = 2100 个时钟周期。每次 cache miss 耗时 100 个时钟周期，需要 251 * 100 = 25100 个时钟周期，共需要 27200 个时钟周期。

优化后的循环，第一个循环每次循环为 9 个时钟周期，需要 9 * 100 = 900 个时钟周期。产生了 7 + 4 = 11 次 cache miss，需要 11 * 100 = 1100 个时钟周期。第二个循环每次循环为 8 个时钟周期，需要 8 * 200 = 1600 个时钟周期，产生了 4 + 4 = 8 次 cache miss，需要 8 * 100 = 800 个始终周期。共需要 900 + 1100 + 1600 + 800 = 4400 个时钟周期，相比于优化前快了 27200 / 4400 = 6.2 倍。

这只是一个简单的用来理解编译器优化的例子，实际情况比这复杂。

10. 使用 HBM 扩展存储层次

目前大部分服务器采用 HBM packaging 的方式来使用大容量的 L4 cache。L4 cache 的介质为 DRAM，容量在 128 MB 到 1 GB 之间。但是使用如此大容量的 DRAM 来作为 L4 cache 存在一个问题，如果 block（这个 block 可以理解为最小存取单元） 太小，tag 占用的空间太大；block 太大，空间利用率低，cache miss 高。这就引入了 HBM(High Bandwidth Memory)。

HBM（High Bandwidth Memory）是一种高带宽内存技术，由英特尔和 SK 海力士等公司联合开发，旨在解决现代计算机系统中的内存瓶颈问题。

HBM 内存使用 3D 堆叠技术，将多个内存芯片垂直堆叠在一起，通过微细间隔的层层排列，实现了高度集成和高带宽的数据传输。同时，HBM 内存还采用了异步时序、多通道和错误修复等技术，提高了内存的性能和可靠性。

与传统的 DDR SDRAM 相比，HBM 内存具有以下优点：

  1. 更高的带宽：HBM 内存可以提供更高的带宽，以满足 GPU、FPGA 等高性能计算设备的需求。
  2. 更小的封装尺寸：HBM 内存采用 3D 堆叠技术，可以将多个内存芯片集成到较小的封装中，提高系统的集成度和可扩展性。
  3. 更低的能耗：HBM 内存使用异步时序技术，可以根据实际数据传输需求动态调整电压和频率，以节约能源。
  4. 更低的延迟：HBM 内存采用多通道设计和高速串行连接技术，可以实现更低的延迟和更高的吞吐量。

HBM 内存主要用于高性能计算、人工智能、数据中心等领域，为计算机系统提供更高效、更可靠、更节能的内存解决方案。

它通常用来连接高性能图形加速器，网络设备，在高性能数据中心连接各种专用加速器或者在超级计算机中连接各种 FPGA。所以 HBM 只是用来扩展存储层次的手段。

为了解决上述 block 大小的问题，现在有如下几种方式：

思考

Reference

[1] 计算机体系结构：量化研究方法

[2] 奔跑吧 Linux 内核