CSAPP / CSE 351 学习笔记（存储器层次结构 The Memory Hierarchy & Cache）

计算机中一个基本而持久的思想：如果你理解了系统是如何将数据再存储器层次结构中上上下下移动的，那么你就可以编写自己的应用程序，使得它们的数据项存储在层次结构中较高的地方，在那里 CPU 能更快地访问到它们。这个思想围绕着一个称为局部性（locality）的基本属性。

存储技术

随机访问存储器

随机访问存储器（Random-Access Memory，RAM）分为两类：静态的和动态的。

静态 RAM（SRAM）

SRAM 将每个位存储在一个双稳态（bistable）的存储器单元里。每个单元是用一个六晶体管电路来实现的。这个电路可以无限期地保持在两个不同的电压配置（configuration）或状态（state）之一，其他任何状态都是不稳定的——从不稳定状态开始，电路会迅速地转移到两个稳定状态中的一个。

倒转的钟摆（CSAPP 6-1）

当钟摆倾斜到最左边或最右边时，它是稳定的。原则上，钟摆也能在垂直的位置无限期地保持平衡，但是这个状态是亚稳态（metastable）的——最细微的扰动也能使它倒下，而且一旦倒下就永远不会再恢复到垂直的位置。

因此，SRAM 存储器单元只有通电就会永远地保持它的值。即使有干扰（例如电子干扰）来扰乱电压，当干扰消除时，电路就会恢复到稳定值。

动态 RAM（DRAM）

DRAM 将每个位存储为对一个电容的充电。因为电容很小，DRAM 存储器可以制造得非常密集——每个单元由一个电容和一个访问晶体管组成。但是，DRAM 存储器单元对干扰非常敏感，如在光线下会导致电容电压改变。

尽管有很多原因导致漏电，使得 DRAM 在 10~100 毫秒时间内失去电荷。幸运的是，计算机运行的时钟周期是以纳秒来衡量的，所以相对而言这个保持时间是比较长的。内存系统必须周期性地通过读出，然后重写来刷新内存每一位。

增强的 DRAM：

快页模式 DRAM（Fast Page Mode DRAM，FPM DRAM）
扩展数据输出 RAM（Extended Data Out DRAM，EDO DRAM）
同步 DRAM（Synchronous DRAM，SDRAM）
双倍数据速率同步 DRAM（Double Data-Rate Synchronous DRAM，DDR SDRAM）
- 使用两个时钟沿作为控制信号。根据预取缓冲区的大小来划分的：DDR（2 位）、DDR2（4 位）、DDR3（8位）。
视频 RAM（Video RAM，VRAM）

非易失性存储器

如果断电，DRAM 和 SRAM 会丢失它们的信息，从这个意义上说，它们是易失性（volatile）的。由于历史原因，虽然 ROM 中有的类型既可以读也可以写，但是它们整体上都被称为只读存储器（Read-Only Memory，ROM）。ROM 是以它们能够被重编程（写）的次数和对它们进行重编程所用的机制来区分的。

PROM（Programmable ROM，可编程 ROM）只能被编程一次。PROM 的每个存储器单元有一种熔丝（fuse），只能用高电流熔断一次。
EPROM（Erasable Programmable ROM，可擦写可编程 ROM）有一个透明的石英窗口，允许光到达存储单元。紫外线照射的时候，单元就被清除为 0。
EEPROM（Electrically Erasable PROM，电子可擦除 PROM）类似于 EPROM，但是它不需要一个物理上独立的编程设备。
闪存（flash memory）是一类非易失性存储器，基于 EEPROM，它已经成为了一种重要的存储技术。

存储在 ROM 设备中的程序通常被称为固件（firmware），提供少量基本的输入和输出函数——例如 PC 的 BIOS（基本输入输出系统）例程。

访问主存：

参考：p405

连接 CPU 和主存的总线结构示例（CSAPP 6-6）

加载操作 moveq A, %rax 的内存读事务（CSAPP 6-7）

Intel 系统使用称为北桥（northbridge）和南桥（southbridge）的芯片组分别将 CPU 连接到内存和 I/O 设备。

磁盘存储

从磁盘上读信息的时间为毫秒级，比从 DRAM 读慢了 10 万倍，比从 SRAM 读慢了 100 万倍。

磁盘构造

磁盘构造（CSAPP 6-9）

磁盘是由盘片（platter）构成的，每个盘片有两面或者称为表面（surface），表面覆盖着磁性记录材料，每个表面上的磁道编号是一致的。每个表面是由一组称为磁道（track）的同心圆组成。

每个磁道被划分为一组扇区（sector）。扇区之间间隙（gap）分隔开，这些间隙中不存储数据位。间隙存储用来标识扇区的格式化位。磁盘制造商通常用术语柱面（cylinder）来描述多个盘片驱动器的构造。

磁盘容量

磁盘容量由以下技术因素决定：

记录密度（recording density）
磁道密度（track density）
面密度（areal density）

磁盘制造商不懈地努力以提高面密度，其每隔几年就会翻倍。随着面密度的提高，扇区之间的间隙（那里没有存储数据位）变得越来越大；因此，现代大容量磁盘使用一种称为多区记录（multiple zone recording）的技术。在这种技术中，柱面的集合被分割成不相交的子集合，称为记录区（recording zone）。

磁盘容量的计算公式：

$$
磁盘容量 = \frac{字节数}{扇区} \times \frac{平均扇区数}{磁道} \times \frac{磁道数}{表面} \times \frac{表面数}{盘片} \times \frac{盘片数}{磁盘}
$$

注意：

对于与 DRAM 和 SRAM 容量相关的计量单位，通常：
- $K = 2^{10}$
- $M = 2^{20}$
- $G = 2^{30}$
- $T = 2^{40}$
对于与像磁盘和网络这样的 I/O 设备容量相关的计量单位（速率、吞吐量），通常：
- $K = 10^3$
- $M = 10^6$
- $G = 10^9$
- $T = 10^{12}$

磁盘操作

一张图：

磁盘的动态特性（CSAPP 6-10）

磁盘以扇区大小的块来读写数据。对扇区的访问时间（access time）有三个主要的部分：

寻道时间（seek time）
旋转时间（rotational latency）
传送时间（transfer time）

通常，因为寻道时间和旋转延迟大致相等，所以将寻道时间乘以 2 是估计磁盘访问时间的简单而合理的方法（传送时间比较短）。

逻辑磁盘块（Logical Disk Blocks，抽象）

现代磁盘构造复杂，有多个盘面，这些盘面上有不同的记录区。为了对操作系统隐藏这样的复杂性，现代磁盘将它们的构造呈现为一个简单的视图，一个 B 个扇区大小的逻辑块的序列。磁盘封装中有一个小的硬件/固件设备，称为磁盘控制器，维护着逻辑块号和实际（物理）磁盘扇区之间的映射关系。磁盘控制器上的固件执行一个快速表查找，将一个逻辑块号翻译成一个（盘面、磁道、扇区）的三元组，这个三元组唯一地标识了对应的物理扇区。

格式化是用标识扇区的信息填写扇区之间的间隙。此外，每个区中都有一些预留的备用柱面，所以磁盘制造商所说的格式化容量比最大的容量要小。

访问磁盘

直接内存访问（Direct Memory Access，DMA）：设备可以自己执行读或者写总线事务而不需要 CPU 干涉的过程。

固态硬盘

固态硬盘（Solid State Disk，SSD）是一种基于闪存的存储技术。一个 SSD 封装由一个或多个闪存芯片和闪存翻译层（flash translation layer）组成，闪存芯片代替传统磁盘中的机械驱动器，而闪存翻译层是一个硬件/固件设备，扮演与磁盘控制器相同的角色，将对逻辑块的请求翻译成对底层物理设备的访问。

固态硬盘（CSAPP 6-13）

缺点：因为反复写之后，闪存块容易磨损，所以 SSD 也容易磨损。闪存翻译层中的平均磨损（wearing leveling）逻辑试图通过将擦除平均分布在所有的块上来最大化每个块的寿命。

速度：SRAM > DRAM > SSD > DISK

局部性

一个编写良好的计算机程序常常具有良好的局部性（locality）。也就是，它们倾向于引用邻近于其他最近引用过的数据项，或者最近引用过的数据项本身。这种倾向性称为局部性原理（principle of locality），是一个持久的概念，对硬件和软件系统的设计和性能有极大的影响。

局部性通常有两种不同的形式：时间局部性（temporal locality）和空间局部性（spatial locality）。在一个具有良好的时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用。在一个具有良好的空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

例子：

考虑以下简单的函数sumvec，它对一个向量的元素求和。变量sum在每次循环迭代中被引用一次，因为，对于sum来说，有好的时间局部性。另一方面，因为sum是标量，对于sum来说，没有空间局部性。

int sumvec(int v[N]) {
  int i, sum = 0;
  for (i = 0; i < N; ++i)
    sum += v[i];
  return sum;
}

变量v的元素是被顺序读取的，一个接一个。因此，对于变量v，函数有很好的空间局部性，但是时间局部性很差，因为每个向量元素只被访问一次。因为对于循环体中的每个变量，这个函数要么有好的空间局部性，要么有好的时间局部性。所以，我们可以断定sumvec函数具有良好的局部性。

sumvec这样顺序访问一个向量每个元素的函数，具有步长为 1 的引用模式（stride-1 reference pattern）。有时我们也称步长为 1 的引用模式为顺序引用模式。一般而言，随着步长的增加，空间局部性下降。

例子：

int sumarrayrows(int a[M][N]) {
  int i, j, sum = 0;
  for (i = 0; i < M; ++i)
    for (j = 0; j < N; ++j) 
      sum += a[i][j];
  return sum;
} // 具有良好的空间局部性，引用模式的步长为 1

int sumarraycols(int a[M][N]) {
  int i, j, sum = 0;
  for (j = 0; i < N; ++j)
    for (i = 0; j < M; ++i) 
      sum += a[i][j];
  return sum;
} // 局部性很差，因为采用了步长为 N 的引用模式

存储器层次结构

存储器层级结构（The memory hierarchy，CSAPP 6-21）

分布式文件系统有安德鲁文件系统（Andrew File System，AFS）、网络文件系统（Network File System，NFS）。

存储器层次结构的中心思想是，对于每个 k，位于 k 层的更快更小的存储设备作为位于 k + 1 层的更大更慢的存储设备的缓存。（k 上，k + 1 下）

第 k + 1 层的存储器被划分成连续的数据对象组块（chunk），称为块（block）。数据总是以块大小为传送单位（transfer unit）在第 k 层和第 k + 1 层之间来回复制。

存储器层次结构中基本的缓存原理（CSAPP 6-22）

缓存命中（cache hit）
缓存不命中（cache miss）
- 冷缓存（cold cache），此类不命中称为强制性不命中（compulsory miss）或冷不命中（cold miss）
- 冷不命中很重要，因为它们通常是短暂的事件，不会在反复访问存储器使得缓存暖身（warmed up）之后的稳定状态中出现。

只要发生了不命中，第 k 层的缓存必须执行某个放置策略（placement policy），确定把从第 k + 1 层中取出的块放在哪里，比如随机地放置。这种随机性的放置会导致一种叫做冲突不命中（conflict miss）的不命中。

（CSE 351 - Caches, Video 5: Cache organization, part 2）

缓存管理：

编译器管理寄存器文件，它决定当发生不命中时何时发射加载，以及确定哪个寄存器来存放数据。
L1、L2、L3 层的缓存完全由内置在缓存中的硬件逻辑来管理。
DRAM 是由操作系统软件和 CPU 上的地址翻译硬件共同管理的。
对于远程文件系统，自然由该系统的程序管理。

高速缓存存储器 Cache

E = 1：直接映射高速缓存（direct-mapped cache）
E > 1：组相联高速缓存（set associative cache）
E = C/B：全相联高速缓存（fully associative cache）

Associativity（CSE 351 - Caches, Video 4: Cache organization）

Professor: Blocks and lines are the same things. They are interchangable.

组、行、块：

组（set）：一个或多个行的集合。
行（line）：高速缓存中的一个容器，存储块以及其他信息（有效位和标记位）。
块（block）：一个固定大小的信息包，在高速缓存和主存（或下一级高速缓存）之间来回传送。

注意：因为一行总是存储一个块，术语行和块通常互换使用。比如，系统专家总是说高速缓存的行大小，实际上他们指的是块大小。

通用的高速缓存存储器组织结构

考虑一个计算机系统，其中每个存储器地址有 m 位，形成 $M=2^m$ 个不同的地址。这样一个机器的高速缓存被组织成一个有 $S=2^s$ 个高速缓存组（cache set）的数组。每个组包含 E 个高速缓存行（cache line）。每个行是由一个 $B = 2^b$ 字节的数据块（block）组成的，一个有效位（valid bit）指明这个行是否包含有意义的信息（为了方便），还有 t = m-(b+s) 个标记位（tag bit）（是当前块的内存地址的位的一个子集），它们唯一地标识存储在这个高速缓存行中的块。

高速缓存（S，E，B，m）的通用组织（CSAPP 6-25）

（CSE 351 - Caches, Video 5: Cache organization, part 2）

参数 S 和 B 将 m 个地址位分为了三个字段。

地址 A 中有 s 个组索引位是一个到 S 个组的数组的索引，是一个无符号整数。
地址 A 中的 t 个标记位告诉我们这个组中的哪一行包含这个字。当且仅当设置了有效位并且该行的标记位与地址 A 中的标记位相匹配时，组中的这一行才包含这个字。(Valid bits are also used in the context of multiprocessors)
一旦我们在由组索引标识的组中定位了由标号所标识的行，那么 b 个块偏移位给出了 B 个字节的数据块中的字偏移。

Cache Read:

Locate set (set index)
Check if any line in set has matching tag (match the block)
Yes + line valid: hit
Locate data starting at offset

直接映射高速缓存（single block/line per set）

虽然书上讲得挺好的，但我发现视频里面讲得更好，应该先看视频的：链接.

每个组只有一行（E = 1）的高速缓存称为直接映射高速缓存（direct-mapped cache）

直接映射高速缓存（CSAPP 6-27）

三步匹配过程：

组选择

组选择（CSAPP 6-28）

行匹配

行匹配（CSAPP 6-29）

字抽取（字选择）

最后，如果不命中则进行行替换，需要驱逐出一个现存的行。

参考：p429 有实例。

x 与 y 块之间的抖动（thrash），即高速缓存反复地加载和驱逐相同的高速缓存块的组。

1 2	for (int i = 0; i < 8; ++i) sum += x[i] * y[i]; /* 当 x[i] 和 y[i] 映射到相同的缓存组 */

组相联高速缓存（E-way Set-Associative Cache or E blocks/lines per set）

直接映射高速缓存中冲突不命中造成的问题起源于每个组只有一行这个限制。组相联高速缓存（set associative cache）放宽了这条限制。

E 路组相联高速缓存（1 < E < C/B）（CSAPP 6-32）

组选择

同理

行匹配和字选择

组相联高速缓存中的行匹配比直接映射高速缓存中的更复杂。它必须检查多个行的标记位和有效位，以确定所请求的字是否在集合中。相联存储器是一个（key，value）对的数组。我们可以把组相联高速缓存中的每个组都看成一个小的相联存储器，key是标记和有效位，而value是块的内容。

组选择（CSAPP 6-33）

这里一个重要思想是组中的任何一行可以包含任何映射到这个组的内存块，所以高速缓存必须搜索组中的每一行，寻找一个有效的行，其标记与地址中的标记相匹配。

行匹配和字选择（CSAPP 6-34）

不命中时的行替换

替换组中的哪一行（没有空行）？替换策略：

最不常使用（Least-Frequently-Used，LFU）
最近最少使用（Least-Recently-Used，LRU）

所有这些策略都需要额外的时间和硬件。

全相联高速缓存

全相联高速缓存（fully associative cache）是由一个包含所有高速缓存行z组（即 E=C/B）组成的。

全相联高速缓存（E=C/B）（CSAPP 6-35）

组选择

注意地址中没有组索引位，地址只被划分成了一个标记和一个块偏移。

组选择（CSAPP 6-36）

行匹配和字选择

行匹配和字选择，与组相联一致（CSAPP 6-37）

有关写的问题 - What about writes?

Multiple copies of data exist:
- L1, L2, possibly L3, main memory
What is the main problem with that?
- Disagreement in between copies
What to do on a write-hit?
- Write-through (write immediately to memory)
- Write-back (defer write to memory until line is evicted)
  - Need a dirty bit to indicate if line is different from memory or not
What to do on a write-miss?
- Write-allocate (load into cache, update line in cache)
  - Load first then do the write
  - Good if more writes to the location follow because you have allocated the data
  - Good if later do read
- No-write-allocate (just write immediately to memory)
Typically
- Write-back + Write-allocate, usually
- Write-through + No-write-allocate, occasionally

写的情况要复杂一些。假设我们要写一个已经缓存了的字 w（写命中 ，write hit）。在高速缓存更新了它的 w 的副本之后，怎么更新 w 在层次结构中紧接着低一层中的副本呢？

最简单的方法，称为直写（write-through），就是立即将 w 的高速缓存块写回到紧接着的低一层中。虽然简单，但是直写的缺点是每次都会引起总线流量。

另一种方法，称为写回（write-back），尽可能地推迟更新，只有当替换算法要驱逐这个更新过的块的时候，才把它写到紧接着的低一层中。由于局部性，写回能显著地减少总线流量，但是它的缺点是增加了复杂性。高速缓存必须为每个高速缓存行维护一个额外的修改位（dirty bit），表明这个高速缓存块是否被修改过。

另一个问题是如何处理写不命中。一种方法，称为写分配（write-allocate），加载相应的低一层中的块到高速缓存中，然后更新这个高速缓存块。写分配试图利用写的空间局部性，但是缺点是每次不命中都会导致一个块从低一层传送到高速缓存。另一种方法，称为非写分配（not-write-allocate），避开高速缓存，直接把这个字写到低一层（主存）中。直写是非写分配的，写回是写分配的。

存储器层次解耦股中较低层的缓存更可能使用写回，而不是直写。

一个真实的高速缓存层次结构的剖析

高速缓存既保存数据，也保存指令。只保存指令的高速缓存称为i-cache；只保存程序数据的高速缓存称为d-cache；既保存指令又保存数据的高速缓存称为统一的高速缓存（unified cache）。现在处理器包括独立的 i-cache 和 d-cache，这样做的好处是处理器能够同时读一个指令字和一个数据字。

Intel Core i7 的高速缓存层次结构（CSE 351 - Caches, Video 5: Cache organization, part 2）

L3 unified cache: why 16-way? Because it’s very important to get hit, otherwise we’ll fetch from the memory. Very slow!

高速缓存参数的性能影响

不命中率（miss rate）
命中率（hit rate）
命中时间（hit time）
- Time to deliver a line in the cache to the processor
  - Includes time to determine whether the line is in the cache
- Typical hit times: 1 - 2 clock cycles for L1
不命中处罚（miss penalty）
- Additional time required because of a miss
- Typically 50 - 200 clock cycles

Cost of Cache Misses

Huge difference between a hit and amiss
- could be 100x, if just L1 and main memory
Would you believe 99% hits is twice as good as 97%?
- Consider:
  - Cache hit time of 1 cycle
  - Miss penalty of 100 cycles
- Average access time:
  - 97% hits: 1 cycle + 0.03 * 100 cycles = 4 cycles
  - 99% hits: 1 cycle + 0.01 * 100 cycles = 2 cycles
This is also why “miss rate” is used instead of “hit rate”

优化高速缓存的成本和性能的折中是一项很精细的工作，它需要在现实的基准程序代码上进行大量的模拟。考虑：

高速缓存大小的影响
块大小的影响
相联度的影响（抖动的可能性）
写策略的影响

编写高速缓存友好的代码

好的程序员总是应该试着去编写高速缓存友好的代码（cache friendly code）。

让最常见的情况运行得更快
尽量减小每个循环内部的缓存不命中数量

Cache Miss Analysis

Matrix Multiplication - 1st Iteration（CSE 351 - Caches, Video 6: Code optimization for caches）
Matrix Multiplication - 2nd Iteration（CSE 351 - Caches, Video 6: Code optimization for caches）

One way to improve this is to do blocked matrix multiplication.

Blocked Matrix Multiplication (CSE 351 - Caches, Video 6: Code optimization for caches)

Summary:

No blocking: (9/8) * n^3
Blocking: 1/(4B) * n^3
If B = 8 difference is 4 * 8 * 9 / 8 = 36x
If B = 16 difference is 4 * 16 * 9 / 8 = 72x

Reason for dramatic difference:

Matrix multiplication has inherent temporal locality.

Programmer can optimize for cache performance:

How data structures are organized
How data are accessed
- Nested loop structure
- Blocking is a general technique

存储器山 The Memory Mountain

一个程序从存储系统中读数据的速率称为读吞吐量（read throughput），或者有时称为读带宽（read bandwidth）。

如果我们反复以不同的size和stride值调用 run 函数（参考 p445），那么我们就能得到一个读带宽的时间和空间局部性的二维函数，称为存储器山（memory mountain）。

存储器山，展示了读吞吐量，它是时间和空间局部性的函数（CSAPP 6-41）

注意到即使是当程序的时间局部性很差时，空间局部性仍然能补救，并且是非常重要的。