26-计组-存储器与Cache机制

发布于：2025-07-04 ⋅ 阅读:(19) ⋅ 点赞:(0)

一、存储器与局部性原理

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路）。