第五章存储层次

国防科大计算机体系结构课程第五章笔记

5.1 存储器的层次结构

5.1.1 从单级存储器到多级存储器

主存储器与 CPU 速度差距越来越大，存储墙问题严重制约着计算机性能的提升
系统与应用的规模不断扩大，需要更大的存储器来支撑程序的运行
各类存储器的容量/速度/价格不可兼得，如SRAM（已经可以和 CPU 速度持平）、DRAM、磁盘等，凭现有单种存储器件，无法构建一个可行的存储系统
处理器性能与存储系统性能之间存在巨大差距，这叫做存储墙（Memory Wall）
怎么办？
利用多种存储器件，取长补短，构建层次式存储系统
- 快速但昂贵的存储器：容量少点，尽量让 CPU 多访问
- 慢速但容量大的存储器：容量大点， CPU 尽可能少访问

能否达到预期效果？

访问速度方面：采用快速存储器，尽量让 CPU 多访问快速存储器中的内容（增加 Cache 层次）
- 程序局部性原理：
  - 时间局部性：当前访问的数据存放 Cache 中
  - 空间局部性：把与当前访问地址相邻的数据放入 Cache 中（以块为单位从内存调入）
容量方面：采用慢速但容量大的存储器，内存不够时数据可以放到外存中（增加辅存层次）

5.1.2 Cache——主存和主存——辅存层次

这是最主要的两种存储层次
从主存的角度来看
- Cache——主存层次：弥补主存速度的不足
- 主存——辅存层次：弥补主存容量的不足
失效时 CPU 是否切换：Cache——主存层次不切换，主存——辅存层次需要切换到其他进程

5.1.3 存储层次的四个问题

当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上？
- 映象规则：调入块可以放在哪些位置
当所要访问的块在高一层存储器中时，如何找到该块？
- 查找算法：如何在映象规则规定的候选位置查找
当发生失效时，应替换哪一块？
- 替换算法：规定的候选位置均被别的块占用
当进行写访问时，应进行哪些操作？
- 写策略：如何处理写操作

5.1.4 存储层次的性能参数

$C$(平均每位价格), $H$(命中率), $T_A$(平均访问时间)
假设：
- $S$ ——容量
- $T_A$——访问时间
- $C$——每位价格
仅考虑 $M_1 M_2$构成的两级存储层次时：
- $M_1$的参数：$S_1$，$T_{A1}$，$C_1$
- $M_2$的参数：$S_2$，$T_{A2}$，$C_2$
- 每位价格 $C=\cfrac{C_1S_1+C_2S_2}{S_1+S_2}$
- 命中率 $H$ 和失效率 $F$
  - $H=\cfrac{N_1}{N_1+N_2}$
  - $F=1-H$
- 平均访问时间 $T_A$
  - $T_A=T_{A1}+(1-H)T_M ; 或 ; T_A=T_{A1}+F·T_M$
  - $T_M=T_{A2}+T_B$
  - $T_{A1}$——命中时间
  - $T_{A2}$——$M2$ 访问时间
  - $T_M$——失效开销

5.2 Cache 基本知识

5.2.1 映像规则

1. 全相联映象

全相联：主存中的任一块可以被放置到 Cache 中的任意一个位置。
- 对比：阅览室位置──随便坐
- 特点：空间利用率最高，冲突概率最低，实现最复杂。

2. 直接映象

直接映象：主存中的每一块只能被放置到 Cache 中唯一的一个位置。(循环分配)
- 对比：阅览室位置 ── 只有一个位置可以坐
- 特点：空间利用率最低，冲突概率最高，实现最简单。

3. 组相联映像

组相联：主存中的每一块可以放到Cache中唯一的一个组中的任何一个位置
组的选择常采用位选择算法
n 路组相联，每个组中有 n 个块，n 称为相联度，相联度越高，Cache 空间利用率就越高，块冲突概率就越低，失效率也就越低
- 绝大多数计算机的 Cache<=4
- 相联度不是越大越好

5.2.2 查找方法

如何确定 Cache 中是否有所要访问的块？若有的话如何确定其位置？
- Cache 块调入时记录存放的位置到目录表（标识存储器）
  - 表项中只需要放入标识（tag）和有效位即可，因 index 都一样，是冗余信息，所以无需放入表项
- 只需查找候选位置所对应的目录表项
- 并行查找与顺序查找（减少硬件开销）
  - 相联存储器（代价高）
  - 单体多字存储器＋比较器
    - 只有一套访存机制，一次可读多个字
  - ４路组相联 Cache 的查找过程
    - 首先根据给定的物理地址的组号找到对应的表项，再将该组中的 4 个 cache 块的标记读出，分别与物理地址的 tag 标记字段进行比较，若没有匹配，则 Cache 缺失
    - 若有匹配，则从数据存储体中读取该组中所有的数据（四路），然后再通过 4：1 MUX 选择是哪一路命中了数据，再根据块内偏移确定具体的数据送给 CPU
    - 对于比较器的个数，应等于组相联中的相联度（2022年408真题中考察了该知识点）

- 直接映象 Cache 的查找过程
- 先根据 index 选择到对应的 Cache 块，然后将给定的物理地址的 tag 和标识存储体中的标识通过一个标识检查器（比较器）进行比较，若不命中，则 Cache 缺失
- 若命中，直接访问数据存储体，将数据读出送至 CPU

提高性能的重要思想：主候选位置(MRU块)

5.2.3 替换算法

所要解决的问题：当新调入一块，而该块能够占用的 Cache 位置已被占满时，替换哪一块？

随机法
FIFO: 实现简单
LRU（最近最久未使用）：失效率低，但是硬件实现较为复杂
LFU：最不常使用法

5.2.4 写策略

“写”操作所占的比例
- Load 指令：26%
- Store 指令：9%
- “写”在所有访存操作中所占的比例：9%/(100%＋26%＋9%)≈7%
- “写”在访问数据 Cache 操作中所占的比例：9%/(26%+9%)≈25%
“写”操作必须在确认是否命中后才能进行
“写”访问可能导致 Cache 和主存内容不一致
两种写策略
- 写直达法：执行“写”操作时，不仅写入 Cache ，而且也写入下一级存储器
- 写回法：执行“写”操作时，只写入
  Cache，仅当 Cache 中相应的块被替换时，才写回主存（设置“脏位”）
- 两种写策略比较
  - 写回法优点：速度快，占用存储器频带低
  - 写直达法易于实现，一致性好
写缓冲器
- 将数据写入写缓冲器便完成了一次写操作，无需再写入存储器中
- 写缓冲器若满，只能等待
写合并
- 当把数据写入写缓冲器时，判断本次所写入单元的块地址是否与写缓冲器中某个有效块的地址相同，若是，则把新数据与该块合并
写回法——按写分配
写直达法——不按写分配

5.2.3 Cache 结构

DEC 的 Alpha AXP21064 中的内部数据 Cache

简介

容量： 8KB
块大小： 32B
块数： 256
映象方法：直接映象
“写”策略：写直达——不按写分配
写缓冲器大小： 4 个块

混合 Cache 与分离 Cache

优缺点
- 两种 Cache 可以采用不同策略，方便进行读写
分离 Cache 平均失效率的计算：
- 访问指令 Cache 的百分比 × 指令 Cache 的失效率＋访问数据 Cache 的百分比 × 数据 Cache 的失效率

5.2.6 性能分析

平均访问时间
- 平均访问时间＝命中时间＋失效率 × 失效开销
CPU 时间
- CPU 时间＝(CPU 执行周期数＋存储器停顿周期数)×时钟周期时间
- 存储器停顿周期数=访存次数×失效率×失效开销
- CPU 时间＝IC×(CPI~~exe~~＋访存次数/指令数×失效率×失效开销)×时钟周期时间
- CPU 时间＝IC×(CPI~~exe~~ + 每条指令平均存储器停顿周期数)×时钟周期时间
  
  注：$CPI_{exe}$ 表示理想情况下的 CPI

例 5.1 假设 Cache 的命中时间为 1 个时钟周期，失效开销为 50 个时钟周期，在混合 Cache 中一次 load 或 store 操作访问 Cache 的命中时间都要增加一个时钟周期(因为混合 Cache 只有一个端口，无法同时满足两个请求。按照前一章中有关流水线的术语，混合 Cache 会导致结构冲突)，根据表 5-4 所列的失效率，试问：
(1) 指令 Cache 和数据 Cache 容量均为 16KB 的分离 Cache 和容量为 32KB 的混合 Cache 相比，哪种 Cache 的失效率更低？
(2) 又假设采用写直达策略，且有一个写缓冲器
，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？

[解析]
(1) 75% 的访存为取指令，因此分离 Cache 总体失效率为 (75%×0.64%)+(25%×6.47%)=2.10%
根据表 5-4 ，容量为 32KB 的混合 Cache 的失
效率略低一些，只有 1.99%
(2) 平均访存时间公式可以分为指令访问和数据访
问两部分
平均访存时间＝指令所占的百分比 ×(指令命中时间＋指令失效率 × 失效开销) ＋数据所占的百分比 × (数据命中时间＋数据失效率 × 失效开销)
所以，两种结构的平均访存时间分别为
平均访存时间分离＝ 75%×(1＋0.64%×50)＋25%×(1＋6.47%×50)＝(75%×1.32)＋(25%×4.325)＝0.990＋1.059＝2.05
平均访存时间混合＝ 75%×(1＋1.99%×50)＋25%×(1＋1＋1.99%×50)＝(75%×1.995)＋(25%×2.995)＝1.496＋0.749＝2.24

这里混合 Cache 平均访存时间较长的主要原因是，混合 Cache 共用指令 Cache 和数据 Cache，节约了硬件，但是可能会造成结构冲突

[注意] 在访问数据段时候同时也在访问指令，因此要多增加一个时钟周期

例 5.2 我们用一个和 Alpha AXP 类似的机器作为第一个例子。当不考虑存储器停顿时，所有指令的执行时间都是 2.0 个时钟周期。假设 Cache 失效开销为 50 个时钟周期， Cache 的失效率为 2% ，平均每条指令访存 1.33 次。试分析 Cache 对性能的影响。

[分析]
CPU 时间＝IC×(CPI~~exe~~+存储器停顿周期数/指令数)×时钟周期时间
考虑 Cache 失效后，性能为

CPU 时间~~有Cache~~＝IC×(2.0+(1.33×2%×50))×时钟周期时间＝IC×3.33×时钟周期时间
实际 CPI＝3.33，3.33/2.0＝1.67倍
CPU 时间增加了 1.67 倍
若不采用 Cache，则：CPI＝2.0+50×1.33＝68.5
差距显而易见

5.2.7 改进 Cache 性能

平均访存时间＝命中时间＋失效率 × 失效
开销
可以从三个方面改进 Cache 的性能：
(1) 降低失效率
(2) 减少失效开销
(3) 减少 Cache 命中时间
15 种 Cache 优化技术

1. 降低失效率

增加块大小
提高相联度
Victim Cache
伪相联 Cache
硬件预取
编译器控制的预取
用编译器技术减少 Cache 失效

2. 减少失效开销

使读失效优于写
子块放置技术
尽早重启动和关键字优先
非阻塞 Cache
第二级 Cache

3. 减少命中时间

容量小且结构简单的 Cache
对 Cache 索引时，不必进行地址转换
流水化写

值得注意的是，要想提高平均访存时间，不是从单一的某一方面去进行优化，而是要从全局进行考虑，这是体系结构的核心观点。
比如仅仅减少失效开销，不一定会降低平均访存时间，因为降低失开销率可能需要更改整个体系结构，从而带来失效率的增加，最终反而会增加平均访存时间。

5.3 降低 Cache 失效率的方法

5.3.1 三种失效（3C）

1. 强制性失效（Compulsory miss）
当第一次访问一个块时，该块不在 Cache 中，需要从下一级存储器中调入 Cache，这就是强制性失效。
也叫冷启动失效，首次访问失效

2. 容量失效（Capacity miss）
如果程序执行时所需的块不能全部调入 Cache 中，则当某些块被替换后，若又被重新访问，就会发生失效。这种失效成为容量失效。（全相联映射完全是因为容量失效造成的，因为没有替换算法）

3. 冲突失效（Conflict miss）
在组相联或直接映像 Cache 中，若太多的块映像到同一组或同一块中，则会出现该组中某个块被别的块替换（即使其他组有空闲块），然后又被重新访问的情况，这就是冲突失效，也叫碰撞失效或干扰失效。若同一个块不断被换进换出，便产生了颠簸，要尽量避免颠簸造成的系统损耗。

三种失效所占的比例

通过上图可以看出：
(1) 相联度越高，冲突失效就越少；
(2) 强制性失效不受 Cache 容量的影响，但容量失效却随着容量的增加而减少；强制性失效和容
量失效不受相联度的影响（容量失效一般是在全相联映像下测试出来的）
(3) 表中的数据符合 2:1 的 Cache 经验规则，即大小为 N 的直接映象 Cache 的失效率约等于大小为 N/2 的两路组相联 Cache 的失效率

减少三种失效的方法

强制性失效：增加块大小，预取
- 增加块大小后，每个块包含的内容就更多了，程序局部性更好了，需要读取的块就少了，于是便减少了强制性失效的次数
容量失效：增加容量，防止出现颠簸现象
冲突失效：增加相联度，理想情况是全相联

但是许多降低失效率的方法会增加命中时间

5.3.2 增加 Cache 块大小

失效率与块大小的关系

对于给定的 Cache 容量，当块大小增加失效率开始时下降，后来反而上升
Cache 容量越大，失效率达到最低的块大小就越大

那么这是为什么呢？

导致 Cache 失效率先下降后上升的原因在于增加块大小会产生双重作用。
一方面它减少了强制性失效。因为局部性原理有两方面的含义，即时间局部性和空间局部性，增加块大小便利用了程序的局部性。
另一方面由于增加块大小会减少 Cache 中块的数目，所以有可能会增加冲突失效。在 Cache 容量较小时甚至还会增加容量失效。刚开始增加块大小时，由于块大小还不是很大，上述的第一种作用超过第二种作用从而使失效率下降。但等到块大小较大时，第二种作用超过第一种作用使失效率上升。

例 5.4
假定存储系统在延迟 40 个时钟周期后，每 2 个时钟周期能送出 16 个字节。即 : 经过 42 个时钟周期，它可提供 16 个字节；经过 44 个时钟周期，可提供 32 个字节；依此类推。试问：对于表 5-6 中列出的各种容量的 Cache ，在块大小分别为多少时，平均访存时间最小？假设命中时间为一个时钟周期。

5.3.3 提高相联度

采用相联度超过 8 的方法实际意义不大（一般 n 为 4 或 2）
2:1 Cache 经验规则：容量为 N 的直接映象 Cache ≈ 容量为 N/2 的两路组相联
提高相联度是以增加命中时间为代价 Cache

TTL 或 ECL 板级 Cache ，两路组相联：增加 10 ％
定制的 CMOS Cache, 两路组相联：增加 2 ％

例 5.5
假定提高相联度会按下列比例增大处理器时钟周期：
时钟周期2路＝ 1.10 × 时钟周期1路
时钟周期4路＝ 1.12 × 时钟周期1路
时钟周期8路＝ 1.14 × 时钟周期1路
假定命中时间为 1 个时钟，直接映象情况下失效开销为 50 个时钟周期，而且假设不必将失效开销
取整。使用表 5-5 中的失效率，试问当 Cache 为多大时，以下不等式成立？
平均访存时间8路 < 平均访存时间4路
平均访存时间4路 < 平均访存时间2路
平均访存时间2路 < 平均访存时间1路
解：
在各种相联度的情况下，平均访存时间分别为：
平均访存时间8路＝命中时间8路 + 失效率8路 × 失效开销8路＝ 1.14＋失效率8路 × 50
平均访存时间4路 = 1.12 ＋失效率4路 × 50
平均访存时间2路 = 1.10 ＋失效率2路 × 50
平均访存时间1路 = 1.00 ＋失效率1路 × 50

例如， 1KB 的直接映象 Cache 的平均访存时间为：
平均访存时间1路＝ 1.00 ＋ (0.133×50) ＝ 7.65
容量为 128KB 的 8 路组相联 Cache 的平均访存时间为：
平均访存时间8路＝ 1.14 ＋ (0.006×50) ＝ 1.44

提高相联度可以减少失效率，但是总体性能可能下降

5.3.4 Victim Cache

基本思想

在 Cache 和它从下一级存储器调数据的通路之间设置一个全相联的小 Cache ，用于存放被替换出去的块 (称为 Victim)，以备重新使用。
当颠簸发生时，被调出去的块很快就要被重新调入，那么从外存中重新写回到内存很浪费时间，于是就增加了一个小 Cache，减少颠簸对系统性能的影响

作用

对于减小冲突失效很有效，特别是对于小容量的直接映象数据 Cache ，作用尤其明显。例如，项数为 4 的 Victim Cache: 使 4KB Cache 的冲突失效减少 20% ～ 90%
开销大。不仅需要 Cache 所需的一切硬件和布线，并且如果在 Victim Cache 中找到数据，而在数据 Cache 中没有找到，还要进行交换，因为此时 Victim Cache 中的数据局部性更好

5.3.5 伪相联 Cache

取直接映象及组相联两者的优点：命中时间小，失效率低
缺点 :多种命中时间会使 CPU 流水线的设计复杂化，时钟周期要按照较慢的过程执行时间为标准，降低了计算机整体的性能

这里并不是真的是两路组相联，只是每次查找有两次选择，用指针相连，这样就不用经过多路选择器了。

(1) 基本思想及工作原理

在逻辑上把直接映象 Cache 的空间上下平分为两个区。对于任何一次访问，伪相联 Cache 先按直接映象 Cache 的方式去处理。若命中，则其访问过程与直接映象 Cache 的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。

(2) 快速命中与慢速命中

要保证绝大多数命中都是快速命中，将命中概率较高的块交换到主位上

5.3.6 硬件预取技术

指令和数据都可以预取
预取内容既可放入 Cache ，也可放在外缓冲器中，例如：指令流缓冲器
预取效果

(1) Joppi 的研究结果

指令预取： (4KB ，直接映象 Cache, 块大小＝16 字节)
- 1 个块的指令流缓冲器：捕获 15%～25%的失效
- 4 个块的指令流缓冲器：捕获 50%
- 16 个块的指令流缓冲器：捕获 72%
数据预取： (4KB, 直接映象 Cache)
- 1 个数据流缓冲器：捕获 25% 的失效，还可以采用多个数据流缓冲器
  (2) Palacharla 和 Kessler 的研究结果
流缓冲器：既能预取指令又能预取数据
对于两个 64KB 四路组相联 Cache 来说：8 个流缓冲器能捕获 50%～70%的失效

5.3.7 由编译器控制的预取

由编译器加入预取指令，在数据被用到之前发出预取请求。

预取的类型

寄存器预取：把数据取到寄存器中
Cache 预取：只将数据取到 Cache 中
故障性预取：预取时，若出现虚地址故障或违反访问权限，就会发生异常
非故障性预取：预取时，若出现虚地址故障或违反访问权限，并不会导致异常，只是转变为“不预取”

在预取数据的同时，处理器应能继续执行，只有这样，预取才有意义。

非阻塞 Cache (非锁定 Cache)
- Cache 可以接受多个读写请求，当 CPU 在访问 Cache 时，同时还能对 Cache 进行预取

循环是预取优化的主要对象

失效开销小时：循环体展开 1～2 次
失效开销大时：循环体展开许多次

例 5.7 对于下面的程序，判断哪些访问可能会导致数据 Cache 失效。然后，加入预取指令以减少失效。最后，计算所执行的预取指令的条数以及通过预取避免的失效次数。假定：
(1) 我们用的是一个容量为 8KB、块大小为 16B 的直接映象 Cache，它采用写回法并且按写分配。
(2) a、b 分别为 3×100(3 行 100 列)和 101×3 的双精度浮点数组，每个元素都是 8 个字节。当程序开始执行时，这些数据都不在 Cache 内。

1
2
3

for (i = 0; i < 3; i++)
  for (j = 0; j < 100; j++)
    a[i][j] = b[j][0] * b[j + 1][0];

[分析]

首先可以得到数组 a 有 3*100=300 个元素，每个块为 16B，一个元素为 8B，因此一个块能放 2 个元素。所以数组 a 的 300 个元素要失效 300/2=150 次
数组 b 没有空间局部性，因为他是按照列访问的。但是却具有较好的时间局部性：

对于 i 的循环，每次 b 都访问同一个元素
对于 j 的循环，b 的每次访问都会有一个和上一次访问重复的元素
因此数组 b 失效 101 次，如下图

综上，在没有指令预取时，这个循环引起的数据 Cache 失效次数为 150+101=251 次

指令预取

//先展开 i = 0 这一层循环
for (j = 0; j < 100; j++) {
  prefetch(b[j + 7][0]);    //预取7次循环后所需的b(j,0)
  prefetch(a[0][j + 7]);    //预取7次循环后所需的a(0,j)
  a[0][j] = b[j][0] * b[j + 1][0];
}
for (int i = 1; i < 3; i++) {
  for (int j = 0; j < 100; j++) {
    prefetch(a[i][j + 7]);  //预取7次循环后所需的a(i,j)
    a[i][j] = b[j][0] * b[j + 1][0];
  }
}

将 i = 0 展开是为了预取 b 数组，因为 b 数组只用到了第一列。
然后在七次循环之后（七次循环是一个比较合适的次数）预取数组 a 的元素，这样一共失效 12 + 7 = 19 次，远远小于没有指令预取时的 251 次。

例 5.8 在以下条件下，计算例 5.7 中所节约的时间：
(1) 假设预取可以被重叠或与 Cache 失效重叠执行，从而能以最大的存储带宽传送数据。
(2) 不考虑 Cache 失效时，修改前的循环每 7 个时钟周期循环一次。修改后的程序中，第一个预取循环每 9 个时钟周期循环一次，而第二个预取循环每 8 个时钟周期循环一次(包括外层 for 循环的开销) 。
(3) 1 次失效需 100 个时钟周期
[分析]

修改前

循环时间：300 * 7 = 2100
失效开销：251 * 100 = 25100
总时间：2100 + 25100 = 27200

修改后

循环时间：100 * 9 + 200 * 8 = 2500
失效时间：(4 + 7) * 100 + 8 * 100 = 1900（一共失效 19 次）
总时间：2500 + 1900 = 4400
加速比：27200 / 4400 = 6.2

5.3.8 编译器优化

基本思想
在编译时，对程序中的指令和数据进行重新组织，以降低 Cache 失效率
McFaring 发现：通过对指令进行重新排序，可有效地降低指令 Cache 的失效率
数据对存储位置的限制比指令的少，因此更便于优化通过把数据重新组织，使一块数据被从 Cache 替换出去之前，能最大限度利用其中的数据(访问次数最多)

1. 数组合并

//修改前
int val [SIZE];
int key [SIZE];
struct merge {
  int val ;
  int key ;
};
struct merge merged_array[size];

在没有优化之前，val 和 key 单独定义，这样在内存中就不是连续存放，这样空间局部性就差了。优化之后两个数组在内存中实现连续存放，提高了空间局部性。

2. 内外循环交换

//修改前
for (j = 0; j < 100; j++)
  for (i = 0; i < 5000; i++)
    x[i][j] = 2 * x[i][j];
//修改后
for (i = 0; i < 100; i++)
  for (j = 0; j < 5000; j++)
    x[i][j] = 2 * x[i][j];

这个例子不用过多解释了，计组里面计算 Cache 失效率经常用的例子，就是数组按行存放，但是按列读取，增加了 Cache 的失效率

3. 循环融合

//修改前
for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
    a[i][j] = 1 / b[i][j] * c[i][j];
for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
    d[i][j] = a[i][j] + c[i][j];

//修改后
for (i = 0; i < N; i++)
  for (j = 0; j < N; j++) {
    a[i][j] = 1 / b[i][j] * c[i][j];
    d[i][j] = a[i][j] + c[i][j];
  }
}

我们看修改前的两次循环，第一次循环中用到了 a，c 数组，满足了空间局部性，但是第二次循环中仍然用到了 a，c 两个数组，并且都是读取，于是就要把刚刚的循环再来一遍，没有利用好时间局部性，降低了整体效率，也增加了 Cache 失效率。
解决方法就是将两次循环合并起来。

4. 分块

把对数组的整行或整列访问改为按块进行

//修改前
for (i = 0; i < N; i++)
  for (j = 0; j < N; j++) {
    r = 0;
    for (k = 0; k < N; k++) {
      r = r + y[i][k] * z[k][j];
    }
    x[i][j] = r;
  }

失效次数：$2N^3+N^2$

//修改后
for (jj = 0; jj < N; jj += B) 
  for (kk = 0; kk < N; kk += B)
    for (i = 0; i < N; i++)
      for (j = jj; j < min(jj + B - 1, N); j++) {
        r = 0;
        for (k = kk; k < min(kk + B - 1, N); k++) {
          r = r + y[i][k] * z[k][j];
        }
        x[i][j] = r;
      }

失效次数：$(N/B)×(N/B)×N×2B+N^2= 2N^3/B+N^2$

（问号脸？？上面这些略过吧，我觉得现在没人这样写代码了）

5.4 减少 Cache 失效开销

5.4.1 写缓冲及写合并

写直达 Cache 中，因为所有的写请求都必须发送到下级存储层次中，所以经常使用一个写缓冲来降低失效开销
如何提高写缓冲的效率和利用率——写合并
在写回法 Cache 中，也可采用写缓冲器

5.4.2 让读失效优先于写

Cache 中的写缓冲器导致对存储器访问的复杂化
解决问题的方法（读失效的处理）
- 推迟对读失效的处理直到写缓冲排空（缺点：读失效的开销增加）
- 检查写缓冲器的中的内容：增加硬件

5.4.3 子块放置技术

当一个块比较大的时候，可能需要多次访存，如果失效的话，失效开销会很大。如果当失效的时候，将 Cache 块划分成更小的块（子块），并给每个子块赋予一位有效位，用于指明该子块中的数据是否有效
- 但是块变小了，程序局部性可能没有以前好，失效率可能会增加
Cache 与下一级存储器之间以子块为单位传送数据，但标识仍以块为单位

5.4.4 请求字处理技术

请求字

从下一级存储器调入 Cache 的块中，只有一个字是立即需要的，这个字称为请求字
实际上 CPU 请求的数据并不是整个 Cache 块，而是块内的某个字或字节

应尽早把请求字发送给 CPU

尽早重启动：调块时，从块的起始地址开始读，一旦请求字到达，就立即发送给 CPU，让 CPU 继续执行
请求字优先：调块时，从请求字所在的位置读起，这样第一个读出的字便是请求字，将其立即发送个 CPU

这种技术在以下情况下效果不大：

Cache 块较小
下一条指令正好访问同一 Cache 块的另一部分

5.4.5 多级 Cache

应把 Cache 做得更快？还是更大？
- 二者兼顾：再增加一级 Cache：
  - 第一级 Cache(L1)小而快
  - 第二级 Cache(L2)容量大
性能分析
- 平均访问时间=L1命中开销+L1失效率*L1失效开销
- 其中L1失效开销=L2命中时间+L2失效率*L2失效开销
局部失效率和全局失效率
- 局部失效率=该级 Cache 的失效次数/到达该级 Cache 的访问次数，如上述式子中的失效率L2
- 全局失效率=该级 Cache 的失效次数/CPU 发出的访存次数
- 全局失效率为各级 Cache 局部失效率的乘积
- 评价多级 Cache 时，应使用全局失效率这个指标
- 当第二级 Cache 比第一级 Cache 大得多时，两级 Cache 的全局失效率与容量和第二级 Cache 相同的单级 Cache 的失效率非常接近
第二级 Cache 的参数
- 第二级 Cache 不会影响 CPU 的时钟频率，因此其设计有更大的考虑空间
- 两个问题：
  - 能否降低 CPI 中的平均访存时间部分？
  - 成本是多少？
- (1) 容量：第二级 Cache 的容量一般比第一级的大许多，如 512KB
- (2) 相联度：第二级 Cache 可采用较高的相联度或伪相联

例 5.12
给出有关第二级 Cache 的以下数据：
⑴ 对于直接映象，命中时间 L2=10 个时钟周期
⑵ 对于两路组相联，命中时间增加 10%×CPU 时钟周期
⑶ 对于直接映象，局部失效率 L2=25%
⑷ 对于两路组相联，局部失效率 L2=20%
⑸ 失效开销 L2=50 个时钟周期
试问第二级 Cache 的相联度对失效开销的影响如何？

[分析]

对于直接映像的第二级 Cache 来说，第一级 Cache 失效开销为：10 + 25% * 50 = 22.5 个时钟周期
对于两路组相联来说，命中时间增加了 10% 个时钟周期，因此第一级 Cache 失效开销为：10 + 10 * 10% + 20% * 50 = 20.1 个时钟周期，将命中时间取整（10或11），得到失效开销为 20 或 21 个时钟周期
- (3) 块大小：第二级 Cache 可采用大的块，如64、128、256 字节。为减少平均访问时间，可以让容量较小的第一级 Cache 采用较小的块，而让容量较大的第二级 Cache 采用较大的块

5.4.6 非阻塞 Cache 技术

非阻塞 Cache ： Cache 失效时仍允许 CPU 进行其它的命中访问。即允许“失效下命中”
进一步提高性能：多重失效下命中存储器必须能够处理多个失效
重叠失效个数对平均访问时间的影响

5.5 减少命中时间

5.5.1 采用容量小、结构简单的 Cache

命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是 Cache 的访问时间限制了处理器的时钟频率
硬件越简单，速度就越快
应该使 Cache 足够小，以便可以与 CPU 放在同一块芯片上，如果放在 CPU 外面，内部总线的延迟会增加

5.5.2 虚拟 Cache

虚拟 Cache
- 背景：现代计算机几乎都使用虚拟存储技术，程序运行时都是将虚拟地址转化成物理地址再执行
- 检查 Cache 是否命中首先要将虚拟地址转化成物理地址，然后在 Cache 中找到组号，比较 tag，看是否命中
- 虚拟 Cache 希望能够仅通过虚拟地址访问 Cache 索引，其中 Cache 的索引以及 Cache 中的标识都是虚拟地址(一部分)
并非都采用虚拟 Cache 的原因
- 因为许多进程运行时，有大量虚拟地址可能重叠，若当前进程的数据按照虚拟地址写入虚拟 Cache，当下一个进程运行时，要清空虚拟 Cache，否则取到的就是上一个进程的数据，而清空虚拟 Cache 很耗时
虚拟 Cache 的清空问题
- 解决办法：在地址标识字段中增加 PID 字段（进程 ID）
- PIDs 与单进程相比：时间开销增加 0.3%~0.6%
- PIDs 与清空相比：时间开销减少 0.6%~4.3%
同义/别名问题
- 多个虚拟地址对应同一个物理地址
  - 若两个进程共享同一块物理地址，两个程序中对应的虚拟地址是不同的
- 解决方法：反别名法，页着色
- 具体略
虚拟索引+物理标识
- 利用虚拟地址找到索引读 Cache，同时进行虚实地址转换：前提是虚拟索引=物理索引
- 而页内位移在虚实地址变换时不变，可以将索引 index 放在页内偏移中
- 优点：兼得虚拟 Cache 和物理 Cache 的好处
- 局限性：Cache 容量受限于页大小*相联度
- 举例：IBM3033 的 Cache，页大小＝ 4KB，相联度＝16
另一种方法：硬件散列变换（不展开）

5.5.3 写操作流水化

设置延迟写缓冲器

5.5.4 Cache优化技术总结

[注]：+ 表示对某方面产生有利影响，- 表示不利影响

5.6 主存

存储层次的性价比特征
- 速度越快，每位价格就越高
- 容量越大，每位价格就越低
- 容量越大，速度越慢
寄存器访问（M1），Cache访问（M2），存储器访问（M3），磁盘存储器访问（M4）

名称	寄存器	Cache	主存	磁盘
典型大小	<1KB	<16MB	<512G	>1TB
实现技术	定制多端口存储器，CMOS	片上或片外CMOS SRAM	CMOS DRAM	磁介质盘
访问时间（ns）	0.25-0.5	0.5-25	50-250	5,000,000
带宽（MB/s）	50,000-500,000	5000-20,000	2500-10,000	50-500
管理	编译器	硬件	操作系统	操作系统和用户
后备	Cache	主存	磁盘	CD或磁带

主存的主要性能指标：延迟和带宽

以往：Cache 主要关心延迟，I/O 主要关心带宽
现在：Cache 关心两者

本节讨论几种提高主存性能的存储器组织技术在下面的讨论中，以处理 Cache 失效为开销例来说明各种存储器组织结构的好处。

为了减少失效开销 $T_M$，应该：
- 减少主存延迟
- 提高主存带宽
增加 Cache 块大小能利用主存带宽增加所来的好处
==假设基本存储器结构性能为：==
- 送地址需要 4 个时钟周期
- 每个字的访问时间为 24 个时钟周期
- 传送一个字的数据需要 4 个时钟周期
- 如果 Cache 大小为 4 个字，则：失效开销为4*(4+24+4)=128 时钟周期
- 带宽 = 16 / 128 = 0.0125(字节/时钟周期)

5.6.1 存储器组织技术

1. 增加存储器的宽度

性能分析（按照之前的假设）
- 当宽度为 4 个字时，失效开销为 1 * 32 = 32 时钟周期，带宽 = 0.5 (字节/时钟周期)
缺点
- 增加 CPU 和存储器之间的连接通路宽度
- CPU 和 Cache 之间有一个多路选择器，增加了硬件开销，使得在关键路径上的时间开销增加
- 扩充主存的最小增量增加了相应的倍数
- 写入有可能变得复杂
- 实例： DEC 的 Alpha Axp21064 ：256 位宽

2. 采用简单的多体交叉存储器

在多体交叉存储器中，存储系统采用多个 DRAM，利用他们潜在的并行性，他们可以同时工作，但是向 Cache 传送数据的通路不变，是比较窄的，只有一个送地址部件

高位交叉与低位交叉编址

低位交叉编址

能够很好的利用其并行性

高位交叉编址

无法利用其并行性

那么如何充分发挥多体交叉的并行性呢？

1. 同时启动

前提：要取的存储体内的字必须是同一个偏移地址

2. 分时启动

性能分析（参照之前的假设）
- 失效开销 = 4 + 24 + 4 * 4 = 44 时钟周期（低位交叉编址 4 个字可同时取出，但是写进 Cache 还是要按字节写入，因为存储体和 Cache 之间的总线宽度仍然是一个字）
- 带宽 = 0.4 （字节/时钟周期）
存储器的各个体一般是按照字交叉，低位字交叉存储器非常适合处理 Cache 读失效，写回法 Cache 中的写回

例 5.14
假设某台机器的特性及其 Cache 的性能为：
· 块大小为 1 个字
· 存储器总线宽度为 1 个字（32 位）
· Cache 失效率为 3 %
· 平均每条指令访存 1.2 次
· Cache 失效开销为 32 个时钟周期 (和上面相同)
· 平均 CPI(忽略 Cache 失效) 为 2
试问多体交叉和增加存储器宽度对提高性能各有何作用？

如果当把 Cache 块大小变为 2 个字时，失效率降为 2%；块大小变为 4 个字时，失效率降为 1%。根据 5.6.2 小节中给出的访问时间，求在采用 2 路、4 路多体交叉存取以及将存储器和总线宽度增加一倍时，性能分别提高多少？

[分析]

在改变前的机器中，Cache 块大小为一个字，其 CPI 为：2 + (1.2 * 3% * 32) = 3.15
将块大小增加为 2 个字时，在下面三种情况下的 CPI 分别为
- 32 位总线和存储器，不采用多体交叉 CPI = 2 + (1.2 * 2% * 2 * 32) = 3.54 （公式里的 *2 是因为 32 位总线和存储器传送 2 个字失效时需要传送两次）
- 32 位总线和存储器，采用多体交叉 CPI = 2 + (1.2 * 2% * (4 + 24 + 8)) = 2.86（多体交叉传送地址需要 4 个周期，数据取出来要 24 个周期，总线宽度只有一个字，传送一个字要 4 个时钟周期，传送两个字则是 8 个时钟周期） 性能提高了 10%
- 64 位总线和存储器，不采用多体交叉 CPI = 2 + (1.2 * 2% * 1 * (4 + 24 + 4)) = 2.77（64 字节为两个字，读一次即可，故失效开销为 32 个时钟周期）性能提高了14%
如果将块大小增加到 4 个字，则：
- 32 位总线和存储器，不采用多体交叉 CPI = 2 + (1.2 * 1% * 4 * 32) = 3.54 （传送四次）
- 32 位总线和存储器，采用多体交叉 CPI = 2 + (1.2 * 1% * (4 + 24 + 16)) = 2.53（多体交叉传送地址需要 4 个周期，数据取出来要 24 个周期，总线宽度只有一个字，传送一个字要 4 个时钟周期，传送四个字则是 16 个时钟周期） 性能提高了 25%
- 64 位总线和存储器，不采用多体交叉 CPI = 2 + (1.2 * 1% * 2 * (4 + 24 + 4)) = 2.77（64 字节为两个字，读两次，每次失效开销为 32 个时钟周期）性能提高了14%

在采用简单的多体交叉存储器时，体的数目 ≥ 访问体中一个字所需的时钟周期

3. 独立存储体

设置多个存储控制器，使多个体能独立操作，以便能同时进行多个独立的访存

每个体有独立的地址线
非阻塞 Cache 与多体结构
- Cache 失效时仍允许 CPU 进行其它的访存。这样的设计对于独立多体结构才有意义
- IO 访存
体和超体

5.6.2 存储器芯片技术

1. DRAM 与 SRAM

容量： 4～8:1
存储周期： 8～16:1
价格： 1：8～16
一般来说：主存一般是DRAM，Cache一般是SRAM
Amdahl 经验规则：
- 为了保持系统平衡，存储容量应随 CPU 速度的提高而线性增加。（每 3 年增加 4 倍）
各代 DRAM 的典型参数
- DIMM(dual inline memory modules)
  - 多个 DRAM 芯片经常被组装在称为条的小型板上，构成“双列直插式存储模块”。
  - 一个 DIMM 通常包含 4~16 片 DRAM 芯片，这些芯片常被组织成 8 字节宽的主存(带 ECC 校验)

2. DRAM 芯片优化技术

芯片内部优化技术是提高主存系统性能的一个重要方面
快页模式：内部缓冲一行的数据以便进行列访问
SDRAM : Synchronous DRAM，DRAM 接口增加一个时钟信号可使 DRAM 能针对一个请求连续同步地传输多个数据而不需同步开销
DDR(Double Data Rate，双数据率)：在 DRAM 时钟的上沿和下沿都进行数据传输，可把数据传输率提高一倍。
现代 DRAM 的名称和性能

总结：

DDR 技术规定的标准电压为 2.5V ， DDR2 技术的电压将为 1.8V ，工作频率范围为 266MHz~400MHz，DDR3 的电压将为 1.5V，最大工作频率为 800MHz
存储器优化技术都是通过增加少量逻辑来开发 DRAM 内部潜在的高带宽，这种优化代价很小，却能使带宽显著提高

5.7 虚拟存储器

……系统被设计成将主存储器和后备存储器组合在一起，在程序员看来好像只有一级存储，必须进行的地址变换是自动完成的。
——Kilburn et al.(1962)

5.7.1 虚拟存储器基本原理

虚存系统：

由价格较贵、速度较快、容量较小的主存储器 M1 和一个价格低廉、速度较慢、容量很大的辅助存储器 M2(通常是硬盘)组成
在系统软件和辅助硬件的管理下，就象一个单一的、可直接访问的大容量主存储器
程序员可以用机器指令的地址码对整个程序统一编址，就如同应用程序员具有对应于这个地址码宽度的存储空间(称为程序空间)一样，而不必考虑实际主存空间的大小

1. 虚拟存储器的特点

程序员可以利用巨大的逻辑空间，而不必做存储管理工作
多个进程可以共享主存空间
采用动态重定位，简化了程序的装入

2. 虚存管理方式

分两类：页式和段式

页式虚存把空间划分为大小相同的块，称为页
面。常用页大小为 4KB～64KB。
段式虚存把空间划分为可变长的块，称为段。
段最小长度为 1 个字节，最大因机器而异，常为 $2^{16}B～2^{32}B$。
页面是对空间的机械划分，而段则往往是按程序的逻辑意义进行划分

采用页式虚存还是段式虚存对 CPU 有不同的影响

页式虚存：地址是单一、固定长度的地址字，由页号和页内位移两部分组成
段式虚存：地址需要用两个字表示，一个为段号，另一个为段内位移。因为段的长度是可变的
段页式：每段被划分成若干个页面。既保持了段作为逻辑单位的优点，又简化了替换的实现，而且段不必作为整体全部一次调入主存，而是可以以页面为单位部分调入

3. 存储层次中 Cache 和虚存的对比

虚存处于“主存—辅存”层次
与“ cache——主存”层次的相似点
- 都是分块方式： Cache 块、页、段
- 都有失效问题： Cache 块失效、页故障、地址故障
与“cache——主存”层次的不同点
- 失效替换：Cache 由硬件完成，虚存主要由 OS
- 处理器地址大小决定虚存大小，但与 Cache 大小无关
- 辅存除用做主存的后备存储器外，还用于文件系统

4. 存储层次中 Cache 和虚存的典型指标

5. 有关虚拟存储器的四个问题

映像规则
- 全相联。以降低失效率为主要目标，不在关键路径上，因此降低命中时间没那么重要了
查找算法
- 页表，段表，TLB
- 页表和段表：索引页号或段号的数据结构，含有所要查找的块的物理地址。
- 段式系统：段内位移加上段的物理地址就是最终的物理地址。
- 页式系统：只需简单地将页内位移拼接在相应页面的物理地址之后
替换算法
- LRU。尽可能减少页故障，OS 为每个页面设置“使用位”
写策略
- 写回法

（具体例子和相关图片就不放了，计组和 OS 里面重点中的重点）

5.7.2 快表 TLB

TLB （ Table Look-aside buffer ）

TLB 是一个专用的高速缓冲器，用于存放近期经常使用的页表项
TLB 中的内容是页表部分内容的一个副本
TLB 也利用了局部性原理

Alpha Axp 21064 的地址转换过程
TLB 一般比 Cache 的标识存储器更小、更快

5.8 进程保护和虚存实例

进程：程序呼吸所需的空气和生存的空间

5.8.1 进程保护

1. 界地址寄存器
基地址，上界地址
检测条件：（基地址 + 地址）≤上界地址
2. 虚拟存储器
给每个页面增加访问权限标识
3. 环形保护
4. 加锁和解锁

5.8.2 页式虚存举例

Alpha Axp 的存储管理和 21064 的 TLB
Alpha Axp 体系结构采用段页相结合的方式

1. Alpha 的地址空间分为 3 段
kseg(地址最高两位：10) (内核)
sego(最高位：0) (用户)
seg1(最高两位：11) (用户)

2. Alpha 采用三级页表

3. Alpha 的页表项
（PTE，8 字节）

4. Alpha Axp21064 TLB 的参数

块大小：1 PTE（8字节）
命中时间：1 个时钟周期
平均失效开销：20 个时钟周期
TLB 容量
- 指令 TLB：8 个 PTE 用于大小为 8K 字节的页，4 个 PTE 用于大小为 4MB 的页（共 96 字节）
- 数据 TLB：32 个 PTE 用于大小为 8KB ，512KB 和 4MB 的页（共 256 字节）
块替换策略：随机
写策略：不适用
块映像策略：全相联

第五章 存储层次

5.1 存储器的层次结构

5.1.1 从单级存储器到多级存储器

5.1.2 Cache——主存和主存——辅存层次

5.1.3 存储层次的四个问题

5.1.4 存储层次的性能参数

5.2 Cache 基本知识

5.2.1 映像规则

1. 全相联映象

2. 直接映象

3. 组相联映像

5.2.2 查找方法

5.2.3 替换算法

5.2.4 写策略

5.2.3 Cache 结构

5.2.6 性能分析

5.2.7 改进 Cache 性能

1. 降低失效率

2. 减少失效开销

3. 减少命中时间

5.3 降低 Cache 失效率的方法

5.3.1 三种失效（3C）

减少三种失效的方法

5.3.2 增加 Cache 块大小

5.3.3 提高相联度

5.3.4 Victim Cache

5.3.5 伪相联 Cache

5.3.6 硬件预取技术

5.3.7 由编译器控制的预取

5.3.8 编译器优化

1. 数组合并

2. 内外循环交换

3. 循环融合

4. 分块

5.4 减少 Cache 失效开销

5.4.1 写缓冲及写合并

5.4.2 让读失效优先于写

5.4.3 子块放置技术

5.4.4 请求字处理技术

5.4.5 多级 Cache

5.4.6 非阻塞 Cache 技术

5.5 减少命中时间

5.5.1 采用容量小、结构简单的 Cache

5.5.2 虚拟 Cache

5.5.3 写操作流水化

5.5.4 Cache优化技术总结

5.6 主存

5.6.1 存储器组织技术

1. 增加存储器的宽度

2. 采用简单的多体交叉存储器

3. 独立存储体

5.6.2 存储器芯片技术

1. DRAM 与 SRAM

2. DRAM 芯片优化技术

5.7 虚拟存储器

5.7.1 虚拟存储器基本原理

1. 虚拟存储器的特点

2. 虚存管理方式

3. 存储层次中 Cache 和虚存的对比

4. 存储层次中 Cache 和虚存的典型指标

5. 有关虚拟存储器的四个问题

5.7.2 快表 TLB

5.8 进程保护和虚存实例

5.8.1 进程保护

5.8.2 页式虚存举例

第五章存储层次