重要程度：☆☆☆☆
原文：https://skillful-radius-e2d.notion.site/5-4-cache-0e8f5b1ccff6490493287ee863e306a3
前情提要：
李无厌：存储器层次结构（二）Cache 基础知识 - 结构、读写
一、cache 性能评估
CPU 时间可被分成 CPU 用于执行程序的时间 和 CPU 用来等待访存的时间。
时间执行的时钟周期数等待存储访问的时钟周期数时钟周期
等待存储访间的时钟周期数 = 读操作带来的停顿周期数 + 写操作带来的停顿周期数
之前的例子和等式都假设命中时间不是影响 cache 性能的重要因素，但实际上如果命中时间增加在存储系统中访问一个字所花的时间也在增加。这可能引起处理器时钟周期的增大。
不论命中还是失效访问数据存储的时间都会影响性能。
设计者采用平均存储访问时间 (Average Memory Access Time,AMAT) 作为指标来衡量不同的 cache 设计。
命中时间失效率失效代价
二、采用更灵活的映射策略（Placement of Blocks）
所谓 placement（放置），就是指 cache 块和 memory 地址的映射策略
Tips：直接映射只用对比一个块，组相联要对比多个块，全相联要对比全部块
全相联（fully associative）
放置方式：数据块可以存放在 cache 的任意位置，主存中的某个数据块和 cache 中的任意表项都可能有关联。
查找方式：所有的 entry 都必须进行比对
缺点
每个 cache 表项都有一个比较器可以并行地进行比较。这些比较器显然增加了硬件开销，这使得全相连策略只能用于那些小容量的 cache。
组相联（set associative）：一般性
介于直接映射和全相联之间的组织结构，每一个数据块可以存放在不同位置，但位置数量是固定的。
放置方式
每个数据块有 n 个位置可放的组相联 cache 称为 n 路组相联 cache（n-way set-associative cache）。这 n 个位置（n 个数据块）为一组（set）。
公式：数据块号中的组数
查找方式
由于数据块可以放置在该组内的任意位置，组内所有元素的所有标签都必须被检查。
有 m 个分组，则根据地址中索引的
例：地址为 12 的主存数据块在 cache 中的位置，该 cache 具有 8 个数据块，分别采用直接映射、组相联和全相联策略。
- 在直接映射 cache 中，主存块 12 只对应一个数据块位置，数据块号为 (12 mod8)=4。
- 在两路组相联 cache 中，共有 4 组，主存块 12 对应的组为 (12 mod4)=0; 主存块可以在这个组中的任意位置。
- 在全相联 cache 中，主存块 12 可以放置在任意块中。
可以将所有的 cache 组织结构看作组相联结构的特例，直接映射 cache 就是一路组相联 cache，m 个表项的全相联 cache 则是一个 m 路组相联 cache。
相联度的影响
提高相联度的好处：降低失效率，但问题是可能会增加命中时间
例题结论：从直接映射到两路组相联，失效率减少了大约 15%；但是，随着相联度的增加，失效率几乎没有变化。
tradeoff
任何一个存储层次，在直接映射、组相联或全相联映射结构之间进行选择，都需要在失效代价与相联度实现两方面进行权衡，既需要考虑时间，也需要考虑额外的硬件成本。
- 在直接映射 cache 中，只需要一个比较器，但具有最长的索引字段（耗费时间）；
- 在组相联中，相联度以 2 的幂递增，索引的位长将减少 1, 标签的位长将增加 1，即索引减少（时间减少），但需要的比较器加倍（硬件开销加倍）。
替换数据块策略
LRU(最近最少使用): 通过跟踪某个数据块相对于同组内其他数据块的使用时间来实现, 但当相联度变大时，LRU 的实现将变得困难。
三、多级 cache
二级 cache 一般与一级 cache 封装在同一颗芯片中，一级 cache 失效后就会访问下一级缓存。
侧重点不同
两级 cache 结构允许其一级 cache 关注命中时间最小化以提高工作频率或关注流水级数的减少；同时其二级 cache 关注失效率来降低长访存延迟带来的失效代价。
- 多级 cache 中的一级 cache 通常都较小，并且使用较小的数据块容量，以配合较小的 cache 容量，降低失效代价。
- 相对地，因为二级 cache 的访问时间没有那么关键，二级 cache 会比单个 cache 容量大很多，会使用更大的数据块。由于更关注降低失效率，二级 cache 也会使用比一级 cache 更高的相联度。
四、分块软件优化
Cache Blocking 的思想
分块思想挖掘出程序的时间局部性和空间局部性，比如数组 A 的访问得益于空间局部性，而数组 B 的访问得益于时间局部性。