第六章：存储器层次结构

这章决定做一些简单的整理。

6.1 存储技术

6.1.1 随机访问存储器RAM

随机访问存储器（Random-Access Memory，RAM）可以分为两类：静态的RAM（SRAM）和动态的RAM（DRAM）。区别如下：

• SRAM：每个位保存到由6个晶体管电路构成的双稳态的（Bistable）存储器单元。只要有供电，它保存的数据就不会丢失。对光和电噪音等干扰不敏感。 访问速度快，但造价较为昂贵且密集度低。适合作为小容量高速的高速缓存存储器。
• DRAM：将每个位保存为，对一个由访问晶体管控制的电容的充电。有供电以及刷新，才能保持存储的数据不丢失。对光和电噪音等干扰敏感。 访问速度相对较慢，但造价便宜且密集度高。适合作为主存和帧缓冲区。

传统的DRAM

一些名称约定：

• cell：DRAM芯片中的一个bit
• supercell：w个cell组成的单元
• pin：引脚，每个引脚可以传递一个比特信号

现在将DRAM芯片分为d个supercell，每个supercell中包含了w个cell。则称这是一个d × w DRAM芯片，存储了dw位信息。下图是一个16 × 8的DRAM芯片。

首先内存控制器通过addr引脚发送两位行地址到DRAM芯片，DRAM芯片找到该行并放入内部行缓冲区。内存控制器再发送两位的列地址，DRAM芯片找到行缓冲区的该列，并通过data引脚发送8位的数据到内存控制器。 之所以把DRAM芯片排列成矩阵的形式，是为了减少addr引脚数。如果我们把八个DRAM芯片封装到一个内存模块中，就可以一次能对64位字进行读写。

enhanced DRAM

• 快页模式DRAM（Fast Page Mode DRAM，FPM DRAM）：传统的DRAM芯片通过CAS获得数据后，会将那一行的数据从内部行缓冲区直接删掉，如果访问多个在同一行的超单元时，需要反复读取相同的行。而FPM DRAM能够获取一次行数据后，后面的读取直接从内部行缓冲区读取。
• 扩展数据输出DRAM（Extended Data Out DRAM，EDO DRAM）：对FPM DRAM进行改进，使得各个CAS信号在时间上更加紧密。
• 同步DRAM（Synchronous DRAM，SDRAM）：DRAM芯片与内存控制器的通信使用一组显示的控制信号，通常是异步的，而SDRAM使用了，控制内存控制器的外部时钟信号的上升沿来代替控制信号。
• 双倍数据速率同步DRAM（Double Data-Rate Sychronous DRAM，DDR SDRAM）：对SDRAM的优化，通过使用两个时钟沿作为控制信号，从而使得DRAM的速度翻倍。
• 视频RAM（Video RAM，VRAM）：用于图形系统的帧缓冲区，与FPM DRAM的区别：VRAM的输出是通过对内部缓冲区的移位得到的，VRAM允许对内存并行地读和写。

6.1.2 非易失性存储器ROM

之前介绍的DRAM和SRAM在断电时都会丢失数据，所以是易失的（Volatile）。而非易失性存储器（Nonvolatile Memory）即使断电后，也会保存信息，该类存储器称为只读存储器（Read-Only Memory，ROM）。 但是现在ROM中有的类型既可以读也可以写了。ROM可以分为以下几类：

• PROM：programmable ROM，由保险丝等实现，只可编程一次
• EPROM：erasable programmable ROM，通过石英、紫外线等物理手段实现。可以擦写1000次
• EEPROM：electrically erasable PROM，由电路实现，可擦写100000次
• Flash memory：闪存，基于EEPROM，固态硬盘（SSD）就基于闪存

存储在ROM设备中的程序称为固件（Firmware），包括BIOS、磁盘控制器、网卡、图形加速器和安全子系统等。当计算机系统通电后，会运行存储在ROM中的固件。

6.1.3 磁盘disk

磁盘（Disk）是被用来保存大量数据的存储设备，但是读信息的速度比DRAM慢10万倍，比SRAM慢100万倍。

上图所示的是一个磁盘的构造。磁盘是由多个叠放在一起的盘片（Platter）构成。每个盘片有两个覆盖着磁性记录材料的表面（Surface）。 每个表面由一组称为磁道（Track）的同心圆组成。每个磁道被划分为若干扇区（Sector）。每个扇区包含相同数量的数据位（通常为512位）作为读写数据的基本单位。 扇区之间通过间隙（Gap）分隔开来，间隙不保存数据信息，只用来表示扇区的格式化位。 通常会使用柱面（Cylinder）来描述不同表面上相同磁道的集合，比如柱面k就是6个表面上磁道k的集合。 盘片中央会有一个可以旋转的主轴（Spindle），使得盘片以固定的旋转速率（Rotational Rate）旋转，单位通常为RPM（Revolution Per Minute）。

现代大容量磁盘采用多区记录（Multiple Zone Recording）技术，将一组连续的柱面划分成一个区。 在同一个区中，每个柱面的每条磁道都有相同数量的扇区，数量由该区中最内侧的磁道决定。由此外侧的区能划分成更多的扇区。

6.1.4 固态硬盘SSD

固态硬盘（Solid State Disk，SSD）是一种基于闪存的存储技术。从CPU的角度来看，SSD与磁盘完全相同，有相同的接口和包装。

如上图所示是一个SSD的基本结构。它由闪存和闪存翻译层（Flash Translation Layer）组成

• 闪存翻译层是一个硬件/固件设备，用来将对逻辑块的请求翻译成对底层物理设备的访问。
• 闪存的基本属性决定了SSD随机读写的性能，通常由B个块的序列组成，每个块由P页组成，页作为数据的单位进行读写。通常页大小为512字节~4KB，块中包含32~128页，则块的大小有16KB~512KB。

SSD的随机写操作慢于随机读操作，这是因为：1）擦除块耗时长；2）当块中包含其他数据时，会先将块中带有有效数据的页复制到被擦出过的块中，才能对那个块进行擦除。

SSD的优缺点：

• 优点：由于闪存是半导体存储器，没有移动的部件，所以速度比磁盘更快且磨损小，能耗低
• 缺点：SSD每字节比磁盘贵大约30倍。此外SSD也有擦除次数的限制，但是由于闪存翻译层会把擦除尽可能平分到每一个块中，这件事情不用担心。

6.1.5 总线结构

总线(bus)是一组并行的导线，能够携带地址、数据和控制信号。这里要提及一下直接内存访问（Direct Memory Access，DMA）技术。 当磁盘控制器接收到CPU发出的Read命令后，直接将磁盘内容传送到主存中，无需CPU干涉，该过程称为直接内存访问。

6.2 局部性

高速缓存（cache）是小而快的存储器，它存放着大且慢存储器里的部分数据。如果我们访问的数据均来自顶层的缓存之中，则可以提高程序运行速度。 为了做到这一点需要利用局部性（locality）。局部性有两种：

• 时间局部性（Temporal Locality）：引用过的数据项在不久会被多次引用
• 空间局部性（Spatial Locality）：引用过的数据项，在不久会引用附近的数据项

局部性应该比较好理解，这里就不赘述了。

6.3 存储器层次结构

存储器层次结构的中心思想是让层次结构中的每一层来缓存低一层的数据对象，将第k层的更快更小的存储设备作为第k+1层的更大更慢的存储设备的缓存。 显然该结构利用了局部性。

相邻层的存储器以块（block）作为数据传送单元。通常较低层的使用较大的块。

6.3.1 缓存命中

当程序需要第k+1层的某个数据对象d时，会现在第k层的块中搜索d，如果d刚好缓存在第k层中，则称为缓存命中（Cache Hit）。于是该程序会直接从第k层中读取d。

6.3.2 缓存不命中

如果第k层没有缓存数据对象d，则称为缓存不命中（Cache Miss）。则会从第k+1层中取出包含d的块，然后第k层的缓存会执行某个放置策略（Placement Policy）来决定该块要保存在第k层的什么位置。 如果第k层的缓存满了，则会覆盖现存的一个牺牲块（Victim Block），称为替换（Replacing）或驱逐（Evicting）这个牺牲块，会根据替换策略（Replacement Policy）来决定要替换第k层的哪个块。

特殊地，如果第k层的缓存为空，那么对于任意的数据对象的访问都会不命中。空的缓存称为冷缓存（Cold Cache），该不命中称为强制性不命中（Compulsory Miss）或冷不命中（Cold Miss）。

特殊地，如果访问的块是一个相对不变的集合，比如在嵌套循环中反复访问一个数组的每个元素，那么该集合称为工作集（Working Set）。如果工作集大小超过缓存大小，则缓存会出现容量不命中（Capacity Miss），这是由缓存太小导致的。

6.3.3 缓存管理

缓存在现代计算机系统中无处不在：

6.4 高速缓存存储器

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

如上图的b中所示，会将m位的地址划分成三部分：

• s位：高速缓存被组织成S = 2^s组
• b位：每个组包含E个高速缓存行，每个行有B = 2^b个高速缓存块
• t位：每一个高速缓存行有一个t = m - s - b位的标记位

显然可以方便地通过地址确定目标数据块。 该高速缓存的结构可以通过元组(S, E, B, m)来描述，且容量C为所有块的大小之和，C = S × E × B。

6.4.2 直接映射高速缓存

如上图所示，当E = 1时，高速缓存称为直接映射高速缓存（Direct-mapped Cache），每个高速缓存组中只含有一个高速缓存行。

首先读取地址的s位，找到该组。然后检查有效位是否为1以及标记和t位是否一致。如果一致，再通过b位找到目标字节，返回即可。 如果不一致，则发生不命中情况，从下一级的缓存找到该目标高速缓存块，并替换当前的块。

运气不好的话，会发生抖动（Thrash），即高速缓存反复地加载和驱逐相同的高速缓存块的组。

6.4.3 组相联高速缓存

直接映射高速缓存的冲突不命中是由于每个高速缓存组中只有一个高速缓存行，所以扩大E的值，当1 < E < C/B时，称为E路组相联高速缓存（E-way set associative cache）。 下图所示的是一个2路组相联高速缓存。

当缓存不命中时需要进行缓存行替换，如果对应的高速缓存组中有空的高速缓存行，则直接将其保存到空行中。但是如果没有空行，就要考虑合适的替换策略：

• 随机选择要替换的行
• 最不常使用（Least-Frequently-Used，LFU）策略：替换过去某个时间窗口内引用次数最少的一行
• 最近最少使用（Least-Recently-Used，LRU）策略：替换最后一次访问时间最久远的那一行

6.4.4 全相联高速缓存

全相联高速缓存（Fully Associative Cache）是用一个包含所有高速缓存行的组组成的，其中E = C/B，即S = 1。

由于全相联高速缓存只有一个组，所以不包含组索引编码。 其行匹配和字选择与组相联高速缓存相同，只是规模大小不同。 想要得到高速的全相联高速缓存十分困难，所以通常适合用于较小的高速缓存，比如虚拟内存中的翻译备用缓冲器（TLB）。

6.4.5 写操作

当CPU想要对地址A进行写操作时，会通过地址A判断是否缓存了该地址，如果缓存了称为写命中（Write Hit），否则称为写不命中（Write Miss）。 下面分别分析写命中和写不命中的不同实现思路：

写命中

• 直写（Write-Though）：立即更新下一层的副本值。缺点是每次写都会引起总线流量。
• 写回（Write-Back）：为每个高速缓存行维护一个修改位（Dirty Bit），表明这个高速缓存块是否被修改。当被修改的高速缓存块被驱逐时，才会更新下一层的副本值。能够显著减少总线流量，但是复杂性高。

写不命中

• 写分配（write-allocate）：加载相应的下一层的块到当前层的高速缓存中，然后更新当前高速缓存块。得益于空间局部性，进行一次写分配后，下一次有较高几率会写命中，但是缺点是每次写不命中就要将块从低级向上传输。
• 写不分配（no-write-allocate）：绕过缓存，直接把字写到下一层中

直写高速缓存通常为写不分配的，写回高速缓存通常为写分配的。建议采用写回写分配模型，因为随着逻辑电路密度的提高，写回的复杂性不再成为阻碍，并且和处理读相同，都利用了局部性原理，效率较高。

6.4.6 i7 高速缓存层次结构

i-cache：只保存指令的高速缓存；d-cache：只保存程序数据的高速缓存。如图：

6.5 存储器山

这是一个比较有名的lab，甚至csapp的封面就是这个存储器山，我便泛泛而谈一下。话不多说，先上图：

这是一座时间局部性和空间局部性构成的山。整个测试的核心代码其实很简单：

for (int i = 0; i < size; i += stride) {
    result += data[i];
}

通过size来控制我们工作集的大小，由此来控制工作集存放的高速缓存的级别。 假设工作集很小，则工作集会全部存放在L1高速缓存中，模拟了时间局部性优异的程序反复读取之前访问过的数据，则都是从L1高速缓存读取数据的。 假设工作集很大，则工作集会存放到L3高速缓存中，模拟了时间局部性很差的程序。不断读取新的数据，则会出现缓存不命中，而不断从L3高速缓存中取数据的过程。 所以通过控制工作集大小，来模拟程序局部性。

通过stride来控制读取的步长，来控制程序的空间局部性。

6.6 一些建议

• 将你的注意力集中在内循环上，大部分计算的存储器访问都集中在这里
• 按照数据对象存储在内存中的顺序，以步长为1来读数据，使得空间局部性最大
• 一旦从存储器读入一个数据对象时，就尽可能使用它，使得时间局部性最大。特别是局部变量，编译器会将其保存在寄存器中。