第五章:存储系统

存储系统的大纲。主要内容是 Cache 的特性及优化。

5.1 存储系统基础

存储系统的层次结构
1. 要求：容量大、速度快、价格低
2. 但是这三个要求相互矛盾
3. 解决办法：采用多种存储器技术，构成多级存储层次
  1. 利用程序的局部性原理：时间局部性&空间局部性
4. 存储系统要达到的目标：整个存储系统的速度接近于最快的访问速度，而容量和单位价格接近于最大的存储器
性能参数
1. 考虑两层存储层次
  | $M_1$ | $S_1$（容量） | $T_1$（访问时间） | $C_1$（每单位价格） |
  | ——- | ——————- | ————————- | —————————- |
  | $M_2$ | $S_2$ | $T_2$ | $C_2$ |
2. 整个存储系统的容量即为第二级存储器的容量，即$S=S_2$。
3. 每单位价格$ C=\frac{C_1S_1+C_2S_2}{S_1+S_2} $。
4. 命中率
  1. $ H=\frac{N_1}{N_1+N_2} $
  2. $ N_1 $：访问$ M_1 $的次数
5. 平均访问时间$ T_A $
  1. $ T_A=HT_1+(1-H)(T_1+T_M)=T_1+(1-H)T_M $
  2. 不命中开销：$ T_M=T_2+T_B $。从向$M_2$发送访问请求到把整个数据块调入$M_1$所需的时间。
  3. 传送信息块的时间：$ T_B $。
三级存储结构
1. 三级存储系统
  1. Cache
  2. 主存储器
  3. 磁盘存储器
2. “Cache-主存”层次和“主存-辅存”层次
  1. 前一个层次弥补速度不足，由硬件实现
  2. 后一个层次弥补容量的不足，主要由软件实现

5.2 Cache基础

基本构造和原理
1. 存储空间分割和地址计算
2. Cache 和主存
  1. Cache 是按照块进行管理的。其被分割为大小相同的块。
  2. 主存块地址：用于查找该块在 Cache 中的位置。
  3. 块内位移：用于确定数据在该块的位置。
  4. 地址串 = 块地址|块内位移
映像规则
1. 全相联
  1. 空间利用率最高、冲突概率最小、实现最复杂
2. 直接映像：每一块只能放在 Cache 的一个位置
  1. 空间利用率低、冲突概率高、实现简单
3. 组相联映像：分组
  1. 低位被称为索引（对应组相联的组数/直接映像的块大小）
  2. 相联度 n
查找算法
1. 确定 Cache 中有需要的块
2. 通过查找目录实现
  1. 目录表：
  2. 并行查找：
    1. 相联存储器：根据查到的组内块地址，从 Cache 中读出一个发送给 CPU
    2. 单体多姿存储器+比较器
容量：$Cache=2^{index}\times 相联度\times 块大小$
过程
1. 写缓冲器：如果在进行写入操作时，写缓冲器不满，则可以把数据及完整地址交给写缓冲器。
2. 读不命中：向 CPU 发送暂停信号，从下一级存储器调入数据块
替换算法
1. 当新调入一块，而 Cache 又已被占满时，替换哪一块？
2. 主要替换算法：随机法；FIFO；LRU
3. LRU 的实现：
  1. 堆栈法：用一个堆栈来记录组相联 Cache 的同一组中各块被访问的先后次序。
    1. 这个方法需要为每一个相联组准备一个小堆栈。
    2. 该方法速度低成本高
  2. 比较对法
    1. 让块两两组合，每一个比较对用一个除法器的状态表示所相关的两个块最近一次被访问的远近次序。
    2. 需要的硬件
      1. 与门，数量等同块数目
      2. 触发器，和两两组合的比较对的数目相同 $=n(n-1) $
    3. 当组内块数较多时，可以使用多级状态位技术减少所需的硬件量。
4. 写策略
  1. 写必须再确认命中之后才可以进行
  2. 写操作可能导致 Cache 和主存内容不一致
  3. 两种写策略：写直达法和写回法
  4. 两种策略的比较：写回法地速度快，使用的存储器的带宽较低；写直达法易于实现、一致性好
  5. 写直达法中，CPU 必须停顿，这个称为“CPU 写停顿”。（可以采用写缓冲器进行优化）
  6. 写操作的调块：写时取，先把所写旦苑所在的块调入 Cache；绕写法，直接写入下一级存储而不调块
5. 性能分析
  1. 不命中率：与硬件速度无关
  2. 平均访存时间：平均访存时间 = 命中时间 + 不命中率 × 不命中开销
  3. 程序执行时间：CPU 时间 = ( CPU 执行时间 + 存储器停顿周期数 ) × 时钟周期时间
    1. 存储器停顿周期数：“读”的次数 × 读不命中率 × 读不命中开销＋“写”的次数 × 写不命中率 × 写不命中开销
    2. 存储器停顿周期数＝访存次数 × 不命中率 × 不命中开销
  4. $CPI_{execution}$越低，固定周期数的 Cache 的不命中开销的相对影响就越大；在计算 CPI 时，不命中开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的 CPU 的不命中开销较大，其 CPI 中存储器停顿这部分也就较大。因此Cache 对于低 CPI、高时钟频率的 CPU 来说更加重要。
6. 改进 Cache 的性能
  1. 平均访存时间 = 命中时间 + 不命中率 × 不命中开销
  2. 从三个方面改进性能：降低不命中率；减少不命中开销；减少 Cache 命中时间

5.3 降低Cache不命中率

提高 Cache 性能的方法是降低不命中率。本节介绍 8 种降低不命中率的方法。需要降低不命中率的方法都会增加命中时间或者不命中开销。因此，使用时需要综合考虑。

三种类型的不命中
1. 强制不命中：第一次访问一个块，其不在 Cache 中。这种不命中称为冷启动不命中或访问不命中。
2. 容量不命中：执行程序所需要的所有块不能同时调入 Cache，在程序运行时需要被重复调用。
3. 冲突不命中：太多块映射到同一组，被重新访问的情况。
4. 相联度越高，冲突不命中就越少；强制不命中和容量不命中与相联度无关；强制性不命中与 Cache 容量大小无关
增加块的大小
1. 增加块的大小：增加了空间局部性，减少了强制不命中；同时减少了 Cache 中块的数目，导致冲突不命中上升；会增加不命中开销
2. 当第二个作用超过第一个作用时，不命中率会上升
增加 Cache 容量：该方法会增加成本，并增加命中时间
提高相联度
1. 8 路相连和全相联一样有效，故超过 8 的方案实际意义不大
2. 2：1 经验规则：容量为 N 的直接映像 Cache 的不命中率和容量为 N/2 的两路相联的 Cache 的不命中率相似

伪相联 Cache

又称为列相联。获得多路相联的低不命中率，又能保持直接映像的命中速度。

1. 先按直接相联的方式进行访问，如果命中则返回
   2. 如果不命中，则会检查另一个块上是否匹配
      3. 如果命中，则发生伪命中
      4. 如果不命中，则访问下一级存储器

如果许多时候，命中发生在伪命中，则速度会变慢。一种简单的方法是，发生伪命中时交换两个块的位置。
这个方法会使 CPU 流水线设计复杂化，因此一般使用在离处理器较远的 Cache 上。

硬件预取
1. 指令和数据都可以在处理器提出访问请求之前预取，可以将其放在 Cache 中或者放在访问速度较快的外部缓冲其中。
2. 指令预取：一般由 Cache 之外的硬件完成。在一次不命中时，取出相邻的两块指令数据。被请求指令返回时放入 Cache，而预取的指令则放入高速缓冲器。下一次 Cache 访问不命中时，则可能可以通过访问高速缓存器获得信息。
3. 预取建立在空闲带宽上。如果它影响了对于正常不命中的处理，则有可能会降低性能。可以利用编译器减少不必要的预取。
编译器控制的预取
1. 它不是通过硬件预取，而是由编译器在程序中降入预取指令来实现的，这些指令在数据被用到之前，就将它们取到寄存器中去。
2. 分为：寄存器预取；Cache 预取。
3. 也可分为：故障性预取，如果出现虚地址故障或者违反保护权限，则会异常；非故障性预取，如果出现故障，则会放弃预取变为空操作
4. 预取不会改变指令和数值之间的逻辑关系。
5. 编译器预取的目的是要在执行指令和读取数据能重叠进行。循环是预取优化的对象。每一次预取需要消耗一次指令的开销。
编译优化
1. 对于软件进行优化降低不命中率。这个方法的特点是不需要对硬件做出改动。
2. 程序代码和数据重组：
  1. 将程序中的过程重新排序，减少冲突不命中；将基本块对齐
  2. 如果编译器知道分支指令很可能转移，则可以
    1. 将转移目标处的基本块和紧跟着该分支指令的基本块进行对调
    2. 把该分支指令换为操作语义相反的分支指令
  3. 同时也可以对数据进行变换，例如调整顺序以改善空间局部性
  4. 编译优化技术包括数组合并、内外循环交换。数组合并是将本来相互独立的多个数组合并为一个复合数组；循环融合是把独立的循环融合为单个的循环
3. 内外循环交换：程序中包含的嵌套循环，并不是按照存储器中存储的顺序进行访问，这时需要交换嵌套关系。
4. 分块：提高时间局部性来减少不命中。在一次循环中既有对行的访问，也有对列的访问
牺牲 Cache：在 Cache 和下一级存储器的数据通路上增设全相联的小 Cache。这个 Cache 存储因为冲突被替换出去的块，当不命中发生时，在访问下一级存储器之前，先检查牺牲 Cache

5.4 降低Cache不命中开销

随着技术的发展，Cache 不命中开销随时间不断增加。

采用两级 Cache
1. 本技术不会印象 CPU
2. 令第一级 Cache 和 CPU 的时钟周期匹配；第二级 Cache 足够大，能够捕捉大部分到达主存的访问
3. 平均访问时间公式：
  $平均访存时间 = 命中时间{L1}+不命中率{L1} \times 不命中开销{L1}$
  $不命中开销{L1} = 命中时间{L2}+不命中率{L2}\times 不命中开销{L2}$
  即，访存时间为$平均访存时间 = 命中时间{L1}+不命中率{L1}\times(命中时间{L2}+不命中率{L2} \times 不命中开销{L2})$
4. $局部不命中率=该级 Cache 的不命中次数/到达该级的访存次数$；$全局不命中率=该级 Cache 不命中次数/CPU 发出的访存次数$
5. 对于第二级 Cache，其命中次数小于第一级 Cache，所以其重点放在减少不命中次数上，导致了更大的容量、更高的相联度和更大的块大小；第二级 Cache 不会影响 CPU 的时钟频率，因此设计有更大的考虑空间。
读不命中优先
1. 对于写直达，每一次访问需要对主存进行写入。为了提高性能，设置一个写缓冲器，但是这个操作会导致储存访问的复杂化，因为所读单元的最新值可能正在写入
2. 最简单方法是推迟对读不命中的处理，直至写缓冲器清空。而这个增加了读不命中的开销。
3. 另一种策略是，检查写缓冲器，如果没有冲突则继续访问
4. 对于写回 Cache 法，也可以利用写缓冲器。读不命中将替换一个修改过的储存块时，将被替换的块临时复制到一个缓冲器中，从存储器调块，再写入存储器
写缓冲合并：对于写缓冲器。在写缓冲器不为空的情况下，需要将这一次写入地址和写缓冲器中地址进行比较，寻找匹配项：如果有地址匹配而对应的位置是空闲的，则将要写入的数据和该项合并。
请求字处理技术
本方法不用增加硬件。从存储器向 CPU 调入一块时，往往只有一个字是立刻需要的。请求字处理技术，就是着眼于这个特性，在 CPU 的请求的字到达后，CPU 不需要等待整个块调入，就将 CPU 重启并继续执行。有两种策略：
1. 尽早重启动：一旦请求字到达，就立刻发送给 CPU，CPU 重启继续执行
2. 请求字优先：调块时先传递 CPU 需要的请求字，让 CPU 继续执行。
  这个方法有效需要块相对大才能生效；以及下一个指令没有访问同一个块。
非阻塞 Cache 技术
Cache 在不命中时仍允许 CPU 进行其他的命中访问，能处理部分的访问，减少了实际不命中开销。

5.5 减少命中时间

直接印象时钟频率的高低。

容量小、结构简单的 Cache：硬件越简单，速度越快；应让 Cache 足够小，以便可以和 CPU 放在同一个芯片上。
虚拟 Cache
采用虚拟存储器的计算机中，每一次访存都必须进行虚实转换，将 CPU 发出的虚地址转换为物理地址，这个一般是由存储部件 MMU 完成的。
物理 Cache：使用物理地址访问的传统 Cache。其标识存储器中存储的是物理地址，地址检测使用的也是物理地址。CPU 需要访问时，先给出一个虚拟地址，由 MMU 转换为主存物理地址，再使用这个物理地址访问 Cache。缺点：地址转换和访问 Cache 是串行进行的，访问速度很慢。
虚拟 Cache：可以直接用虚拟地址进行访问的 Cache，存储器中存储的是虚拟地址，检测的也是虚拟地址。当 CPU 访问存储器时，虚拟地址同时送给 MMU 和 Cache，Cache 找出相应的指令。如果 Cache 不命中，则需要 MMU 读出物理地址进行访问。虚拟 Cache 的优点是命中时不需要地址转换；并且不命中时也是并行的，速度更快。
但并不是所有的计算机都是用虚拟 Cache。其在进行切换时，需要清空 Cache，因为新进程的虚拟地址可能和原进程使用的地址相同。解决这个的方法可以是增加一个 PID，用于标识进程。在 PID 被重用的时候，仍然需要清空 Cache。
虚拟 Cache 没有流行的另一个原因。操作系统可能对一个物理地址有多种虚拟地址访问，这可能会导致虚拟 Cache 存在两个副本。
虚拟索引-物理标识方法
优点：兼得虚拟 Cache 和物理 Cache 的好处。
局限性：直接映像 Cache 的容量不能超过页面的大小。$Cache 容量\le 页大小\times 相联度$
直接用虚地址内的页内位移作为访问 Cache 的索引，但标识是物理索引。CPU 在发出访存请求后，在进行虚实转换的同时，可以进行标识的读取。在完成地址转换以后再比较物理地址和标识。其局限性是为了实现大容量 Cache，又能使索引数比较少，可以采用提高相联度的方法。
Cache 访问流水化：不能减少命中时间，但能增加带宽
追踪 Cache：存放 CPU 执行的动态指令序列

5.6 并行主存系统

主存的性能主要用延迟和带宽衡量。第二级 Cache 很大，对主存带宽有一定要求。并行主存系统就是一个访问周期内能并行访问多个存储字的存储器，其能有效提高存储器的带宽。
对于一个单字宽普通存储器，其字长与 CPU 字长相同，每一次只能访问一个存储字。设其访问周期是$T_M$，字长为$W$，其带宽为：

$B_M=\frac{W}{T_M}$

在相同器件条件下，为提高主存带宽，可以采用并行存储器结构：单体多字存储器和多体交叉存储器

单体多字存储器。
1. 对于一个单体 m 字存储器，该存储器可以在每个存储周期读出 m 个 CPU 字，将其带宽提升为原来的 m 倍。但是由于程序执行访问的数据具有一定的随机性，所以实际带宽比最大带宽小。
2. 优点是实现简单，确定是效率不高：
  1. 如果提出的指令含有分支指令，且分支成功，则有一部分指令是无效的
  2. 当前指令所需要的多个操作数不一定在一个长存储字中
  3. 必须凑齐 m 个数才一起写入存储器。如果只写个别的字，则需要把相应的长存储字取出，放到数据寄存器中，再修改一个字放回存储器
  4. 如果独写数据在一个长存储字内时，读写操作无法在一个存储周期内完成
多体交叉存储器
1. 多体存储器由多个单体存储器构成，每一个体有自己的地址寄存器等电路。
2. 设有 m 个体，每个体有 n 个存储单元。对于计算机使用者来说，存储器是按照顺序线性编址的，如何在二维矩阵和线性地址之间建立对应关系，就是多体存储器编址问题。
3. 有两种编址方法：高位交叉编址和低位交叉编址。低位交叉编址才能解决访问冲突问题。高位交叉编址能方便地扩展常规存储器的容量
  1. 高位交叉编址
    1. 对存储单元矩阵按列优先方式进行编址，即先给第 0 列的各单元按从上到下的顺序依次赋予地址，然后按第一列赋予地址。对于同一个体的高$log_2m$位都是相同的，这就是体号。
    2. 对于第 i 行第 j 列，其地址为$A=j\times n+i$
  2. 低位交叉编址
    1. 先给第 0 行编码，然后从左到右赋予地址
    2. 同一个体的低$log_2m$位是相同的，这是体号
    3. 需要分时启动 m 个存储器。如果每个存储体的访问周期是$T_M$，则各个存储体的启动间隔是$t=T_M/m$。
    4. 采用低位交叉访问能大幅度提高存储器的带宽。由于访问冲突，实际加速比小于 m
    5. $B=\frac{1-(1-\lambda)^m}{\lambda}$，$\lambda$为转移指令成功的概率。当$\lambda=1$时，并行多体交叉的实际带宽同单体单字并没有区别。由于数据的随机性，单纯依靠增大 m 来提高并行的带宽是有限的。对于标量运算，一般取$m\le8$
避免存储体冲突
1. 体冲突：两个访问要求访问同一个存储体。
2. 解决这个问题的方法是采用许多体去减少体冲突的次数。体冲突问题可以通过硬件解决也可以通过软件解决。
3. 软件方法：循环优化法/拓展数组大小，使之不是 2 的幂次
4. 硬件方法：使体数为素数。体内地址为$地址~~mod~~存储体中字数$

5.7 虚拟存储器

基本概念
“主存-辅存”进一步发展的结果。由小主存储器和大的辅助存储器组成，在管理下像一个单一的、可以直接访问的大容量主存存储器。程序员可以使用地址码对整个程序进行编址，不需要考虑实际主存空间的大小。
虚拟存储器可以分为页式和段式。页式存储器把空间划分为大小相同的块，称为页面；段式把空间划分为可变长的块，称为段。此二者各有优劣。许多计算机采用段页式，每段被分为若干个页面。
快速地址转换技术
页表放在主存中，每一次访存会引起两次访问，第一次是访问页表，以获得数据的物理地址；第二次是访问数据。这个效率是不可用的，一般采用翻译后备（TLB）解决这个问题。
TLB是一个专用高速缓存器，用于存放近期经常使用的页表项。TLB 是页表部分内容的一个副本。只有在 TLB 不命中时才会进入主存页表查询。TLB 中的项由两部分组成：标识和数据。标识放的是虚地址的一部分，而数据部分存放的是物理页帧号、有效位、使用位等。操作系统需要保证 TLB 中没有该页表项的副本。