Lecture 10: 高速缓存存储器 (Cache Memories)

目录 · ← l9 · l11 →

Lecture 10: 高速缓存存储器 (Cache Memories)

讲义对应：CMU 15-213 Lecture 10 — Cache Memories（素材：F25-10-cache-memories.txt） 教材对应：CS:APP3e 第 6 章 6.4–6.7（高速缓存的组织与操作、性能影响、存储器山、循环重排与分块） 关联 Lab：L4 Cache Lab（Part A 写缓存模拟器 csim.c，Part B 优化矩阵转置 trans.c）

10.1 概述

第 9 讲建立了”存储层次 + 局部性（locality）”的定性图景：程序倾向于访问最近用过的、地址相近的数据。本讲把这张定性图景变成一个可以精确计算的硬件模型：真实的缓存（cache）由 $S$ 个组（set）、每组 $E$ 行（line）、每行 $B$ 字节块（block）构成，容量 $C = S \times E \times B$；CPU 发出的地址被硬件切成标记（tag）、组索引（set index）、块偏移（block offset）三段，每组一次查找就能判定命中（hit）还是未命中（miss）。有了这套模型，我们才能解释为什么”按列遍历矩阵比按行慢 25 倍”、为什么循环交换一下顺序就能提速 10 倍、为什么 $64\times64$ 矩阵转置需要一套看起来极其古怪的分块写法。

本讲承接第 9 讲的局部性与存储层次，向下为第 15 讲”代码优化”提供量化的性能语言，并直接支撑 L4 Cache Lab 的两个部分。

10.2 核心概念与底层机制图解

10.2.1 缓存的组织结构 $C = S \times E \times B$（Cache Organization）

  • 定义与目的：缓存是”小、快、贵”的 SRAM，缓存住”大、慢、便宜”的 DRAM 中一块子集。硬件不做任何程序分析，只靠地址位做机械查表，因此必须有一个规整的阵列结构。
  • 直观解释（”它是什么？”）：把缓存想成一栋图书馆：全馆分成 $S$ 个书架（组），每个书架上恰好有 $E$ 层隔板（行），每层隔板上放一个书盒（块），盒里装 $B$ 字节数据。要知道某本书在不在馆里，先由”索书号中段”决定去哪个书架（组索引），再逐层比对”书脊上的编号”（标记），全都对不上就说明没这本书。
  • 底层机制图解：
                     高速缓存 Cache：C = S x E x B 字节(数据)
       组 0                                        组 S-1
 +--------------------------------+          +--------------------------------+
 | 行0   : [v][d][ tag ][ data ]  |          | 行0   : [v][d][ tag ][ data ]  |
 | 行1   : [v][d][ tag ][ data ]  |          | 行1   : [v][d][ tag ][ data ]  |
 |  ...                           |   ...    |  ...                           |
 | 行E-1 : [v][d][ tag ][ data ]  |          | 行E-1 : [v][d][ tag ][ data ]  |
 +--------------------------------+          +--------------------------------+
 |<------- E = 2^e 行/组 -------->|

      ^        ^          ^
      |        |          +--- B = 2^b 字节的数据块(data block)
      |        +-------------- d：脏位(dirty bit)，写回策略下标记"已被改过"
      +----------------------- v：有效位(valid bit)，1 表示这一行真的存了数据

     地址划分（总位宽 m = t + s + b 位）
     高位                                                            低位
 +---------------------------+--------------------+-------------------+
 |        tag (t 位)         |  set index (s 位)  | block offset(b 位)|
 +---------------------------+--------------------+-------------------+
              |                        |                     |
   与组内 E 行并行比较 tag      选中第 set 组           块内第几个字节
  • 与机器码/硬件的对应：全部由地址译码逻辑完成——set index 位直接接到一个多路选择器选中 SRAM 组；tag 位送进 $E$ 个并行的比较器；block offset 位用于从块内取出字节。因此”查找”是组合逻辑，不需要指令、不需要软件参与。唯一会出现在汇编里的是访存指令本身（如 movslq (%rax), %rcx）。

10.2.2 直接映射缓存（Direct-Mapped Cache，$E=1$）

  • 定义与目的：每组只有一行，每个内存块在全缓存中只有唯一一个位置可放：块地址 $\bmod\ S$。极端简单、快，但容易冲突。
  • 直观解释：每个书架只有一层隔板，一本书只能放固定书架。于是两本”必须放在同一书架”的书只能轮流上架——这正是冲突未命中（conflict miss）的来源。
  • 底层机制图解：讲义用 4 位地址、$S=4,E=1,B=2$（$s=2,b=1,t=1$）演示，访存序列 $0,1,7,8,0$：
 地址 4 位:  t s s b
   0 = 0000 -> tag=0 set=0 off=0   Set0 空        -> miss  装入 M[0-1]
   1 = 0001 -> tag=0 set=0 off=1   tag 匹配,v=1   -> hit
   7 = 0111 -> tag=0 set=3 off=1   Set3 空        -> miss  装入 M[6-7]
   8 = 1000 -> tag=1 set=0 off=0   组0 现有 tag=0 -> miss  替换 -> eviction
   0 = 0000 -> tag=0 set=0 off=0   组0 现为 tag=1 -> miss  替换 -> eviction
 结果: hits:1 misses:4 evictions:2

10.2.3 组相联缓存（Set-Associative，$E>1$）与全相联（Fully Associative，$S=1$）

  • 定义与目的：一组放 $E$ 行，块可以放到组内任意一行。$E$ 越大冲突越少，但并行比较器越多、命中时间越长。$S=1$（即 $s=0$，无组索引位）就是全相联，此时地址只剩 tag\|offset 两段。
  • 直观解释：$E$ 路组相联就是”每个书架有 $E$ 层隔板”，能容忍 $E$ 本同书架的书共存；全相联则是”整馆一个大书架”，随便放——永远不会发生冲突未命中，但查找最贵。
  • 组相联的替换策略：组满时必须选一个牺牲行（victim）踢出去，称为替换（replacement）：
    • LRU（Least Recently Used，最近最少使用）：踢最久未被访问的行。命中率好，但需要为每行维护时间戳/计数器，硬件成本高。Cache Lab 用的就是 LRU。
    • LFU（Least Frequently Used）：踢访问次数最少的行。实现简单，但对”曾经很热、现在已冷”的块不友好。
    • 随机（Random）：硬件最省事，平均效果不差（现代 L3 常用伪随机）。
  • $E$ 路组相联（讲义中 $E=2$）的另一条访存序列（4 位地址，$S=2,E=2,B=2$，$s=1,b=1,t=2$），仍是 $0,1,7,8,0$：
   0 = 0000 -> set=0 tag=00  组0 空 -> miss   装入
   1 = 0001 -> set=0 tag=00  命中      -> hit
   7 = 0111 -> set=1 tag=01  组1 空 -> miss   装入
   8 = 1000 -> set=0 tag=10  组0 还有空行 -> miss 装入(不替换!)
   0 = 0000 -> set=0 tag=00  组0 里 tag=00 仍在 -> hit
 结果: hits:2 misses:3 evictions:0

同一个访问序列，直接映射是 1 命中/2 替换，2 路组相联是 2 命中/0 替换——多出来的这次命中，正是”冲突未命中”被相联度消化掉的证据。

10.2.4 查找流程图与读写策略（Lookup & Write Policy）

            CPU 发出地址 addr
                    |
                    v
  +---------------------------------------+
  | b   = log2(B)                         |
  | set = (addr >> b) & (S - 1)           |
  | tag = addr >> (s + b)                 |
  | off = addr & (B - 1)                  |
  +---------------------------------------+
                    |
                    v
  +---------------------------------------+  组内所有 E 行 tag 都不匹配
  | 选中"组 set"，对 E 行的 tag 并行比较   |------- 或 v = 0 ---------------+
  | 同时检查 v = 1                         |                                |
  +---------------------------------------+                                |
        | 有匹配且 v=1                                                     |
        v                                                                  v
  +--------------------+                          +----------------------------------+
  |   HIT 命中         |                          |   MISS 未命中                    |
  | 从块内 off 处取/   |                          | 1. 向下一级存储请求整个块        |
  | 写入该字           |                          | 2. 组满? -> 按替换策略选牺牲行   |
  +--------------------+                          |    若牺牲行 d=1 -> 整块写回内存  |
        |                                         |    (write-back)                  |
        | 读命中: 直接返回                        | 3. 装入新块, v=1, 清 d           |
        | 写命中: write-through -> 同时写下一级    | 4. 若为写未命中且 write-allocate,|
        |         write-back    -> 只写本行, d=1   |    再按"写命中"处理本次写        |
        v                                         +----------------------------------+
   (完成一次访存)

写策略的两组正交选择（讲义明确给出）：

时机 策略 含义 代价
写命中 写直达（write-through） 立刻写到下一级 每次写都产生总线/下一级流量
写命中 写回（write-back） 只改缓存行并置脏位（dirty bit），直到该行被替换才整块写回 节省流量，但需要脏位与更复杂的替换逻辑
写未命中 写分配（write-allocate） 先把块取进缓存，再在缓存里改 若后续还会写同一块则很赚
写未命中 非写分配（no-write-allocate） 直接写进下一级，不取块 避免”只写一次却要取一整块”的浪费

工程上成对出现：写直达 + 非写分配（简单，早期机器）、写回 + 写分配（现代通用处理器的 L1/L2 选择，也是 Cache Lab 模拟器必须实现的行为）。

10.2.5 Intel Core i7 的真实缓存层次

                       +---------------------------+
                       |  Core 0            Core 3 |  ...每个核内私有：
                       |  +-----+   +-----+        |   L1 i-cache 32 KB, 8-way
                       |  | Regs|   | Regs|        |   L1 d-cache 32 KB, 8-way
                       |  +--+--+   +--+--+        |   L2 unified 256 KB, 8-way
                       |  +--+--+   +--+--+        |   访问延迟 ~4 / ~10 周期
                       |  |L1i  |   |L1i  |        |
                       |  |L1d  |   |L1d  |        |
                       |  +--+--+   +--+--+        |
                       |  | L2  |   | L2  |        |
                       |  +--+--+   +--+--+        |
                       +-----+--------+------------+
                             |        |
                       +-----v--------v------------+
                       |   L3 unified 8 MB, 16-way |
                       |   所有核共享, ~40-75 周期  |
                       +-------------+-------------+
                                     |
                              +------v------+
                              | Main Memory |  ~50-200 周期
                              +-------------+
                       所有层次 block size 均为 64 B
层次 容量 相联度 块大小 组数 $S$ $s$ $b$ $t$（47 位地址）
L1 d-cache 32 KB 8 路 64 B $32768/(8\times64)=64$ 6 6 $47-6-6=35$
L1 i-cache 32 KB 8 路 64 B 64 6 6 35
L2 unified 256 KB 8 路 64 B $262144/(8\times64)=512$ 9 6 32
L3 unified 8 MB 16 路 64 B $8388608/(16\times64)=8192$ 13 6 28

讲义给出的 Core i7 L1 数据缓存例题：地址 0x00007f7262a1e010，$s=6,b=6$，则

 块偏移 = addr & 0x3F      = 0x10      (块内第 16 字节)
 组索引 = (addr >> 6) & 0x3F = 0x0     (第 0 组)
 标记   = addr >> 12       = 0x7f7262a1e

10.2.6 性能度量与 3C 未命中

  • 未命中率（miss rate） = misses / accesses = 1 − 命中率。L1 典型 3–10%，L2 常 <1%。
  • 命中时间（hit time）：把一行数据交给 CPU 的时间，含”判定是否命中”的时间。L1 约 4 周期，L2 约 10 周期。
  • 未命中惩罚（miss penalty）：主存约 50–200 周期，且趋势是变大（CPU 越快，相对差距越大）。
  • 平均访存时间：
\[AMAT = \text{命中时间} + \text{未命中率} \times \text{未命中惩罚}\]

讲义用它解释了”为什么用未命中率而不是命中率”：命中时间 1 周期、未命中惩罚 100 周期时，命中率 97% ⟹ $1+0.03\times100=4$ 周期，命中率 99% ⟹ $1+0.01\times100=2$ 周期。命中率只提高 2 个百分点，平均访存时间却快了一倍。 命中率高的区间里，它看起来”几乎一样”（97% vs 99%），而对性能的影响却是翻倍的——所以要盯住未命中率。

  • 3C 未命中（”C”指 Cache miss 的分类）：
类型 讲义定义 消除手段
强制/冷未命中（compulsory / cold） 对某块的第一次引用，缓存不可能有它 无法消除；可增大块以摊薄（一次取更多有用字节）
容量未命中（capacity） 活跃块的集合大于缓存本身（即使全相联也会发生） 增大缓存；分块（blocking）把工作集切小
冲突未命中（conflict） 缓存够大，但太多对象按放置策略映射到同一小组行上 提高相联度；调整数据布局/访问顺序

recitation 给了一个可操作的判别法：找到该块上一次被引用，数中间出现过的唯一块数——若 ≥ 缓存总行数则是容量未命中，否则是冲突未命中。

10.3 代码示例与底层机制分析

10.3.1 示例一：按行、按列、分块三种访存顺序（/tmp/cachech10/rowcol.c）

代码 (C)：

/* rowcol.c - 按行 / 按列 / 分块 三种访存顺序的性能对比
 * 编译: gcc -O2 -g -Wall -std=c11 rowcol.c -o rowcol
 */
#define _POSIX_C_SOURCE 199309L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define N 2048          /* 矩阵阶数, 2048*2048*8 = 32 MB */
#define BLK 64          /* 分块大小 */

static double *A, *B, *C;
static int *M;          /* N x N 的 int 矩阵, 16 MB */

static double now(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec * 1e-9;
}

static double sum_row(int n, int *a) {      /* stride-1 */
    long s = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) s += a[i * n + j];
    return (double)s;
}

static double sum_col(int n, int *a) {      /* stride-n */
    long s = 0;
    for (int j = 0; j < n; j++)
        for (int i = 0; i < n; i++) s += a[i * n + j];
    return (double)s;
}

static double sum_block(int n, int *a) {    /* 两个方向都 stride-1 */
    long s = 0;
    for (int ii = 0; ii < n; ii += BLK)
        for (int jj = 0; jj < n; jj += BLK)
            for (int i = ii; i < ii + BLK; i++)
                for (int j = jj; j < jj + BLK; j++) s += a[i * n + j];
    return (double)s;
}

static void mm_ijk(int n, double *a, double *b, double *c) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            double sum = 0.0;
            for (int k = 0; k < n; k++) sum += a[i * n + k] * b[k * n + j];
            c[i * n + j] = sum;
        }
}

static void mm_kij(int n, double *a, double *b, double *c) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++) {
            double r = a[i * n + k];
            for (int j = 0; j < n; j++) c[i * n + j] += r * b[k * n + j];
        }
}

static void mm_block(int n, double *a, double *b, double *c) {
    for (int kk = 0; kk < n; kk += BLK)
        for (int ii = 0; ii < n; ii += BLK)
            for (int jj = 0; jj < n; jj += BLK)
                for (int i = ii; i < ii + BLK; i++)
                    for (int k = kk; k < kk + BLK; k++) {
                        double r = a[i * n + k];
                        for (int j = jj; j < jj + BLK; j++)
                            c[i * n + j] += r * b[k * n + j];
                    }
}

int main(void) {
    M = malloc(sizeof(int) * (size_t)N * N);
    A = malloc(sizeof(double) * (size_t)N * N);
    B = malloc(sizeof(double) * (size_t)N * N);
    C = malloc(sizeof(double) * (size_t)N * N);
    if (!M || !A || !B || !C) { fprintf(stderr, "malloc failed\n"); return 1; }
    for (size_t i = 0; i < (size_t)N * N; i++) {
        M[i] = (int)(i % 7);
        A[i] = (double)(i % 13) * 0.5;
        B[i] = (double)(i % 11) * 0.25;
    }
    double t, r;
    printf("矩阵阶数 N = %d, 分块 BLK = %d\n", N, BLK);
    t = now(); r = sum_row(N, M);   printf("sum_row   : %8.4f s  (sum=%g)\n", now()-t, r);
    t = now(); r = sum_col(N, M);   printf("sum_col   : %8.4f s  (sum=%g)\n", now()-t, r);
    t = now(); r = sum_block(N, M); printf("sum_block : %8.4f s  (sum=%g)\n", now()-t, r);
    memset(C, 0, sizeof(double) * (size_t)N * N);
    t = now(); mm_ijk(N, A, B, C);  printf("mm_ijk    : %8.4f s\n", now()-t);
    memset(C, 0, sizeof(double) * (size_t)N * N);
    t = now(); mm_kij(N, A, B, C);  printf("mm_kij    : %8.4f s\n", now()-t);
    memset(C, 0, sizeof(double) * (size_t)N * N);
    t = now(); mm_block(N, A, B, C);printf("mm_block  : %8.4f s\n", now()-t);
    free(M); free(A); free(B); free(C);
    return 0;
}

【代码做什么？】

  1. sum_row 双层循环按 $i$ 外层、$j$ 内层扫描：内层 a[i*n+j] 地址连续递增，stride = 1。
  2. sum_col 交换两层循环：内层 a[i*n+j] 每次跨一整行（$2048\times4$ B $= 8$ KB），stride = n。
  3. sum_block 用 $64\times64$ 的块把整个扫描切成许多小方阵，块内两维都是 stride-1。
  4. mm_ijk / mm_kij 是讲义经典的矩阵乘法循环顺序对比；mm_block 是分块版本。

【底层机制透视】

  • sum_row：每个 32 B 缓存块装 8 个 int，一次未命中换来 8 次命中，未命中率 $= 4/32 = 1/8$（讲义把这一情形写作 miss rate = sizeof(aij)/B）。整个矩阵 16 MB，但访问是流式（streaming）的，L1 只需少量行即可，硬件预取器（prefetcher）还能提前把后面的块拉进 L2。
  • sum_col：每一步都跨 8 KB，不同行的同一列元素属于不同块，每个元素都要一次未命中，未命中率 $\approx 1$（100%）。而且 16 MB 的工作集会被预取器”越界取一整行”，反而放大了流量。
  • sum_block：块内两维都 stride-1，未命中率被压回 $1/8$，同时又保证块的工作集（$64\times64\times4=16$ KB）留在 L1（32 KB）里，把时间局部性也吃满。
  • mm_ijk：内层对 b[k*n+j] 是按列访问，按讲义的分析 $B$ 数组贡献 1.0 miss/iter；mm_kij 把内层换成对 c 和 b 的按行访问，平均 0.5 miss/iter。

【内存布局 / 数据结构图解】

 C 语言二维数组是行主序(row-major)：a[i][j] 在 a + 4*(i*N + j)

   sum_row 的访问轨迹(内存地址递增方向 --->)
   a[0][0] a[0][1] ... a[0][7] | a[0][8] ...        <- 一个块 8 个 int
   ^^^^^^^ 一次 miss，后面 7 次 hit

   sum_col 的访问轨迹(每步 +8KB)
        a[0][j]
        a[1][j]   <- +8192 B
        a[2][j]   <- +8192 B
        ...
   每一步都落在不同的块 -> 每一步都 miss

【与汇编 / 硬件的对应】（gcc -O1 -S -fno-tree-vectorize s.c 真实输出，AT&T 语法）

# ---- sum_row 的内层循环（stride = 1） ----
.L4:
        movslq  (%rax), %rcx            # 取一个 int (4 B)
        addq    %rcx, %rdx
        addq    $4, %rax                # 地址 +4 B  <-- stride-1
        cmpq    %rsi, %rax
        jne     .L4

# ---- sum_col 的内层循环（stride = n） ----
#   %r9 在外层由 salq $2, %r9 算得 = n*4
.L10:
        movslq  (%rdx), %r8             # 取一个 int (4 B)
        addq    %r8, %rcx
        addq    %r9, %rdx               # 地址 +n*4 B  <-- stride-n !!
        cmpl    %eax, %edi
        jne     .L10

两段代码的指令条数几乎一样——唯一区别是内层地址增量：addq $4, %rax 对应 stride-1 的复用（硬件缓存友好），addq %r9, %rdx 对应 stride-$n$ 的跳跃。这 8 KB 的步长，就是 25 倍性能差的全部来源。

【实测验证】（本机 AMD EPYC 7V13，gcc -O2）

矩阵阶数 N = 2048, 分块 BLK = 64
--------------------------------------------------
sum_row   :   0.0010 s  (sum=1.25829e+07)
sum_col   :   0.0259 s  (sum=1.25829e+07)     <- 慢约 26 倍
sum_block :   0.0008 s  (sum=1.25829e+07)
--------------------------------------------------
mm_ijk    :  61.9224 s                        <- 讲义说 1.25 miss/iter
mm_kij    :   5.9067 s                        <- 讲义说 0.50 miss/iter, 快 10.5 倍
mm_block  :   5.8397 s

同一程序多次重跑结果稳定（如 mm_ijk 61.33 s–61.92 s、mm_kij 5.85 s–5.93 s），循环顺序带来的 10 倍级差距不是测量噪声，而是本讲缓存模型预测的真实后果。

10.3.2 示例二：简化缓存模拟器（/tmp/cachech10/csim_demo.c）

代码 (C)：

/* csim_demo.c - 简化缓存模拟器（LRU，写回 + 写分配）
 * 用法: ./csim_demo -s <s> -E <E> -b <b> [-v] [-t tracefile]
 * 编译: gcc -O2 -g -Wall -std=c11 csim_demo.c -o csim_demo
 */
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <getopt.h>

typedef struct {                    /* 一条缓存行 */
    unsigned long tag;
    int valid;
    int dirty;
    unsigned long stamp;            /* LRU 时间戳, 越大越近 */
} line_t;

static line_t *cache;
static int S, E, B, s, b;
static unsigned long lru_counter, hits, misses, evictions;

/* 返回 1 = hit, 0 = miss; *evicted 置 1 表示本次发生了替换 */
static int access_cache(unsigned long addr, int is_write, int *evicted)
{
    unsigned long set = (addr >> b) & ((1UL << s) - 1);
    unsigned long tag = addr >> (s + b);
    line_t *base = cache + set * (long)E;
    int i, lru_way = 0;

    *evicted = 0;
    lru_counter++;
    for (i = 0; i < E; i++) {
        if (base[i].valid && base[i].tag == tag) {   /* 命中 */
            base[i].stamp = lru_counter;
            if (is_write) base[i].dirty = 1;
            hits++;
            return 1;
        }
        if (base[i].stamp < base[lru_way].stamp) lru_way = i;
    }
    misses++;                                        /* 未命中 */
    for (i = 0; i < E; i++)
        if (!base[i].valid) { lru_way = i; break; }
    if (base[lru_way].valid) {                       /* 需要替换 */
        evictions++;
        *evicted = 1;
        if (base[lru_way].dirty)
            printf("        [dirty eviction: 把整块写回内存]\n");
    }
    base[lru_way].valid = 1;
    base[lru_way].tag = tag;
    base[lru_way].dirty = is_write;                  /* 写分配: 装入即置脏 */
    base[lru_way].stamp = lru_counter;
    return 0;
}

/* 处理一条 trace: " L 10,1" / "M 20,1" / "S 18,1" */
static void do_trace(const char *op, unsigned long addr, int size, int verbose)
{
    int is_write = (op[0] == 'S' || op[0] == 'M');
    int r, evicted;

    if (op[0] == 'M') {                              /* 修改 = 读 + 写 */
        r = access_cache(addr, 0, &evicted);
        if (verbose) printf(" %c %lx,%d %s%s", op[0], addr, size,
                            r ? "hit" : "miss", evicted ? " eviction" : "");
        r = access_cache(addr, 1, &evicted);
        if (verbose) printf(" %s\n", r ? "hit" : "miss");
    } else {
        r = access_cache(addr, is_write, &evicted);
        if (verbose) printf(" %c %lx,%d %s%s\n", op[0], addr, size,
                            r ? "hit" : "miss", evicted ? " eviction" : "");
    }
}

int main(int argc, char *argv[])
{
    int opt, verbose = 0;
    const char *tracefile = NULL;

    s = E = b = -1;
    while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
        switch (opt) {
        case 'v': verbose = 1; break;
        case 's': s = atoi(optarg); break;
        case 'E': E = atoi(optarg); break;
        case 'b': b = atoi(optarg); break;
        case 't': tracefile = optarg; break;
        default:  return 1;
        }
    }
    if (s < 0 || E <= 0 || b < 0) return 1;
    S = 1 << s;  B = 1 << b;
    cache = calloc((size_t)S * E, sizeof(line_t));
    if (!cache) return 1;
    printf("cache: S=%d sets, E=%d ways, B=%d bytes (C=%d bytes)\n\n",
           S, E, B, S * E * B);

    if (tracefile) {
        FILE *fp = fopen(tracefile, "r");
        char op[8]; unsigned long addr; int size;
        if (!fp) { perror("fopen"); free(cache); return 1; }
        while (fscanf(fp, "%7s %lx,%d", op, &addr, &size) == 3) {
            if (op[0] == 'I') continue;              /* 忽略取指 */
            do_trace(op, addr, size, verbose);
        }
        fclose(fp);
    } else {                                         /* 内置讲义 trace */
        unsigned long addrs[] = {0, 1, 7, 8, 0};
        for (unsigned i = 0; i < sizeof(addrs)/sizeof(addrs[0]); i++) {
            if (verbose) printf(" L %lx,1 ", addrs[i]);
            do_trace("L", addrs[i], 1, 0);
            if (verbose) printf("\n");
        }
    }
    printf("hits:%lu misses:%lu evictions:%lu\n", hits, misses, evictions);
    free(cache);
    return 0;
}

【代码做什么？】

  1. getopt 解析 -s/-E/-b/-t/-v，与 csim-ref 的接口完全一致（这正是 Part A 的接口要求）。
  2. 用 calloc 分配 $S\times E$ 个 line_t，下标为 set*E + way，组内 $E$ 行在一块连续内存里（便于”并行比较”的抽象）。
  3. access_cache：先由 (addr>>b) & (S-1) 求组号、addr>>(s+b) 求标记，然后线性扫描组内 $E$ 行找匹配；命中就刷新 LRU 时间戳。
  4. 未命中时先看有没有无效行（!valid）可直接占用，否则选 stamp 最小的行作为牺牲行；若该行 dirty，打印一条”脏替换”提示，模拟把整块写回内存。
  5. do_trace 把 M（modify）展开成”读一次 + 写一次”，这正是 Lab 文档强调的语义：“An M operation can result in two cache hits, or a miss and a hit plus a possible eviction.”
  6. I（instruction load）被直接 continue 跳过——Lab 只关心数据缓存。

【底层机制透视】

  • LRU 用时间戳数组而不是链表：全局 lru_counter 单调递增，每次访问把命中行/新装入行的 stamp 置为当前计数值；选牺牲行时取 stamp 最小者。这样每次访存是 $O(E)$，且不需要维护指针——这正是 Part A 推荐的实现方式（讲义 recitation 里称为 lru_counter 方案）。
  • 注意 lru_way 的初值：初始 lru_way = 0，如果组内有多个无效行，第一次扫描结束时会选中”stamp 最小”的那一行，随后被”找无效行”的循环覆盖。只有当组满时才真正按 LRU 替换——这就是”未命中但无替换”与”未命中且替换”的区别，也是 misses 与 evictions 会分开统计的原因。
  • 写分配 + 写回的体现：写未命中会把它当读未命中一样装块（miss++），并把新行的 dirty 置 1；写命中只改 dirty，不产生任何额外计数。

【内存布局 / 数据结构图解】

 cache 数组（S=4, E=2 时的实际内存布局，每个 line_t 24 B 打包前）

  下标 0  set0 way0 : tag=..., v=1, d=0, stamp=7
  下标 1  set0 way1 : tag=..., v=1, d=0, stamp=3   <- stamp 最小 => 牺牲行
  下标 2  set1 way0 : tag=..., v=0, d=0, stamp=0   <- v=0 优先占用
  下标 3  set1 way1 : tag=..., v=1, d=1, stamp=9   <- d=1, 被替换时要写回
  ...
  组 set 的首地址 = cache + set * E

 4 位地址 s=2,b=1 时:
      addr = 0 1 0 1
             t t s s b
                 ^^^ -> set = (addr>>1)&0b11
       tag = addr>>3

【与汇编 / 硬件的对应】：真实硬件里，组选择由 addr[s+b-1:b] 直接驱动 SRAM 的字线（word line），$E$ 个 tag 比较器并行工作，命中信号经 OR 门合成。软件里无法直接看到这个过程，但 perf stat -e cache-misses 读到的正是同一套硬件计数器。

【实测验证】（真实运行输出）

$ ./csim_demo -s 2 -E 1 -b 1 -v          # 直接映射: S=4, E=1, B=2
cache: S=4 sets, E=1 ways, B=2 bytes (C=8 bytes), s=2 E=1 b=1
 L 0,1
 L 1,1
 L 7,1
 L 8,1
 L 0,1
hits:1 misses:4 evictions:2

$ ./csim_demo -s 1 -E 2 -b 1 -v          # 2 路组相联: S=2, E=2, B=2
cache: S=2 sets, E=2 ways, B=2 bytes (C=8 bytes), s=1 E=2 b=1
hits:2 misses:3 evictions:0

$ ./csim-ref  -s 4 -E 1 -b 4 -t yi.txt   # 与官方参考模拟器对照
hits:4 misses:5 evictions:3
$ ./csim_demo -s 4 -E 1 -b 4 -t yi.txt
        [dirty eviction: 把整块写回内存]
hits:4 misses:5 evictions:3              # 计数完全一致

10.3.3 示例三：$64\times64$ 转置的特殊分块法（trans.c）

Part B 要求 transpose_submit 在 $(s=5,E=1,b=5)$ 的直接映射缓存（32 组、1 行/组、32 B 块 = 8 个 int）上把未命中数压到阈值以下。关键在于：64 个 int 一行的字节数是 $64\times4=256$ B $= 8$ 个块 $= 8$ 个组，而整个缓存只有 32 组。

 64x64 int 矩阵, 一行 = 256 B = 8 个 32 B 块
     块号:  8i+0  8i+1 ... 8i+7        组号 = 块号 mod 32 = (8i + t) mod 32
           所以第 i 行占用的组集合随 i 每 4 行重复一次！

 8x8 tile 的行 i0..i0+7 映射到的组:  8*i0+m, 8*(i0+1)+m, ..., 8*(i0+7)+m  (mod 32)
   u=0 和 u=4 -> 同一组!
   u=1 和 u=5 -> 同一组!
   u=2 和 u=6 -> 同一组!
   u=3 和 u=7 -> 同一组!
 => 一个 8x8 tile 的 8 行只落在 4 个组上, 每组挤 2 行。
    而 A 的 tile 与 B 的 tile (若基址对齐相同) 落在同样的 4 个组 => 直接映射下灾难。

这就是朴素 8×8 分块在 64×64 上完全失效的原因（实测未命中 4724，与不做分块的朴素转置完全相同）。解法是：把每个 8×8 tile 再拆成四个 4×4 子块，用 8 个局部变量（寄存器）做中转。

   A 的 8x8 tile (行 i0..i0+7, 列 j0..j0+7)      B 的 8x8 tile (行 j0..j0+7, 列 i0..i0+7)
            列 j0    列 j0+4                              列 i0    列 i0+4
          +--------+--------+                          +--------+--------+
   行 i0  |  A_TL  |  A_TR  |                   行 j0  | B_TL   | B_TR   |
          |  4x4   |  4x4   |                          | =A_TL^T| =A_BL^T|
          +--------+--------+                          +--------+--------+
 行 i0+4  |  A_BL  |  A_BR  |                 行 j0+4  | B_BL   | B_BR   |
          |  4x4   |  4x4   |                          | =A_TR^T| =A_BR^T|
          +--------+--------+                          +--------+--------+

  步骤 1: 读 A 第 i 行 (j0..j0+7) -> 8 个寄存器 v0..v7      [i = i0..i0+3]
          B[j0+0..3][i]   = v0..v3      (B_TL 象限, 正式的转置值)
          B[j0+0..3][i+4] = v4..v7      (B_TR 象限的"暂存区", 尚未转置)
          <<< 8 个 int 正好凑满一条 32 B 缓存行: 1 次 miss 换 8 个寄存器 >>>
  步骤 2: 对 k = i0..i0+3:
          a0..a3 = B[k][i0+4..i0+7]      (读回暂存区 = A_TR 的原始数据)
          a4..a7 = A[i0+4..i0+7][k]      (A_BL 的一列, 正是 B_TR 需要的)
          B[k][i0+4..i0+7]   = a4..a7    (B_TR 象限 = A_BL^T)
          B[k+4][i0+0..i0+3] = a0..a3    (B_BL 象限 = A_TR^T)
  步骤 3: A_BR -> B_BR: for k = i0+4..i0+7:
          B[j0+4..j0+7][k] = A[k][j0+4..j0+7]

核心思想：A 的每个 4×4 子块和 B 的对应 4×4 子块会争同一批组，所以绝不能”读一个、写一个”交替进行；必须先把整行 8 个 int 一次性读进寄存器（8 个变量刚好覆盖一条缓存行），再集中写 B，并且借用 B 自己的一块区域当临时仓库做 A_TR 与 A_BL 的对调。

【实测验证】（本机真实跑通官方 tracegen + csim-ref，s=5,E=1,b=5）

$ ./test-trans -M 32 -N 32
func 1 (naive row-wise):                    hits:869,  misses:1184, evictions:1152
func 2 (8x8 blocking, diagonal-aware):      hits:1765, misses:288,  evictions:256
$ ./test-trans -M 64 -N 64
func 1 (naive row-wise):                    hits:3473, misses:4724, evictions:4692
func 2 (8x8 blocking, diagonal-aware):      hits:3585, misses:4612, evictions:4580
func 3 (64x64 8x8 with four 4x4 sub-blocks):hits:9017, misses:1228, evictions:1196
Summary for official submission: correctness=1 misses=1228      # 阈值 < 1300 ✓
$ ./test-trans -M 61 -N 67
func 3 (61x67 blocked with margins):        hits:6186, misses:1993, evictions:1961
Summary for official submission: correctness=1 misses:1993      # 阈值 < 2000 ✓

$64\times64$ 的理论下界是 $2\times(64\times64/8)=1024$ 次强制未命中（A、B 各 512 块），实测 1228 只多出 204 次冲突未命中。$32\times32$ 用 8×8 分块并对对角块额外处理（先读满 8 个再写，避免 A、B 同行同列争夺同一组）得到 288（阈值 <300）；$61\times67$ 因为不是 8 的倍数、组数多，用 $16\times16$ 分块并把边界用 && 判据逐行裁剪即可到 1993。

10.3.4 存储器山（The Memory Mountain）

mountain 程序测的是读吞吐率（read throughput / read bandwidth，MB/s）随工作集大小 size 与步长 stride 的二维变化；对每个 (size, stride) 先跑一次预热缓存，再跑一次计时。讲义的核心函数用 4×4 循环展开：

long data[MAXELEMS];
int test(int elems, int stride) {
    long i, sx2 = stride*2, sx3 = stride*3, sx4 = stride*4;
    long acc0 = 0, acc1 = 0, acc2 = 0, acc3 = 0;
    long length = elems, limit = length - sx4;
    for (i = 0; i < limit; i += sx4) {          /* 一次合并 4 个元素 */
        acc0 = acc0 + data[i];
        acc1 = acc1 + data[i+stride];
        acc2 = acc2 + data[i+sx2];
        acc3 = acc3 + data[i+sx3];
    }
    for (; i < length; i++) acc0 = acc0 + data[i];
    return ((acc0 + acc1) + (acc2 + acc3));
}

   读吞吐率
    (MB/s)
      ^
 14000|#####
      |#####
 12000|#####
      |#####
 10000|#####*****
      |#####     *****
  8000|#####          *****
      |#####               *****
  6000|#####                    *****=====
      |#####                         =====
  4000|#####                              =====
      |#####                                   =====
  2000|#####                                        =====##########
      |#####                                             ##########
     0+-----+-----+-----+-----+-----+-----+-----+-----+--------------> Size
         32k  64k  128k 256k 512k  1m    2m    4m    8m  16m  32m 128m
          |         |              |                   |
          |<-- L1 -->|<---- L2 ---->|<------ L3 ------->|<-- 主存 -->|
          32 KB      256 KB          8 MB

      图例: "山脊"(ridges of temporal locality) 沿 size 方向 ——
            每跨过一级缓存容量就掉一个台阶:
              < 32 KB   : L1 平台, 吞吐最高
              32K - 256K: L2 平台
              256K - 8M : L3 平台
              > 8 MB    : 主存平台, 吞吐最低
            "山坡"(slopes of spatial locality) 沿 stride 方向 ——
              stride 越小吞吐越高; 若 stride 以 8 B 为单位,
              未命中率 = stride/8, stride >= 8 时未命中率 = 1.0,
              吞吐出现"悬崖"。

讲义还指出：现代 CPU 的激进预取（aggressive prefetching）会把”悬崖”变形，2018 年前的 Core 2 Duo（无预取）的”山”更规整，而 Haswell 的山在 stride=8 附近仍有较高的吞吐——预取器替你把下一块提前拉进来了。

【实测验证】 本机把同样的 test() 遍历缩小规模跑了一遍（AMD EPYC 7V13，每核 L1d 32 KB、L2 512 KB，16 核共享 L3 32 MB），读吞吐率（MB/s）如下表——台阶位置与本机缓存容量一一对应，正是讲义那座”山”的局部切片：

 size\stride      1       2       4       8      16
      16K    80638   68292   52230   39847   26223   <- L1 内, 全速; 差距 3.1 倍
      64K    93254   88640   80628   68289   52234
     256K    97054   95783   93270   88615   80663
    1024K    98100   97660   97118   95810   93293   <- L2 之外
    4096K    98370   98259   98072   97801   97105
   16384K    98417   98441   98326   98306   98144   <- 远超所有缓存, 几乎不随 stride 变化

两个现象与讲义完全一致：(1) 沿 size 增大方向吞吐单调下降（山脊，16 KB 时的 8 万 MB/s 看似低于 1 MB 时的 9.8 万，是因为 16 KB 工作集全部落在 L1 但循环太短、启动开销不可忽略）；(2) 沿 stride 增大方向吞吐下降（山坡），在 16 KB 工作集上 stride=1 与 stride=16 相差 3.1 倍。而 16 MB 那一行几乎不随 stride 变化（98417 → 98144），因为数据总量已远超缓存、且预取器把大 stride 的访问也提前拉了进来——讲义标注的 “aggressive prefetching” 说的就是这种失真：它让”山坡”在末端变平了。

10.4 实验关联

L4 Cache Lab，两部分都直接来自本讲：

Part A — 写缓存模拟器 csim.c（27 分）

  • 接口：./csim [-hv] -s <s> -E <E> -b <b> -t <tracefile>，输出格式必须是 hits:H misses:M evictions:E；必须调用 printSummary(hit_count, miss_count, eviction_count)。
  • 输入是 valgrind（lackey 工具）产生的 trace：I（取指，必须忽略）、L（数据读）、S（数据写）、M（数据修改，等价于一次读加一次写）。格式为 [空格]op 地址,长度，注意 I 前没有空格、L/M/S 前有空格——文件里第 0 列是不是空格，恰好可以拿来区分。
  • 因为假设访存不跨块边界，size 字段可以直接忽略。
  • 编译必须 -Wall -Werror 零警告；数据结构要用 malloc 动态分配（缓存参数是运行时给的）。
  • 讲义给出的 8 个测试用例（前 7 个 3 分、最后一个 6 分），实测样例：
./csim -s 1 -E 1 -b 1 -t traces/yi2.trace    -> hits:9   misses:8   evictions:6
./csim -s 4 -E 2 -b 4 -t traces/yi.trace     -> hits:4   misses:5   evictions:2
./csim -s 2 -E 1 -b 4 -t traces/dave.trace   -> hits:2   misses:3   evictions:1
./csim -s 5 -E 1 -b 5 -t traces/trans.trace  -> hits:231 misses:7   evictions:0
./csim -s 5 -E 1 -b 5 -t traces/long.trace   -> hits:265189 misses:21775 evictions:21743

Part B — 优化 transpose_submit（26 分）

  • 评测缓存固定为 $(s=5,E=1,b=5)$，用 valgrind 抽取 trace 后交给参考模拟器统计。
  • 三条硬性约束：每个转置函数最多 12 个 int 局部变量（跨辅助函数累计）、不得定义数组 / 不得用 malloc / 不得递归 / 不得改 A、编译零警告。局部数组被禁的原因是 valgrind 产生的栈访问会被过滤掉，课程希望你把注意力放在 A、B 两个数组的访问模式上。
  • 阈值：$32\times32$ 未命中 <300 得 8 分（>600 得 0）；$64\times64$ <1300 得 8 分（>2000 得 0）；$61\times67$ <2000 得 10 分（>3000 得 0）。
  • 调参建议：./test-trans -M 64 -N 64 会写出 trace.f0，再用 ./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0 逐条查看命中/未命中/替换，对照矩阵状态图就能定位是哪个 tile 在互相驱逐。
  • 本讲最容易踩的坑：$32\times32$ 用 8×8 分块时对角块（$i=j$ 的那些 tile）会让 A 与 B 同时争同一批组，必须把一整行 8 个 int 先读进寄存器再写，才能把未命中从 344 降到 288。$64\times64$ 若只用朴素 8×8 分块，结果与不做分块一模一样（都是 4724），必须有 4×4 子块 + 8 个局部变量这一层。

10.5 常见错误与调试技巧

  • 忽略 M 的双重访存语义：把 M 当成一次访问，导致 hits/misses 各少算一次。调试：用 ./csim-ref -v 对照你 -v 的输出，注意 M 那一行会打印两次结果（如 M 12,1 miss eviction hit）；一个 M 最多带来”1 miss + 1 hit”外加一次 eviction。
  • 误把 I 行计入数据缓存：trace 里 I 行没有前导空格，sscanf 若用宽松格式会把它们吃进来。调试：在解析循环里加 if (op[0]=='I') continue;，并统计跳过的行数与 trace 中 I 行数是否一致（grep -c '^I ' traces/*.trace）。
  • lru_way 初值导致”必然替换”：若 lru_way 初值指向一个无效行却仍走替换分支，evictions 会虚高。调试：先用 -s 5 -E 1 -b 5 -t traces/trans.trace 验证 evictions:0（此时只有 7 次未命中、远未填满），若你的输出出现 eviction 说明替换逻辑有 bug。
  • 位运算溢出 / 移位数不当：(1UL << s) - 1 写成 (1 << s) - 1 在 $s\ge31$ 时有 UB。调试：-fsanitize=undefined 编译一次，或 gcc -Wall -Wextra 看 shift 警告。
  • 64×64 转置的”行内冲突”：只用朴素 8×8 分块时未命中恒为 4724（与朴素转置相同）。诊断命令：./test-trans -M 64 -N 64 看 func 行；再用 ./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0 \| head -40 观察是否每读一次 A 就紧跟一次 B 的 eviction。
  • 数组越界却”看似正确”：$61\times67$ 或 $32\times32$ 的边界 tile 若忘记 k < N && l < M，会越界写坏相邻数据。调试：valgrind --tool=memcheck ./test-trans -M 61 -N 67，或 gcc -fsanitize=address 重编译 tracegen。
  • 只看命中率不看访存延迟：优化后命中率从 97% 升到 99%，有人以为”只提升 2%”。调试：改用 AMAT = 1 + 0.01×100 = 2 vs 1 + 0.03×100 = 4 来沟通收益；或在真机上用 perf stat -e L1-dcache-loads,L1-dcache-load-misses,cache-misses ./a.out 直接读硬件计数器。
  • 忘记 -Werror：Makefile 用 -Werror -std=c99，一个未使用变量就编不过。调试：本地先 gcc -Wall -Werror -std=c99 -m64 -c csim.c 单独编译。

10.6 关键要点

  • 缓存的全部行为都由地址位决定：$C=S\times E\times B$、$s=\log_2 S$、$b=\log_2 B$、$t=m-s-b$，”组索引用地址中段”是为了让相邻块落到不同组、从而吃满空间局部性；若改用高位索引，stride-1 的程序会疯狂冲突。
  • 未命中率比命中率更能说明性能：$AMAT=\text{hit time}+\text{miss rate}\times\text{miss penalty}$，而 miss penalty 高达 50–200 周期，命中率从 97% 到 99% 会让 AMAT 直接减半。
  • 3C 各有各的药：强制未命中靠”增大块”摊薄、容量未命中靠”分块”切小工作集、冲突未命中靠”提高相联度或改访问顺序”。
  • 写策略是成对选择的：写直达 + 非写分配简单但费流量；写回 + 写分配省流量但需要脏位。现代处理器的 L1/L2 走后者，Cache Lab 也要求实现后者。
  • 循环顺序就是性能：ijk（1.25 miss/iter）平均比 kij（0.5 miss/iter）慢 10 倍以上（本机实测 61.9 s vs 5.9 s）；把内层循环改成 stride-1 往往是零成本的十倍提速。
  • 分块把 $\Theta(n)$ 的未命中降到 $\Theta(1/n)$：无分块时 $n^3$ 次乘法伴随 $(9/8)n^3$ 次未命中，分块（$3B^2<C$，两块输入 + 一块输出同时驻留）后降到 $n^3/(4B)$；$B$ 取满足 $3B^2<C$ 的最大值。
  • $64\times64$ 转置的教训：当矩阵行字节数恰好是缓存容量的整数倍关系时，任何”规整”的分块都会出现 A、B 组冲突，必须用寄存器当暂存区、借 B 自身当临时仓库做象限对调——这是把缓存参数（$s=5,b=5$，一行 8 块=8 组）算清楚之后才能想到的技巧。

10.7 思考题（带答案）

题 1（计算题：地址位域划分 + 手算未命中率）

某 32 位地址机器上的数据缓存：容量 32 KB、8 路组相联、块大小 64 B。现有访问序列（地址为十六进制，每次访问 1 字节，初始缓存全空，LRU 替换）：

L 0x0000
L 0x0040
L 0x0080
L 0x00C0
L 0x0100
L 0x0000

(1) 求 $S,s,b,t,E,e$ 以及 $t$ 的位数。 (2) 逐步写出每次访问的 set / tag / 命中情况，统计 hits、misses、evictions。 (3) 若把相联度改为 $E=1$（保持容量与块大小不变），结果会怎样变化？说明了什么？

答案：

(1) $B=64 \Rightarrow b=6$；$S = C/(E\times B) = 32768/(8\times64) = 64 \Rightarrow s=6$；$E=8 \Rightarrow e=3$；$t = 32-6-6 = 20$。

(2) 块偏移取低 6 位（地址低 6 位都是 0），组索引取第 6–11 位，标记取第 12–31 位：

 地址      二进制(低位示意)   set = (a>>6)&0x3F   tag = a>>12   结果
 0x0000    ...0000 0000 0000     0                 0x0         miss (set0 空)
 0x0040    ...0000 0001 0000     1                 0x0         miss (set1 空)
 0x0080    ...0000 0010 0000     2                 0x0         miss (set2 空)
 0x00C0    ...0000 0011 0000     3                 0x0         miss (set3 空)
 0x0100    ...0000 0100 0000     4                 0x0         miss (set4 空)
 0x0000    ...0000 0000 0000     0                 0x0         HIT  (set0 里 tag0 仍在)
 合计: hits:1  misses:5  evictions:0

6 次访问用了 5 个不同的组（0,1,2,3,4），组内都只有 1 行被占用，远未填满 8 路，没有任何替换。

(3) 改为 $E=1$ 时 $S = 32768/64 = 512 \Rightarrow s=9$，$t = 32-6-9 = 17$。此时组索引变成第 6–14 位：

 0x0000 -> set 0, tag 0
 0x0040 -> set 1, tag 0
 0x0080 -> set 2, tag 0
 0x00C0 -> set 3, tag 0
 0x0100 -> set 4, tag 0
 0x0000 -> set 0, tag 0  -> HIT (仍然命中!)
 合计: hits:1 misses:5 evictions:0   (与 E=8 相同)

结论：本例中 5 个地址分散在 5 个不同的组，不构成冲突，所以相联度高低对结果没有影响——这正说明”提高相联度只对冲突未命中有效”。真正的对照组是 10.2.3 节那组 4 位地址实验：$S=4,E=1$ 时 0,1,7,8,0 得 1 命中/2 替换，$S=2,E=2$ 时同一序列得 2 命中/0 替换，多出来的那次命中就是被相联度吸收掉的冲突未命中。

题 2（计算题：AMAT）

三级存储层次：L1 命中时间 1 周期；L1 未命中率 10%；L2 命中时间 10 周期；L2 的局部未命中率 20%（即 L1 未命中中有 20% 在 L2 也失败）；主存访问 200 周期。

(1) 求 AMAT。 (2) 若通过分块把 L1 未命中率降到 5%（L2 局部未命中率不变），AMAT 变成多少？相对提升多少？ (3) 若只把 L2 局部未命中率从 20% 降到 5%（L1 未命中率仍为 10%），AMAT 变成多少？哪一项更值得优化？

答案：

(1) L1 未命中的代价是”访问 L2 的代价”，即

\[AMAT = 1 + 0.10\times\bigl(10 + 0.20\times200\bigr) = 1 + 0.10\times50 = 6\ \text{周期}\]

(2) $AMAT = 1 + 0.05\times50 = 3.5$ 周期，相对提升 $6/3.5 \approx 1.71$ 倍（时间下降 41.7%）。

(3) $AMAT = 1 + 0.10\times(10 + 0.05\times200) = 1 + 0.10\times20 = 3$ 周期，相对提升 $6/3 = 2$ 倍（时间下降 50%）。

倾向性结论：本例中优化 L2 的局部未命中率收益更大（3 周期 vs 3.5 周期），因为它削减的是被 200 周期惩罚放大的那一项。但工程上更常见的做法是先优化 L1（分块、循环重排都是零成本改动），因为 $0.10\times50$ 里的 0.10 通常是程序员唯一能直接控制的因子。

题 3（”直观但错误的想法”）

同学 A 说：”既然缓存有 32 KB，我的 $64\times64$ 矩阵一共才 16 KB，完全可以全放进缓存，所以转置时怎么写都不会有冲突未命中。”同学 B 说：”那我只要把块大小从 64 B 调到 8 KB，一次取一整行，stride-$n$ 的遍历也不会未命中了。”

请分别指出两人的错误。

答案：

  • 同学 A 错在忽略了相联度。这 16 KB 是能装下，但 $(s=5,E=1,b=5)$ 的缓存只有 32 组、每组 1 行：组号 $=\lfloor addr/32\rfloor \bmod 32$，所以地址相差 $32\times32=1024$ 字节的两个块必然落在同一组。$64\times64$ 矩阵一行 256 B = 8 个块占 8 个连续组，第 $i$ 行与第 $i+4$ 行落同一批组（本讲 10.3.3 节有完整推导）。容量够 ≠ 不冲突，这正是 conflict miss 的定义：”缓存够大，但太多对象映射到同一小组行上”。实测：朴素的 8×8 分块在 $64\times64$ 上仍是 4724 次未命中，和完全不分块一样。
  • 同学 B 错在混淆了”块大小”与”缓存容量”。把 $B$ 从 64 B 提高到 8 KB 会把 $S = C/(E\times B)$ 从 64 降到 0.5——缓存根本装不下几行，块变大是以”行数变少”为代价的。而且块太大时，stride-$n$ 的遍历每次只用一个字节、其余全浪费，空间局部性并没有真正利用起来；同时块传输时间变长（”一次取一整行”要占满总线）。正确做法是分块（blocking）：不改缓存参数，而是改程序的访问顺序，让工作集在现有缓存容量内被重复使用。

题 4（”直观但错误的想法”）

“写直达（write-through）每次写都要访问内存，肯定比写回（write-back）差，所以写回永远是更好的选择。”这个说法错在哪？

答案：错在把”流量”当成唯一成本。

  1. 写回需要脏位与更复杂的替换逻辑：每行多一个 d 位，替换时必须先判断”是否是脏行”、必要时整块写回，控制器状态机比写直达复杂；写直达行则永远可以随意丢弃。
  2. 写回的收益依赖”写局部性”：只有当同一行的多个字被反复改写时，写回才省流量（多次写合并成一次块写回）。若程序是”写遍全表、每个字只写一次”的流式写（如大规模 memset、流式拷贝），写回反而要先把整块读进来（写分配），再整块写回去，流量翻倍——这类场景写直达 + 非写分配更合适。
  3. 多级一致性：写回意味着下层可能持有过期副本，多核/多级缓存之间需要额外的失效与监听（snooping）协议；写直达则天然让下层保持最新（代价是流量）。
  4. 讲义给出的正是这两种成对的典型组合——写直达 + 非写分配（简单、适合流式写）与写回 + 写分配（现代通用处理器 L1/L2 的选择）。把”写回总是更好”绝对化，会漏掉”写回必须搭配写分配、且依赖写局部性”这个前提。Cache Lab 的模拟器选择实现后者，只是因为它更复杂、更有教学价值，不是因为它在所有场景下都更快。