1 / 4概念
Hierarchy and AMAT
存储层次是一条用容量换延迟的阶梯。每一层都比下一层快三到十倍、小一到两个数量级,程序的时间局部性与空间局部性让大多数访问停在上面几层。AMAT 把这条阶梯折成一个可计算的平均值,也把优化方向限定为三条。
1 概念
1.1 一句话定义
存储层次是按容量与延迟排序、由局部性驱动的多级存储结构。AMAT 是平均访存时间,等于命中时间加上未命中率乘以未命中代价。
1.2 它解决什么问题
- 容量与延迟的矛盾:最快的存储器装不下程序,最大的存储器又太慢,只能分层。
- 可计算的平均值:用一个公式比较不同层次配置的收益,而不是凭直觉。
- 优化方向:把改进限定为降命中时间、降未命中率、降未命中代价三条。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 缓存组织、索引与相联度 | hw-cache-organization |
| 替换策略、写回与直写 | hw-replacement-write |
| 未命中分类、预取、分块 | hw-misses-prefetch-blocking |
| 多级之间的包含与互斥 | hw-multilevel-inclusion |
| 页表、TLB 与缺页 | hw-paging-page-tables、hw-tlb |
| CPI 的完整分解 | hw-metrics-cpi |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 命中时间 | 命中时从发起到取回的时间 | 不含未命中的排队 |
| 未命中代价 | 从下一层取回块的全部时间 | 不只是下一层延迟 |
| 未命中率 | 访问中未命中的比例 | 分母是访问次数,不是块数 |
| 局部未命中率 | 本层未命中占本层访问的比例 | 用于逐层连乘 |
| 全局未命中率 | 占最初访问的比例 | 等于各级局部未命中率之积 |
| 工作集 | 一段时间内被反复访问的块集合 | 不是总数据量 |
2 机制
2.1 心智模型
把最常访问的一小部分放在最快的一层,AMAT 就是这条链的加权平均。 一次访问要么在 L1 命中付出几纳秒,要么一路走到 DRAM 付出上百纳秒,平均值取决于未命中的比例。
2.2 机制拆解
- 局部性:时间局部性让刚用过的块值得留下,空间局部性让相邻字节可以一起搬。
- 单级公式:
AMAT = 命中时间 + 未命中率 × 未命中代价。 - 多级递归:
AMAT = t1 + m1 × (t2 + m2 × (t3 + m3 × t_mem)),每层把下一层整体当作自己的未命中代价。 - 全局与局部:局部未命中率逐层相乘得全局未命中率,报告中必须说明用的是哪一个。
- 未命中代价的组成:检测、排队、下一层延迟、块传输时间。高带宽链路上传输时间不可忽略。
- 三条路径:降命中时间(更小更简单)、降未命中率(更大、更相联、预取、分块)、降未命中代价(多级、非阻塞、关键优先)。
- 并发需求:由 Little 定律,跑满带宽所需的在途数据等于带宽乘以延迟。
- 层次的台阶:每层容量约下一层的十分之一到百分之一,延迟约三分之一到十分之一。
2.3 完整枚举
| 层次 | 典型容量 | 典型延迟 | 管理方 | 全局未命中率 | 备注 |
|---|---|---|---|---|---|
| 寄存器 | 约 1 KB | 约 0.3 ns | 编译器 | 接近 0 | 由 ISA 规定 |
| L1 | 32–64 KB | 约 1 ns | 硬件 | 5–10% | 分指令与数据 |
| L2 | 512 KB–2 MB | 约 4 ns | 硬件 | 1–3% | 通常私有 |
| L3 | 8–64 MB | 约 15 ns | 硬件 | 0.2–1% | 常为共享 |
| DRAM | 数十到数百 GB | 约 90 ns | 控制器 | — | 需刷新 |
| SSD | 1–10 TB | 约 100 µs | 设备固件 | — | 队列并行 |
表中只有缓存层给出未命中率,且是全局口径的典型值。主存以下的未命中其实是页错误与 I/O 等待,量级差三个数量级以上,不能与缓存未命中混算。
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| L1 命中时间 | 3–5 个周期 | 先进核约 1 ns |
| L2 命中时间 | 10–20 个周期 | 约 4–7 ns |
| L3 命中时间 | 30–60 个周期 | 约 10–20 ns |
| DRAM 未命中代价 | 200–400 个周期 | 约 80–120 ns |
| 典型 AMAT | 1–4 个周期 | 命中率 95% 以上时 |
| 每层容量与延迟比 | 3–10 倍 | 相邻层之间 |
| 页错误代价 | 数十到数百 µs | 远高于缓存未命中 |
示例:L1 命中 1 ns、未命中率 5%,L2 命中 12 ns、未命中率 2%,DRAM 200 ns,则 AMAT = 1 + 0.05 × (12 + 0.02 × 200) = 1.8 ns。若 L1 未命中率降到 2%,AMAT 降到约 1.3 ns;若 DRAM 延迟翻倍,AMAT 升到约 2.0 ns。在这个区间里,未命中率比未命中代价更敏感。
3 实践
3.1 最小示例
# 两级缓存加主存:AMAT = t1 + m1 * (t2 + m2 * t_mem)
t_l1, m_l1 = 1.0, 0.05 # 1 ns,5% 未命中
t_l2, m_l2 = 12.0, 0.02 # 12 ns,2% 未命中
t_mem = 200.0 # 200 ns
print(f"{t_l1 + m_l1 * (t_l2 + m_l2 * t_mem):.2f}") # 1.80
# 未命中率减到 2%:把 m_l1 换掉,看收益是否值得加容量。
print(f"{t_l1 + 0.02 * (t_l2 + m_l2 * t_mem):.2f}") # 1.32
3.2 常用操作与参数
| 操作 | 命令 | 说明 |
|---|---|---|
| 看层次容量 | lscpu -C、getconf LEVEL1_DCACHE_SIZE | 各级大小与关联度 |
| 测延迟台阶 | lmbench lat_mem_rd | 工作集从小到大扫 |
| 看未命中 | perf stat -e cache-misses,LLC-load-misses | 各级未命中计数 |
| 逐访存延迟 | perf mem record、perf mem report | 按指令归因 |
| 看缺页 | perf stat -e page-faults | 页错误对平均值的污染 |
3.3 标准流程
- 用不同工作集大小扫出延迟曲线,标出每级台阶的断点。
- 用
perf stat取各级未命中率,换算成全局口径。 - 代入 AMAT,判断瓶颈在命中时间、未命中率还是未命中代价。
- 只改一个变量,再扫一次曲线,确认台阶是否抬升或后移。
3.4 与相邻技术的组合
- 缓存组织:相联度与行大小直接改变未命中率。
- 预取:把未命中提前成命中,等价于降低有效未命中率。
- CPI 分解:把 AMAT 折算成每条指令的停顿周期。
3.5 选型维度
| 目标 | 手段 | 典型收益 | 代价 |
|---|---|---|---|
| 降命中时间 | 缩小 L1、降低相联、流水化 | 1–2 个周期 | 未命中率上升 |
| 降未命中率 | 加大容量、提高相联、预取、分块 | 未命中率减半 | 面积、功耗、复杂度 |
| 降未命中代价 | 加一级、非阻塞、关键优先 | 代价降 20%–50% | 面积、验证成本 |
| 提高带宽 | 加通道、HBM | 带宽翻倍 | 成本、封装 |
3.6 决策规则
- 未命中率已低于 1% 时,应优先降命中时间或未命中代价。
- 未命中代价超过 100 个周期时,降未命中率的收益通常更大。
- 带宽已经饱和时,再加缓存不会提高吞吐,应改数据流。
3.7 替代方案对比
| 方案 | 作用点 | 优势 | 代价 |
|---|---|---|---|
| 加缓存容量 | 未命中率 | 通用、无需改代码 | 面积、功耗、延迟 |
| 加预取 | 有效未命中率 | 不改语义 | 污染、带宽浪费 |
| 分块与重排 | 时间局部性 | 软件可控、收益大 | 需改代码 |
| 换介质 | 未命中代价 | 台阶整体下移 | 成本高 |
3.8 何时不该用
- 数据只扫一遍且没有重用时,不要指望缓存层次。
- 不要在尾延迟敏感的在线服务上用平均 AMAT 做容量规划。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 台阶与容量不符 | 虚拟化或缓存被共享 | 查 lstopo 与邻居负载 |
| 延迟曲线无台阶 | 预取掩盖了真实层次 | 关闭预取复测 |
| 平均值正常但尾延迟高 | 少数访问打到 DRAM 或页错误 | 看分位数与 page-faults |
| 加缓存后性能不升 | 瓶颈已转移到带宽 | 测 STREAM |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 只报未命中率不报口径 | 全局与局部混淆 | 明确说明分母 |
| 用平均值代替分布 | 尾延迟被掩盖 | 报 p99 与最大值 |
| 忽略 TLB 与缺页 | 把页错误算进缓存 | 分层归因 |
4.3 可观测信号
lmbench lat_mem_rd 的延迟曲线;perf stat 的 cache-misses 与 LLC-load-misses;perf mem report 的逐指令延迟;perf stat -e page-faults 的缺页次数;numastat 的本地与远程比例;lstopo 的私有与共享关系。
4.4 安全 / 性能 / 一致性边界
- 平均值不是承诺:AMAT 只描述期望,尾延迟由最慢的访问决定。
- 共享会稀释层次:多核共享的 LLC 让每个核的有效容量小于标称容量。
- 侧信道:命中与未命中的时间差可被观测,缓存时序能推断访问模式。