Lecture 9: 存储层次结构 (The Memory Hierarchy)
Lecture 9: 存储层次结构 (The Memory Hierarchy)
讲义对应：CMU 15-213 Lecture 9 — The Memory Hierarchy（素材：
F25-09-memory-hierarchy.txt） 教材对应：CS:APP3e 第 6 章 6.1–6.3（6.1.1 存储器抽象、6.1.2–6.1.4 存储技术与趋势、6.2 局部性、6.3 存储层次） 关联 Lab：L4 Cache Lab（Part A 缓存模拟器csim；Part B 矩阵转置优化）
9.1 概述
前八讲讨论”计算”，但计算需要数据，而数据存放在”存储器（memory）”里。本讲回答：存储器的速度永远追不上 CPU，计算机为什么还能跑得这么快？
答案由三个事实拼成：快的存储器又小又贵又费电；CPU 与主存的速度差距持续拉大（内存墙，memory wall）；写得好的程序天然具有局部性（locality）。三者咬合，催生了存储层次结构（memory hierarchy）——用便宜的慢速设备海量堆积，却以接近顶级速度交付数据。本讲为第 10 讲与 L4 Cache Lab 打地基。
9.2 核心概念与底层机制图解
9.2.1 存储器抽象与总线事务（Memory Abstraction & Bus Transaction）
存储器就是巨大的字节数组，用地址索引：movq A, %rax 读、movq %rax, A 写。总线像共享传送带，CPU 与主存在两端，地址、数据、控制信号同时跑，故任一时刻只容一个”包裹”。
CPU 芯片 (CPU chip)
+-------------------------------------+
| 寄存器文件 <----> ALU |
| (Register file) |
+-------------------------------------+
^
| 内存总线 (memory bus)：地址线 + 数据线 + 控制线
v
+------------------+ +-------------------+
| 内存控制器 | <----> | 主存 (DRAM) |
| (Memory Controller)| | 0 ... A ... x |
+------------------+ +-------------------+
读事务三步：地址 $A$ 上总线 → 主存取字 $x$ 放回总线 → CPU 写入 %rax，写事务反向。每次访存占用总线若干周期，这就是”访问时间”的物理来源。
9.2.2 随机访问存储器：SRAM 与 DRAM（Random-Access Memory）
RAM 封装为芯片，基本单元是单元（cell），每 cell 一位；分 SRAM（静态）与 DRAM（动态）。SRAM 像带自锁开关的灯——通电即稳定保持，代价是每 bit 要 6 晶体管；DRAM 像漏水的桶——以水量表示 0/1，须周期重灌（刷新，refresh），好处是每 bit 仅需 1 晶体管 + 1 电容。
16 x 8 DRAM 芯片：d=16 个超单元(supercell)，每个 w=8 位
列 cols
0 1 2 3
+----+----+----+----+
行 0 | | | | |
+----+----+----+----+
rows1 | | | | |
+----+----+----+----+
2 | | |####| | <== 目标超单元 (2,1)
+----+----+----+----+
3 | | | | |
+----+----+----+----+
^
| 内部行缓冲 (internal row buffer)
addr ----> | 步骤1: RAS=2 选中第 2 行 -> 整行搬进行缓冲
data <---- | 步骤2: CAS=1 选中第 1 列 -> 超单元送到数据线
| 步骤3: 整行写回数组，顺带完成一次刷新
movq A, %rax 被翻译成 RAS/CAS 时序；整行搬入行缓冲就是 DRAM 的空间局部性红利——同一行后续访问无需重发 RAS（行命中）。
| 每 bit 晶体管数 | 访问时间 | 需刷新？ | 需 EDC？ | 相对成本 | 典型用途 | |
|---|---|---|---|---|---|---|
| SRAM | 6 或 8 | $1\times$ | 否 | 也许 | 约 $100\times$ | 缓存（cache memories） |
| DRAM | 1 | $10\times$ | 是 | 是 | $1\times$ | 主存、帧缓冲（frame buffers） |
（EDC = 错误检测与纠正。）SRAM 随工艺缩放已近极限；DRAM 缩放受最小电容与深宽比限制，同样近极限。
9.2.3 非易失性存储器（Nonvolatile Memories）
DRAM/SRAM 易失（volatile），断电即失；非易失存储器断电仍保留数据。谱系：ROM（生产时写入）→ PROM（可编程一次）→ EPROM（紫外线擦除；讲义此处直接跳到 EEPROM，二者同属一谱系）→ EEPROM（电可擦除）→ 闪存（flash）：一种 EEPROM，支持块级（block-level）部分擦除，擦写约 10 万次后磨损；另有 3D XPoint（Intel Optane）等新兴 NVM。用于固件（BIOS、磁盘/网卡控制器）、SSD 与磁盘缓存。闪存像一本只能”整页撕掉”才能改的笔记本。
9.2.4 磁盘存储：几何结构（Disk Geometry）
磁盘以磁性介质存储、机电方式访问；直观像老式唱机——盘片转，唱臂径向找”音轨”。
磁盘驱动器内部 (What's inside a disk drive?)
+-----------------------------------------------------------+
| 主轴 (Spindle) +-------------------------------+ |
| | | 盘片 (Platter) 上表面/下表面 | |
| +---------->| ~~~~ 磁道 (track) ~~~~ |<--+ |
| | +--+--+--+ 扇区(sector) 间隙 | |读写头|
| +-------------------------------+ |(R/W |
| 传动臂 (Arm) + 驱动器 (Actuator) -------------------+ head)|
| 电子线路 (Electronics: 内含处理器与内存!) SCSI 接口 |
+-----------------------------------------------------------+
单个盘面的几何 (single-platter view)
磁道 k (Track k) 扇区 (Sectors) 由间隙 (Gaps) 分隔
+-----------------------------------------+
| ___----___ <== 最外圈磁道 |
| / ___--_ \ |
| | / \ | ~~~~~ 同心圆 = 磁道 |
| | | o | | o = 主轴 |
| | \______/ | |
| \ / |
| ---____--- |
+-----------------------------------------+
容量公式：
\[\text{Capacity} = \frac{\#\text{bytes}}{\text{sector}} \times \frac{\#\text{avg sectors}}{\text{track}} \times \frac{\#\text{tracks}}{\text{surface}} \times \frac{\#\text{surfaces}}{\text{platter}} \times \frac{\#\text{platters}}{\text{disk}}\]技术因子：记录密度（bits/in）× 磁道密度（tracks/in）= 面密度（areal density, bits/in²）；厂商按 $1\ \text{GB}=10^9$、$1\ \text{TB}=10^{12}$ 字节标称。多盘片视图下读写头同步移动（move in unison），同时刻停在所有盘面的同一柱面（cylinder）上——这就是磁盘调度优先读完整个柱面的原因。
9.2.5 磁盘访问时间（Disk Access Time）
\[T_{\text{access}} = T_{\text{avg seek}} + T_{\text{avg rotation}} + T_{\text{avg transfer}}\]- 寻道（seek time）：读写头移到目标柱面，典型 3–9 ms。
- 旋转延迟（rotational latency）：等目标扇区首位转到读写头下。最坏转满一圈 $T_{\max}=\frac{1}{\text{RPM}}\times\frac{60\ \text{sec}}{1\ \text{min}}$，平均是一半：$T_{\text{avg rotation}}=\frac{1}{2}\times\frac{1}{\text{RPM}}\times\frac{60\ \text{sec}}{1\ \text{min}}$。
- 传送（transfer time）：$T_{\text{avg transfer}}=\frac{1}{\text{RPM}}\times\frac{1}{\text{avg \# sectors/track}}\times\frac{60\ \text{sec}}{1\ \text{min}}$（转一圈时长 × 目标段占整圈比例）。
- 完整数值计算（讲义原例）：7200 RPM、平均寻道 9 ms、平均每道 400 扇区：
三点结论：① 访问时间被寻道与旋转延迟主导，传送可忽略；② 扇区第一位最贵，其余位几乎免费——”按块传输”的合理性来源；③ SRAM 约 4 ns/doubleword、DRAM 约 60 ns，磁盘比 SRAM 慢约 4 万倍、比 DRAM 慢约 2500 倍（教材口径；若直接拿 13.02 ms 除以 4 ns 会得约 $3.3\times10^6$，以”量级差 3–6 个数量级”为准）。
9.2.6 逻辑块、磁盘控制器与 DMA
操作系统把磁盘视作逻辑块（logical block）序列，由磁盘控制器（disk controller）做地址翻译与坏块重映射：
CPU 芯片 I/O 总线
+----------------+ +------------------------------+
| 寄存器 | ALU | | 磁盘控制器 图形适配器 USB |
+----------------+ +------------------------------+
| (系统总线 / 内存总线) | |
v v v
+----------+ +---------+ +----------+
| 主存 |<---- DMA ----------| 磁盘 | | 鼠标键盘 |
+----------+ +---------+ +----------+
(1) CPU 写端口: 命令 + 逻辑块号 + 目标内存地址
(2) 磁盘控制器读扇区, 用 DMA 直接搬进主存
(3) DMA 完成, 控制器用中断(interrupt)通知 CPU
第 (3) 步的中断正是 Lecture 17”异常控制流”的主题；磁盘 I/O 天生异步，这是后续 shell、proxy、SFS 等 lab 并发模型的根源。
9.2.7 固态硬盘（Solid State Disks, SSD）
SSD 基于闪存，对外提供”逻辑磁盘块”接口，由闪存翻译层（flash translation layer, FTL）把逻辑块映射到物理页：
Solid State Disk (SSD)
+--------------------------------------------------------+
| I/O 总线 <-> 闪存翻译层 (FTL) <-> DRAM 缓冲(Buffer) |
+--------------------------------------------------------+
| | |
+--------+ +--------+ +--------+
| Block 0| ... | Block i| ... |Block B-1|
| Page0 | | Page0 | | Page0 |
| Page1 | | Page1 | | Page1 |
| ... | | ... | | ... |
|Page P-1| |Page P-1| |Page P-1|
+--------+ +--------+ +--------+
页(Page): 512 B ~ 4 KB 块(Block): 32 ~ 128 页
读/写以页为单位; 但一个页只有在所在块被整体擦除后才能写入
- 读写不对称与写放大（write amplification）：读是页粒度、直接；写必须先擦掉整块（约 1 ms），改一页要把块内其它页搬到新块（读-改-写），”写 1 字节”引发几十倍内部写。
- 磨损均衡（wear leveling）：每块约 1 万次重复写即报废，FTL 把写入摊到全盘（讲义举例：某三星 EVO Plus 保证每字节 600 次写入）。
- 实测性能（三星 970 EVO Plus，MB/s）：
| 顺序读 | 顺序写 | 随机读 | 随机写 | 随机读 DQ | 随机写 DQ |
|---|---|---|---|---|---|
| 2,221 | 1,912 | 61.7 | 165 | 947 | 1,028 |
读法：① 顺序远快于随机——整个存储层次的共同主题；② 深队列（DQ）用并发掩盖延迟；③ 随机写反比随机读快，因为写缓存攒批 + 预擦除块池。
- SSD vs 旋转磁盘：优势无机械部件（更快、省电、抗震）；劣势会磨损（FTL 缓解）、每字节更贵。旋转磁盘仍用于冷数据、视频与廉价桌面存储。
9.2.8 存储技术趋势与”内存墙”
| 年份 | 1985 | 1990 | 1995 | 2003 | 2005 | 2010 | 2015 | 2015:1985 |
|---|---|---|---|---|---|---|---|---|
| CPU | 80286 | 80386 | Pentium | P-4 | Core 2 | Core i7(n) | Core i7(h) | — |
| 时钟频率 (MHz) | 6 | 20 | 150 | 3,300 | 2,000 | 2,500 | 3,000 | 500 |
| 周期时间 (ns) | 166 | 50 | 6 | 0.30 | 0.50 | 0.4 | 0.33 | 500 |
| 核数 | 1 | 1 | 1 | 1 | 2 | 4 | 4 | 4 |
| 有效周期时间 (ns) | 166 | 50 | 6 | 0.30 | 0.25 | 0.10 | 0.08 | 2,075 |
| 指标 | 1985 | 2015 | 倍数 | 指标 | 1985 | 2015 | 倍数 |
|---|---|---|---|---|---|---|---|
| DRAM 价格 ($/MB) | 880 | 0.02 | 44,000 | DRAM 典型容量 (MB) | 0.256 | 16,000 | 62,500 |
| DRAM 访问时间 (ns) | 200 | 20 | 10 | 磁盘价格 ($/GB) | 100,000 | 0.03 | 3,333,333 |
| 磁盘访问时间 (ms) | 75 | 3 | 25 | 磁盘典型容量 (GB) | 0.01 | 3,000 | 300,000 |
一句话读懂：CPU 有效周期时间改善 2075 倍，DRAM 访问时间只改善 10 倍，磁盘只 25 倍——容量与价格改善 5–6 个数量级，速度只改善 1–2 个数量级。鸿沟持续拉大，这就是内存墙（memory wall）／冯·诺依曼瓶颈（Von Neumann bottleneck）。2003–2005 年撞上功耗墙（Power Wall），主频不再上涨，只能靠多核提升”有效”性能。三条出路：① 建造层次结构（本课）；② 找别的事做（指令级并行、乱序执行，15-346/15-418）；③ 把计算搬到数据旁边（近存计算）。摩尔定律放缓之下，闪存因能三维堆叠单元而进步最快。
9.2.9 局部性原理（Locality of Reference）——本章的灵魂
局部性原理：程序倾向于引用最近引用过的数据/指令本身，或与其地址相近者。这是存储层次能工作的唯一理由。
- 时间局部性（temporal locality）：被引用过的项很快会被再次引用（地址相等）。
- 空间局部性（spatial locality）：地址相邻的项倾向于被紧挨着引用（地址相近）。
写程序像在厨房做菜——调味料（时间局部性）与案板食材（空间局部性）都放手边，不必每切一次菜就跑一趟超市。工作集（working set）就是”此刻正在处理的那堆东西”，局部性好意味着工作集小、能塞进缓存。
C 数组按"行主序"(row-major) 存放：a[i][j] 的地址 = base + (i*N + j)*4
按行求和 (内层 j)：stride = 1 -> 空间局部性好 ✅
时间 -->
|a[i][0]|a[i][1]|a[i][2]|a[i][3]|a[i][4]| ... |a[i][N-1]|a[i+1][0]|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
^^^^^^^^^^^^^^^^^^^^^^^ 连续地址, 一个 cache block 装下多个元素
· · · · · · （每格 4 字节，64 B 的块可装 16 个 int）
按列求和 (内层 i)：stride = N -> 空间局部性差 ❌
时间 -->
|a[0][j]| ... |a[1][j]| ... |a[2][j]|
+-------+---------------+-------+---------------+-------+
每跳一次跨 N*4 字节（N=4096 时 = 16 KiB），每次落在全新的一块
-
定量感受：讲义例子
for (i = 0; i < 16; i++) sum += a[i];，若 cache 初始为空、一块恰放 8 个元素、a起点与块边界对齐，则只有 2 次冷未命中（是否已有元素在缓存中、一块放几个元素、起点是否对齐共同决定答案）。 -
对取指令的局部性：指令按顺序取（空间局部性）、循环体反复执行（时间局部性），故
for循环天生有好局部性。 -
循环置换（loop permutation）：讲义的三维例子把
k放最内层（步长 $N\times N$）；答案是把j换成最内层——最后一片下标变化才对应相邻地址，步长退化为 1。 - 易忽略的细节：按列求和并非永远差——讲义提示”若 M 非常小，局部性也不错，为什么？“，因为此时整列元素靠得近（跨距 $M\times4$ 字节），可能全落在同一或少数几个 block 里。局部性是相对工作集大小而言的。
9.2.10 存储层次结构（Memory Hierarchy）
最快的存储每字节最贵、容量最小、最耗电；CPU 与主存速度差距在扩大；写得好程序有良好局部性——三者共同指向存储层次结构：
更小、更快、更贵（每字节） <== 靠近 CPU
+----------------------------------------------------------------+
| L0 寄存器 Registers (CPU 内) <1 KB ~0.3 ns |
+----------------------------------------------------------------+
| L1 L1 cache (SRAM) 片上 32 KB ~1 ns |
+----------------------------------------------------------------+
| L2 L2 cache (SRAM) 片上 512 KB ~4 ns |
+----------------------------------------------------------------+
| L3 L3 cache (SRAM) 片上 32 MB ~15 ns |
+----------------------------------------------------------------+
| L4 主存 Main memory (DRAM) 16 GB ~60 ns |
+----------------------------------------------------------------+
| L5 本地二级存储 Local secondary 4 TB ~10 ms |
| storage (local disk / SSD) |
+----------------------------------------------------------------+
| L6 远程二级存储 Remote secondary PB 级 ~100 ms |
| storage (e.g., Web servers) |
+----------------------------------------------------------------+
更大、更慢、更便宜（每字节） <== 靠近数据源
逐级搬运：L1 存放从 L2 取来的 cache line，L2 从 L3 取，L3 从主存取；主存存放从本地磁盘取来的磁盘块（disk blocks）。为什么有效？ 对每个 $k$，第 $k$ 层更小更快的设备充当第 $k+1$ 层更大更慢设备的缓存；因局部性，程序访问第 $k$ 层远多于第 $k+1$ 层，于是第 $k+1$ 层可放心更慢、更大、更便宜。
“大思想（Big Idea）”：层次结构创造了巨大存储池——每字节成本接近最底层最便宜的设备，却以接近最顶层最快设备的速度供数。至于”为什么大内存更慢”：内存越大，信号走得更远、扇出（fan-out）更多，”更大”与”更慢”天然绑定。
9.2.11 缓存的通用概念（General Cache Concepts）
缓存（cache）是更小更快的设备，充当更大更慢设备中一个子集数据的中转站（staging area）：
Memory (更大、更慢、更便宜) Cache (更小、更快、更贵)
被划分为固定大小的 "块"(block) 缓存其中一部分块的副本
+----+----+----+----+----+----+ +----+----+----+----+
| 0 | 1 | 2 | 3 | .. | 15 | | 8 | 9 | 14 | 3 |
+----+----+----+----+----+----+ +----+----+----+----+
^ ^
| 数据总是以"块"为单位整块搬运 |
+----------------------------------+
请求 14 -> 块 14 在 cache 中 -> Hit !
请求 12 -> 块 12 不在 cache 中 -> Miss!
1) 从下一层取出块 12（放置策略决定 b 放哪里）
2) 缓存已满时按替换策略选一个"牺牲者"(victim) 淘汰
| 未命中类型 | 英文 | 操作化定义 |
|---|---|---|
| 冷未命中 / 强制未命中 | cold (compulsory) miss | 对该块的第一次引用；即”无限大且无放置限制的缓存仍会发生的未命中” |
| 容量未命中 | capacity miss | 工作集大于缓存本身；即”缓存仍无限大但不限放置”时额外出现的未命中 |
| 冲突未命中 | conflict miss | 第 $k+1$ 层的块只能放到第 $k$ 层的一小部分位置；即”实际放置策略”带来的额外未命中 |
经典反例：若块 $i$ 只能放在第 $i \bmod 4$ 个位置，则序列 0, 8, 0, 8, ... 每次都未命中。性能指标：命中率（hit rate） = 命中次数/总访问次数；未命中率（miss rate） $=1-\text{hit rate}$；命中时间（hit time） = 从缓存取块到上层的时间；未命中惩罚（miss penalty） = 从下一层取块、放入缓存并交付的时间，故 $\text{AMAT}=T_{\text{hit}}+\text{miss rate}\times T_{\text{miss penalty}}$。
缓存无处不在：寄存器、TLB、L1/L2、虚拟内存、缓冲区缓存、磁盘缓存、浏览器缓存、Web 缓存（代理）——对象与延迟各异，机制完全同构。可见性差异（关键区分）：缓存对软件透明，由硬件响应 load/store 自动管理，无需改代码即改善（例外：prefetch、invalidate、分区等指令）；而存储器对软件可见，可直接用地址寻址，优化必须靠改代码。
9.2.12 缓存管理的四种组合
| 写直达（write-through） | 写回（write-back） | |
|---|---|---|
| 写分配（write-allocate） | 写命中：同时写缓存和下一层；写未命中：先把块取进缓存再写 | 写命中：只写缓存并置脏位；写未命中：先把块取进缓存再写 |
| 非写分配（no-write-allocate） | 写命中：同时写缓存和下一层；写未命中：直接写下一层，不取块 | （组合不常见，讲义未推荐） |
记法：写命中时写直达”两头都写”、写回”只改缓存并标脏（dirty），被淘汰时再写回”；写未命中时写分配”先把块搬上来再改”、非写分配”绕过缓存直接往下写”。真实 L1/L2 通常是写回 + 写分配；写直达常与更慢但更简单可靠的下一层搭配——选择的本质是在”降低下层写流量”与”保持多层一致性/简单性”之间权衡。
9.3 代码示例与底层机制分析
9.3.1 示例一：按行求和 vs 按列求和（实测 20 倍差距）
/* rowcol.c —— Lecture 9 局部性实测：按行求和 (stride-1) vs 按列求和 (stride-N)
* 编译: gcc -g -Wall -std=c11 -O2 rowcol.c -o rowcol
* 运行: ./rowcol
*/
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 4096 /* 4096x4096 int = 64 MiB */
#define REPS 5 /* 每个规模重复 5 轮，取最快一轮 */
static int a[MAXN][MAXN]; /* 静态分配，避免 64 MiB 爆栈 */
static double now(void)
{
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return ts.tv_sec + ts.tv_nsec * 1e-9;
}
/* 空间局部性好：stride = 1 */
static long sum_rows(int n)
{
long sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
sum += a[i][j];
return sum;
}
/* 空间局部性差：stride = n（跨 n*4 字节） */
static long sum_cols(int n)
{
long sum = 0;
for (int j = 0; j < n; j++)
for (int i = 0; i < n; i++)
sum += a[i][j];
return sum;
}
int main(void)
{
for (int i = 0; i < MAXN; i++) /* 初始化按行写 */
for (int j = 0; j < MAXN; j++)
a[i][j] = (i + j) & 0xff;
printf("%6s %10s %12s %12s %10s %10s\n",
"N", "数组", "按行(ms)", "按列(ms)", "按行MB/s", "按列MB/s");
printf("%6s %10s %12s %12s %10s %10s\n",
"", "(KiB)", "stride-1", "stride-N", "", "");
for (int n = 256; n <= MAXN; n *= 2) {
double bytes = (double)n * n * 4;
long sr = 0, sc = 0;
double tr = 1e30, tc = 1e30;
for (int r = 0; r < REPS; r++) {
double t0 = now(); sr = sum_rows(n); double t1 = now();
double t2 = now(); sc = sum_cols(n); double t3 = now();
if (t1 - t0 < tr) tr = t1 - t0;
if (t3 - t2 < tc) tc = t3 - t2;
}
if (sr != sc) { fprintf(stderr, "结果不一致!\n"); return 1; }
printf("%6d %10.0f %12.3f %12.3f %10.0f %10.0f (慢 %.1fx)\n",
n, bytes / 1024, tr * 1e3, tc * 1e3,
bytes / tr / 1e6, bytes / tc / 1e6, tc / tr);
}
return 0;
}
【代码做什么？】 静态分配 $4096\times4096$ 的 int 数组（64 MiB，不能放成局部变量，否则撑爆 8 MiB 栈）；按行初始化；对 $N=256\ldots4096$ 各跑两函数 5 轮取最快一轮；用 sr != sc 断言两者相等——局部性只影响性能，绝不影响语义。
【底层机制透视】 两段代码的访存指令几乎相同，唯一区别是地址增量：sum_rows 每次 +4 字节，sum_cols 每次 +N*4 字节。前者一个 64 B block 装 16 个 int，取一次块后续 15 次迭代全命中，每 16 次访问才 1 次未命中，预取器还能识别 stride-1 提前灌数据。后者在 $N=4096$ 时步长 16 KiB，每次访问落在不同 block；访问完 a[0][j] 要过整整一行才回来碰 a[0][j+1]，此时该行早已被淘汰——几乎每次都是冷/容量未命中，64 MiB 全要从 DRAM 重拉；16 KiB 步长还几乎每次换页表项，TLB 同时被打爆。
【内存布局 / 数据结构图解】
行主序布局 (row-major), 假设 base = 0x7f0000, N = 4, int = 4B
地址: 0x7f0000 0x7f0004 0x7f0008 0x7f000c 0x7f0010 ...
+---------+---------+---------+---------+---------+
| a[0][0] | a[0][1] | a[0][2] | a[0][3] | a[1][0] | ...
+---------+---------+---------+---------+---------+
按行: -------> -------> -------> -------> stride=4B ✅
按列: a[0][0] ---------------------------> a[1][0] stride=16B ❌
\___________________ ___________________/
v
跨越 3 个元素 + 1 个新块（N 越大越糟）
【与汇编 / 硬件的对应】（gcc -O1 -S -masm=att -fno-tree-vectorize，$N=1024$）
sum_rows: sum_cols:
movl $a+4096, %esi movl $a+4194304, %esi
movl $a+4198400, %edi movl $a+4198400, %edi
movl $0, %ecx movl $0, %ecx
.L2: .L7:
leaq -4096(%rsi), %rax leaq -4194304(%rsi), %rax
.L3: .L8:
movl %ecx, %edx movl %ecx, %edx
addl (%rax), %edx addl (%rax), %edx
movl %edx, %ecx movl %edx, %ecx
addq $4, %rax <=== addq $4096, %rax <===
cmpq %rsi, %rax cmpq %rsi, %rax
jne .L3 jne .L8
addq $4096, %rsi addq $4, %rsi
cmpq %rdi, %rsi cmpq %rdi, %rsi
jne .L2 jne .L7
movl %edx, %eax movl %edx, %eax
ret ret
两条循环的唯一差别就是 addq $4, %rax 与 addq $4096, %rax——指令数、分支数、访存指令全同，所有性能差距 100% 来自这个立即数。
【实测验证】（AMD EPYC 7V13，L1d 32 KB / L2 512 KB / L3 32 MB，均 8 路组相联、64 B 行；择时数据每轮略有波动）
N 数组 按行(ms) 按列(ms) 按行MB/s 按列MB/s
(KiB) stride-1 stride-N
256 256 0.030 0.228 8598 1150 (慢 7.5x)
512 1024 0.096 0.971 10867 1080 (慢 10.1x)
1024 4096 0.372 4.798 11289 874 (慢 12.9x)
2048 16384 1.468 26.933 11430 623 (慢 18.3x)
4096 65536 5.689 114.279 11796 587 (慢 20.1x)
$ perf stat -e cache-references,cache-misses,cycles,instructions ./rowcol
500,115,620 cache-references:u # 34.80% of all cache refs
174,025,565 cache-misses:u
3,500,895,765 cycles:u
1,330,307,783 instructions:u # 0.38 insn per cycle
三条结论：① 数组越大按列访问相对越慢（7.5x → 20.1x）；② 按行吞吐稳定在 8.6–11.8 GB/s，几乎与数组大小无关——”层次结构提供恒定高速”的直接证据；③ IPC 仅 0.38，CPU 大部分时间在等内存（memory bound）。
9.3.2 示例二：存储器山简化版（Memory Mountain）
/* mountain.c —— 存储器山（简化版）
* 扫描 (工作集大小 x 步长) 二维网格，测量每次访存耗时并换算成读吞吐率 (MB/s)。
* 编译: gcc -g -Wall -std=c11 -O2 mountain.c -o mountain
* 运行: ./mountain
*/
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAXELEMS (32u << 20) /* 32M 个 int = 128 MiB */
#define MINBYTES (1u << 12) /* 最小工作集 4 KiB */
#define MAXBYTES (1u << 26) /* 最大工作集 64 MiB */
#define MAXSTRIDE 32
#define BUDGET (64u << 20) /* 目标访存次数，保证计时可信 */
static int data[MAXELEMS];
static double now(void)
{
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return ts.tv_sec + ts.tv_nsec * 1e-9;
}
/* 沿步长 stride 扫完工作集，返回累加和（防止被优化掉） */
static long touch(int n, int stride)
{
long acc = 0;
for (int i = 0; i < n; i += stride)
acc += data[i];
return acc;
}
/* 返回"平均每次访存耗时(秒)" */
static double run(int n, int stride, long *sink)
{
long per_pass = (n + stride - 1) / stride; /* 一趟的访存次数 */
long passes = BUDGET / per_pass;
if (passes < 4) passes = 4; /* 至少 4 趟 */
if (passes > 40000) passes = 40000; /* 小工作集别测太久 */
*sink += touch(n, stride); /* 预热 */
double t0 = now();
for (long p = 0; p < passes; p++)
*sink += touch(n, stride);
double t1 = now();
return (t1 - t0) / (double)(passes * per_pass);
}
int main(void)
{
long sink = 0;
memset(data, 1, sizeof(data));
printf("存储器山（简化版）：行 = 工作集大小，列 = 步长；格值 = 读吞吐 MB/s\n");
printf("%12s", "size");
for (int s = 1; s <= MAXSTRIDE; s *= 2)
printf("%9d", s);
printf(" <- stride (元素，int=4B)\n");
for (unsigned sz = MINBYTES; sz <= MAXBYTES; sz <<= 1) {
int n = (int)(sz / sizeof(int));
printf("%12u", sz);
for (int s = 1; s <= MAXSTRIDE; s *= 2) {
double per = run(n, s, &sink); /* 秒/访存 */
printf("%9.0f", 4.0 / per / 1e6); /* 4B/s -> MB/s */
}
printf("\n");
}
printf("\n(校验和 = %ld)\n", sink);
return 0;
}
【代码做什么？】 分配 128 MiB 的 int 数组并填 1；外层让工作集从 4 KiB 倍增到 64 MiB（16 档），内层让步长取 1,2,4,8,16,32（6 档）；每个 $(N,s)$ 先预热一趟，再反复完整遍历直到累计访存达 BUDGET，统计每次访存平均耗时。
【底层机制透视】 早期版本用”限制迭代次数”计时，大工作集在计时窗口内只走了一小段（仍在缓存里），测出 12 GB/s 假高值；改成长时间跑完整 N 趟后，大工作集被迫反复从 DRAM 重读，山形才正确显现。
【内存布局 / 数据结构图解 —— 山的三维形状】
吞吐率 (MB/s)
^
| ~~~ 山脊 (ridge): 步长=1, 工作集小, 数据在 L1/L2
| /|
12000| / |\
|/ | \___
| | \____
10000| | \____
| | \___
8000| | 山坡 (slope) \____
| | \____
6000| | \___
| | 冲突/容量未命中加剧 \___
4000| | \____ DRAM 平原
| | \______
2000| |
0+---+-------------------------------------------------> 工作集大小
4K 32K 512K 8M 32M 64M
^ ^ ^ ^ ^ ^
L1 L1/L2 L2 L3 L3/DRAM DRAM
|<--- 步长 1..32 方向是"纬线"，向里凹陷 --->|
【实测输出】（格值 = 读吞吐 MB/s）
size 1 2 4 8 16 32 <- stride (元素，int=4B)
4096 7127 7020 7001 6968 7815 7924
8192 7034 7030 7024 7138 6978 7747
16384 7038 7031 7029 7023 7009 6976
32768 8214 7060 7695 7487 7170 7164
65536 7643 7191 7508 6905 6144 6058
131072 7703 7079 7172 7043 6151 6104
262144 7188 7088 7482 7718 5978 5812
524288 8381 8132 7732 8557 5156 4555
1048576 10269 8265 7592 7191 4665 3130
2097152 10425 10589 7330 6847 4634 2934
4194304 10340 10133 7420 6707 4697 2918
8388608 10160 10091 7466 6850 4632 2921
16777216 10048 8104 7551 6935 4562 2951
33554432 9827 8759 5175 3614 2332 1517
67108864 10157 8107 4978 3012 1717 1173
如何解读：① 对角线趋势清晰——64 MiB + 步长 32 时仅 1173 MB/s，而 4 MiB + 步长 1 时是 10340 MB/s，差约 8.8 倍；② 小工作集（$\le$512 KB）各行平坦（数据基本命中 L2 及以上，步长影响被层级掩盖），但工作集到 1 MB 后步长 16/32 的列骤降到约 1900 MB/s 以下；③ 工作集 $\ge$32 MB 时连步长 8 也掉到 3800 MB/s 以下——大工作集 + 大 stride 最差（块内 16 个元素只用到 1–2 个）。
与 Cache Lab 的关系：存储器山是 L4 Part B”为什么分块有效”的实验证据——分块就是把大工作集切成能塞进某层缓存的小块。
9.3.3 示例三：Cache Lab Part A 的 LRU 缓存模拟器
/* csim.c —— Cache Lab Part A：LRU 缓存模拟器
* 用法: ./csim [-v] -s <s> -E <E> -b <b> -t <tracefile>
* 编译: gcc -g -Wall -std=c11 csim.c -o csim
*/
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <getopt.h>
#include <unistd.h>
typedef struct {
int valid; /* 该行是否装有数据 */
unsigned long tag; /* 标记位 */
unsigned long stamp; /* LRU 时间戳，越大越新 */
} line_t;
static int s, E, b, verbose;
static long hits, misses, evictions;
static unsigned long clk = 0; /* 全局逻辑时钟，每次访存 +1 */
static line_t **cache; /* cache[S][E] */
static int S; /* 组数 = 2^s */
/* 一次访存：bit0=hit, bit1=发生淘汰(eviction) */
#define RES_HIT 1
#define RES_EVICT 2
static int access_cache(unsigned long addr)
{
unsigned long tag = addr >> (s + b); /* 标记位 */
unsigned long set = (addr >> b) & ((1UL << s) - 1); /* 组索引 */
line_t *L = cache[set];
clk++;
for (int i = 0; i < E; i++) { /* 1) 找命中 */
if (L[i].valid && L[i].tag == tag) {
L[i].stamp = clk; /* 刷新 LRU */
hits++;
return RES_HIT;
}
}
misses++; /* 2) 未命中 */
int victim = -1, evicted = 0;
for (int i = 0; i < E; i++)
if (!L[i].valid) { victim = i; break; } /* 3a) 优先用空行 */
if (victim < 0) { /* 3b) 否则淘汰 LRU 行 */
victim = 0;
for (int i = 1; i < E; i++)
if (L[i].stamp < L[victim].stamp) victim = i;
evictions++;
evicted = 1;
}
L[victim].valid = 1;
L[victim].tag = tag;
L[victim].stamp = clk;
return evicted ? RES_EVICT : 0;
}
static void replay(FILE *fp)
{
char op;
unsigned long addr;
int size;
while (fscanf(fp, " %c %lx,%d", &op, &addr, &size) == 3) {
if (op == 'I') continue; /* 忽略取指 */
int r1, r2 = -1;
if (op == 'M') { /* M = load + store */
r1 = access_cache(addr);
r2 = access_cache(addr);
} else {
r1 = access_cache(addr);
}
if (verbose) {
printf("%c %lx,%d", op, addr, size);
printf("%s", (r1 & RES_HIT) ? " hit" : " miss");
if (r1 & RES_EVICT) printf(" eviction");
if (r2 >= 0) {
printf("%s", (r2 & RES_HIT) ? " hit" : " miss");
if (r2 & RES_EVICT) printf(" eviction");
}
printf("\n");
}
}
}
int main(int argc, char **argv)
{
const char *tracefile = NULL;
int opt;
while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
switch (opt) {
case 's': s = atoi(optarg); break;
case 'E': E = atoi(optarg); break;
case 'b': b = atoi(optarg); break;
case 't': tracefile = optarg; break;
case 'v': verbose = 1; break;
default:
printf("Usage: %s [-hv] -s <s> -E <E> -b <b> -t <tracefile>\n", argv[0]);
return 0;
}
}
if (!tracefile || E <= 0 || s < 0 || b < 0) {
fprintf(stderr, "Usage: %s [-hv] -s <s> -E <E> -b <b> -t <tracefile>\n", argv[0]);
return 1;
}
S = 1 << s;
cache = malloc(sizeof(line_t *) * S);
for (int i = 0; i < S; i++) {
cache[i] = calloc(E, sizeof(line_t));
if (!cache[i]) { perror("calloc"); return 1; }
}
FILE *fp = fopen(tracefile, "r");
if (!fp) { perror(tracefile); return 1; }
replay(fp);
fclose(fp);
printf("hits:%ld misses:%ld evictions:%ld\n", hits, misses, evictions);
for (int i = 0; i < S; i++) free(cache[i]);
free(cache);
return 0;
}
【代码做什么？】 ① getopt 解析 -s/-E/-b/-t/-v，$S=2^s$ 为组数、$E$ 为每组行数、$B=2^b$（只用于地址切分，不真正存数据）；② 用 malloc/calloc 为 $S\times E$ 个 line_t 分配空间——这正是 lab 要求”必须用 malloc 支持任意参数”的原因；③ 逐行解析 trace：忽略 I，L/S 各算一次访存，M 算两次；④ 把地址切成 tag\|set\|block，在 cache[set] 内找 tag，命中刷新时间戳，未命中先找空行、无空行则淘汰 stamp 最小者。
【底层机制透视 —— 地址切分】
64 位地址 A，参数 m = 64, s = 组索引位数, b = 块偏移位数
+---------------------------+----------------+------------------+
| tag (t = 64-s-b 位) | set (s 位) | block (b 位) |
+---------------------------+----------------+------------------+
| | |
| | +-> 块内偏移，模拟器不关心
| +-> cache[set]，直接索引到某一组
+-> 与组内每行的 tag 比较，判断是否命中
例: -s 4 -E 1 -b 4, 地址 0x110 (十进制 272)
272 = 0b1_0001_0000
b=4 -> 块偏移 = 0b0000
s=4 -> 组索引 = 0b0001 = 1
t=56 -> 标记 = 0b1 = 1 => 到第 1 组找 tag==1 的行
M 为什么要算两次？ 讲义明确说明：M 是”一次数据装载后紧跟一次数据存储”，可能产生两次命中，或一次未命中 + 一次命中（外加可能的淘汰）；但淘汰只可能发生在第一次访问上——第二次访问时该行必定已在缓存。这是 Part A 最容易多算 evictions 的地方。
【LRU 的实现方式】（时间戳数组 vs 双向链表）
| 实现 | 数据结构 | 命中时 | 淘汰时 | 复杂度 | 说明 |
|---|---|---|---|---|---|
| 时间戳数组（上面代码） | 每行一个 stamp + 全局单调计数器 clk
|
L[i].stamp = ++clk |
线性扫描找 stamp 最小者 |
命中 $O(E)$，淘汰 $O(E)$ | 实现最短，推荐首选 |
| 双向链表 | 每组一条链表，MRU 在头、LRU 在尾 | 摘下插到头 | 摘尾插头 | 命中 $O(1)$（需哈希或额外指针） | 理论更优，但代码量大、易出指针 bug |
实践中 $E$ 最多几十，时间戳数组的线性扫描开销可忽略。
【实测验证 —— 与官方 csim-ref 逐例比对】（8 个官方用例全部一致，27/27 分）
$ ./csim -v -s 4 -E 1 -b 4 -t traces/yi.trace # 我们的实现
L 10,1 miss
M 20,1 miss hit
L 22,1 hit
S 18,1 hit
L 110,1 miss eviction
L 210,1 miss eviction
M 12,1 miss eviction hit
hits:4 misses:5 evictions:3
$ csim-ref -v -s 4 -E 1 -b 4 -t traces/yi.trace # 官方参考模拟器
L 10,1 miss
M 20,1 miss hit
...
hits:4 misses:5 evictions:3
| (s, E, b) | trace | 我们 hits/misses/evictions | csim-ref |
一致？ |
|---|---|---|---|---|
| (1,1,1) | yi2.trace | 9 / 8 / 6 | 9 / 8 / 6 | ✅ |
| (4,2,4) | yi.trace | 4 / 5 / 2 | 4 / 5 / 2 | ✅ |
| (2,1,4) | dave.trace | 2 / 3 / 1 | 2 / 3 / 1 | ✅ |
| (2,1,3) | trans.trace | 167 / 71 / 67 | 167 / 71 / 67 | ✅ |
| (2,2,3) | trans.trace | 201 / 37 / 29 | 201 / 37 / 29 | ✅ |
| (2,4,3) | trans.trace | 212 / 26 / 10 | 212 / 26 / 10 | ✅ |
| (5,1,5) | trans.trace | 231 / 7 / 0 | 231 / 7 / 0 | ✅ |
| (5,1,5) | long.trace | 265189 / 21775 / 21743 | 265189 / 21775 / 21743 | ✅ |
观察：trans.trace 在 $E$ 从 1 增到 4 时未命中从 71 降到 26、淘汰从 67 降到 10——组相联消除了冲突未命中；(5,1,5) 淘汰为 0，余下 7 次未命中全是冷未命中。
9.4 实验关联
L4 Cache Lab（本讲布置，约 2 周完成），共 60 分（Part A 27 + Part B 26 + 风格 7）。
Part A：缓存模拟器（本讲学完立刻动手）
-
交付：从零填写
csim.c（约 200–300 行），命令行与csim-ref一致：./csim [-hv] -s <s> -E <E> -b <b> -t <tracefile>。 -
必做七件事：① 用
malloc分配数据结构以支持任意 $s,E,b$；② 忽略所有I开头的行——valgrind 约定I在第一列且前面无空格，M/L/S在第二列且前面有空格，而fscanf(" %c %lx,%d", ...)的前导空格正好吃掉这一差异；③M必须算两次访存；④ 可忽略 size 字段（lab 保证访存不跨块边界）；⑤main结尾必须调用printSummary(hit_count, miss_count, eviction_count)；⑥ 用 LRU 替换策略；⑦ 必须无警告编译（-Wall），并写上姓名与 loginID。 -
建议实现
-v详细模式：不强制，但可与csim-ref -v逐行 diff，是最快的调试手段。评分：8 个用例，每个 3 分、最后一个 6 分；hits/misses/evictions 各占 1/3 分——evictions算错仍能拿 2/3 分。
linux> make
linux> ./test-csim
Your simulator Reference simulator
Points (s,E,b) Hits Misses Evicts Hits Misses Evicts
3 (1,1,1) 9 8 6 9 8 6 traces/yi2.trace
...
6 (5,1,5) 265189 21775 21743 265189 21775 21743 traces/long.trace
27
Part B：矩阵转置优化（第 10 讲后完成）
- 写
transpose_submit，在 $32\times32$、$64\times64$、$61\times67$ 三种尺寸下最小化未命中；用 valgrind 取 trace，再用csim-ref -s 5 -E 1 -b 5（32 组 × 1 路 × 32 B 直接映射缓存）打分。 - 阈值：$32\times32$ 未命中 $<300$ 得 8 分（$>600$ 得 0）；$64\times64$ $<1300$ 得 8 分（$>2000$ 得 0）；$61\times67$ $<2000$ 得 10 分（$>3000$ 得 0），性能分按未命中数线性插值。
-
规则坑：每个转置函数最多 12 个
int局部变量（栈访问被 valgrind 过滤，故须限制）；禁止递归、禁止定义任何数组、禁止任何形式的malloc、禁止改A；辅助函数间活动局部变量总数也不得超过 12。 -
核心技巧：分块（blocking）——把大矩阵切成能装进缓存的小块：$32\times32$ 用 $8\times8$ 块；$64\times64$ 因直接映射冲突严重，常用 $8\times8$ 分块 + 临时变量缓存对角线元素。入门材料见
csapp.cs.cmu.edu/public/waside/waside-blocking.pdf。 -
调试利器：
test-trans为每个注册函数生成trace.fi，再用./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0逐条对照每次命中与未命中，精确定位哪一行引起冲突未命中。反例数据（讲义示例）：简单按行扫描转置 $32\times32$ 有 1183 次未命中、1151 次淘汰，分块版本只有 287 次。
9.5 常见错误与调试技巧
按行/按列写反了：
for j/for i嵌套写错，功能正确但性能掉数倍。调试：perf stat -e cache-misses,cache-references ./prog；perf record -e cache-misses ./prog && perf report定位循环行。判据：内层下标应对应数组最右边（变化最快）的那一维。大数组放成局部变量导致栈溢出：
int a[4096][4096]要 64 MiB，默认栈仅 8 MiB → 段错误。调试：ulimit -s查上限；gdb下bt见地址接近0x7ffd...边界即为栈溢出。解决：改static/全局/malloc。存储器山测量窗口没覆盖完整工作集：固定迭代次数计时使大工作集一轮只走一小段（仍在缓存），测出 12 GB/s 假高值。调试：保证每点完整遍历若干趟，用
perf stat验证未命中数随工作集增长。csim的 evictions 多算：把M的第二次访存也算作可能淘汰，或在未命中且找到空行时仍累加。调试：./csim -v ... \| diff - <(csim-ref -v ...)；重点看M行——正确形式是M xxx,n miss eviction hit，第二次永远是hit。直接映射缓存的对角线冲突未命中（Part B 的 $64\times64$ 是重灾区）：$E=1$ 时 $A$、$B$ 的第 $i$ 行常映射到同组，转置时互相踢出。调试：
./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0 \| head -50看是否反复出现同组地址的miss eviction；解决：分块 + 用 8 个临时变量一次读出整行再写出。误以为”缓存对程序员完全不可见”：缓存确由硬件透明管理，但访问模式由你决定。调试：
valgrind --tool=cachegrind ./prog得到逐行 D1/LL 未命中统计（cg_annotate）。
9.6 关键要点
局部性是存储层次结构存在的唯一理由。 时间局部性让”缓存最近用过的块”有意义，空间局部性让”以块为单位搬运”有意义；没有局部性，金字塔立刻崩塌。
步长（stride）是局部性的第一指标。 内层下标必须对应地址变化最快的那一维（C 中是最后一维）；步长变大，每次访问能利用的块内数据成比例减少。
级联缓存让”又大又快又便宜”同时成立。 每层的目标不是自己快，而是”让上一层觉得自己快”；这就是 Big Idea。
内存墙是物理必然。 更大的存储意味着信号更远、扇出更多，”大”与”慢”天然绑定；CPU 有效周期时间 40 年改善 2075 倍而 DRAM 访问时间只改善 10 倍。
未命中分三类，诊断方法各异。 冷未命中不可免（除非预取）；容量未命中靠缩小工作集或分块；冲突未命中靠提高相联度（增大 $E$）或改变访问地址。“增加 $E$ 后未命中大降”就说明冲突未命中占主导。
磁盘/SSD 性能被”第一位”主导。 传送时间可忽略，故减少随机访问次数比减少总字节数更重要——这正是缓冲区缓存、预读与顺序写日志有效的原因。
9.7 思考题（带答案）
① （计算题）磁盘容量与访问时间
某磁盘：每扇区 512 字节，平均每磁道 400 个扇区，每盘面 20,000 条磁道，每盘片 2 个盘面，共 5 个盘片；转速 10,000 RPM；平均寻道 6 ms。(a) 求总容量（十进制 GB）。(b) 求平均访问时间。(c) 转速提到 15,000 RPM 后改善多少百分比？
答：
(a) 套容量公式：$512\times400=204{,}800$ B/track；$\times20{,}000=4.096\times10^9$ B（单面）；$\times2\times5=\boxed{40.96\ \text{GB}}$
(b) $T_{\text{avg seek}}=6\ \text{ms}$；$T_{\text{avg rotation}}=\frac{1}{2}\times\frac{60}{10000}\times1000=3\ \text{ms}$；$T_{\text{avg transfer}}=\frac{60}{10000}\times\frac{1}{400}\times1000=0.015\ \text{ms}$，故
\[T_{\text{access}}=6+3+0.015=\boxed{9.015\ \text{ms}}\](c) 转速只影响旋转延迟与传送时间，不影响寻道：新 $T_{\text{avg rotation}}=2\ \text{ms}$、新 $T_{\text{avg transfer}}=0.01\ \text{ms}$，故新 $T_{\text{access}}=8.01\ \text{ms}$，改善 $\frac{9.015-8.01}{9.015}\approx11.2\%$。
关键结论：转速提升 50% 只让总时间改善约 11%——6 ms 寻道占 2/3 且不受转速影响。所以磁盘优化重点是”减少寻道次数”（柱面优先、电梯调度、顺序访问），而非”提高转速”。
② （计算题）局部性判断与冷未命中计数
#define N 8
int a[N][N];
long sum_cols(void) /* 按列求和：stride = N */
{
long sum = 0;
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum += a[i][j];
return sum;
}
int 为 4 字节，cache 初始为空，块大小 32 字节，a 起点与块边界对齐，cache 足够大不发生容量/冲突未命中。求总未命中次数，并说明如何重写循环以消除绝大部分未命中。
答：矩阵共 $8\times8\times4=256$ 字节 = 8 个 32 字节块，每块装 8 个 int；行主序下第 $i$ 行的 8 个元素恰好占满一个块（$N=8$，一行 32 字节）。
- $j=0$：访问
a[0..7][0]，地址间隔 $8\times4=32$ 字节，8 次访问落在 8 个互不相同的块上 → 8 次未命中。 - $j=1$：这 8 个块都已在缓存中 → 0 次未命中；$j=2..7$ 同理全命中。
总未命中 = 8 次，全是冷未命中。
注意：这是”按列访问但局部性仍好”的典型——因 $N=8$ 太小，一整列元素全挤在少数几个块里（讲义”若 M 非常小则局部性也不错”一题即由此而来）。若把 $N$ 改成 1024：按列访问一列需 1024 个块，而矩阵共 $131{,}072$ 个块、远超缓存，每轮 $j$ 几乎全未命中（共约 $10^6$ 次）；改写成内层下标对应最后维度后，每块连续访问 8 次只用 1 次未命中，总未命中降到 131,072 次。
③ （”直观但错误”的想法）”既然缓存是硬件自动管理的，程序员不需要关心局部性”
请指出这个想法错在哪里，并举出本讲的具体反例。
答：错在把”缓存的正确性”与”缓存的性能”混为一谈。 硬件透明地保证正确性——不写代码，sum_rows 与 sum_cols 也算出相同答案。但性能完全取决于访问模式，而访问模式是程序员唯一能控制的东西；硬件只负责”用你给的访问序列去填缓存”，不能替你改变序列。
反例一：示例一中两函数的汇编指令几乎逐条相同，唯一差别是 addq $4, %rax 与 addq $4096, %rax，结果 $N=4096$ 时 5.689 ms vs 114.279 ms，相差约 20 倍——同算法、同数据、同机器、同编译器，性能差距 100% 来自遍历顺序。反例二：Cache Lab Part B 中，简单按行扫描转置在 $32\times32$ 上产生 1183 次未命中，仅改变分块方式（数学逻辑一行不改）就降到 287 次，性能分从 0 变满分。
结论：硬件提供”机制”，程序员提供”策略”。“缓存不可见”意味着不必为正确性操心，而不是不必为性能操心。
④ （推演题）未命中类型的归因
某程序在 32 KB 缓存上测得未命中率 10%；换成同样大小的 16 路组相联后降到 6%；再扩大到 128 KB 全相联（不限放置）降到 4%。估算冲突未命中与容量未命中在原始 10% 中各占多少，并说明依据。
答：依据讲义的三条操作化定义——冷未命中：用无限大且无放置限制的缓存仍会发生的未命中；容量未命中：在冷未命中之上，因缓存有限（但不限放置）而额外增加的未命中；冲突未命中：在容量未命中之上，因实际放置限制而额外增加的未命中。
归因：① 128 KB 全相联的 4% 已接近”无限大无限制”下界，冷未命中 ≈ 4%；② “无放置限制（4%）”与”16 路组相联（6%）”之差来自放置限制，故高相联度下 冲突未命中 = 2%；③ 原始配置冲突未命中 = 10% − 4% − 2% = 4%，容量未命中 = 2%。
| 未命中类型 | 占原始 10% 的比例 |
|---|---|
| 冷未命中（compulsory/cold） | 4%（不可消除） |
| 容量未命中（capacity） | 2% |
| 冲突未命中（conflict） | 4% |
依据：以”无限大无限制”为冷未命中基准；”大而不限放置 vs 实际放置”的差额是冲突未命中；”无限大 vs 有限大（不限放置）”的差额是容量未命中。本例冲突未命中占大头（4/10），说明提高相联度收益最高——与示例三中 trans.trace 把 $E$ 从 1 增到 4 时未命中从 71 降到 26 的实测一致。