存储器层次结构的一般框架

1. 存储器层次结构的共性与差异

1.1. 共性原理

不同类型的存储器层次结构（如Cache的不同级别、虚拟存储器）虽然在量 (Quantitative) 的特征上有显著区别，但其运作的许多策略和特征在本质上是相同的。
目标都是让程序员感觉像在使用单层存储，数据传输自动完成。

1.2. 量化特征差异

块/页的总容量 (Total Capacity of Blocks/Pages)：
- L1 Cache: 16-64 KB
- L2 Cache: 128-2000 KB
- 主存 (for VM): 1,000,000 - 1,000,000,000 KB (1GB - 1TB)
- TLB: 0.25 - 16 KB (按条目数和条目大小估算)
块/页的大小 (Bytes per Block/Page)：
- L1 Cache: 16-64 字节
- L2 Cache: 64-128 字节
- 主存 (Page Size): 4,000 - 64,000 字节 (4KB - 64KB)
- TLB (Entry Size, 1-2 PTEs): 4-32 字节 (假设PTE 4-8字节)
缺失代价 (Miss Penalty in Clock Cycles)：
- L1 Cache: 10-25 周期
- L2 Cache: 100-1000 周期 (若有L3，则L2 Miss Penalty可降至30-40周期)
- 主存 (Page Fault): 10,000,000 - 100,000,000 周期
- TLB: 10-1000 周期 (通常指TLB refill，非Page Fault)
缺失率 (Miss Rate)：
- L1 Cache: 2% - 5%
- L2 Cache (Global Miss Rate): 0.1% - 2%
- 主存 (Page Fault Rate): 0.00001% - 0.0001%
- TLB: 0.01% - 2%
服务器处理器的三级Cache (L3 Cache)： 容量通常为2-8MB，块数比二级Cache多很多，能将二级Cache的缺失代价降低到30-40个时钟周期。
参数变化趋势： 许多值随时间变化，例如Cache容量增大以克服较高的缺失代价时，块大小也随之增长。

2. 存储器层次结构设计的四个基本问题

以下通过四个适用于存储器层次结构任意两层之间的基本问题来研究通用策略，主要使用Cache术语进行解释。

2.1. 问题1: 一个块可以被放在何处？ (Block Placement)

放置策略：
- 直接映射 (Direct Mapped)： 每个主存块只能映射到Cache中的一个固定位置。
  - 组数 = Cache中的块数
  - 每组块数 (相联度) = 1
- 组相联 (Set Associative)： 主存块映射到Cache中的一个特定组，在该组内的任何一个位置都可以存放。
  - 组数 = Cache中的块数 / 相联度
  - 每组块数 (相联度) = N (通常为2-16)
- 全相联 (Fully Associative)： 主存块可以放置在Cache中的任何位置。
  - 组数 = 1
  - 每组块数 (相联度) = Cache中的块数
相联度的影响：
- 好处： 增加相联度通常能降低缺失率，主要通过减少因竞争同一Cache位置而产生的冲突缺失 (Conflict Miss)。
- 效果递减：
  - 从直接映射（1路）到2路组相联，缺失率改进最明显（约20%-30%）。
  - 从2路到4路，改进幅度减小（约1%-10%）。
  - 从4路到8路，改进更小，缺失率接近全相联Cache。
- 容量与相联度关系： Cache容量增加时，相联度提高对性能改进作用减小，因为大容量Cache本身总缺失率较低，改进空间有限。
- 小容量Cache： 从相联度中获益更明显，因其本身缺失率较高。
- 潜在缺点： 增加相联度会增加硬件成本（更多比较器）和访问时间（并行比较和选择逻辑）。

2.2. 问题2: 如何找到一个块？ (Block Identification/Finding)

块的查找方法取决于其放置策略：

放置策略	查找方法	相联度 (Ways)
直接映射	通过地址的索引 (Index) 字段直接定位，比较一个标记 (Tag)。	1
组相联	通过地址的索引 (Index) 字段定位到组 (Set)，然后在组内并行比较所有路的标记 (Tag)。	N (e.g., 2, 4, 8, 16)
全相联	查找所有Cache项，即并行比较所有Cache行的标记 (Tag)（对于Cache）。使用独立的查找表 (Lookup Table)（如虚拟存储器中的页表）。	Cache中的总块数

选择依据： 取决于缺失代价和实现相联度的代价（时间和硬件开销）之间的权衡。
Cache中的应用：
- 片上二级Cache (On-chip L2 Cache): 允许实现更高的相联度，因为命中时间相对不那么关键，且不依赖标准SRAM芯片构建。
- 全相联Cache： 除非容量很小（此时比较器开销不大，且绝对缺失率改进明显），否则不常用。
- 直接映射Cache： 一些系统使用，因其访问时间短（无需比较选择）且实现简单。选择取决于具体实现细节（如是否片上集成、实现技术、Cache访问时间对CPU时钟周期的重要性）。
虚拟存储器中的应用 (页表)：
- 通常采用全相联映射（通过页表实现）。
- 原因：
  1. 缺失代价非常高： 值得用更灵活的放置来降低缺失率。
  2. 允许复杂替换策略： 软件可以实现复杂的替换算法以进一步降低缺失率。
  3. 易于索引： 页表本身就是索引结构，查找不需要额外硬件并行比较，但页表访问本身会引起额外的存储器访问（由TLB缓解）。

2.3. 问题3: 当Cache缺失时替换哪一块？ (Block Replacement)

当Cache发生缺失且需要替换块时（在组相联或全相联Cache中）：

直接映射： 替换策略简单，只有一个候选块。
组相联/全相联： 需要选择一个块进行替换。
- 全相联： 所有块都是候选者。
- 组相联： 在发生缺失的那个组内的所有块中选择。
主要替换策略：
- 随机法 (Random)：
  - 随机选择一个候选块进行替换。
  - 硬件实现简单。
  - MIPS的TLB缺失支持随机替换。
  - 对于2路组相联Cache，随机替换的缺失率通常比LRU高约1.1倍。
- 最近最少使用算法 (Least Recently Used, LRU)：
  - 替换最长时间未被访问过的块。
  - 实现代价： 在相联度较高（如超过4路）时，精确硬件实现LRU的代价很高（需要跟踪所有块的使用顺序）。
  - 近似LRU： 对于4路组相联，通常采用近似实现（如跟踪哪一对块最近最少使用，再跟踪每对中哪一块最近最少使用）。对于更高相联度，也采用近似LRU或随机替换。
Cache中的替换： 由硬件实现，要求算法简单。随着Cache容量增大，不同替换策略的绝对缺失率差异变小。有时，简单的随机替换性能可能优于复杂硬件实现的近似LRU。
虚拟存储器中的替换：
- 通常采用LRU的某种近似算法，由软件（操作系统）实现。
- 因为缺页代价极高，即使微小的缺失率降低也很重要，值得用软件实现更复杂的跟踪。
- 通常提供引用位 (Reference bit) 或类似功能，帮助操作系统追踪最近使用的页。

2.4. 问题4: 写操作如何处理？ (Write Strategy)

处理写操作的两种基本选项：

写直达 (Write-Through)：
- 信息同时写入当前层的块和下一较低层的块中（例如，Cache块和主存块）。
- 优点：
  - 缺失处理相对简单，缺失代价较低，因为不需要将被替换的块写回到较低层。
  - 比写回更易于实现（尽管通常需要写缓冲区 Write Buffer 来隐藏部分写延迟）。
- 通常需要写缓冲区： 隐藏处理器写操作与较慢的下一层存储器之间的速度差异。
写回 (Write-Back)：
- 信息仅仅写入当前层的块中。该块被标记为“脏”（Dirty）。
- 被修改过的（脏）块只有在它被替换时才写回到存储器层次结构的较低层中。
- 优点：
  - 处理器可以以当前层存储器（如Cache）的速度写入单个字。
  - 对同一块中的多次写操作只需要对较低层进行一次写回操作（在替换时）。
  - 当块被写回时，可以利用高带宽传输整块数据，提高效率。
- 虚拟存储器系统： 通常采用写回策略，因为写到磁盘的延迟巨大。
- 现代Cache： 最低一级的Cache（离主存最近的Cache）通常也采用写回策略，因为处理器产生写操作的速度往往超过主存系统的处理能力，即使主存接口带宽较大。

2.5. 四个问题的总结

所有存储器层次结构（Cache, TLB, 虚拟存储器）都基于相同的定位原理，并可以通过对以下4个问题的不同解答来理解其设计： 1. 一个块可以被放在何处？ (放置策略) * 一个位置（直接映射），一些位置（组相联），或任何位置（全相联）。 2. 如何找到一个块？ (查找方法) * 索引（直接映射），有限检索（组相联），全部检索（全相联），或专用查找表（页表）。 3. 当缺失时替换哪一块？ (替换策略) * 通常是最近最少使用的块 (LRU或其近似) 或随机选取的块。 4. 写操作如何处理？ (写策略) * 层次结构中的每一层都可以使用写直达或写回策略。

3. 3C模型：一种理解存储器层次结构行为的直观模型

3.1. 缺失分类 (3C Model)

将所有Cache缺失（也适用于其他层次）归为三种类型：

强制缺失 (Compulsory Miss / Cold-Start Miss)：
- 对一个块第一次访问时发生的缺失，因为该块从未在Cache中出现过。
容量缺失 (Capacity Miss)：
- 由于Cache的容量不足以容纳一个程序执行过程中所需要的所有块而引起的缺失。
- 即使是全相联Cache，如果工作集大于Cache容量，也会发生容量缺失。当某些块被替换出去，随后再被程序访问时发生。
冲突缺失 (Conflict Miss / Collision Miss)：
- 在组相联或直接映射的Cache中，由于多个不同的主存块竞争映射到Cache中的同一个组（或同一个行，对于直接映射）而引起的缺失。
- 这种缺失在同样大小的全相联Cache中不存在（因为全相联Cache没有组内位置冲突）。

3.2. 3C模型与Cache设计参数的关系

冲突缺失：
- 主要受相联度影响。提高相联度可以减少冲突缺失。
- 也受Cache容量影响（容量越大，平均每组的竞争压力可能减小）。
容量缺失：
- 主要受Cache容量影响。增大Cache容量可以减少容量缺失。
强制缺失：
- 主要受块大小 (Block Size) 影响。增加块大小，程序由较少的块组成，首次访问的总块数减少，从而可能减少强制缺失。
- 图中显示强制缺失部分占比很小（0.006%），几乎看不出来。

3.3. 3C模型的应用与局限性

优点： 提供了一个有用的定性模型，帮助理解Cache缺失的原因以及不同设计选择对缺失率的影响。
局限性： 在实际Cache设计中，许多设计选择是相互影响的，改变一个特征通常会影响多个缺失类型的组成部分。例如，增大块大小可能减少强制缺失，但也可能因为每个块占用更多空间而增加容量缺失或冲突缺失的压力（如果总容量不变），同时还会增加缺失代价。
尽管有缺点，3C模型仍是观察Cache设计性能的有效方法。

4. 存储器层次结构设计的挑战

存储器层次结构设计面临的核心挑战在于：任何一个旨在改进缺失率的设计决策，同时也可能对整体性能产生负面影响。

改进措施	正面作用 (通常减少某种缺失)	负面作用 (可能增加其他开销或影响其他方面)
增加Cache容量	减少容量缺失	可能增加命中时间，增加成本和功耗
提高相联度	减少冲突缺失	可能增加命中时间（比较和选择逻辑更复杂），增加硬件成本
增加块大小	减少强制缺失（利用空间局部性）	增加缺失代价（传输更多数据），可能增加冲突/容量缺失（若总容量不变），可能浪费带宽（若空间局部性不好）