The Memory Hierarchy

实际存储系统 — 层次结构

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

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

存储器的层次结构是可行的, 这是因为与下一个低层次的存储设备相比, 一个编写良好的程序
倾向于更频繁地访问某一个层次上的存储设备(具有良好的局部性). 所以底层的存储设备可以
慢速一点、每比特更便宜因而可以更大一点.

层次结构的整体效果是一个存储池, 其成本与低层次最便宜的存储设备相当, 但却以接近于
顶层存储设备的高速率向程序提供数据.

为何要理解存储系统

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

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

这个思想围绕着计算机程序的一个称为局部性(locality)的基本属性. 具有良好局部性的
程序倾向于一次又一次地访问相同的数据项集合, 或倾向于访问邻近的数据项集合. 具有
良好局部性的程序比局部性差的程序更多的倾向于从存储器层次结构中较高层次处访问数据项,
因此运行地更快.

本章内容

在本章中, 我们会看到基本的存储技术 — SRAM存储器、DRAM存储器、ROM存储器以及
旋转的和固态的硬盘 — 并描述它们是如何被组织成层次结构的.

特别地, 我们将注意力集中在高速缓存存储器上, 它是作为CPU和主存之间的缓存区域, 因为
它们对程序性能的影响最大.

我们向你展示如何分析C程序的局部性, 并且介绍改进你的程序局部性的技术. 你还会学到
一种描绘某台机器上存储器层次结构的性能的有趣的方法: “存储器山”(memory mountain),
它展示出读访问时间是局部性的一个函数.

6.1 存储技术 Storage Technologies

计算机技术的成功很大程度上源自于存储技术的巨大进步.

6.1.1 随机访问存储器 Random-Access Memory

随机访问存储器(random-access memory, RAM)分为两类: 静态的和动态的. 静态RAM(SRAM)
比动态RAM(DRAM)更快, 但也贵得多. SRAM用来作为高速缓存存储器; DRAM用来作为主存
以及图形系统的帧缓冲区. 一般情况下, 一个桌面系统的SRAM不会超过几兆字节, 而DRAM却有
几百或几千兆字节.

1. 静态RAM

双稳态性

SRAM将每个位存储在一个双稳态(bistable)存储单元里. 每个单元用6个晶体管实现. 电路具有
这样一个属性 — 它可以无限期的保持在两个不同电压状态(state)之一. 其他任何状态都是不稳定
的 — 从不稳定状态开始, 电路会迅速地转移到两个稳态中的一个, 存储单元类似下图倒转的钟摆:

钟摆倾斜到最左边或最右边时, 它是稳定的. 从其他任何位置, 钟摆都会导向其中的一侧. 原则上,
钟摆也能在垂直的位置无限期的保持平衡, 但是这个状态是亚稳态的(metastable) — 最细微的
扰动都会使他倒下, 而且倒下后就永远不会再恢复到原垂直位置.

由于SRAM的双稳态性, 只要有电, 它就永远会保持它的值. 即使有干扰(如电子噪音)来扰乱电压,
当干扰消除时, 电路就会恢复到稳定值. (相比DRAM充电后不用持续刷新).

2. 动态RAM

DRAM将每个位存储为对一个电容充电. 这个电容非常小, 通常只有大约30毫微法拉(femtofarad).
DRAM存储器可以制造的非常密集 — 每个单元由一个电容和一个访问晶体管组成. 但是与SRAM不同,
DRAM存储单元对干扰非常敏感 — 当电容的电压被扰乱后, 它就永远不会恢复了; 暴露在光线下会
导致电容电压改变.

很多原因都会导致漏电, 使得DRAM单元在$10\sim 100$毫秒时间内失去电荷. 幸运的是, 计算机运行的
时钟是以纳秒来衡量的, 所以相对而言这个保持时间是比较长的. 内存系统必须周期性地通过读出, 然后
重写来刷新内存的每一位. 有些系统也是用纠错码纠错.(因DRAM很容易被干扰).

下图总结了SRAM和DRAM存储器的特性: 只要有供电, SRAM就会保持不变, 所以与DRAM不同, 它不
需要刷新; SRAM的存取更快, 对光电干扰不敏感, 代价是SRAM单元比DRAM单元使用更多的晶体管,
因而密集程度低, 更贵, 功耗更大.

3. 传统的DRAM

DRAM芯片中的单元(位, cell)被分成d个超单元(supercell), 每个超单元都由$w$个单元(cell)
组成. 一个$d\times w$的DRAM共存储了$dw$位信息. 一个超单元被组织成一个$r$行$c$列的长方形阵列,
这里$d=rc$, 超单元具有形如$(i, j)$的地址. (类似二维数组的表示)

例如下图是一个$16\times 8$的DRAM芯片的组织: 有$d = 16$个超单元, 每个超单元有$w = 8$位, $r = c = 4$.

带阴影的方框表示地址$(2, 1)$处的超单元. 信息通过称为引脚(pin)的外部连接器流入和流出芯片.
每个引脚携带一个位的信息. 图中给出两组引脚:

• 8个data引脚($w = 8$), 它能将一字节信息传入或传出芯片.

• 2个addr引脚($r = c = 2^2$), 它们携带2位的行和列超单元.

这里超单元(supercell)指的是图中DRAM阵列的单个元素.(例如超单元$(2, 1)$ ).

每个DRAM芯片被连接到某个称为内存控制器(memory controller)的电路, 这个电路可以一次传送$w$位
到每个DRAM芯片或从每个DRAM芯片传出$w$位.

• 为了读出超单元$(2, 1)$的内容, 内存控制器将行地址$i$发送到DRAM, 然后是列地址$j$. DRAM把
  超单元$(2, 1)$的内容发回给内存控制器作为响应. 行地址$i$称为RAS(Row Access Strobe, 行访问
  选通脉冲请求); 列地址$j$被称为CAS(列访问选通脉冲请求), 两者共享相同的DRAM地址引脚.

例如, 要从上图读出超单元$(2, 1)$, 内存控制器首先发送行地址2, 如下图 — DRAM的响应是将行2
的整个内容都复制到一个内部行缓冲区.

接下来, 内存控制器发送列地址1. DRAM的响应是从行缓冲区复制到出超单元$(2, 1)$中的8位, 并把
它们发送到内存控制器.

电路设计者将DRAM组织成二维阵列而不是线性数组的一个原因是降低芯片上地址引脚的数目.

4. 内存模块

接下来我们来观察由DRAM分装成的内存模块(memory module), 它以64位为单元与内存控制器交换数据.

下图展示了内存模块的基本思想:

实例模块由8个大小为$8M\times 8$DRAM芯片组成, 编号$0\sim 7$. 每个超单元存储主存的一个字节.

用响应超单元地址$(i, j)$的8个超单元组成主存某地址单元的64位字. 其中DRAM0存储最低字节,
DRAM1存储下一个字节, 以此类推.

要存取内存地址$A$处的一个字(64位机器), 内存控制器将地址$A$转换成超单元地址$(i, j)$, 并将
它发送到内存模块, 然后内存模块再将$i$, $j$广播到每个DRAM. 作为响应, 每个DRAM输出对应$(i, j)$
超单元的8位内容. 模块收集这些输出, 合成一个64位的字, 再返回给内存控制器.

通过将多个内存模块连接到内存控制器, 聚合成主存. 当控制器收到一个地址$A$时, 控制器选择包含$A$
的模块$k$, 将$A$转换成$(i, j)$的形式, 并将$(i, j)$发送到模块$k$.

5. 增强的DRAM

生产厂商试图跟上迅速增长的处理器速度, 所以市场上会定期推出新的DRAM种类, 每种都是在基于传统
DRAM的基础上进行一些优化, 提高访问DRAM基本单元的速度.

• 快页模式DRAM
• 扩展数据输出DRAM
• 双倍数据速率同步DRAM
• $…$

6. 非易失性存储器

如果断电, DRAM和SRAM会丢失它们的信息, 从这个意义上说, 它们是易失的(volatile). 另一方面,
非易失性存储器(nonvolatile memory)即使是在关电后, 仍然保持着它们的信息. 现在有多种非易失性
存储器.

由于历史原因, 虽然ROM中有的类型既可以读也可以写, 但它们整体上都被称为只读存储器(Read-Only-Memory).
ROM是以它们能够被写(重新编程)的次数和进行重新变成所用的机制来区分的:

• PROM(Programmable ROM, 可编程ROM)只能被编程一次 — 存储单元中有一种只能用高电流熔断一次的熔丝.

• 可擦写可编程ROM(EPROM), 能够被编程的次数的数量级达到$10^5$次.

• 闪存(flush), 基于EPROM, 为电子设备如手机、数码照相机等提供快速而持久的非易失性存储.
  之后我们还会研究一种新型的基于闪存的磁盘驱动器 — 固态硬盘(Solid State Disk, SSD).

• 固件(firmware), 存储在ROM中的程序, 例如PC通电后运行的BIOS(基本输入/输出系统).

7. 访问主存

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

总线是一组并行导线, 能携带地址、数据和控制信号. 取决于总线设计， 数据和地址信号可以共享同一组总线, 也可以使用不同总线. 两个以上的设备也能共享一组总线.

控制线携带的信号会同步事务, 并标识出正在被执行的事务的类型. 例如当前事务是到主存还是其他设备;
是读还是写; 总线上的信息是地址还是数据等.

下图展示了计算机系统的配置:

其中主要部件是CPU芯片、I/O桥接器(I\O brige)芯片组(其中包括内存控制器), 以及组成主存的
DRAM内存模块. 这些部件由总线连接, 其中一条是系统总线(system bus) — 连接CPU和I/O
桥接器, 另一条是内存总线(memory bus) — 连接I/O桥接器和主存.

I/O桥接器将系统总线的电子信号翻译成内存总线的电子信号. I/O桥也将系统总线和内存总线连接
到I/O总线. 我们现在将注意力集中在内存总线上.

考虑到CPU执行一个如下加载操作时会发送什么:

    movq A, %rax

这里, 地址$A$的内容被加载到寄存器%rax中. CPU上被称为总线接口(bus interface)的电路在
总线上发起读事务. 读事务由3个步骤组成.

首先, CPU将地址$A$放到系统总线上, I/O桥将信号传递到内存总线:

接下来, 主存接受到内存总线上的地址信号, 从内存总线读地址, 从DRAM读取数据字, 并将数据写到
内存总线. I/O桥将内存总线信号翻译成系统总线信号, 沿系统总线传递:

最后, CPU接收到系统总线上的数据, 从总线读出数据, 将数据复制到寄存器%rax中.

反过来, 当CPU执行向下面这样的存储操作时:

    movq %rax, A

寄存器内容写入地址$A$中. 同样, 有3个步骤. 首先, CPU将地址放到系统总线上, 主存从内存总线
读出地址, 并等待数据到达:

接着, CPU将%rax中的数据复制到系统总线:

最后, 主存从内存总线读出数据, 写入对应的DRAM中:

6.1.2 磁盘存储

磁盘💽时广为应用的保持大量数据的存储设备, 存储数据的数量级可以达到几百到几千千兆字节, 而
基于RAM的存储器只能有几百或几千兆字节(相差接近$10^3$). 不过, 从磁盘上读信息的时间为毫秒级,
比从DRAM读慢了$10$万倍, 比从SRAM读满了$100$万倍.

1. 磁盘构造

磁盘由盘片(platter)构成. 每个盘片有两面(或称表面, surface), 表面覆盖着磁性记录材料. 盘片
中央有一个可旋转主轴(spindle), 它使得盘片以固定旋转速率(rotational rate)旋转, 通常是
$5400\sim 15000$转每分钟(Revolution Per Minute, RPM).

下图展示了一个典型磁盘表面的结构:

每个表面由一组称为磁道(track)的同心圆组成. 每个磁道被划分为一组扇区(sector). 每个扇区包含
数量相等的数据为(通常是512字节). 这些数据编码在扇区上的磁性材料中. 扇区之间由一些间隙(gap)
分开, 这些间隙不保存数据, 而用来存储标识扇区的格式化位.

磁盘由一个或多个叠放在一起的盘片组成, 它们被封装在一个密闭的包装里, 如下图:

整个装置通常被称为磁盘驱动器/旋转磁盘(rotating disk), 以使之区别于基于闪存的固态硬盘(SSD),
SSD没有移动部分.

2. 磁盘容量

一个磁盘上可以记录的最大位数称为它的最大容量, 或简称为容量. 磁盘容量由以下技术因素决定:

• 记录密度(recording density)(位/英寸) — 磁道一英寸的段中可以放入的位数.

• 磁道密度(track density)(道/英寸) — 从盘片中心出发半径上一英寸的段内的磁道数.

• 面密度(areal desity)(位/平方英寸) — 记录密度$\times$磁道密度.

注意, 制造商以千兆字节(GB)或找兆字节(TB)为单位来表达磁盘容量的, 这里的$1GB = 10^9$.
也就是像$K$(kilo), $M$(mega), $G$(giga)和$T$(tera)这样的前缀的含义依赖于上下文:

• 对于DRAM和SRAM容量相关的计量单位, 通常$K = 2^{10}$.
• 对于像磁盘和网络这样的I/O设备容量单位(还有速率和吞吐量), 通常$K = 10^3$.

3. 磁盘操作

磁盘用读/写头(read/write head)来读写存储在磁盘表面的位, 而读写头连接在传动臂(actuator arm)
的一端:

通过沿半径轴前后移动传动臂, 驱动器可以将读/写头定位在盘面上的任何磁道上 — 这样的机械运动
称为寻道(seek).

一旦读/写头定位到了期望的磁道上, 那么当磁道上的每个位通过它的下面时, 读/写头可以感知到
这个位的值(读), 也可以修改这个位(写).

每个盘面都有其对应的磁盘针以及独立的读/写头:

读/写头垂直排列, 一致行动.

在传动臂末端的读/写头在磁盘表面高度大约$0.1$微米处的一层薄薄的气垫上飞翔, 速度大约$80km/h$.
在这样小的空隙里, 表面上一粒微小的灰尘都像一块巨石. 如果读/写头碰到了这样的一块巨石, 读/写头
会停下来, 撞到表面 — 读/写头冲撞(head crash). 为此, 磁盘总是密封包装的.

磁盘以扇区大小位单位读写数据. 对扇区的访问时间(access time)有3个主要组成部分:

• 寻道时间(seek time) — 读/写头从当前磁道移动到(通过传动臂)目标磁道的时间.

  寻道时间$T_{seek}$依赖于读/写头当前位置和传动臂在磁盘上移动的速度. 现代驱动器中平均寻道时间
  $T_{avg\;seek}$通过几千次对随机磁盘的寻道求平均值, 通常为$3\sim 9\;ms$, 一次寻道的最大时间
  $T_{max\;seek}$可高达$20\;ms$.

• 旋转延迟(rotational latency) — 读/写头从当前位置到目标扇区的第一个位的时间.

  旋转时间$T_{rotation}$依赖于读/写头当前位置和磁盘的旋转速度. 在最坏情况下, 读/写头刚刚
  错过目标扇区, 必须等待磁盘旋转一圈, 通常需要$8\;ms$. 平均旋转时间是最大旋转时间的一半, $4\;ms$.

• 传送时间(transfer time) — 读写扇区内容所需时间.

  传送时间$T_{transfer}$依赖于旋转速度和每条磁道的扇区数目. 一般约为$0.02\;ms$.

上述关于3个时间的描述说明:

• 访问一个磁盘扇区的访问时间主要是寻道时间和旋转延迟.

• 寻道时间和旋转延迟大致相等, 所以寻道时间乘以$2$是估计磁盘访问时间的简单合理的方法.

4. 磁盘逻辑快

正如我们看到的, 现代磁盘结构复杂, 有多个盘面, 每个盘面上有多个记录区. 为了对操作系统隐藏
这样的复杂性, 现代磁盘将它们的构造呈现为一个简单的视图 — 一个$B$个扇区的逻辑块序列, 编号
为$0, 1, …, B - 1$(类似数组结构). 磁盘封装中有一个小的磁盘/固件设备, 称为磁盘控制器,
维护着逻辑块号和实际(物理)磁盘扇区之间的映射关系.

当操作系统向磁盘发送一个I/O操作时, 操作系统会发送一个命令到磁盘控制器, 让它读某个逻辑块号,
控制器上的固件执行一个快速查找表, 将逻辑块号翻译成$($盘面, 磁道, 扇区$)$三元组, 这个三元组
唯一标识了对应的物理扇区.

6.1.3 固态硬盘

固态硬盘(Solid State Disk, SSD)是一种基于闪存的存储技术(见6.1.1节), 在某些情况下是传统
旋转磁盘的极有吸引力的替代品.

下图展示了SSD的基本思想:

SSD封装插到I/O总线上标准硬盘插槽(通常是USB中), 处理来自CPU的读写逻辑磁盘快的请求. 一个
SSD封装由一个或多个闪存芯片和闪存翻译层(flash translation layer) — 功能类似旋转磁盘中的
驱动器, 对逻辑块的请求翻译成对底层物理设备的访问 — 组成.

从图中可以看到, 一个闪存由$B$个块(block)的序列组成, 每个块由$P$页(page)组成. 数据是以页为单位读写的, 页的大小
通常是$512B\sim 4KB$.

传统的机械磁盘包含读和写这两个基本操作. 对于SSD, 还多了一个擦除操作 — 将所有存储位都变为$1$. 由于闪存编程(写)原理的限制, 只能将$1$改为$0$, 不能将$0$改成$1$. 所以一个page在写数据之前, 所有的存储位都是$1$.对于写入操作的本质, 就是将某些存储位从$1$变成$0$. 在写入操作之前需要进行擦除操作, 不能直接覆盖.
需要注意的是, 写入操作以页为单位, 擦除操作是以块为单位的 — 当一个block完成了擦除操作, 那么这个block中所包含的所有page都被擦除了, 此时所有的page都能够执行一次写操作.

在经过一定次数的擦除后, block就会发生磨损. 一旦一个block发生损坏后, 就不能再使用了. 因此,
固态硬盘中的闪存翻译层会使用平均磨损算法以延长SSD的使用寿命.

下图展示了典型SSD的性能特性:

比起旋转硬盘(或机械硬盘), SSD有很多优点:

• 由半导体存储器构成, 没有移动部分, 因而随机访问的时间比旋转磁盘块, 能耗低, 同时也更结实.

SSD每字节比旋转磁盘贵大约$30$倍, 因此常用的存储容量比旋转磁盘小$100$倍. 不过, 随着SSD
变得越来越受欢迎, 它的价格下降的非常快, 两者价格的差距正在减少.

6.1.4 存储技术的趋势

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

1)不同的存储技术有不同的价格和性能折中.

• 速度方面: SRAM$\gt$DRAM$\gt$磁盘
• 价格方面: SRAM$\gt$DRAM$\gt$磁盘, SSD位于DRAM和旋转磁盘之间. 这里的造假指每比特造价.

2)不同存储技术的价格和性能属性以截然不同的速率变化着.

• 自1985年以来, SRAM技术的成本和性能基本上是以相同的速度改善的, 访问时间和每兆字节成本下降
  了大约$100$倍:

• DRAM和磁盘的变化趋势更大, 且更不一致. DRAM每兆字节成本下降了$44000$倍, 而DRAM的访问时间
  只下降了大约$10$倍:

• 磁盘的变化趋势更大, 磁盘存储每兆字节成本暴跌了$3000000$倍, 但是访问时间只提高了约$25$倍:

这些惊人的长期趋势突出了内存和磁盘的一个基本事实: 增加密度(从而降低成本)比降低访问时间容易得多.

3)``DRAM和磁盘的性能之后于CPU的性能.

正如我们在下图看到的, CPU周期时间提高了$500$倍. 如果我们看有效周期时间(effective cycle time)
— 定义为一个单独CPU的周期时间除以它的处理器核数 — 那么提高幅度更大一些, 为$2000$倍.

注意, 虽然SRAM的性能滞后于CPU的性能, 但还是在保持增长. 不过, DRAM和磁盘的性能与CPU性能
之间的差距实际上是在加大的. 下图表面了各种趋势, 注意纵轴每单位相差一个数量级(对数比例):

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

6.2 局部性 Locality

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

局部性通常具有2种形式:

• 时间局部性(temporal locality) — 被引用过一次的内存位置很可能在不远的将来再被多次引用.

• 空间局部性(spatial locality) — 如果一个内存位置被引用了一次, 那么程序很可能在不远的将来
  引用附近的一个内存位置.

程序员应该理解局部性原理, 因为一般而言, 有良好局部性的程序比局部性差的程序运行得更快.
现代计算机系统的各个层次, 从硬件到操作系统、再到程序, 它们的设计都利用了局部性原理.

接下来, 我们通过几个代码示例来观察程序的局部性原理.

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

考虑对向量元素求和的简单函数:

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

这个程序是否具有良好的局部性? 要回答这个问题, 需要观察每个变量的引用模式. 变量sum在每次循环迭代
中被引用一次, 因此, 对sum来说, 程序具有良好的时间局部性; 因为sum是一个标量, 所以对sum来说没有
空间局部性.

实例中向量v是顺序存储的