一、存储器与局部性原理

1. 局部性原理

基础概念：

• 时间局部性：一个存储单元被访问后，短时间内可能再次被访问（例如循环变量）。
• 空间局部性：一个存储单元被访问后，其附近单元可能在短时间内被访问（例如数组连续访问）。

通俗理解：

• 时间局部性：程序反复访问同一数据，如循环中的变量 sum。
• 空间局部性：程序访问连续存储的数据，如数组按存储顺序访问。

例题：程序访问局部性分析

• 背景：数组按行优先存储，比较两个求和程序段。
  • 程序段A（行优先访问）：
    • 访问顺序与存储顺序一致，空间局部性优秀，Cache命中率高。
  • 程序段B（列优先访问）：
    • 访问顺序与存储顺序不一致，空间局部性差，Cache命中率低。
  • 变量sum分析：
    • 时间局部性：优秀（每次循环都访问 sum）。
    • 空间局部性：无意义（单个变量不涉及相邻单元）。

---

二、Cache工作原理

类比说明：

• 主存：像超市，存储所有数据，访问慢。
• Cache：像储物柜，存放高频数据，访问快。
• 优势：利用局部性原理预存数据，避免频繁访问主存，提升效率。
• 性能关键：Cache命中率，访问速度：Cache > 主存 > 外存。

1. Cache与主存结构关系

• 结构对应：
  • Cache分为行，每行大小等于主存的一个块。
  • 主存块频繁访问时被复制到Cache行。
• 容量差异：
  • Cache容量远小于主存，仅存储高频数据副本，出于成本和需求考虑。

2. Cache地址结构

• 地址组成：
  • Cache地址：行号（高位） + 块内地址（低位）。
  • 例：16行×16单元的Cache，地址8位（高4位行号，低4位块内地址）。
  • 二进制地址 0010 0001：高4位 0010（行号2），低4位 0001（块内偏移1）。
• 设计思想：
  • n位地址表示2ⁿ种含义。
  • Cache行数2ᶜ → 行号占c位；每行2ᵇ单元 → 块内地址占b位。

3. 主存地址特点

• 地址结构：
  • 主存地址：块号（高位，t位，2ᵗ块） + 块内地址（低位，b位，与Cache一致）。
  • 主存块数2ᵗ >> Cache行数2ᶜ，t > c。
• 地址长度差异：
  • 主存地址比Cache地址长，高位（块号）位数多，块内地址位数相同。
• 映射问题：
  • 主存地址不含Cache行号，需通过映射方式确定Cache位置。

4. 有效位

• 功能：
  • 每个Cache行有有效位，标识该行是否存储有效主存块副本。
  • 初始化：系统启动时有效位为0（无效）。
  • 数据装入：主存块复制到Cache后有效位设为1。
  • 淘汰：有效位置0，实现逻辑删除。
• 特点：
  • Cache行内多个存储单元共享1个有效位。
  • 主存块无有效位，仅为Cache设计。

5. CPU访问Cache流程

• 目的：通过主存地址访问Cache获取数据。
• 命中流程：
  • 主存地址的块在Cache中：
    1. 读取Cache行数据。
    2. 传送至CPU。
    3. 结束访存。
• 缺失流程：
  • 主存地址的块不在Cache中：
    1. 从主存读取整个块。
    2. 寻找Cache空闲行（若无空闲，触发淘汰）。
    3. 复制主存块到Cache。
    4. 传送目标单元数据至CPU。
  • 局部性原理：整块调入利用空间局部性。
• 性能指标：
  • 命中率：命中次数/总访问次数。
  • 访问时间：命中时（T_c：Cache访问+判断），未命中时（T_c + T_m：Cache判断+主存读取）。

6. 平均访问时间（AMAT）

• 公式：
  • AMAT = p * T_c + (1-p) * (T_m + T_c) = T_c + (1-p) * T_m
  • p：命中率，T_c：Cache访问时间，T_m：缺失代价（主存读取+传输）。
• 定义：AMAT = 命中时间 + 缺失率 × 缺失代价。

例题：命中率计算

• 条件：总访存1000次，缺失50次。
• 计算：
  • 命中次数 = 1000 - 50 = 950。
  • 命中率 = 950/1000 = 95%。
• 答案：95%。

---

三、Cache映射方式

1. 直接映射

• 原理：主存块固定映射到特定Cache行。
• 地址划分：
  • 主存地址：tag（t-c位） + Cache行号（c位） + 块内地址（b位）。
  • Cache地址：行号（c位） + **块内地址（b主存地址：tag（t-c位） + Cache行号（c位） + 块内地址（b位）。
  • Cache地址：行号（c位） + 块内地址（b位）。
• 映射方法：
  • 主存块号取模Cache行数，得Cache行号。
  • tag位：主存块号与Cache行号的差（t-c位）。
• 命中判断：
  • 比较主存地址tag与Cache行tag。
  • 检查有效位是否为1。
• 缺失处理：
  • 读取主存块到Cache。
  • 更新tag位和有效位。
  • 数据送回CPU。

例题：地址划分计算

• 条件：主存容量是Cache的4096倍，Cache有64块，直接映射。
• 解题：
  • Cache行数：2⁶ = 64 → 行号6位。
  • 主存块数：64 × 4096 = 2¹⁸ → 块号18位。
  • tag位：18 - 6 = 12位。
  • 映射表大小：(tag位12 + 有效位1) × 64 = 832位。
• 答案：832位。
• 易错点：tag位存在于主存地址和Cache行，需计入有效位。

2. 全相联映射

• 特点：主存块可存入任意Cache行。
• 地址结构：
  • 主存地址：tag（t位，主存块号） + 块内地址（b位）。
  • 无Cache行号，需全行比较。
• tag作用：标识主存块位置。

3. 组相联映射

• 原理：
  • Cache分为组，组间直接映射，组内全相联。
  • 主存块映射到固定组，组内任意行。
• 地址解析：
  • 主存地址：tag + 组号（g位） + 块内地址（b位）。
  • 组数2ᵍ，组内行数（路数）决定关联度。
• 例题：主存地址tag计算
  • 条件：Cache 128KB，每行16B，8路组相联，主存地址1234567H，字节编址。
  • 解题：
    • 总行数：128KB / 16B = 2¹⁷ / 2⁴ = 2¹³。
    • 组数：2¹³ / 8 = 2¹⁰ → 组号10位。
    • 块内地址：16B = 2⁴字节 → 4位。
    • 主存地址：7位16进制 = 28位二进制。
    • tag位：28 - 10 - 4 = 14位。
  • 答案：tag位14位。
  • 易错点：字节编址影响块内地址，路数影响组号位数。

---

四、关联度与比较器

1. 关联度

• 定义：主存块可映射的Cache位置数。
  • 直接映射：关联度1（固定1行）。
  • 全相联：关联度=Cache行数（任意行）。
  • 组相联：关联度=组路数（组内任意行）。

2. 命中率与时间

• 命中率：直接映射最低，全相联最高。
• 命中时间：直接映射最短（1比较），全相联最长（全行比较）。

3. 比较器

• 功能：比较tag位，位数等于tag位数。
• 数量：
  • 直接映射：1个（精确定位）。
  • 全相联：Cache行数个（全行比较）。
  • 组相联：路数个（组内比较）。

---

五、Cache替换算法

1. LRU（最近最少用）

• 原理：替换近期最少使用的块。
• 实现：
  • 每行有LRU计数器，计数值高表示最少使用。
  • 命中：访问行计数器清0，其他低于其值的加1。
  • 未命中有空间：新行计数器置0，其他加1。
  • 未命中无空间：淘汰最大计数行，新行置0，其他加1。
• 计数器位数：⌈log₂(组路数)⌉。

2. 其他算法

• FIFO：淘汰最早装入的块。
• LFU：淘汰引用次数最少的块。
• 随机替换：随机选择。

---

六、Cache一致性

1. 写命中

• 全写法（直写）：
  • 同时更新Cache和主存。
  • 优势：一致性强。
  • 劣势：每次写访问主存，速度慢。
• 回写法：
  • 只更新Cache，替换时写回主存。
  • 控制位：脏位（1位），标记是否修改。
  • 优势：减少主存访问。
  • 劣势：需额外存储脏位。

2. 写不命中

• 写分配法：
  • 更新主存并装入Cache。
  • 常与回写法配合，提高后续命中率。
• 非写分配法：
  • 仅更新主存，不装入Cache。
  • 常与全写法配合，简单但后续可能不命中。

3. 方法搭配

• 回写法+写分配法：效率高，符合Cache设计。
• 回写法+非写分配：效率低，数据不装入Cache。
• 全写法：搭配写分配或非写分配，效率相当，因始终写主存。

---

七、总结

• 局部性原理是Cache设计基础，时间局部性和空间局部性决定数据预存策略。
• Cache工作依赖地址映射（直接、组相联、全相联）、有效位和替换算法（如LRU）。
• 命中率与时间：高关联度提升命中率，但增加比较时间。
• 一致性：全写法保证强一致性，回写法+写分配法效率更高。
• 例题解析：
  • 命中率：95%（950/1000）。
  • 直接映射地址划分：832位（12位tag+1位有效位×64行）。
  • 组相联tag计算：14位（128KB，16B/行，8路）。