外观
缓存与局部性：相同运算为什么速度不同
CPU 读取一个数组元素时，通常会把附近一整条缓存行一起带入缓存。随后访问同一行的其他元素，可能无需再等待下一级存储。这让循环顺序、数据布局和复用距离影响运行时间；只计算加法与乘法次数，无法完整解释程序性能。
地址拆分
设缓存有
以 32 字节缓存、2 组、每组 2 行、每行 8 字节为例，s=1、E=2、b=3。地址 0x28 即十进制 40：偏移为 0，组索引为 1，tag 为 2。地址 0x2c 的 tag 和组索引不变，偏移变成 4，属于同一条行。
c
set = (address >> b) & ((1ULL << s) - 1);
tag = address >> (s + b);在真实实现中还要防止移位超出字宽，以及 1 << s 使用了错误的有符号类型。本站模拟器限制 s、b 和总行数，避免配置导致巨大分配或非法移位。
命中、未命中与替换
若 tag 匹配有效行，就是 hit；找不到就是 miss。miss 时有空行直接填入；整组已满才发生 eviction。LRU 替换最长时间没有访问的那一行。这里用单调递增的访问序号作时间戳，命中和装入都更新它。
flowchart TD
A[地址选组] --> B{有效行的 tag 匹配?}
B -- 是 --> C[hit 并更新时间戳]
B -- 否 --> D[miss]
D --> E{组内存在空行?}
E -- 是 --> F[装入空行]
E -- 否 --> G[eviction: 替换最老行]
F --> H[记录新 tag 与时间戳]
G --> H
查看流程图文本
flowchart TD
A[地址选组] --> B{有效行的 tag 匹配?}
B -- 是 --> C[hit 并更新时间戳]
B -- 否 --> D[miss]
D --> E{组内存在空行?}
E -- 是 --> F[装入空行]
E -- 否 --> G[eviction: 替换最老行]
F --> H[记录新 tag 与时间戳]
G --> H
手算仓库 direct.trace，配置 s=1、E=1、b=2。地址按十六进制读取，10 是 16。I 不参与数据缓存统计，M 表示先读后写。
| 操作 | 组 | tag | 结果 |
|---|---|---|---|
| L 0 | 0 | 0 | miss，填空行 |
| L 0 | 0 | 0 | hit |
| L 8 | 0 | 1 | miss + eviction |
| L 10 | 0 | 2 | miss + eviction |
| L 0 | 0 | 0 | miss + eviction |
| M 8 | 0 | 1 | 读 miss + eviction，写 hit |
总计 hit=2、miss=5、eviction=4。组 1 即使一直空着，也无法容纳映射到组 0 的额外行。这说明冲突未命中可以发生在总容量尚未充分利用的时候。
阅读模拟器
Cache 保存参数、各行、时钟和统计；Line 只保存 valid、tag、stamp。access_block 依次完成查找命中、记住空行或最老行、更新统计。代码的关键不变量是：只在 miss 且替换有效行时加 eviction，不能把每次 miss 都算替换。
access_range 将跨缓存行的访问拆开。比如每行 4 字节，M 3,2 读了地址 3 和 4，跨两行，先完成两个块的读，再完成两个块的写。s=1、E=1 时结果为 miss=2、hit=2；s=0、E=1、b=0 时每字节一行且只有一行，四次访问互相驱逐，结果为 miss=4、hit=0、eviction=3。
这是本站明确增加的输入语义。官方 Cache Lab trace 可以依照实验约定处理访问大小，不应不加说明地把不同 trace 假设混用。官方 Cache Lab 说明
sh
make -C labs/csapp cache_sim
./labs/csapp/cache_sim 1 1 2 labs/csapp/traces/direct.trace
./labs/csapp/cache_sim 1 2 2 labs/csapp/traces/lru.trace预期分别是 hits:2 misses:5 evictions:4 与 hits:1 misses:4 evictions:2。第二个 trace 专门验证 hit 会改变 LRU 次序；若只在 miss 更新时间，结果会错。
c
/* A small LRU simulator. Cross-block requests are split, unlike Cache Lab's
* simplifying input assumption. A modify runs the whole load, then the store. */
#include <ctype.h>
#include <errno.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct { bool valid; uint64_t tag, stamp; } Line;
typedef struct {
unsigned s, b;
size_t ways, sets;
Line *lines;
uint64_t clock, hits, misses, evictions;
} Cache;
static bool number(const char *text, uint64_t *value) {
if (!*text || *text == '-') return false;
char *end;
errno = 0;
unsigned long long n = strtoull(text, &end, 10);
if (errno || *end) return false;
*value = (uint64_t)n;
return true;
}
static void access_block(Cache *c, uint64_t address) {
uint64_t set = (address >> c->b) & (c->sets - 1);
uint64_t tag = address >> (c->s + c->b);
Line *lines = c->lines + set * c->ways;
size_t victim = 0;
bool found_empty = false;
++c->clock;
for (size_t i = 0; i < c->ways; ++i) {
if (lines[i].valid && lines[i].tag == tag) {
++c->hits;
lines[i].stamp = c->clock;
return;
}
if (!lines[i].valid) {
if (!found_empty) victim = i;
found_empty = true;
} else if (!found_empty && lines[i].stamp < lines[victim].stamp) {
victim = i;
}
}
++c->misses;
if (lines[victim].valid) ++c->evictions;
lines[victim] = (Line){true, tag, c->clock};
}
static void access_range(Cache *c, uint64_t address, uint64_t size) {
uint64_t block = address >> c->b;
uint64_t last = (address + size - 1) >> c->b;
for (;;) {
access_block(c, block << c->b);
if (block == last) break;
++block;
}
}
int main(int argc, char **argv) {
uint64_t s, ways, b;
if (argc != 5 || !number(argv[1], &s) || !number(argv[2], &ways) ||
!number(argv[3], &b) || s > 20 || b > 63 || s + b > 63 ||
ways == 0 || ways > (UINT64_C(1) << 22) / (UINT64_C(1) << s)) {
fprintf(stderr, "usage: %s s E b trace (s<=20, s+b<=63, 1<=E, <=2^22 lines)\n", argv[0]);
return 2;
}
Cache c = {(unsigned)s, (unsigned)b, (size_t)ways, (size_t)1 << s, NULL, 0, 0, 0, 0};
c.lines = calloc(c.sets * c.ways, sizeof *c.lines);
if (!c.lines) { perror("calloc"); return 1; }
FILE *input = fopen(argv[4], "r");
if (!input) { perror(argv[4]); free(c.lines); return 1; }
char *line = NULL;
size_t capacity = 0, lineno = 0;
int result = 0;
while (getline(&line, &capacity, input) >= 0) {
++lineno;
char *start = line;
while (isspace((unsigned char)*start)) ++start;
if (!*start || *start == '#') continue;
char op;
uint64_t address, size;
int end = 0;
if (sscanf(start, " %c %" SCNx64 ",%" SCNu64 " %n", &op, &address, &size, &end) != 3 ||
!end || start[end] || !strchr("ILSM", op) || !size || size > (UINT64_C(1) << 20) ||
address > UINT64_MAX - (size - 1)) {
fprintf(stderr, "invalid trace at line %zu\n", lineno);
result = 2;
break;
}
if (op == 'I') continue;
access_range(&c, address, size);
if (op == 'M') access_range(&c, address, size);
}
if (ferror(input)) { perror("trace read"); result = 1; }
if (!result)
printf("hits:%" PRIu64 " misses:%" PRIu64 " evictions:%" PRIu64 "\n", c.hits, c.misses, c.evictions);
free(line);
fclose(input);
free(c.lines);
return result;
}矩阵转置为何需要分块
C 的二维数组按行存储。读取 A[i][j] 的相邻 j 利于空间局部性，但写 B[j][i] 的连续 j 可能跨很远。以 64×64 的 int 矩阵为例，相邻行间距 256 字节。若直接映射缓存组数与这个步长形成周期，A 与 B 的行还可能反复竞争同一组。
分块转置把访问限制在一个小区域，先选择能让活跃数据装入缓存的 tile，再研究读写冲突。8×8 并非所有尺寸都最佳；对角块、行跨度、相联度都会改变冲突。可以把一行的少量元素先保存到寄存器，再写入，减少读写交错造成的互相驱逐。
做实验时固定矩阵内容，先验证 B[j][i] == A[i][j]，再统计 miss。性能指标必须绑定缓存参数和数据尺寸。“miss 减少”不直接等于真实 CPU 时间按相同比例下降，因为真实机器还有预取、多级缓存、乱序执行和写缓冲等机制。
实验扩展
先自己创建 5 条访问的 trace，手算两个 E 值，再和程序比较。接着增加逐条 verbose 输出，展示 set、tag 和结果。最后把 LRU 改成 FIFO，构造能使两者不同的 trace：关键是在替换前重访一个早装入的块。保留旧版本作为参考，防止“改变策略”时同时改变解析逻辑。
自测：为什么增大缓存总容量不一定消除某个冲突？
要看容量通过哪种参数增加，以及索引函数如何变化。映射到同一组的活跃块仍超过相联度，就可能继续冲突。工作集总大小只是一个条件，映射分布和复用顺序同样重要。
自测：缓存 miss 就是缺页吗？
不是。缓存 miss 在存储层次里寻找数据，通常不进入操作系统；缺页是页表所描述的映射或权限不能直接完成当前访问，需要异常处理。TLB miss 又是第三件事。下一章组会将它们区分开。
下一章：异常控制流与进程。