The Memory Hierarchy

一个矛盾：CPU 很快，内存跟不上。Cache 就夹在 CPU 和内存之间，保存最近可能用到的数据。

1. Load、Store 与主存

1 2	movq 8(%rsp), %rax # load：内存 -> 寄存器 movq %rax, 8(%rsp) # store：寄存器 -> 内存

CPU 真正计算时用的是寄存器，内存负责放数据。大致过程：

1	内存 -> 寄存器 -> ALU -> 寄存器 -> 内存

1 2	SRAM：快、贵、不用刷新，通常拿来做 Cache DRAM：慢一些、便宜、需要刷新，通常拿来做主存

2. Locality：局部性

Cache 能起作用，是因为程序访问地址通常不是乱跳的。

时间局部性：刚用过的数据很可能马上再用，例如循环中的 sum。
空间局部性：用了某个地址，很可能接着用旁边的地址，例如 a[0]、a[1]、a[2]。

C 的二维数组按行连续存放：

1 2	按行：a[0][0] -> a[0][1] -> a[0][2] 按列：a[0][0] -> a[1][0] -> a[2][0]

所以按行走通常更快。按列走每次跨过一整行，stride 比较大。

3. Memory Hierarchy

1 2	寄存器 -> L1 -> L2 -> L3 -> DRAM -> SSD 更快、更小更慢、更大

上面一层保存下面一层的一小部分。程序希望多数访问停在上面几层，不要每次都跑到 DRAM。

4. Cache 的基本概念

1 2	cache hit：数据已经在 Cache 中 cache miss：数据不在，要去下一层拿

Cache 搬数据不是一个字节一个字节搬，而是一次搬一个 block。第一次读 a[0] 时，旁边几个元素也可能一起进来，后面读 a[1] 就有机会 hit。

三种 miss：

1
2
3

cold miss：第一次访问，Cache 里本来就没有
capacity miss：最近常用的数据太多，Cache 放不下
conflict miss：总容量也许够，但几个 block 偏偏映射到同一个位置

Working set 就是程序这一小段时间正在频繁使用的数据。它能塞进 Cache，运行一般就比较顺。

Cache Memories

1. Cache 组织方式：S、E、B

General Cache Organization (S, E, B)

1
2
3

S：一共有多少个 set
E：每个 set 有多少条 line
B：每条 line 能装多少字节的 block data

例如 S = 4, E = 2, B = 8：4 个 set，每个 set 2 条 line，每条 line 装 8 字节数据。

1.1 Cache line

1	valid bit \| tag \| block data

1
2
3

valid bit：这条 line 现在有没有有效数据
tag：这条 line 里装的是内存中的哪一个 block
block data：真正的数据

这里我之前容易把 line 和 block 混在一起：

1 2	line 是 Cache 中的一个槽位 block 是从内存搬进这个槽位的一整块数据

判断 hit 要同时满足：

1	valid = 1 && tag 匹配

Cache 数据容量：

1	C = S x E x B

这里只算 block data，不算 valid、tag 和 dirty bit。

1.2 地址拆分

一个地址直接拆成三段：

1	tag \| set index \| block offset

我的记法：

1
2
3

set index：先去第几个 set，不用比较
tag：到了 set 以后，确认是不是我要的 block，需要比较
block offset：已经找到 block，再取里面第几个字节

例如 B = 64 = 2^6 bytes，就需要 6 个 offset bit，表示 block 中的第 0～63 个字节。

2. Cache Read

CPU 读一个地址时：

地址拆成 tag | set index | block offset
              |
              v
用 set index 找 set
              |
              v
检查 valid bit，再比较 tag
              |
       +------+------+
       |             |
     匹配           不匹配
      hit             miss
       |
用 offset 取具体字节

所以 set index 只是定位；真正判断“是不是这块内存”的是 valid bit 和 tag。

3. Direct-Mapped Cache

Direct-Mapped Cache 就是 E = 1：

Set 0: [line]
Set 1: [line]
Set 2: [line]
Set 3: [line]

每个 block 只能去唯一的 set，而且这个 set 里只有一个位置。两个 block 如果 set index 相同，只能互相顶掉，这就是 conflict miss。

4. E-way Set Associative Cache

E > 1，一个 set 里可以有多个位置：

1 2	Set 0: [line 0] [line 1] ... Set 1: [line 0] [line 1] ...

set index 还是只负责找到 set。找到后，要把 tag 和里面 E 条 line 都比较一次，只要一条满足 valid && tag_match 就 hit。

miss 后：

1 2	有 invalid line：直接放进去已经放满：选一条替换，常见有 LRU、Random、FIFO

E 越大越不容易互相顶掉，但硬件要同时比较更多 tag。

5. Cache Simulation

例子：

1 2	4-bit address S = 4，E = 1，B = 2 bytes

先算地址各部分占几位：

s = log2(S) = 2
b = log2(B) = 1
t = 4 - s - b = 1

tag(1) | set index(2) | block offset(1)

访问 0, 1, 7, 8, 0：

地址	二进制	tag	set	offset	结果
0	0000	0	00	0	miss，加载 `M[0-1]`
1	0001	0	00	1	hit
7	0111	0	11	1	miss，加载 `M[6-7]`
8	1000	1	00	0	miss，顶掉 `M[0-1]`
0	0000	0	00	0	miss，再顶回来

B = 2 bytes，所以一个 block 里确实有两个字节。只需要 1 个 offset bit，就能用 0/1 区分这两个位置。因此地址 0 和 1 属于同一个 block，先访问 0 后再访问 1 会 hit。

地址 0 和 8 的 set index 都是 00，但 tag 不同。因为这里 E = 1，它们会在 Set 0 里互相替换。

6. 写操作与 dirty bit

读操作只要把数据拿到 CPU。写操作多一个问题：Cache 改了，内存什么时候改？

6.1 Write hit

目标 block 已经在 Cache 中，有两种做法：

1 2	write-through：改 Cache，同时立刻改下一级存储 write-back：只改 Cache，等 line 被替换时再写回

write-through 简单，但是每次 store 都会占用总线。write-back 可以把同一个 block 的多次修改合成一次写回，但此时 Cache 和内存可能不一样，所以要加 dirty bit：

valid bit | dirty bit | tag | block data

dirty = 0：没有欠下一级存储更新，可以直接替换
dirty = 1：Cache 里是新数据，替换前必须先写回

这个trade-off在 RoCC 卷积加速器时类似：每算出一个结果就 DMA 写回，逻辑简单，但小块写太密会占总线；先存在 BRAM 或寄存器堆里，攒一批再 burst 出去，事务会少很多。只是思路相似，并不等于 CPU Cache 的 write-back。

6.2 Write miss

目标 block 不在 Cache 中：

1 2	write-allocate：先把整个 block 搬进 Cache，再修改 no-write-allocate：不进 Cache，直接写下一级存储

常见搭配：

1 2	write-back + write-allocate write-through + no-write-allocate

为什么 write-allocate 要搬整个 block？例如 B = 4 bytes，CPU 只改地址 10，它所属的 block 是地址 8～11。Cache line 要保存整个 block，其他三个没改的字节也不能丢，所以要先把 8～11 全部拿进来，再改地址 10。

6.3 和 DMA 的关系

CPU 和 DMA 都访问内存，但 DMA 不一定经过 CPU Cache。

1 2	CPU 写，DMA 读：新数据可能还在 Cache，DMA 从内存读到旧数据 DMA 写，CPU 读：内存已经更新，CPU 却命中 Cache 里的旧数据

从 Cache 角度看：

1 2	DMA 读取前：CPU 的 dirty 数据要 clean/write back CPU 读取前：旧 Cache line 要 invalidate

Linux 驱动里通常通过 DMA API 做映射和同步，不应该自己随便操作 Cache。

7. Cache 性能：为什么 miss 很贵

CPU 如果在 L1 Cache 中 hit，通常只需要很少的 cycles；一旦 miss，就要继续访问 L2、L3，甚至 DRAM。CPU 后面的指令如果正好依赖这个数据，就只能等。

常见指标：

1
2
3

hit rate = 命中次数 / 总访问次数
miss rate = 未命中次数 / 总访问次数
hit rate + miss rate = 1

平均内存访问时间：

AMAT = hit time + miss rate x miss penalty

hit time     = 4 cycles
miss rate    = 5%
miss penalty = 100 cycles

AMAT = 4 + 0.05 x 100 = 9 cycles

虽然只有 5% 的访问 miss，平均时间却从 4 cycles 增加到了 9 cycles。miss rate 看起来不高，也可能把实际访问时间拖慢很多。

实际处理器还有多级 Cache：

CPU
  ↓ L1 miss
L2
  ↓ L2 miss
L3
  ↓ L3 miss
DRAM

所以 L1 miss 不代表一定访问 DRAM，但每往下一层走一次，代价都会增加。如果被替换的 Cache line 还是 dirty，还要先写回旧 block，再加载新 block。

8. 访问模式：working set、stride 与 Memory Mountain

Working set 不是程序申请的全部内存，而是程序在一段时间内反复使用的那部分数据。

working set < L1：大部分访问停在 L1
working set < L2：L1 放不下，但多数还能在 L2 找到
working set < L3：速度继续下降
working set > L3：频繁访问 DRAM

stride 表示连续两次访问之间隔了多少个元素。例如：

1
2
3

for (int i = 0; i < n; i += stride) {
    sum += a[i];
}

假设一条 Cache line 是 64 bytes，一个 int 是 4 bytes，那么一条 line 可以放 16 个 int：

stride = 1：一条 line 中的 16 个 int 基本都能用到
stride = 2：大约用到其中 8 个
stride = 16：每条 line 通常只用一个 int
stride > 16：每次访问很可能都要换一条 line

所以 stride 越大，空间局部性通常越差。某些固定 stride 还会让地址反复映射到相同的几个 set，额外产生 conflict miss。

Memory Mountain 就是把 working set、stride 和读取速度画到一起：

1
2
3

一个方向：working set size
一个方向：stride
高度：内存读取吞吐量

小 working set、小 stride 的区域最高；working set 超过 L1、L2、L3，或者 stride 逐渐变大后，吞吐量就会下降。图上的几个性能平台，大致对应数据主要停留在 L1、L2、L3 和 DRAM 时的速度。

9. 写出 Cache-friendly 的代码：矩阵乘法与 Blocking

C 语言二维数组按行连续存放。对于矩阵乘法：

1	C[i][j] += A[i][k] * B[k][j];

六种循环顺序不用逐个背，先看最内层循环是谁。

ijk / jik 的最内层是 k：

1 2	A[i][k]：沿 A 的一行连续访问 B[k][j]：沿 B 的一列跳跃访问

A 友好，B 不友好，整体不算好。

ikj / kij 的最内层是 j：

1
2
3

A[i][k]：同一个值反复使用
B[k][j]：沿 B 的一行连续访问
C[i][j]：沿 C 的一行连续访问

这一组通常最好。可以理解成：先取出一个 A[i][k]，让它依次乘 B 的一整行，并累加到 C 的一整行。

jki / kji 的最内层是 i：

1 2	A[i][k]：沿 A 的一列跳跃访问 C[i][j]：沿 C 的一列跳跃访问

两个矩阵都在跨行访问，通常最差。暂时可以这样记：

1
2
3

内层 j：通常最好
内层 k：一个连续，一个跳跃
内层 i：通常最差

但矩阵很大时，光改循环顺序还不够，因为一整行或整个矩阵仍然放不进 Cache。这时使用 Blocking：把大矩阵切成小块。

大矩阵
┌────┬────┬────┐
│小块 │小块│小块 │
├────┼────┼────┤
│小块 │小块│小块 │
└────┴────┴────┘

for (ii = 0; ii < n; ii += BS)
    for (kk = 0; kk < n; kk += BS)
        for (jj = 0; jj < n; jj += BS)
            // 只计算当前 A、B、C 小块

每次只处理能放进 Cache 的几个小块，让刚加载的数据在被替换前多用几次。Blocking 没有减少乘法次数，它减少的是同一批数据被反复从内存加载的次数。

Cache Lab 的矩阵转置部分做的就是这件事：计算结果不能变，但可以通过调整访问顺序和 block size，把 miss 数量降下来。