第六章 存储器层次结构

csapp
loading...

存储器层次结构

到目前为止，在对系统的研究中，我们依赖于一个简单的计算机系统模型，CPU 执行指令，而存储器系统为 CPU 存放指令和数据。在简单模型中，存储器系统是一个线性的字节数组，而 CPU 能够在一个常数时间内访问每个存储器位置。虽然迄今为止这都是个有效的模型，但是它没有反映现代系统实际工作的方式。

实际上，存储器系统（memory system）是一个具有不同容量、成本和访问时间的存储设备的层次结构。CPU 寄存器保存着最常用的数据。靠近 CPU 的小的、快速的高 速缓存存储器（cache memory）作为一部分存储在相对慢速的主存储器（main memory）中数据和指令的缓冲区域。主存缓存存储在容量较大的、慢速磁盘上的数据，而这些磁盘常常又作为存储在通过网络连接的其他机器的磁盘或磁带上的数据的缓冲区域。

存储器层次结构是可行的，这是因为与下一个更低层次的存储设备相比来说，一个编写良好的程序倾向于更频繁地访问某一个层次上的存储设备。所以，下一层的存储设备可以更慢速一点，也因此可以更大，每个比特位更便宜。整体效果是一个大的存储器池，其成本与层次结构底层最便宜的存储设备相当，但是却以接近于层次结构顶部存储设备的髙速率向程序提供数据。

需要理解存储器层次结构，因为它对应用程序的性能有着巨大的影响。如果你的程序需要的数据是存储在 CPU 寄存器中的，那么在指令的执行期间，在 0个周期内就能访问到它们。如果存储在高速缓存中，需要 4 75 个周期。如果存储在主存中，需要上百个周期。而如果存储在磁盘上，需要大约几千万个周期！

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

这个思想围绕着计算机程序的一个称为局部性（locality）的基本属性。具有良好局部性的程序倾向于一次又一次地访问相同的数据项集合，或是倾向于访问邻近的数据项集合。具有良好局部性的程序比局部性差的程序更多地倾向于从存储器层次结构中较高层次处访问数据项，因此运行得更快。例如，在 Core i7 系统，不同的矩阵乘法核心程序执行相同数量的算术操作，但是有不同程度的局部性，它们的运行时间可以相差 40 倍！

在本章中，我们会看看基本的存储技术棗 SRAM 存储器、DRAM 存储器、ROM 存储器以及旋转的和固态的硬盘棗 并描述它们是如何被组织成层次结构的。特别地，我们将注意力集中在高速缓存存储器上，它是作为 CPU 和主存之间的缓存区域，因为它们对应用程序性能的影响最大。我们向你展示如何分析 C 程序的局部性，并且介绍改进你的程序中局部性的技术。你还会学到一种描绘某台机器上存储器层次结构的性能的有趣方法，称为“存储器山（memory mountain）”，它展示出读访问时间是局部性的一个函数。

6.1 存储技术

计算机技术的成功很大程度上源自于存储技术的巨大进步。早期的计算机只有几千字400 第一部分程序结构和执行节的随机访问存储器。最早的 IBM PC 甚至于没有硬盘。1982 年引人的 IBM PC-XT 有 10M字节的磁盘。到 2015 年，典型的计算机已有 3Q0 0QQ 倍于 PC-XT 的磁盘存储，而且磁盘的容量以每两年加倍的速度增长。

6.1.1 随机访问存储器

随机访问存储器（Random-Access Memory, RAM）分为两类：静态的和动态的。静态RAM(SRAM)比动态 RAM(DRAM)更快，但也贵得多。SRAM 用来作为高速缓存存储器，既可以在 CPU 芯片上，也可以在片下。DRAM 用来作为主存以及图形系统的帧缓冲区。典型地，一个桌面系统的 SRAM 不会超过几兆字节，但是 DRAM 却有几百或几千兆字节。

  1. 静态 RAM

SRAM 将每个位存储在一个双稳态的（bistable）存储器单元里。每个单元是用一个六晶体管电路来实现的。这个电路有这样一个属性，它可以无限期地保持在两个不同的电压配置（configuration）或状态（state）之一。其他任何状态都是不稳定的棗 从不稳定状态开始，电路会迅速地转移到两个稳定状态中的一个。这样一个存储器单元类似于图 6-1 中画出的倒转的钟摆。


图 6-1 倒转的钟摆。同 SRAM 单元一样，钟摆只有两个稳定的配置或状态

当钟摆倾斜到最左边或最右边时，它是稳定的。从其他任何位置，钟摆都会倒向一边或另一边。原则上，钟摆也能在垂直的位置无限期地保持平衡，但是这个状态是亚稳态的(metastable)棗 最细微的扰动也能使它倒下，而且一旦倒下就永远不会再恢复到垂直的位置。由于 SRAM 存储器单元的双稳态特性，只要有电，它就会永远地保持它的值。即使有干扰（例如电子噪音)来扰乱电压，当干扰消除时，电路就会恢复到稳定值。

  1. 动态 RAM

DRAM 将每个位存储为对一个电容的充电。这个电容非常小，通常只有大约 30 毫微微法拉(femtofarad)——30X1015 法拉。不过，回想一下法拉是一个非常大的计量单位。DRAM 存储器可以制造得非常密集棗 每个单元由一个电容和一个访问晶体管组成。但是，与 SRAM 不同，DRAM 存储器单元对干扰非常敏感。当电容的电压被扰乱之后，它就永远不会恢复了。暴露在光线下会导致电容电压改变。实际上，数码照相机和摄像机中的传感器本质上就是 DRAM 单元的阵列。很多原因会导致漏电，使得 DRAM 单元在 10 100 毫秒时间内失去电荷。幸运的是,计算机运行的时钟周期是以纳秒来衡量的，所以相对而言这个保持时间是比较长的。内存系统必须周期性地通过读出，然后重写来刷新内存每一位。有些系统也使用纠错码，其中计算机的字会被多编码几个位（例如 64 位的字可能用 72 位来编码）， 这样一来，电路可以发现并纠正一个字中任何单个的错误位。

图 6-2 总结了 SRAM 和 DRAM 存储器的特性。只要有供电，SRAM 就会保持不变。与 DRAM 不同，它不需要刷新。SRAM 的存取比 DRAM 快。SRAM 对诸如光和电噪声这样的干扰不敏感。代价是 SRAM 单元比 DRAM 单元使用更多的晶体管，因而密集度低，而且更贵，功耗更大。


图 6-2 DRAM 和 SRAM 存储器的特性

  1. 传统的 DRAM

DRAM 芯片中的单元(位)被分成 d 个超单元（supercell）, 每个超单元都由 w 个 DRAM单元组成。一个 的 DRAM 总共存储了 位信息。超单元被组织成一个 r 行 c 列的长方形阵列，这里 每个超单元有形如(i, j)的地址，这里 i 表示行，而 j 表示列。

图 6-3 给出了两组引脚：8 个 data引脚，它们能传送一个字节到芯片或从芯片传出一个字节，以及 2 个 addr引脚，它们携带 2 位的行和列超单元地址。其他携带控制信息的引脚没有显示出来。


图 6-3 —个 128 位 16X8 的 DRAM 芯片的髙级视图

存储领域从来没有为 DRAM 的阵列元素确定一个标准的名字。计算机构架师倾向于称之为“单元”，使这个术语具有 DRAM 存储单元之意。电路设计者倾向于称之为“字”，使之具有主存一个字之意。为 了避免混淆，我们采用了无歧义的术语“超单元”

每个 DRAM 芯片被连接到某个称为内存控制器（memory controller）的电路，这个电路可以一次传送切位到每个 DRAM 芯片或一次从每个 DRAM 芯片传出 w 位。为了读出超单元(i,j)的内容，内存控制器将行地址；发送到 DRAM,然后是列地址 DRAM 把超单元(i,j)的内容发回给控制器作为响应。行地址 i 称为 RAS(Row Access Strobe, 行访问选通脉冲）请求。列地址 j 称为 CAS（column Access Strobe, 列访问选通脉冲）请求。注意，RAS 和 CAS 请求共享相同的 DRAM 地址引脚。


图 6-4 读一个 DRAM 超单元的内容

电路设计者将 DRAM 组织成二维阵列而不是线性数组的一个原因是降低芯片上地址引脚的数量。例如，如果示例的 128 位 DRAM 被组织成一个 16 个超单元的线性数组，地址为 0 15, 那么芯片会需要 4 个地址引脚而不是 2 个。二维阵列姐织的缺点是必须分两步发送地址，这增加了访间时间。

  1. 内存模块

DRAM 芯片封装在内存模块（memory module)中，它插到主板的扩展槽上。Core系统使用的 240 个引脚的双列直插内存模块（Dual Inline Memory Module DIMM）, 它以;64 位为块传送数据到内存控制器和从内存控制器传出数据。


图 6-5 读一个内存模块的内容

  1. 增强的 DRAM

有许多种 DRAM 存储器，而生产厂商试图跟上迅速增长的处理器速度，市场上就会定期推出新的种类。每种都是基于传统的 DRAM 单元，并进行一些优化，提高访问基本DRAM 单元的速度。

  • 快页模式 DRAM(Fast Page Mode DRAM, FPM DRAM)
  • 扩展数据输出 DRAM(Extended Data Out DRAM, EDO DRAM)
  • 同步 DRAM(Synchronous USDRAM,SDRAM)
  • 双倍数据速 率同步 DRAM(Double Data-Rate Synchronous DRAM, DDR SDRAM)
  • 视频 RAM(Video RAM,VRAM)
  1. 非易失性存储器

如果断电，DRAM 和 SRAM 会丢失它们的信息，从这个意义上说，它们是 易失的(volatile) 另一方面，非 易失性存储器（nonvolatile memory)即使是在关电后，仍然保存着它们的信息。现在有很多种非易失性存储器。由于历史原因，虽然 ROM 中有的类型既可以读也可以写，但是它们整体上都被称为只读 存储器（Read-Only Memory, ROM）ROM 是以它们能够被重编程（写）的次数和对它们进行重编程所用的机制来区分的。

PROM(ProgrammableROM 可编程 ROM)只能被编程一次。PROM 的每个存储器单元有一种熔丝（fuse）, 只能用高电流熔断一次。

可擦写可编程 ROM(Erasable Programmable ROM, EPROM)有一个透明的石英窗口，允许光 到达存储单元。紫外线光照射过窗口，EPROM 单元就被 清除为 0。对EPROM 编程是通过使用一种把 1 写人 EPROM 的特殊设备来完成的。EPROM 能够被擦除和重编程的次数的数量级可以达到 1000 次。电子 可擦除 PROM(ElectriCally ErasablePROM, EEPR0M)类似于 EPROM, 但是它不需要一个物理上独立的编程设备，因此可以直接在印制电路卡上编程。EEPROM 能够被编程的次数的数量级可以达到 105次。

闪存（flash memory）是一类非易失性存储器，基于 EEPROM，它已经成为了一种重要的存储技术。闪存无处不在，为大量的电子设备提供快速而持久的非易失性存储，包括数码相机、手机、音乐播放器、PDA 和笔记本、台式机和服务器计算机系统。

存储在 ROM 设备中的程序通常被称为固件(firmware)当一个计算机系统通电以后，它会运行存储在 ROM 中的固件。一些系统在固件中提供了少量基本的输入和输出函数——例如 PC 的 BIOS（基本输人/输出系统）例程。复杂的设备，像图形卡和磁盘驱动控制器，也依赖固件翻译来自 CPU 的 1/0(输人/输出）请求。

  1. 访问主存

数据流通过称为总线（bus)的共享电子电路在处理器和 DRAM 主存之间来来回回。每次 CPU 和主存之间的数据传送都是通过一系列步骤来完成的，这些步骤称为总线事务(bus transaction)。读事务（read transaction）从主存传送数据到 CPU。写事务（write transaction）从 CPU 传送数据到主存。

总线是一组并行的导线，能携带地址、数据和控制信号。取决于总线的设计，数据和地址信号可以共享同一组导线，也可以使用不同的。同时，两个以上的设备也能共享同一总线。控制线携带的信号会同步事务，并标识出当前正在被执行的事务的类型。例如，当前关注的这个事务是到主存的吗？还是到诸如磁盘控制器这样的其他 I/O 设备？这个事务是读还是写？总线上的信息是地址还是数据项？

图 6-6 展示了一个示例计算机系统的配置。主要部件是 CPU 芯片、我们将称为 I/O桥接器(I/O bridge)的芯片组（其中包括内存控制器）， 以及组成主存的 DRAM 内存模块。这些部件由一对总线连接起来，其中一条总线是系统总线（system bus）, 它连接 CPU 和I/O 桥接器，另一条总线是内存总线（memory bus），它连接 I/O 桥接器和主存。I/O 桥接器将系统总线的电子信号翻译成内存总线的电子信号。正如我们看到的那样，I/O 桥也将系统总线和内存总线连接到 I/O 总线，像磁盘和图形卡这样的 1/◦设备共享 I/O 总线。不过现在，我们将注意力集中在内存总线上。


图 6-6 连接 CPU 和主存的总线结构示例

考虑当 CPU 执行一个如下加载操作时会发生什么
movq A,%rax
这里，地址 A 的内容被加载到寄存器 %rax 中。CPU 芯片上称为总线接口（bus interface）的电路在总线上发起读事务。读事务是由三个步骤组成的。首先，CPU 将地址 A 放到系统总线上。I/O 桥将信号传递到内存总线（图 6-7a）。 接下来，主存感觉到内存总线上的地址信号，从内存总线读地址，从 DRAM 取出数据字，并将数据写到内存总线。I/O 桥将内存总线信号翻成系统总线信号，然后沿着系统总线传递（图 6-7b）。 最后，CPU 感觉到系统总线上的数据，从总线上读数据，并将数据复制到寄存器 %rax(图 6-7c)。


图 6-7 加载操作 movqA,%rax 的内存读事务

反过来，当 CPU 执行一个像下面这样的存储操作时
movq %rax,A
这里，寄存器 %rax 的内容被写到地址 A, CPU 发起写事务。同样，有三个基本步骤。首先,CPU 将地址放到系统总线上。内存从内存总线读出地址，并等待数据到达（图 6-8a）。接下来，CPU 将 %rax 中的数据字复制到系统总线（图 6-8b）。最后，主存从内存总线读出数据字，并且将这些位存储到 DRAM 中（图 6-8c）。


图 6-8 存储操作 movq %rax,A 的内存写事务

6.1.2 磁盘存储

磁盘是广为应用的保存大量数据的存储设备，存储数据的数量级可以达到几百到几千千兆字节，而基于 RAM 的存储器只能有几百或几千兆字节。不过，从磁盘上读信息的时间为毫秒级，比从 DRAM 读慢了 10 万倍，比从 SRAM 读慢了 100 万倍。

  1. 磁盘构造

磁盘是由盘片(platter)构成的。每个盘片有两面或者称为表面(surface)，表面覆盖着磁性记录材料。盘片中央有一个可以旋转的主轴(spindle)，它使得盘片以固定的旋转速率(rotational rate)旋转，通常是 5400 15 000 转每分钟(Revolution Per Minute，RPM)磁盘通常包含一个或多个这样的盘片，并封装在一个密封的容器内。

图 6-9a 展示了一个典型的磁盘表面的结构。每个表面是由一组称为磁道（track）的同心圆组成的。每个磁道被划分为一组扇区（sector）。每个扇区包含相等数量的数据位（通常是 512 字节）， 这些数据编码在扇区上的磁性材料中。扇区之间由一些间隙（gap）分隔开，这些间隙中不存储数据位。间隙存储用来标识扇区的格式化位。

磁盘是由一个或多个叠放在一起的盘片组成的，它们被封装在一个密封的包装里，如图 6-9b 所示。整个装置通常被称为磁盘驱动器（disk drive）， 我们通常简称为磁盘（disk）。有时，我们会称磁盘为旋转磁盘（rotating disk）， 以使之区别于基于闪存的固态硬盘(SSD)，SSD 是没有移动部分的。

磁盘制造商通常用术语柱面（cylinder）来描述多个盘片驱动器的构造，这里，柱面是所有盘片表面上到主轴中心的距离相等的磁道的集合 例如，如果一个驱动器有三个盘片六个面，每个表面上的磁道的编号都是一致的，那么柱面 A 就是 6 个磁道k的集合。


图 6-9 磁盘构造

  1. 磁盘容量

一个磁盘上可以记录的最大位数称为它的最大容量，或者简称为容量。磁盘容量是由以下技术因素决定的：

  • 记录密度(recording density)（位/英寸）： 磁道一英寸的段中可以放入的位数。
  • 磁道密度(track density)（道/英寸）：从盘片中心出发半径上一英寸的段内可以有的磁道数。
  • 面密度(areal density)（位/平方英寸）：记录密度与磁道密度的乘积。

磁盘制造商不懈地努力以提高面密度（从而增加容量）， 而面密度每隔几年就会翻倍。最初的磁盘，是在面密度很低的时代设计的，将每个磁道分为数目相同的扇区，扇区的数目是由最靠内的磁道能记录的扇区数决定的。为了保持每个磁道有固定的扇区数，越往外的磁道扇区隔得越开。在面密度相对比较低的时候，这种方法还算合理。不过，随着面密度的提高，扇区之间的间隙（那里没有存储数据位）变得不可接受地大。因此，现代大容量磁盘使用一种称为多 区记录(multiple zone recording)的技术，在这种技术中，柱面的集合被分割成不相交的子集合，称为记录区(recording zone)。 每个区包含一组连续的柱面。一个区中的每个柱面中的每条磁道都有相同数量的扇区，这个扇区的数量是由该区中最里面的磁道所能包含的扇区数确定的。

  1. 磁盘操作

磁盘用读/写头(read/write head)来读写存储在磁性表面的位，而读写头连接到一个传动臂(actuator arm)—端，如图 6-10a 所示。


图 6-10 磁盘的动态特性

磁盘以扇区大小的块来读写数据。对扇区的访问时间(access time)有 三个主要的部分：寻道时间(seek time) 旋转时间(rotational latency)和传送时间(transfer time)

  1. 逻辑磁盘块

正如我们看到的那样，现代磁盘构造复杂，有多个盘面，这些盘面上有不同的记录区。为了对操作系统隐藏这样的复杂性，现代磁盘将它们的构造呈现为一个简单的视图，—个 B 个扇区大小的逻辑块的序列，编号为 0, 1,…,B— 1。磁盘封装中有一个小的硬件/固件设备，称为磁盘控制器，维护着逻辑块号和实际（物理）磁盘扇区之间的映射关系。

当操作系统想要执行一个 I/O 操作时，例如读一个磁盘扇区的数据到主存，操作系统会发送—个命令到磁盘控制器，让它读某个逻辑块号。控制器上的固件执行一个快速表査找，将一个逻辑块号翻译成一个（盘面，磁道，扇区）的三元组，这个三元组唯一地标识了对应的物理扇区。控制器上的硬件会解释这个三元组，将读/写头移动到适当的柱面，等待扇区移动到读/写头下，将读/写头感知到的位放到控制器上的一个小缓冲区中，然后将它们复制到主存中。

  1. 连接 I/O 设备

例如图形卡、监视器、鼠标、键盘和磁盘这样的输人/输出(I/O)设备，都是通过 I/O总线，例如 Intel 的外围设备互连(Peripheral Component Interconnect, PCI)总线连接到CPU 和主存的。系统总线和内存总线是与 CPU 相关的，与它们不同，诸如 PCI 这样的 I/O 总线设计成与底层 CPU 无关。例如，PC 和 Mac 都可以使用 PCI 总线。图 6-11 展示了一个典型的 I/O 总线结构，它连接了 CPU、主存和 I/O 设备。

虽然 I/O 总线比系统总线和内存总线慢，但是它可以容纳种类繁多的第三方 I/O 设备。例如，在图 6-11 中，有三种不同类型的设备连接到总线。


图 6-11 总线结构示例，它连接 CPU、主存和 I/O 设备

  1. 访问磁盘

虽然详细描述 I/O 设备是如何工作的以及如何对它们进行编程超出了我们讨论的范围，但是我们可以给你一个概要的描述。例如，图 6-12 总结了当 CPU 从磁盘读数据时发生的步骤。


图 6-12 读一个磁盘扇区

CPU 使用一种称为内存映射 I/O(memory-mapped I/O)的技术来向 I/O 设备发射命令(图 6-12a)。在使用内存映射 I/O 的系统中，地址空间中有一块地址是为与 I/O 设备通信保留的。每个这样的地址称为一个 I/O 端口(I/O port) 当一个设备连接到总线时，它与一个或多个端口相关联（或它被映射到一个或多个端口）。

6.1.3 固态硬盘

固态硬盘(Solid State Disk, SSD)是一种基于闪存的存储技术（参见 6.1.1 节），在某些情况下是传统旋转磁盘的极有吸引力的替代产品。图 6-13 展示了它的基本思想。


图 6-13 固态硬盘(SSD)

图 6-14 展示了典型 SSD 的性能特性。注意，读 SSD 比写要快。随机读和写的性能差别是由底层闪存基本属性决定的。如图 6-13 所示，一个闪存由 B 个块的序列组成，每个块由 P 页组成。通常，页的大小是 512 字节4KB, 块是由 32128 页组成的，块的大小为 16KB~512KB。数据是以页为单位读写的。只有在一页所属的块整个被擦除之后，才能写这一页(通常是指该块中的所有位都被设置为 1)。不过，一旦一个块被擦除了，块中每一个页都可以不需要再进行擦除就写一次。在大约进行 100 000 次重复写之后，块就会磨损坏。一旦一个块磨损坏之后，就不能再使用了。


图 6-14 一个商业固态硬盘的性能特性

随机写很慢，有两个原因。首先，擦除块需要相对较长的时间，lms 级的，比访问页所需时间要高一个数量级。其次，如果写操作试图修改一个包含已经有数据(也就是不是全为 1)的页p，那么这个块中所有带有用数据的页都必须被复制到一个新（擦除过的）块，然后才能进行对页p的写。制造商已经在闪存翻译层中实现了复杂的逻辑，试图抵消擦写块的高昂代价，最小化内部写的次数，但是随机写的性能不太可能和读一样好。

6.1.4 存储技术趋势

从我们对存储技术的讨论中，可以总结出几个很重要的思想：

不同的存储技术有不同的价格和性能折中。SRAM 比 DRAM 快一点，而 DRAM 比磁盘要快很多。另一方面，快速存储总是比慢速存储要贵的。SRAM 每字节的造价比DRAM 高，DRAM 的造价又比磁盘高得多。SSD 位于 DRAM 和旋转磁盘之间。

不同存储技术的价格和性能属性以截然不同的速率变化着。这些惊人的长期趋势突出了内存和磁盘技术的一个基本事实：增加密度（从而降低成本）比降低访问时间容易得多。

DRAM 和磁盘的性能 滞后于 CPU 的性能。

正如我们将在 6.4 节中看到的那样，现代计算机频繁地使用基于 SRAM 的高速缓存，试图弥补处理器-内存之间的差距。这种方法行之有效是因为应用程序的一个称为局部性(locality)的基本属性，接下来我们就讨论这个问题。

6.2 局部性

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

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

6.2.1 对程序数据引用的局部性

考虑图 6-17a 中的简单函数，它对一个向量的元素求和。这个程序有良好的局部性吗？要回答这个问题，我们来看看每个变量的引用模式。在这个例子中，变量 sum 在每次循环迭代中被引用一次，因此，对于 sum 来说，有好的时间局部性。另一方面，因为是标量，对于 sum 来说，没有空间局部性。

正如我们在图 6-17b 中看到的，向量 v 的元素是被顺序读取的，一个接一个，按照它们存储在内存中的顺序（为了方便，我们假设数组是从地址 0 开始的）。 因此，对于变量 v,函数有很好的空间局部性，但是时间局部性很差，因为每个向量元素只被访问一次。因为对于循环体中的每个变量，这个函数要么有好的空间局部性，要么有好的时间局部性，所以我们可以断定 sumvec 函数有良好的局部性。


图 6-17 注意如何按照向量元素存储在内存中的顺序来访问它们

我们说像 sumvec 这样的顺序访问一个向量每个元素的函数，具有步长为 1 的引用模式(stride-1 reference pattern)（相对于元素的大小）（相对于元素的大小）。 有时我们称步长为 1 的引用模式为顺序引用模式(sequential reference pattern)。 一个连续向量中，每隔k个元素进行访问，就称为步长为 k 的引用模式(stride-k reference pattern)。步长为 1 的引用模式是程序中空间局部性常见和重要的来源。一般而言，随着步长的增加，空间局部性下降。


图 6-18 有良好的空间局部性，是因为数组是按照与它存储在内存中一样的行优先顺序来被访问的


图 6-19 函数的空间局部性很差，这是因为它使用步长为 N 的引用模式来扫描

6.2.2 取指令的局部性

因为程序指令是存放在内存中的，CPU 必须取出（读出）这些指令，所以我们也能够评价一个程序关于取指令的局部性。例如，图 6-17 中 for 循环体里的指令是按照连续的内存顺序执行的，因此循环有良好的空间局部性。因为循环体会被执行多次，所以它也有很好的时间局部性

代码区别于程序数据的一个重要属性是在运行时它是不能被修改的。当程序正在执行时，CPU 只从内存中读出它的指令。CPU 很少会重写或修改这些指令。

6.2.3 局部性小结

在这一节中，我们介绍了局部性的基本思想，还给出了量化评价程序中局部性的一些

简单原则：

  • 重复引用相同变量的程序有良好的时间局部性。
  • 对于具有步长为々的引用模式的程序，步长越小，空间局部性越好。具有步长为 Z的引用模式的程序有很好的空间局部性。在内存中以大步长跳来跳去的程序空间局部性会很差。
  • 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

在本章后面，在我们学习了高速缓存存储器以及它们是如何工作的之后，我们会介绍如何用髙速缓存命中率和不命中率来量化局部性的概念。你还会弄明白为什么有良好局部性的程序通常比局部性差的程序运行得更快。尽管如此，了解如何看一眼源代码就能获得对程序中局部性的高层次的认识，是程序员要掌握的一项有用而且重要的技能。

6.3 存储器层次结构

6.1 节和 6.2 节描述了存储技术和计算机软件的一些基本的和持久的属性：

  • 存储技术：不同存储技术的访问时间差异很大。速度较快的技术每字节的成本要比速度较慢的技术高，而且容量较小。CPU 和主存之间的速度差距在增大。
  • 计算机软件：一个编写良好的程序倾向于展示出良好的局部性。

计算中一个喜人的巧合是，硬件和软件的这些基本属性互相补充得很完美。它们这种相互补充的 性质使人想到一种组织存储 器系统的方法，称 为存 储器层 次结构(memory hierarchy), 所有的现代计算机系统中都使用了这种方法。图 6-21 展示了一个典型的存储器层次结构。一般而言，从高层往底层走，存储设备变得更慢、更便宜和更大。在最高层(L0),是少量快速的 CPU 寄存器，CPU 可以在一个时钟周期内访问它们。接下来是一个或多个小型到中型的基于 SRAM 的高速缓存存储器，可以在几个 CPU 时钟周期内访问它们。然后是一个大的基于 DRAM 的主存，可以在几十到几百个时钟周期内访问它们,接下来是慢速但是容量很大的本地磁盘。最后，有些系统甚至包括了一层附加的远程服务器上的磁盘，要 通过网络来访问它们。例如，像安德鲁文件系统(Andrew File System, AFS)或者网络文件系统(Network File System, NFS)这样的分布式文件系统，允许程序访问存储在远程的网络服务器上的文件。类似地，万维网允许程序访问存储在世界上任何地方的 Web 服务器上的远程文件。


图 6-21 存储器层次结构

6.3.1 存储器层次结构中的缓存

一般而言，高速缓存(cache, 读作”cash”) 是一个小而快速的存储设备，它作为存储在更大、也更慢的设备中的数据对象的缓冲区域。使用高速缓存斑过程称为缓存(caching,读作 “cashing”)。

存储器层次结构的中心思想是，对于每个 k，位于 k 层的更快更小的存储设备作为位于 k+1 层的更大更慢的存储设备的缓存。换句话说，层次结构中的每一层都缓存来自较低一层的数据对象。例如，本地磁盘作为通过网络从远程磁盘取出的文件（例如 Web 页面）的缓存，主存作为本地磁盘上数据的缓存，依此类推，直到最小的缓存——CPU 寄存器组。

图 6-22 展示了存储器层次结构中缓存的一般性概念。第 k+1 层的存储器被划分成连续的数据对象组块(chunk), 称为块(block)。每个块都有一个唯一的地址或名字，使之区别于其他的块。块可以是固定大小的（通常是这样的）， 也可以是可变大小的（例如存储在Web 服务器上的远程 HTML 文件）。 例如，图 6-22 中第 k+1 层存储器被划分成 16 个大小固定的块，编号为 0~15。

类似地，第 k 层的存储器被划分成较少的块的集合，每个块的大小与 k+1 层的块的大小一样。在任何时刻，第 k 层的缓存包含第 k+1 层块的一个子集的副本。例如，在图 6-22中，第 k 层的缓存有 4 个块的空间，当前包含块 4、9、14 和 3 的副本。


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

数据总是以块大小为传送单元(transfer unit)在第 k 层和第 k+1 层之间来回复制的。虽然在层次结构中任何一对相邻的层次之间块大小是固定的，但是其他的层次对之间可以有不同的块大小。例如，在图 6-21 中，L1 和 L0 之间的传送通常使用的是 1 个字大小的块。L2 和 L1 之间（以及 L3 和 L2 之间、L4 和 L3 之间）的传送通常使用的是几十个字节的块。而 L5 和 L4 之间的传送用的是大小为几百或几千字节的块。一般而言，层次结构中较低层（离 CPU 较远）的设备的访问时间较长，因此为了补偿这些较长的访问时间，倾向于使用较大的块。

  1. 缓存命中

当程序需要第 k+1 层的某个数据对象 d 时，它首先在当前存储在第 k 层的一个块中査找。如果 d 刚好缓存在第 k 层中，那么就是我们所说的缓存命中(cache hit)。 该程序直接从第 k 层读取 d，根据存储器层次结构的性质，这要比从第 k+1 层读取 d 更快。例如，一个有良好时间局部性的程序可以从块 14 中读出一个数据对象，得到一个对第 k 层的缓存命中。

  1. 缓存不命中

另一方面，如果第 k 层中没有缓存数据对象d，那么就是我们所说的缓存不命中(cache miss), 当发生缓存不命中时，第 k 层的缓存从第 k+1 层缓存中取出包含 d 的那个块，如果第 k 层的缓存已经满了，可能就会覆盖现存的一个块。

覆羞一个现存的块的过程称为替换(replacing)或驱逐(evicting)这个块。被驱逐的这个块有时也称为牺牲块(victim block)。 决定该替换哪个块是由缓存的替换策略(replace-ment policy)来控制的。例如，一个具有随机替换策略的缓存会随机选择一个牺牲块。一个具，有最近最少被使用(LRU)替换策略的缓存会选择那个最后被访问的时间距现在最远的块。

在第 k 层缓存从第 k+1 层取出那个块之后，程序就能像前面一样从第 A 层读出 d 了。例如，在图 6-22 中，在第 k 层中读块 12 中的一个数据对象，会导致一个缓存不命中，因为块 12 当前不在第 k 层缓存中。一旦把块 12 从第 k+1 层复制到第 k 层之后，它就会保持在那里，等待稍后的访问。

  1. 缓存不命中的种类

区分不同种类的缓存不命中有时候是很有帮助的。如果第 k 层的缓存是空的，那么对任何数据对象的访问都会不命中。一个空的缓存有时被称为冷缓存(cold cache), 此类本命中称为强制性不命中(compulsory miss)或冷不命中(cold miss), 冷不命中很重要，因为它们通常是短暂的事件，不会在反复访问存储器使得缓存暖身(wanned up)之后的稳定状态中出现。

只要发生了不命中，第 k 层的缓存就必须执行某个放置策略(placement policy), 确定把它从第 k+1 层中取出的块放在哪里。最灵活的替换策略是允许来自第 k+1 层的任何块放在第 k 层的任何块中。对于存储器层次结构中高层的缓存(靠近 CPU)。它们是用硬件来实现的，而且速度是最优的，这个策略实现起来通常很昂贵，因为随机地放置块，定位起来代价很高。

因此，硬件缓存通常使用的是更严格的放置策略，这个策略将第 k+1 层的某个块限制放置在第 k 层块的一个小的子集中（有时只是一个块）。

这种限制性的放置策略会引起一种不命中，称为冲突不命中(conflict miss), 在这种情况中，缓存足够大，能够保存被引用的数据对象，但是因为这些对象会映射到同一个缓存块，缓存会一直不命中。

程序通常是按照一系列阶段（如循环）来运行的，每个阶段访问缓存块的某个相对稳定不变的集合。例如，一个嵌套的循环可能会反复地访问同一个数组的元素。这个块的集合称为这个阶段的工作集(working set),当工作集的大小超过缓存的大小时，缓存会经历容量不命中(capacity miss)。换句话说就是，缓存太小了，不能处理这个工作集。

  1. 缓存管理

正如我们提到过的，存储器层次结构的本质是，每一层存储设备都是较低一层的缓存。在每一层上，某种形式的逻辑必须管理缓存。这里，我们的意思是指某个东西要将缓存划分成块，在不同的层之间传送块，判定是命中还是不命中，并处理它们。管理缓存的逻辑可以是硬件、软件，或是两者的结合。

6.3.2 存储器层次结构概念小结

概括来说，基于缓存的存储器层次结构行之有效，是因为较慢的存储设备比较快的存储设备更便宜，还因为程序倾向于展示局部性：

  • 利用时间局部性
  • 利用空间局部性

6.4 高速缓存存储器

早期计算机系统的存储器层次结构只有三层：CPU 寄存器、DRAM 主存储器和磁盘存储。不过，由于 CPU 和主存之间逐渐增大的差距，系统设计者被迫在 CPU 寄存器文件和主存之间插入了一个小的 SRAM 高 速缓存存储器，称为 L1 高 速缓存（一级缓存），如图 6-24 所示。L1 高速缓存的访问速度几乎和寄存器一样快，典型地是大约 4 个时钟周期。


图 6-24 高速缓存存储器的典型总线结构

随着 CPU 和主存之间的性能差距不断增大，系统设计者在 L1 高速缓存和主存之间又插入了一个更大的高速缓存，称为 L2 高速缓存，可以在大约 10 个时钟周期内访问到它。有些现代系统还包括有一个更大的高速缓存，称为 L3 高速缓存，在存储器层次结构中，它位于 L2 高速缓存和主存之间，可以在大约 50 个周期内访问到它。

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

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


图 6-25 高速缓存(S, E, B , m)的通用组织。a)高速缓存是一个高速缓存组的数组。每个组包含一个或多个行，每个行包含一个有效位，一些标记位，以及一个数据块；b)高速缓存的结构将 m 个地址位划分成了 t个标记位、s 个组索引位和 6 个块偏移位

一般而言，高速缓存的结构可以用元组 (S, E, B , m) 来描述。高速缓存的大小（或容量）C 指的是所有块的大小的和。标记位和有效位不包括在内。因此，C=S x E x B。

当一条加载指令指示 CPU 从主存地址 A 中读一个字时，它将地址 A 发送到高速缓存。如果高速缓存正保存着地址 A 处那个字的副本，它就立即将那个字发回给 CPU。那么高速缓存如何知道它是否包含地址 A 处那个字的副本的呢？高速缓存的结构使得它能通过简单地检查地址位，找到所请求的字，类似于使用极其简单的哈希函数的哈希表。下面介绍它是如何工作的：

参数 S 和 B 将 m 个地址位分为了三个字段，如图 6-25b 所示。A 中 s 个组索引位是一个到 S 个组的数组的索引。第一个组是组 0, 第二个组是组 1, 依此类推。组索引位被解释为一个无符号整数，它告诉我们这个字必须存储在哪个组中。一旦我们知道了这个字必须放在哪个组中，A 中的 t 个标记位就告诉我们这个组中的哪一行包含这个字（如果有的话）。 当且仅当设置了有效位并且该行的标记位与地址 A 中的标记位相匹配时，组中的这一行才包含这个字。一旦我们在由组索引标识的组中定位了由标号所标识的行，那么 6 个块偏移位给出了在 B 个字节的数据块中的字偏移。

6.4.2 直接映射高速缓存

据每个组的高速缓存行数 E：， 高速缓存被分为不同的类。每个组只有一行(E=1)的高速缓存称为直接映射高速缓存（direct-mapped cache)(见图 6-27)。直接映射高速缓存是最容易实现和理解的，所以我们会以它为例来说明一些高速缓存工作方式的通用概念。


图 6-27 直接映射高速缓存(E=l)。每个组只有一行

假设我们有一个地址A，这个地址可以分为三个主要字段：标记位（tag bits）、组索引位（set index bits）和块偏移位（block offset bits）。我们用参数S、B和t来表示这些字段：

  • S 表示缓存中的组（set）的数量。
  • B 表示每个块（block）中的字节（byte）数。
  • t 表示标记位的数量。

每个字段的作用如下：

  1. 组索引位（Set Index Bits）：
  • 这些位用来选择缓存中的某一组。一个组可以包含多行（也称为缓存块或缓存行）。
  • 组索引位的数量（s）可以计算为 log2(𝑆)，其中S是组的数量。
    例如，如果有16个组（S=16），那么需要 log2(16)=4 位作为组索引位。
  1. 标记位（Tag Bits）：
  • 这些位用于在一个组内唯一标识一个缓存行。
  • 标记位与组索引位一起用于确定特定的缓存行是否存储了所需的数据。
  • 标记位的数量由地址的总位数减去组索引位和块偏移位的数量。
  1. 块偏移位（Block Offset Bits）：

这些位用于确定在缓存块中的具体字节位置。
块偏移位的数量（b）可以计算为 log2(B)，其中B是每个块中的字节数。
例如，如果每个块有64个字节（B=64），那么需要 log2(64)=6 位作为块偏移位。

缓存操作流程

  1. 计算组索引：
  • 从地址A中提取组索引位。组索引位的值告诉我们数据应该存储在哪个组中。
  1. 定位组中的行：
  • 在确定了组之后，使用标记位来定位该组中的具体行。每一行有一个标记字段，存储了地址的标记部分。
  • 通过比较地址A中的标记位与缓存行中的标记位，可以确定是否存在匹配。
  1. 数据访问：
  • 如果找到了匹配的行，并且有效位（valid bit）为真（表示行中数据有效），则使用块偏移位从缓存行中提取所需的字节。
  • 如果没有找到匹配的行，则发生缓存未命中（cache miss），需要从更高层级的存储（如主存）中读取数据，并将其存储到缓存中。

具体示例

假设我们有以下参数：

总地址位数为32位。
缓存有16个组（S=16），因此组索引位数为 log2(16)=4。
每个块包含64个字节（B=64），因此块偏移位数为 log2(64)=6。
那么，标记位数为 32−4−6=22。

假设地址A为二进制形式的10101010101010101010101010101010。根据上述分配：

  • 标记位（前22位）：1010101010101010101010
  • 组索引位（中间4位）：1010
  • 块偏移位（后6位）：101010

组索引位 1010 对应组索引为10的组。

在组10中，缓存会检查是否存在标记位为 1010101010101010101010 的行，并且该行的有效位是否为真。如果是，缓存命中并使用块偏移位 101010 提取所需字节；否则，缓存未命中，从主存中加载数据。

通过这种方式，缓存能够高效地管理和访问数据，大幅提升计算机系统的性能。

6.4.3 组相联高速缓存

直接映射高速缓存中冲突不命中造成的问题源于每个组只有一行（或者，按照我们的术语来描述就是 E=l）这个限制。组相联高速缓存(set associative cache)放松了这条限制，所以每个组都保存有多于一个的高速缓存行。


图 6-32 组相联髙速缓存(1<E<C/B)。在一个组相联髙速缓存中，每个组包含多于一个行。这里的特例是一个 2 路组相联高速缓存

6.4.4 全相联高速缓存

全相联高速缓存（fully associative cache)是由一个包含所有高速缓存行的组（即 C/B）组成的。图 6-35 给出了基本结构。


图 6-35 全相联高速缓存(E=C/B)。在全相联高速缓存中，一个组包含所有的行

6.4.5 有关写的问题

写的情况就要复杂一些了。假设我们要写一个已经缓存了的字 w 写命中，(write hit)。在高速缓存更新了它的 w 的副本之后，怎么更新 w 在层次结构中紧接着低一层中的副本呢？最简单的方法，称为直写(write-through)，就是立即将 w 的高速缓存块写回到紧接着的低一层中。虽然简单，但是直写的缺点是每次写都会引起总线流量。另一种方法，称为写回(write-back), 尽可能地推迟更新，只有当替换算法要驱逐这个更新过的块时，才把它写到紧接着的低一层中。由于局部性，写回能显著地减少总线流量，但是它的缺点是增加了复杂性。高速缓存必须为每个高速缓存行维护一个额外的修改位(dirty bit) 。表明这个高速缓存块是否被修改过。

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

6.4.6 个真实的高速缓存层次结构的解剖

到目前为止，我们一直假设高速缓存只保存程序数据。不过，实际上，高速缓存既保存数据，也保存指令。只保存指令的高速缓存称为 i-cache。只保存程序数据的高速缓存称为 d-cache 既保存指令又包括数据的高速缓存称为统一的高速缓存(unified cache)。现代处理器包括独立的 i-cache 和 d-cache。 这样做有很多原因。有两个独立的高速缓存，处理器能够同时读一个指令字和一个数据字。i-cache 通常是只读的，因此比较简单。通常会针对不同的访问模式来优化这两个高速缓存，它们可以有不同的块大小，相联度和容量。使用不同的髙速缓存也确保了数据访问不会与指令访问形成冲突不命中，反过来也是一样，代价就是可能会引起容量不命中增加。

图 6-38 给出了 Intel Core i7 处理器的高速缓存层次结构。每个 CFU 芯片有四个核。每个核有自己私有的 L1 i-cache L1 d-cache 和 L2 统一的高速缓存。所有的核共享片上L3 统一的高速缓存。这个层次结构的一个有趣的特性是所有的 SRAM 高速缓存存储器都在 CPU 芯片上。


图 6-38 Intel Core i7 的高速缓存层次结构

图 6-39 总结了 Core i7 高速缓存的基本特性。


图 6-39 Core i7 髙速缓存层次结构的特性

6.4.7 高速缓存参数的性能影响

有许多指标来衡量高速缓存的性能:

  • 不命中率(miss rate)。在一个程序执行或程序的一部分执行期间，内存引用不命中的比率。它是这样计算的：不命中数量/引用数量。
  • 命中率(hit rate)。 命中的内存引用比率。它等于 1-不命中率。
  • 命中时间(hit time)。从高速缓存传送一个字到 CPU 所需的时间，包括组选择、行确认和字选择的时间。对于 L1 高速缓存来说，命中时间的数量级是几个时钟周期。
  • 不命中处罚(miss penalty)。 由于不命中所需要的额外的时间。L1 不命中需要从 L2得到服务的处罚，通常是数 10 个周期；从 L3 得到服务的处罚，50 个周期；，从主存得到的服务的处罚，200 个周期。

优化高速缓存的成本和性能的折中是一项很精细的工作，它需要在现实的基准程序代码上进行大量的模拟，因此超出了我们讨论的范围，不过，还是可以认识一些定性的折中考量的。

  1. 高速缓存大小的影响
  2. 块大小的影响
  3. 相联度的影响
  4. 写策略的影响

6.5 编写高速缓存友好的代码

在 6.2 节中，我们介绍了局部性的思想，而且定性地谈了一下什么会具有良好的局部性。明白了高速缓存存储器是如何工作的，我们就能更加准确一些了。局部性比较好的程序更容易有较低的不命中率，而不命中率较低的程序往往比不命中率较高的程序运行得更快。因此，从具有良好局部性的意义上来说，好的程序员总是应该试着去编写高速缓存友好(cache friendly)的代码。下面就是我们用来确保代码高速缓存友好的基本方法。

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

6.6 综合：高速缓存对程序性能的影响

本节通过研究高速缓存对运行在实际机器上的程序的性能影响，综合了我们对存储器
层次结构的讨论。

6.6.1 存储器山

一个程序从存储系统中读数据的速率称为读呑吐量(read throughput)。 或者有时称为读带宽(read bandwidth)。如果一个程序在 s 秒的时间段内读 n 个字节，那么这段时间内的读吞吐量就等于 ，通常以兆字节每秒(MB/s)为单位。

6.6.2 重新排列循环以提高空间局部性

6.6.3 在程序中利用局部性

  • 将你的注意力集中在内循环上，大部分计算和内存访问都发生在这里。
  • 通过按照数据对象存储在内存中的顺序、以步长为 1 的来读数据，从而使得你程序中的空间局部性最大。
  • 一旦从存睹器中读入了一个数据对象，就尽可能多地使用它，从而使得程序中的时间局部性最大。