CSAPPlab4 cachelab通关记录（未完待续

发表于2026-07-03|更新于2026-07-04|公开课

|浏览量:

本文记录了完成cachelab的全流程，相关代码均在Github。

csim

一个简易的数据cache模拟器，了解了cache所使用的地址结构（t,s,b)之后照着它写就行了，并没有太多阻碍。如果需要一个参考的话可见：csapp/cachelab/cachelab-handout/csim.c at master · yoo2i/csapp

debug时编写了一个打印当前cache内容的函数，很好用：

//for test
void printCache(CacheLine **cache, CacheParams params) {
    for (int i = 0; i < params.S; i++) {
        for (int j = 0; j < params.E; j++) {
            printf("S: %d E: %d valid: %d tag: %llx lru: %d\n", i, j, cache[i][j].valid, cache[i][j].tag, cache[i][j].lru_counter);
        }
    }
}

很多时候不一定非要调试，打印相关信息并观察就足够用了。一步步调试、在脑子里去模拟函数执行流程过于笨重，绕晕自己的同时还没有效率。

matrix

cache结构为2 ^ 5 = 32个组，直接映射（每组一个cache行），每个cache行2 ^ 5 = 32B。

每个cache行能存放2 ^ (5 - 2) = 2 ^ 3 = 8个int值。

32*32

cache容量为2 ^ 8 = 256个int，AB两个矩阵都会被cache缓存，对他俩分块，每个矩阵最多占有128个int的cache容量，2 ^ 3 * 2 ^ 3 = 64 < 128，2 ^ 4 * 2 ^ 4 = 256 > 128，所以按8*8分块。

上面是我解决这个问题时的想法，总感觉哪有问题但是说不出，直到我用相似的思路去解决64*64才明白，这是错的！

参见ai大人的解释：

❌ 你的逻辑盲区：Cache 不是“共享大水池”
你的潜意识里，把这 256 个 int 的容量当成了可以随意瓜分的内存堆（Heap）——“A 拿走一半 128，B 拿走一半 128，我的块只有 64，随便塞！”

但在 Cache Lab 中，这是绝对行不通的。为什么？

因为我们的 Cache 是直接映射（Direct Mapped，E=1）！

直接映射的意思是：Cache 就像一排标了号的 32 个专属储物柜（Set 0 到 Set 31）。矩阵里的每一个元素，它能存进几号柜子，是它的物理地址（取模后）天生注定的，你根本无权干涉！

如果 A 矩阵和 B 矩阵的某些行“命中注定”要抢同一个柜子（比如 Set 0），哪怕 Cache 里剩下 31 个柜子全空着，它们俩也会在 Set 0 这个位置互相把对方踢出去（Conflict Miss）。所以，仅仅算“总容量”是不够的，必须算“组号（Set Index）的分布”。

✅ 为什么 $8 \times 8$ 在 $32 \times 32$ 矩阵中真正完美？
它之所以完美，根本不是因为 $64 < 128$，而是因为在 $32 \times 32$ 的矩阵排布下，一个 $8 \times 8$ 的分块，完美且均匀地霸占了 Cache 的所有 32 个储物柜，没有一丝浪费，也没有一次内讧！

我们来算一笔精确的“柜子账”：

一个 Cache 行装 8 个 int。在 $32 \times 32$ 矩阵中，一行有 32 个 int，恰好占用 $32 \div 8 = \mathbf{4}$ 个 Cache 行（即跨越 4 个 Set）。

当读取一个 $8 \times 8$ 的块（以从坐标 [0][0] 开始的块为例）时，看看它在 Cache 里的占位：

第 0 行（8个int）：占用 Set 0

第 1 行（8个int）：占用 Set 4 （因为上一行占了4个柜子，所以往下挪4个）

第 2 行（8个int）：占用 Set 8

…

第 7 行（8个int）：占用 Set 28

发现了什么奇迹吗？

8 * 8 分块的总共 8 行，精确地落在了 Set 0, 4, 8, 12, 16, 20, 24, 28 上！

它们彼此之间完全错开，在处理这个小块的过程中，A 矩阵连一次自我踩踏（内部冲突）都不会发生。

💥 反证：为什么你的理论在 $64 \times 64$ 里崩溃了？
如果你的“容量分配论”成立，在 $64 \times 64$ 矩阵中，一个 $8 \times 8$ 的块依然是 64 个 int，同样小于 128，为什么就会导致 Miss 率暴增呢？

因为在 $64 \times 64$ 矩阵中，一行有 64 个 int，占用 $64 \div 8 = \mathbf{8}$ 个 Cache 行。

此时你再读 $8 \times 8$ 的块：

第 0 行：占用 Set 0

第 1 行：占用 Set 8

第 2 行：占用 Set 16

第 3 行：占用 Set 24

第 4 行：占用 Set 32 ➡️ 取模 32 后变成 Set 0！

就在这一瞬间，第 4 行一脚把第 0 行踢出了 Cache！这就是惨烈的内部冲突（Internal Conflict）。