Patterson and Hennessy 学习笔记 #5 —— Chapter 5 Large and Fast:Exploiting Memory Hierarchy

Ideally one would desire an indefinitely large memory capacity such that any particular ... word would be immediately available. ... We are ... forced to recognize the possibility of constructing a hierarchy of memories, each of which has greater capacity than the preceding but which is less quickly accessible.

-- A. W. Burks, H. H. Goldstine, and J. von Neumann

-Preliminary Discussion of the Logical Design of an Electronic Computing Instrument-, 1946

Introduction

如前所述，码农和硅农之间有一个矛盾：码农希望内存无限大的同时访问速度足够快，而硅农手上的存储器容量大的速度不够快、速度快的容量不够大。实际上程序访问数据并不是完全随机的，局部性原理 告诉我们，在任何时候程序大概率都是只访问地址空间中相对较小的一部分：

• 时间局部性：如果某个数据被访问了，那么近期很可能会被再次访问
• 空间局部性：如果某个数据被访问了，那么和它相邻的数据也很可能被访问

所以解决前面矛盾的方式就是：利用局部性原理，构建存储器层级结构 Memory Hierarchy，用最低的成本向用户提供尽可能大的存储容量的同时，使得速度和最快的存储器相当。

Memory Hierarchy 的几个概念：

Memory Technologies

主要有 4 种：

Caches

Cache 的形式就是一张 table，大概可以分成 3 个字段：

• valid 指示本 entry 是否有效
• tag 指示本 entry 保存的是 DDR 的哪个地址的数
• data 保存具体数据

使用地址索引 cache 时，地址会相应地被分成 3 部分：

• offset：索引 block 内部的 byte
• index：索引 block
• tag：和 cache 中的 tag 做比较

Mapping

Cache 的组织方式可以分为 3 类：

直接相联和全相联可以看成是组相联的特例：

• 直接相联 = 1-way 组相联
• 全相联 = 只有 1 个 set 的组相联

Writing

如果是 hit 情况，可以有两种操作：

• write through：把数据同时写入 cache 和 DDR
• write back：只把数据写入 cache，替换时再把该 block 全部写入 DDR

write through 的优势：

• 即使需要配合 write buffer，实现依然要比 write back 简单
• 处理 miss 比较简单，因为不需要把 block 写入低层系统

write through 的缺点：

性能很差。假设一个系统中有 10% 的 store 指令，直接写入 DDR 需要花费 100 个 cycle，而没有 cache miss 时的 CPI 为 1, 那么整个系统的 CPI 为 \(1 + 100 * 10\% = 11\)，性能大概降低了 10 倍。

write back 的优点：

• 速度快，可以以 cache 的速度接收单个 word
• 同一个 word 的多次操作可以合并成一次低层操作
• 一整块写回低层时，可以充分利用高带宽传输

如果是 miss 情况，也可以有两种操作：

• write non-allocate：直接把 block 写入 DDR
• write allocate：把该 block 从 DDR 中读到 cache 中，分配空间保存，然后再替换成新数据

产生 write non-allocate 的主要原因是有些程序会写整个 block，比如操作系统可能会把 memory 中的某一个 page 全部填 0。在这种情况下，取回数据就没有必要了。

一般 write through 和 write non-allocate 搭配，write back 和 write allocate 搭配。如果 write back 中某个被修改过的 block 发生了 miss，那么就必须先把该 block 写回到 DDR 然后再把新数据写入该 block。简单地直接用新数据覆盖该 block 会丢失之前的修改数据，因为这些数据没有在低层中进行备份。所以要完成这个过程要么花费两个 cycle（第一个 cycle 检查是否 hit，第二个周期执行写操作），要么使用 write buffer（只花费一个 cycle，先把修改的数据写入 DDR，在下一个周期把新数据从 buffer 写入 cache）。

Replacing

常见的替换策略有 3 种：

• 随机替换
• FIFO
• LRU (least recently used)

一般来说，在相联度不低（2-way 或 4-way）的时候 LRU 的实现代价非常高，因为要追踪记录使用信息的代价很高。即使是 4-way 也是用近似的方法来实现：4-way 分成两组，先用 1bit 记录那一组是 LRU，再在组内使用 1bit 记录哪个 block 是 LRU。

Measuring Cache Performance

CPU time 可以分成两部分：CPU 的执行时间 + 由于 memory 系统导致的 stall 时间。一般来说，cache hit 的开销时间算在执行时间内，所以有下面的公式：

\(CPU\ time = (CPU\ execution\ clock\ cycles + Memory\ stall\ clock\ cycles) * Clock\ cycle\ time\)

我们假设 Memory stall 的时间开销主要来自于 cache miss，并且使用简化的 memory 模型。实际处理器中，读写产生的 stall 非常复杂，精确的性能预测通常需要对处理器和存储系统进行非常详细的仿真。所以我们可以定义下面的公式：

\(Memory\ stall\ clock\ cycles = (Read\ stall\ cycles + Write\ stall\ cycles)\)

其中读的 cycle 数可以用每个程序中读指令的数量、读操作的 miss penalty、读 miss rate 三个因素来定义：

\(Read\ stall\ cycles = \frac{Reads}{Program} * Read\ miss\ rate * Read\ miss\ penalty\)

写的情况要复杂一些，对于 write through 的 cache 而言，分为两部分：

\(Write\ stall\ cycles = (\frac{Writes}{Program} * Write\ miss\ rate * Write\ miss\ penalty) + Write\ buffer\ stall\)

因为 write buffer 不仅和写指令的频率有关，还和写操作的执行时机有关，不能用简单公式来计算。幸运的是，如果系统设置合理，wirte buffer 的阻塞时间可以变得很小，近似忽略。如果系统设计不合理，则设计人员应该用更深的 write buffer 或者是使用 write back 机制。

在大部分 write through 方案中，读写的 penalty 是一样的（都是从 DDR 中读回数据），假设 write buffer 部分可以忽略不计，则上面的公式可以简化为：

\(Memory\ stall\ clock\ cycles = \frac{Memory\ access}{Program} * Miss\ rate * Miss\ penalty\)

或者是：

\(Memory\ stall\ clock\ cycles = \frac{Instrcutions}{Program} * \frac{Misses}{Instrcution} * Miss\ penalty\)

也可以采用另外一种测量方式对 Cache 性能进行建模：每次访存的平均时间 AMAT(Average memory aceess time)。显然，Cache 系统设计越合理，对 Core 表现出来的性能越好，AMAT 就越小。根据定义可以知道 AMAT 的计算公式如下：

\(AMAT = Time\ for\ a\ hit + Miss\ rate * Miss\ penalty\)

对于多级 Cache 系统，AMAT 公式如下（以两级 Cache 为例）：

\(T_{avg}=H_1*C_1 + (1-H_1)*(H_2*(C_1 + C_2) + (1-H_2)*(C_1 + C_2 + M)\)

每个符号的含义：

• \(H_1\) 表示 L1 cache 的命中率
• \(H_2\) 表示 L2 cache 的命中率
• \(C_1\) 表示 L1 cache 命中访问时间
• \(C_2\) 表示 L2 cache 命中访问时间（即 L1 miss 但是 L2 hit 的 penalty）
• \(M\) 表示 DDR 的访问时间（即 L2 miss 的 penalty）

也可以换一种算法：

\(T_{avg}= C_1 + (1-H_1)*C_2 + (1-H_1)*(1-H_2)*M\)

可以证明两种方式是等价的。

The Three Cs

所有的 miss 可以被分为 3 类（3C 模型）：

这几种失效相互之间是关联的，改变设计中的某一方面会直接影响到其中某几种失效。

Controller

• 阻塞式 Cache：基于 FSM 的控制器，必须要等到 Cache 处理完前一个请求后处理器才能继续执行
• 非阻塞 Cache：性能更高

Coherence

• coherence：定义了 read 操作返回什么数据
• consistency：定义了 write 值什么时候才能被 read 操作返回

问题产生的原因：

共享数据在多个 cache 都有备份，多个备份之间会出现一致性问题。

解决方法：

多核系统一般通过一种硬件协议来维护 cache 之间的一致性，这个协议叫做 cache coherence protocals Cache 一致性协议。显然问题由共享数据引起，所以一致性协议的关键就在于追踪所有共享 block 的状态。

最流行的一致性协议叫做 snooping 窥探协议：每个 cache 不仅从 memory 中复制了 block 数据，同时还复制了 block 的状态，按照分布式的方式管理这些状态。每个 cache 都可以通过广播媒介（总线 / 网络）访问，而且每个 cache 控制器都会监听媒介，判断自己是否包含了当前总线上访问的数据。snooping 的实现比较简单，但是它的可扩展性比较低（因为不同所有 core 之间都要交互，复杂度和通信量成指数增长）。

有种保证一致性的方法：确保每个 core 在写数据时是互斥访问，因为这种协议在写一个数据时会设置其他 cache 中的备份无效，所以叫做 write invalidate protocal。

如果一个存储系统满足了下面 3 个条件，就可以认为该存储系统是一致的：

1. 处理器 P 对位置 X 的 write 后面紧跟着 P 对 X 的 read 操作，并且 write 和 read 之间没有其他处理器对 X 进行操作，那么 read 返回的一定是 write 的值
2. 在其他处理器对 X 完成 write 之后，P 对 X 进行 read 操作，这两个操作之间要有足够的时间间隔，并且没有其他处理器对 X 进行写操作，这是 P 的 read 返回的一定是 write 的数据
3. 对同一个地址的操作是串行执行的，即任何两个处理器对同一个地址的操作在所有处理器看来都是相同的顺序

Dependable Memory Hierarchy

如果 memory hierarchy 只是单纯的追求速度，无法保证可靠性，那么它将毫无吸引力。如第一章介绍，dependability 的重要方法就是冗余。所以我们首先讨论如何定义和测量可靠性，然后再看看如何通过冗余设计出可靠的存储器。

Defining Failure

\(Availability = \frac{MTTF}{MTTF + MTTR}\)

我们希望系统有很高的可用性 availability，一种简单表示方法是 “ 可用性 9 的数量 ”，类似于黄金纯度一样，9 的数量越多表示可用性越好。增加 MTTF 或者是减少 MTTR 都可以提高可用性。

为了提高 MTTF，可以提高元件的质量或者是设计一个不受元件故障的系统。因为元件故障不一定和导致系统 failure，所以专门定义一个词 fault 来表示元件的故障。有 3 种方法提高 MTTF：

• fault avoidance：合理构建系统避免发生 fault
• fault tolerance：采用冗余措施，发生 fault 时系统仍然正常工作
• fault forecasting：预测故障，在发生之前替换失效元件

为了减小 MTTR，可以采用检测、诊断、修复工具来处理 failure。

Hamming SEC/DED

Richard Hamming 因为发明这个编码于 1968 年获得图灵奖。如果一种编码可以检测出是否发生 1 bit 错误，我们将其称为 1 bit 错误检测编码 error detection code。

Hamming 编码采用 “ 奇偶校验 ” 码来检测是否发生错误：统计码字中 1 的数量，然后根据统计结果设置校验位（奇数为 1, 偶数为 0）。所以 N+1 的总 bit 中 1 的个数永远是偶数个，如果从 memory 中读出的数据包含奇数个 1, 那么就说明发生了错误。

显然，这个方案只能检测到奇数个错误的情况，而且同时发生 3 个错误的概率非常小，所以一般用来检查 1 bit 错误。

Hamming 为了实现纠正错误的目的，设计一种将数据映射到距离为 3 的码字的方式，为了表达敬意，我们称为 Hamming Error Correction Code, ECC。因为这种编码可以纠正 1bit 错误，检测 2bit 的错误，所以叫做 Single Error Correcting/Double Error Detecting (SEC/DED)，它广泛地应用于服务器的内存中。一般 8 byte 的数据正好需要 1byte 的额外开销，所以许多双列直插式存储模块 DIMM 的宽度是 72 bit。

Virtual Memory

DDR 也可以充当 disk 的 “cache”，这种技术叫做虚拟存储器 virtual memory，就像 cache 一样，局部性原理也适用于 VM。

相似点：

不同点：

因为每个程序都有自己的地址空间，所以 VM 要实现从程序地址空间到物理地址之间的转换，这个转换操作加强了一个程序的地址空间和其他 VM 之间的保护。virutal page number 比 physical page number 多得多是描述一个无限容量的虚拟存储器假象的基础。

virtual address = {virtual page number, page offset} ==> pyhsical address = {physical page number, page offset}

page fault 的代价非常高，每次都要花费几百万个 cycle 才能完成处理（DDR 的速度大概是 disk 的 100,000 倍）。所以 VM 系统的很多设计决策都受 page fault 的影响：

• page 必须要足够大，以缓解很长的访问时间。典型 page 的大小为 4～16 KB
• 采用全相联的结构来降低 page fault
• 通过软件处理，软件相比于 disk 的开销非常小，而且可以采用聪明的替换算法，至少能稍微降低一点 miss rate，算法的开销就值了
• 不可能使用 write through，只能用 write-back

Mapping & Replacing

如上所述，因为 page faut 的代价太高了，所以为了尽可能地降低发生概率，VM 采用全相联的组织方式，允许 virtual page 可以映射到任何一个 physical page 上，这样操作系统就可以在发生 page fault 时用复杂的算法和数据结构跟踪 page 的使用过程，然后选择某个在长时间不会用到的 page 进行替换。

但是全相联的查询复杂度非常高，基本上不可实现，所以 VM 通过一个存储在 DDR 中的特殊的结构 page table 来查询：用 virtual page number 查询 physical page number。因为每个程序都有自己的地址空间，所以有自己的 page table，为了找到自己的 page table，会有一个寄存器 page table register 指向它。

Page Fault

因为 virtual page 可能会映射到 DDR 中，也有可能会映射到 disk 中，所以操作系统一般会在创建每个 process 时开辟一段空间来存储所有的 page，这个空间就叫做 swap space。所以相应地就需要一个数据结构来记录 virtual page 到底是在 DDR 中还是 disk 中，只需要 1bit 的 valid 即可，从逻辑上讲，virtual page 到 DDR 和 disk 的映射是同一张表，但是一般是按照两张独立的表来实现的。

发生 page falut 时，操作系统通过软件算法（LRU）选定要被替换的 page，把它存储到 swap 区域。

Wrting & TLB

因为写回的代价太高了，所以只能用 write-back 的方式把一整块 page 都写回。

程序的每次 memory 访问都需要完成两个步骤：首先查询 page table 得到 physical address，然后根据查询到的地址获取数据。提高访问性能的关键就在于 page table 的访问也有局部性：如果查询了某个 page number，那么很可能会再次查询它，因为它指向的数据具有局部性。

所以处理器会包含一个特殊的叫作 TLB(Translation-Lookaside Buffer) 的 cache 用来追踪最近使用过的地址变换。所以 TLB 的读写操作也遵守前面 cache 的讨论，简单的一次读操作的流程如下。

                lookup TLB
read reference -----------> hit ---------------------------> translate
                    |                                            ^
                    |            lookup page table               |
                    |-----> miss -----------------> hit ---> loading into TLB
                                             |
                                             |----> miss --> OS.exception handle

因为 TLB 是一个小 cache，所以它的设计考虑因素和规格都符合前面 cache 部分的讨论。下面是一个典型配置：

Fallacies and Pitfalls

• Fallacies 谬论：错误概念
• Pitfalls 陷阱：特定条件下成立的规律的错误推广

陷阱：写代码或通过 compiler 生成代码时忽略 memory 系统的行为

另外一个描述是：在写代码时，程序员可以忽略存储器存储结构。显然，这个结论是错误的。

陷阱：模拟一个 cache 时，忘记说明 byte 地址和 block 大小

要区分清楚 byte 地址、block 地址，word 地址。举例说明，假设有个容量为 36 Byte 的 cache，block 大小为 4 Byte，那么内存地址 36 的 block 地址是 9，所以映射到 block1 中（\(9\ modulo\ 8 = 1\)）；如果 36 是 word 地址，那么它会映射到 block4 中（\(36\ modulo\ 8 = 4\)）。

陷阱：对于共享 cache，组相联度 < 核的数量 / 共享该 cache 的线程数

如果 way 数比 core/ 线程数量少时，可能会有严重的性能缺陷。比如，32 个 core 竞争同一个 set 内的 16 个 way，性能很差。

陷阱：用平均的 memory 访问时间来评估 out-of-order 处理器的存储器层次

如果发生 miss 时处理器阻塞，那么就可以用平均时间来评估；如果是乱序执行的处理器，可能在 miss 时会继续执行其他指令，此时要准确评估存储器层次的唯一办法就是模拟乱序执行处理器和存储器层次。

谬误：disk 实际的故障率和规格书中的一致

实际评估的结果表明并不相同。

谬误：操作系统是调度 disk 访问的最佳地方

磁盘自己知道逻辑地址和映射的物理地址，所以磁盘比操作系统好。

陷阱：为一个不支持虚拟化的 ISA 实现虚拟机监视器

某些 ISA 要支持 VMM 必须新增一些其他指令。

Summary

图书馆系统和 memory hierarchy 很相似：

所以问题也可以类比：