csapp第六章——存储器层次结构

存储器层次结构

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

随机访问存储器

静态RAM

由于 SRAM 存储器单元的双稳态特性，只要有电，它就会永远地保持它的值。

动态RAM

DRAM 将每个位存储为对每个电容的充电。与 SRAM 不同， DRAM 存储器单元对干扰非常敏感 。

传统的DRAM

DRAM 芯片中的单元（位）被分成d 个超单元 (supercell) , 每个超单元都个DRAM单元组成。 d*w 的DRAM 总共存储了d w位信息。

图示为168 DRAM 芯片的组织，有 d=l6 个超单元，每个超单元有 w=8 位， r=4 行，c=4 。

• 将 DRAM 组织成二维阵列而不是线性数组的一个原因是降低芯片上地址引脚的数量。

• 二维阵列组织的缺点是必须分两步发送地址，这增加了访问时间。

内存模块

DRAM 芯片封装在内存模块 (memory module) 中，它插到主板的扩展槽上 。

内存控制器将超单元地址 发送到内存模块，然后内存模块再广播到每个 DRAM 。作为响应，每个DRAM 输出它的超单元的8位内容。模块中的电路收集这些输出，并把它们合并成64 位字，再返回给内存控制器。

将多个内存模块连接到内存控制器，能够聚合成主存。

这也是为什么16GB板载内存被分为8*2GB小内存的原因

增强的DRAM

• 快页模式 DRAM(Fast Page Mode DRAM, FPM DRAM)

若第四个超单元来自同一行，那么的第一个发送RAS/CAS请求，后面三个超单元发送CAS请求，直接从行缓冲区获得。

• 扩展数据输出 DRAM(Extended Data Out DRAM, EDO DRAM)

FPM DRAM一个增强的形式，它允许各个 CAS 信号在时间上靠得更紧密一点。

• 同步 DRAM(Synchronous DRAM, SDRAM) 。

  SDRAM 能够比那些异步的存储器更快地输出它的超单元的内容。

• 双倍数据速率同步 DRAM (Double Data-Rate Synchronous DRAM, DDR SDRAM)

它通过使用两个时钟沿作为控制信号，从而使 DRAM 的速度翻倍,不同类型的 DDR SDRAM 是用提高有效带宽的很小的预取缓冲区的大小来划分的： DDR(2 位）、 DDR2(4 位）和 DDR(8 位）

• 视频 RAM(Video RAM, VRAM)

它用在图形系统的帧缓冲区中。

非易失性存储器

非易失性存储器 (nonvolatile memory) 即使是在关电后，仍然保存着它们的信息 。

访问主存

数据流通过称为总线 (bus) 的共享电子电路在处理器和 DRAM 存之间来来回回。

其中一条总线是系统总线 (system bus), 它连接 CPU和I/0 桥接器，另一条总线是内存总线 (memory bus), 它连接 I/0 桥接器和主存，I/O桥接器将系统总线的电子信号翻译成内存总线的电子信号。

磁盘存储

磁盘构造

• 磁盘是由盘片 (platter) 构成的。每个盘片(表面)有两面, 表面覆盖着磁性记录材料。
• 盘面中央有个可以旋转的主轴 (spindle)。
• 每个表面是由一组称为磁道 (track) 的同心圆组成的。
• 每个磁道被划分为一组扇区 (sector)。每个扇区包含相等数量的数据位（通常512 字节），这些数据编码在扇区上的磁性材料中。
• 扇区之间由一些间隙 (gap) 分隔开，这些间隙中不存储数据。间隙存储用来标识扇区的格式化位。
• 磁盘是 一个或多个叠放在一起 的盘片组成的，它们被封装在 一个密封的包装里，整个装置通常被称为磁盘驱动器 (disk drive), 我们通常简称为磁盘 (disk)。
• 柱面(cylinder)是所有盘片表面上到主轴中心的距离相等的磁道的集合。

磁盘容量

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

• 磁道密度 (track density)( 道/英寸）：从盘片中心出发半径上一英寸的段内可以放入的磁道数。

• 面密度 (areal density) (位/平方英寸）：记录密度与磁道密度的乘积。

磁盘操作

• 通过沿着半径轴前后移动这个传动臂，驱动器可以将读/写头定位在盘面上的任何磁道上。这样的机械运动称为寻道 (seek) 。
• 在任何时刻，所有的读/写头都位于同一个柱面上。

访问时间 (access time) 有三个主要的部分：

1. 寻道时间：为了读取某个目标扇区的内容，传动臂首先将读/写头定位到包含目标扇区的磁道上。移动传动臂所需的时间称为寻道时间。寻道时间依赖于读/写头以前的位置和传动臂在盘面上移动的速度。
2. 旋转时间：一旦读/写头定位到了期望的磁道，驱动器等待目标扇区的第一个位旋转到读/写头下。这个步骤的性能依赖于当读/写头到达目标扇区时盘面的位置以及磁盘的旋转速度。在最坏的情况下，读/写头刚刚错过了目标扇区，必须等待磁盘转一整圈。
3. 传送时间：当目标扇区的第一个位位于读/写头下时，驱动器就可以开始读或者写该扇区的内容了。 一个扇区的传送时间依赖于旋转速度和每条磁道的扇区数目。

逻辑磁盘块

磁盘封装中有一个小的硬件/固件设备，称为磁盘控制器，维护着逻辑块号和实际（物理）磁盘扇区之间的映射关系。

连接I/O设备

• 通用串行总线 (Universal Serial Bus, USB) 控制器是一个连接到 USB 总线的设备的中转机构，

• 图形卡（或适配器）包含硬件和软件逻辑，它们负责代表 CPU 在显示器上画像素。

• 主机总线适配器将一个或多个磁盘连接到总线，使用的是一个特别的主线总线接口定义的通信协议。

  两个最常用的这样的磁盘接口是SATA和SCSI

访问磁盘

CPU使用一种称为内存映射 (memory-mapped I/0) 的技术来向 I/0 设备发射命令

1. CPU 发出了请求之后，在磁盘执行读的时候，它通常会做些其他的工作。
2. 在磁盘控制器收到来自 CPU 的读命令之后，它将逻辑块号翻译成一个扇区地址，读该扇区的内容，然后将这些内容直接传送到主存，不需要 CPU 的干涉。设备可以自己执行读或者写总线事务而不需要 CPU 干涉的过程，称为直接内存访问 (Direct Memory Access, DMA) 。这种数据传送称为DMA 传送 (DMA transfer)。
3. DMA 传送完成，磁盘扇区的内容被安全地存储在主存中以后，磁盘控制器通过给CPU 发送一个中断信号来通知 CPU。

固态硬盘

• 固态硬盘 (Solid State Disk , SSD) 种基于闪存的存储技术。

• 一个 SSD 封装由一个或多个闪存芯片和闪存翻译层 (flash translation layer)组成。

• 读 SSD 比写要快。随机读和写的性能别是由底层闪存基本属性决定的。

• 一个闪存由B个块的序列组成，每个块由P页组成。

• 数据是以页为单位读写的。只有在一页所属的块整个被擦除之后，才能写这一页（通常是指该块中的所有位都被设置为 1) 。

• 随机写很慢有两个原因：（1）擦除块需要相对较长的时间。（2）如果试图修改一个巳经有数据（也就是不是全为 1) 的页p, 那么这个块中所有带有用数据的页都必须被复制到一个新（擦除过的）块，然后才能进行对页写。
• 闪存翻译层中的平均磨损 (wear leveling) 逻辑试图通过将擦除平均分布在所有的块上来最大化每个块的寿命。

存储技术趋势

• 增加密度（从而降低成本）比降低访问时间容易得多。

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

局部性

一个编写良好的计 程序常常具有良好的局部性 (locality) 。也就是，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。

时间局部性 (temporal locality) 和空间局部性 (spatial locality):

• 时间局部性：被引用过一次的内存位置很可能在不远的将来再被多次引用

• 空间局部性：如果一个内存位被引用了一次，那么程序很可能在不远的将来引用附近的 一个内存位置。

对程序数据引用的局部性

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，函数有很好的空间局部性，但是时间局部性很差，因为每个向量元素只被访问一次。

我们说像 sumvec这样顺序访问一个向最每个元素的函数，具有步长为1 的引用模式(stride-I reference pattern) (相对于元素的大小）。有时我们称步长为1的引用模式为顺序引用模式 (sequential reference pattern) 。一个连续向量中，每隔 k个元素进行访问，就称为步长为k的引用模式 (stride-k reference pattern) 。

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;
}

sumarraycols按照数组被存储的行优先顺序来访问这个数组。其结果是得到一个很好的步长为1 的引用模式，具有良好的空间局部性。

int sumarraycols(int a[M][N])
{
    int i, j, sum = 0;

    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            sum += a[i][j];
    return sum;
}

sumarraycols步长为 N的引用模式,空间局部性很差。

取指令的局部性

for 循环体里的指令是按照连续的内存顺序执行的，因此循环有良好的空间局部性。因为循环体会被执行多次，所以它也有很好的时间局部性。

局部性小结

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

存储器层次结构

存储器层次结构中的缓存

• 高速缓存 (cache, 读作 “cash”) 是一个小而快速的存储设备，它作为存储在更大、也更慢的设备中的数据对象的缓冲区域。

• 层次结构中的每一层都缓存来自较低一层的数据对象。

• 数据总是以块大小为传送单元 (transfer unit) 在第 k层和第 k+l 层之间来回复制的。

• 较低层的传送使用的块一般比较高层传送用的块更大。

• 缓存命中：直接从第 k层读取对象d, 根据存储器层次结构的性质，这要比从第 k+l 层读取 更快。

• 缓存不命中第k 层中没有缓存数据对象 d。第k 层的缓存从第k+1层缓存中取出包含d的那个块，如果第k层的缓存已经满了，可能就会覆盖现存的一个块（称为牺牲块）。

• 一个空的缓存有时被称为冷缓存 (cold cache) , 此类不命中称为强制性不命中 (compulsory miss) 或冷不命中 (cold miss) 。

• 冲突不命中 (conflict miss), ，多个对象映射到同 一个缓存块，缓存会一直不命中。

• 一个嵌套的循环可能会反复地访问同一个数组的元素。这个块的集合称为这个阶段的工作集 (working set) 。当工作集的大小超过缓存的小时，缓存会经历容量不命中 (capacity miss) 。

小结

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

• 利用时间局部性：由于时间局部性，同一数据对象可能会被多次使用。 一旦一个数据对象在第一次不命中时被复制到缓存中，我们就会期望后面对该目标有一系列的访问命中。因为缓存比低一层的存储设备更快，对后面的命中的服务会比最开始的不命中快很多。
• 利用空间局部性：块通常包含有多个数据对象。由于空间局部性，我们会望后面对该块中其他对象的访问能够补偿不命中后复制该块的花费。

高速缓存存储器

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

直接映射高速缓存

每个组只有一行的高速缓存称为直接映射高速缓存 (direct-mapped cache) 。

1. 直接映射高速缓存中的组选择

高速缓存从w的地址中间抽取出s个组索引位。这些位被解释成一个对应于一个组号的无符号整数。

1. 直接映射高速缓存中的行匹配

当且仅当设置了有效位，而且高速缓存行中的标记与的地址中的标记相匹配时，这 行中包含的一个副本。则缓存命中。

1. 直接映射高速缓存中的字选择

一旦命中，我们知道 就在这个块中的某个地方。块偏移位提供了所需要的字的第一个字节的偏移。

1. 直接映射高速缓存中不命中时的行替换

如果缓存不命中，那么它需要从存储器层次结构中的下一层取出被请求的块 ，然 后将新的块存储在组索引位指示的组中的一个高速缓存行中。

1. 综合：运行中的直接映射高速缓存

• 标记位和索引位连起来唯 地标识了内存中的每个块。

• 多个块会映射到同一个高速缓存组（即它们有相同的组索引）。

• 映射到同一个高速缓存组的块由标记位唯一地标识。

1) 读地址0的字，缓存不命中。高速缓存从内存（或低一层的高速缓存）取出块 0, 并把这个块存储在组0中。然后，高速缓存返回新取出的高速缓存行的块 [0J 的m[0]。

2) 读地址1的字,高速缓存命中。高速缓存立即从高速缓存行的块 [1] 中返m[1] 。

1. 读地址 13 的字。缓存不命中。高速缓存把块6加载到组2中，然后从新的高速缓存行的块[1] 中返回 m[13].

1. 读地址8的字。这会发生缓存不命中。组0中的高速缓存行确实是有效的，但是标记不匹配。

1. 读地址0的字。又会发生缓存不命中，因为在前面引用地址 时，我们刚好替换了，这就是冲突不命中的一个例子。

1. 直接映射高速缓存中的冲突不命中

• 抖动:即高速缓存反复地加载和驱逐相同的高速缓存块的组.

为什么用中间的位来做索引你也许会奇怪，为什么高速缓存用中间的位来作为组索引，而不是用高位 为什么用中间的位更好，是有很好的原因的.如果高位用做索引，那么 一些连续的内存块就会映射到相同的高速缓存块 例如，在图中，头四个块映射到第一个高速缓存组，笫二个四个块映射到笫二个组，依此类推 如果一个程序有良好的空间局部性，顺序扫描一个数组的元素，那么在任何时刻，高速缓存都只保存着一个块大小的数组内容 这样对高速缓存的使用效率很低 .相比较而言，以中间位作为索引，相邻的块总是映射到不同的高速缓存行. 在这里的情况中，高速缓存能够存放整个大小为c的数组片，这里 c是高速缓存的大小。

组相联高速缓存

直接映射高速缓存中冲突不命中造成的问题源于每个组只有一行。组相联高速缓存 (set associative cache)放松了这条限制，所以每个组都保存有多于一个 高速缓存行。

1. 组相联高速缓存中的组选择

它的组选择与直接映射高速缓存的组选择一样，组索引位标识组。

1. 组相联高速缓存中的行匹配和字选择

全相联高速缓存

1. 全相联高速缓存中的组选择。全相联高速缓存中的组选择非常简单，因为只有一个组。

1. 全相联高速缓存中的行匹配。和字选择全相联高速缓存中的行匹配和字选择与组相联高速缓存中的是一样的。

因为高速缓存电路必须并行地搜索许多相匹配的标记，构造一个又大又快的相联高速缓存很困难，而且很昂贵。因此，全相联高速缓存只适合做小的高速缓存，例如虚拟内存系统中的翻译备用缓冲器 (TLB),

有关写的问题

• 直写(write-through)：就是立即将w 的高速缓存块写回到紧接着的低一层中。是直写的缺点是每次写都会引起总线流量。
• 写回 (write-back)：尽可能地推迟更新，只有当替换算法要驱逐这个更新过的块时，才把它写到紧接着的低一层中。但是它的缺点是增
  加了复杂性。高速缓存必须为每个高速缓存行维护一个额外的修改位 (dirty bit)。
• 写分配 (write-allocate), 加载相应的低一层中的块到高速缓存中，然后更新这个高速缓存块。
• 非写分配 (not-write-allocate) , 避开高速缓存，直接把这个字写到低一层中。
• 直写高速缓存通常是非写分配的。写回高速缓存通常是写分配的。

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

高速缓存参数的性能影响

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

• 不命中率 (miss rate) 。在一个程序执行或程序的一部分执行期间，内存引用不命中的比率。
• 命中率 (hit rate) 。命中的内存引用比率。它等于 1-不命中率。
• 命中时间 (hit time) 。从高速缓存传送一个字到 CPU 所需的时间，包括组选择、行确认和字选择的时间。
• 不命中处罚 (miss penalty) 。由于不命中所需要的额外的时间。

1. 高速缓存大小的影响

较大的高速缓存可能会提高命中率，使大存储器运行得更快总是要难一些的 。结果，较大的高速缓存可能会增加命中时间。

1. 块大小的影响

大的块有利有弊。一方面，较大的块能利用程序中可能存在的空间局部性，帮助提高命中率。不过，对于给定的高速缓存大小，块越大就意味着高速缓存行数越少，这会损害时间局部性比空间局部性更好的程序中的命中率。较大的块对不命中处罚也有负面影响，因为块越大，传送时间就越长。

1. 相联度的影响

较高的相联度（也就E的值较大）的优点是降低了高速缓存由于冲突不命中出现抖动的可能性。不过，较高的相联度会造成较高的成本和不命中处罚。相联度的选择最终变成了命中时间和不命中处罚之间的折中 。

1. 写策略的影响

直写高速缓存比较容易实现，而且能使用独立于高速缓存的写缓冲区 (write buffer) , 用来更新内存。越往层次结构下面走，传送时间增加，减少传送的数量就变得更加重要。一般而言，高速缓存越往下层，越可能使用写回而不是直写。

编写高速缓存友好的代码

基本方法：

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

• 一般而言，如果一个高速缓存的块大小为B字节，那么个步长为k的引用模式（这里以字为单位的）平均每次循环迭代 min(l, (wordsize * k)/ B) 次缓存不命中 。

• 对局部变量的反复引用是好的，因为编译器能够将它们缓存在寄存器文 件中（时间局部性）。

• 步长为1的引用模式是好的，因为存储器层次结构中所有层次上的缓存都是将数据存储为连续的块（空间局部性）。

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

存储器山

利用chatgpt生成数据处理程序：

% 存储器山时钟频率和内存速率数据

memory_data = [
    19730   10983   7935    6654    5372    4941    4294    3578    3462    3261    3163    3028    2802    2735    2658;
    21719   10571   8817    6407    5938    4806    4457    3937    3711    3450    3357    3169    3037    2969    2840;
    22330   13040   9658    7674    6594    5863    5089    4385    4334    4150    3970    3851    3492    3586    3503;
    26509   14470   12846   11190   9870    8719    8048    7460    7315    6607    6321    6682    5972    6231    5980;
    46887   31859   24558   19533   16235   14037   10792   9643    8886    8096    7412    7201    6673    6371    6010;
    41056   30640   24099   18308   14804   12374   10634   9290    8610    7927    7179    6956    6426    6104    5684;
    41233   32133   26039   20696   16938   14191   12289   10591   9951    9303    8646    8894    9162    11831   8452;
    40066   38844   36982   33604   30782   26891   23560   20803   21350   24882   25374   26375   27904   27803   28154;
    40280   40730   41249   40166   39069   36080   31765   28163   27859   27057   26582   27722   27764   27846   27826;
    40542   40647   40895   40526   39342   35989   31904   28085   27587   27026   26644   27756   27727   27892   27537;
    40281   40875   40944   40158   38901   35481   31738   27741   27353   26387   25701   27005   27412   27088   26542;
    40009   41533   40809   39201   38497   34454   30365   27021   26643   32405   40993   41530   43676   41363   43004;
    46307   46497   44877   42117   44895   41941   41600   39566   40435   40435   38435   37740   38235   39556   37740;
    46370   44624   42149   42326   39191   35529   38510   36194   35829   33741   34563   31923   30618   31104   29031
];

% 内存大小标签
memory_sizes = {'128m', '64m', '32m', '16m', '8m', '4m', '2m', '1024k', '512k', '256k', '128k', '64k', '32k', '16k'};

% 创建 X 轴和 Y 轴
x = 1:size(memory_data, 2); % 存储器编号
y = 1:size(memory_data, 1); % 内存大小
%x 的取值范围是从 1 到 memory_data 的列数
%y 的取值范围是从 1 到 memory_data 的行数

% 创建 X 轴和 Y 轴的网格
[X, Y] = meshgrid(x, y);

% 创建存储器山图
figure;
surf(X, Y, memory_data);
% surf(X,Y,Z) 创建一个三维曲面图，它是一个具有实色边和实色面的三维曲面。
xlabel('Storage Number');
ylabel('Memory Size');
zlabel('Memory Rate (MB/sec)');
title('Memory Mountain');

% 设置 X 轴和 Y 轴的刻度及标签
xticks(x);
yticks(y);
yticklabels(memory_sizes);

• 对于步长为1的引用模式，由于硬件预取机制，被识别并试图在一个块被加载前取到高速缓存中。

• 在L2，L3，和主存山脊上，随着步长的增加，有一个空间局部性的斜坡，空间局部性下降。

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

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

计算nn矩阵相乘问题，时间复杂度O（n*3）。

void ijk(array A, array B, array C, int n)
{
    int i, j, k;
    double sum;

/* $begin mm-ijk */
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
        sum = 0.0;
        for (k = 0; k < n; k++)
            sum += A[i][k]*B[k][j];
        C[i][j] += sum;
    }
/* $end mm-ijk */

}

void jik(array A, array B, array C, int n)
{
    int i, j, k;
    double sum;

/* $begin mm-jik */
for (j = 0; j < n; j++)
    for (i = 0; i < n; i++) {
        sum = 0.0;
        for (k = 0; k < n; k++)
            sum += A[i][k]*B[k][j];
        C[i][j] += sum;
    }
/* $end mm-jik */
}

void ikj(array A, array B, array C, int n)
{
    int i, j, k;
    double r;

    /* $begin mm-ikj */
for (i = 0; i < n; i++)
    for (k = 0; k < n; k++) {
        r = A[i][k];
        for (j = 0; j < n; j++)
            C[i][j] += r*B[k][j];
    }
/* $end mm-ikj */
}

void kij(array A, array B, array C, int n)
{
    int i, j, k;
    double r;

    /* $begin mm-kij */
for (k = 0; k < n; k++)
    for (i = 0; i < n; i++) {
        r = A[i][k];
        for (j = 0; j < n; j++)
            C[i][j] += r*B[k][j];
    }
/* $end mm-kij */
}

void kji(array A, array B, array C, int n)
{
    int i, j, k;
    double r;

/* $begin mm-kji */
for (k = 0; k < n; k++)
    for (j = 0; j < n; j++) {
        r = B[k][j];
        for (i = 0; i < n; i++)
            C[i][j] += A[i][k]*r;
    }
/* $end mm-kji */
}

void jki(array A, array B, array C, int n)
{
    int i, j, k;
    double r;

/* $begin mm-jki */
for (j = 0; j < n; j++)
    for (k = 0; k < n; k++) {
        r = B[k][j];
        for (i = 0; i < n; i++)
            C[i][j] += A[i][k]*r;
    }
/* $end mm-jki */
}

在程序中利用局部性

• 将你的注意力集中在内循环上，大部分计算和内存访问都发生在这里。

• 通过按照数据对象存储在内存中的顺序、以步长为 1的来读数据，从而使得你程序中的空间局部性最大。

• 一旦从存储器中读入了一个数据对象，就尽可能多地使用它，从而使得程序中的时间局部性最大