L12：缓存一致性 Cache Coherence

1. Cache Coherence Issue       多核缓存一致性问题
2. Snoopy Cache                基于广播/总线监听的一致性协议
3. Directory Cache             基于目录的可扩展一致性协议
4. The Fourth Cache Miss       Coherence Miss：第四类 miss
5. Memory Consistency Model    内存一致性模型：跨地址访问顺序

Cache coherence 解决“同一个地址的值应该是谁”的问题；
Memory consistency 解决“不同地址的 load/store 顺序应该如何被其他线程观察到”的问题。

raise clock frequency → more performance

many cores + parallelism + memory hierarchy + coherence protocol

Q1: How do they share data?       多个处理器如何共享数据？
Q2: How do they coordinate?       多个处理器如何协调顺序？
Q3: How many processors supported? 系统可以扩展到多少处理器？

CPU0 ─ Cache ┐
CPU1 ─ Cache ├── Shared Interconnect ── Main Memory
CPU2 ─ Cache ┘

Node0: CPU + Cache + Local Memory
Node1: CPU + Cache + Local Memory
Node2: CPU + Cache + Local Memory
Nodes connected by interconnect

// Producer
flag = 0;
a = 10;
flag = 1;

// Consumer
while (!flag) {}
x = a * y;

// Producer
send(p2, a, label);

// Consumer
receive(p1, b, label);
x = b * y;

Master requests bus → Bus controller grants → Master drives address/data/control
Other caches observe transaction → decide whether to respond / invalidate / write back

sum = 0;
begin parallel
for (i = 1; i <= 2; i++) {
    lock(id, myLock);
    sum = sum + a[i];
    unlock(id, myLock);
}
end parallel
print sum;

a[1] = 3
a[2] = 7
expected sum = 10

1. lock 本身如何正确实现？
2. 即使临界区互斥，多个 cache 中的 sum 副本是否一致？

同一个 memory address 的 block
可能同时存在于多个 private cache 中。
如果一个 processor 写了它，其他 processor 的旧副本怎么办？

Initial: Memory[Sum] = 0, all caches empty
P1 reads Sum → P1 cache has Sum = 0, valid
P2 reads Sum → P2 cache has Sum = 0, valid
P1 writes Sum = 3 → P1 cache has Sum = 3, dirty
P2 writes Sum = 7 → P2 cache has Sum = 7, dirty
P1 reads Sum → P1 may still read Sum = 3

P1 cache: Sum = 3, dirty
P2 cache: Sum = 7, dirty
Memory:   Sum = 0 or stale value

processor 写 cache 时，也把新值写到 memory

其他 cache 中已有的旧副本会自动失效或更新

P1 cache has Sum = 3
P2 writes Sum = 7 and write-through to memory
Memory becomes 7
P1 later reads Sum

每个 core 有 private cache → 减少主存访问 → 性能提高

private copies → possible stale values → shared memory abstraction broken

P1 reads Memory[1000] = 20 → P1 cache has 20
P2 reads Memory[1000] = 20 → P2 cache has 20
P0 writes Memory[1000] = 40

Invalidate: 让 P1/P2 的旧副本失效
Update:     把新值广播给 P1/P2

所有 cache 监听 shared interconnect / bus 上的 memory transactions。
一旦看到别的 processor 对自己缓存的 line 发起读/写请求，
就根据协议改变本地 line state，必要时提供数据或使副本失效。

processor 自己访问 cache
cache 同时 snoop 别人的 bus transaction

writer obtains exclusive ownership
other copies become Invalid
writer can then write locally

Write miss / write intent
→ broadcast invalidation
→ collect / assume invalidation done depending bus protocol
→ writer obtains line exclusively
→ perform write

Read miss
→ snoop other caches
→ if another cache has Modified/dirty copy:
      dirty owner supplies data or writes back
→ requester receives latest data

M: 我改过，只有我有，memory 旧。
E: 只有我有，但没改，memory 新。
S: 大家可能都有，memory 新。
O: 我负责最新数据，别人也有旧? 不，是 shared clean-looking copies，但 memory 旧。
I: 没有。

M = Modified
S = Shared
I = Invalid

| state bits | address tag | data block |

I --read miss--> S
I --write miss--> M
S --own write intent--> M
S --other write intent--> I
M --own read/write--> M
M --other read--> S + writeback/supply
M --other write intent--> I + writeback/supply

If one cache has a line in M state,
no other cache can have a valid copy of that line.

同一个地址不会同时存在两个不同的最新值。

M: Modified exclusive
E: Exclusive but unmodified
S: Shared
I: Invalid

I --read miss, not shared--> E
E --own read--> E
E --own write--> M   // silent upgrade, no bus transaction

private data read into cache 后，第一次写不需要发 invalidation。

Owner cache has latest data.
Other caches may hold shared copies.
Memory may be stale.
Owner supplies data on read miss.

small L1 + larger L2/L3

L1 中的 line 必须也存在于 L2 中

L2 miss → L1 一定没有 → 不必打扰 L1
L2 invalidation hit → 再检查/invalid L1

任何 processor cache miss / write intent
都要广播给所有 cache。

1. bus / interconnect bandwidth 总线通信带宽
2. snoopy tag bandwidth snoopy 标签带宽——Snooper 要不断访问 cache tag

Most snoops do not find a match.

line state + sharer vector / owner id

requester → home directory
home directory checks who has copies
only contact actual sharers / owner

Snoopy:  你喊一嗓子，所有人都听。
Directory: 你先查登记表，只找相关的人。

CPU + Cache nodes
Directory Controller + DRAM Bank nodes
Interconnection Network

Cache side: tag + data + cache state
Memory side: data + directory state + sharer vector

reliable network
FIFO messages between a given source-destination pair

Directory 是每条 memory line 的 summary state。
它不保存所有 cache 的完整状态，但保存足够信息来找 sharers / owner。

Snoopy: bus order serializes transactions.
Directory: home directory serializes transactions for a line.

1. CPU load request reaches cache.
2. Cache load miss.
3. Cache sends ShReq to directory.
4. Directory receives ShReq.
5. Directory checks line state: R(dir).
6. Directory sets requester bit in sharer vector.
7. Directory sends ShRep with cache line data.
8. ShRep arrives at cache.
9. Cache updates tag/data/state and returns data to CPU.

Directory: R(dir) → R(dir ∪ {requester})
Requester cache: I/Pending → S

1. CPU store reaches cache.
2. Cache store miss.
3. Cache sends ExReq to directory.
4. Directory receives ExReq.
5. Directory sees state R(dir), with sharers.
6. Directory sends InvReq to every sharer.
7. Each sharer receives InvReq.
8. Sharer invalidates local line and sends InvRep.
9. Directory receives InvRep and clears sharer bits.
10. When all sharers invalidated, directory sends ExRep to requester.
11. ExRep reaches requester cache.
12. Requester installs line and performs store.

Old sharers: S → I
Requester:   I/Pending → M
Directory:   R(dir) → TR(dir) → W(requester)

line state bits
sharing vector: one bit per processor

Dir state: 01 = shared
Sharer vector: [1, 0, 1]

P0 and P2 have shared copies.
Memory value is valid.
P1 does not have this line.

Dir state: 10 = modified
Sharer vector can encode owner id, e.g. [0,1,0]

P1 has the only modified copy.
Memory is stale.

Directory: not cached, sharer vector empty
P0 load miss → ShReq
Directory returns value from memory
P0 enters Shared
Directory marks P0 as sharer

Memory valid
P0: S
Directory: R({P0})

Directory: R({P0})
P1 load miss → ShReq
Directory returns memory value
Directory adds P1 to sharer vector

P0: S
P1: S
Directory: R({P0, P1})

Directory: R({P0, P1})
P2 store miss → ExReq
Directory sends InvReq to P0 and P1
P0/P1 invalidate and ACK
Directory sends ExRep to P2
P2 writes and becomes M

P0: I
P1: I
P2: M
Directory: W(P2)
Memory stale

Directory: W(P0)
P1 load miss → ShReq
Directory forwards request to owner P0
P0 supplies latest data / ACK
P0 downgrades from M to S or O depending protocol
P1 becomes S
Directory updates sharer/owner state

P0: A, Shared
P1: A, Shared
P2: A, Shared

你们的 A 副本都失效

P0 -> Directory: ACK
P1 -> Directory: ACK
P2 -> Directory: ACK

Shared -> Modified
Modified owner 转移
Directory 等待某个 cache 回写数据

这个 load/store 到底完成了吗？
状态能不能更新？

P3 请求写 A
Directory 已经发出 invalidate
但 P0/P1/P2 还没全部 ACK

我现在处理不了你的请求，请你稍后重试。

P0, P1, P2, ... P127 都有副本

1. P0 发送 read request for line A
2. P1 发送 read exclusive request for line A，在 directory 等待
3. Directory 回复 P0 的 read，并设置 sharing vector，但消息延迟
4a/4b. Directory 同时回复 P0 和 P1：
       通知 P0 失效，给 P1 新 owner 权限
5. P0 invalidates line A and sends ACK

第 3 步的旧 read reply 可能很晚才到达 P0

如果 P0 对 A 有一个 read 请求还挂起，
它不能随便处理后面和 A 相关的 invalidate / owner 转移。

1. P1 发送 read exclusive request for line A
2. Directory 转发请求给 P0，因为 P0 是 owner
3a. P0 把数据发给 P1
3b. P0 给 Directory 发 ACK，但 ACK 延迟
4. P1 收到数据后认为 read exclusive 完成；
   后来 P1 替换这条 line，把更新值写回内存

第 4 步写回内存可能先到 Directory
第 3b 步 ACK 反而后到

先接受 P1 写回并覆盖内存
后收到 3b，又认为所有权转移刚刚完成，P1 还是 owner

当 ownership transfer 还没完成时，
Directory 不能随便响应后来的 replacement/writeback。

128 个处理器
256GB 内存
每个处理器 1MB L2 cache
64B cache line

128 bit = 16 bytes

16 / 64 = 0.25 = 25%

0.25 × 256GB = 64GB

128 个处理器 × 每个 1MB cache = 128MB cache

128MB / 64B = 2M lines

tag 8B + directory 16B = 24B
24 / 64 = 37.5%

0.375 × 2M × 64B = 768KB

The Fourth Cache Miss
缓存未命中的第四个 C

Compulsory miss
Capacity miss
Conflict miss

Coherence miss

第一次访问没有
cache 容量不够
cache 映射冲突

P0 写 flag = 1
P1 读 flag

invalidate
cache miss
数据在不同 cache 之间转移

Coherence miss

Communication miss

block 大小 = 32B
Processor 0 读写变量 X
Processor 1 读写变量 Y
X 地址 = 4000
Y 地址 = 4012

4000 和 4012 虽然是不同变量，
但它们落在同一个 32B cache block 里。

4000, 4004, 4008, 4012, 4016, ..., 4028

X 和 Y 是不同 word
但属于同一个 cache line

P0 获得整个 block 的独占权

CPU-Memory Bus
A 200
A 100

某个 cache 中 A = 200，是最新值
Memory 中 A = 100，是旧值

看到总线上有人读 A
发现自己有 A 的 modified copy
于是阻止/覆盖 memory 的旧响应
把 A=200 提供出去

当 cache 有最新脏数据时，
cache 需要介入这次读请求，
把最新数据提供给请求者。

state | line addr | data0 | data1 | ... | dataN

Cache coherence 是按 cache line 管理，
不是按 word 管理。

这一整行有没有被别人写？

这一行里的哪个具体 word 被写？

M1 写 word_i
M2 写 word_k
i ≠ k
但 word_i 和 word_k 在同一个 cache line

两个处理器写的是不同变量，没有真正共享同一个变量。

它们写的是同一条 cache line。

P0 反复写 X
P1 反复写 Y

P0 写 X -> P1 的整行失效
P1 写 Y -> P0 的整行失效
P0 再写 X -> P1 又失效
P1 再写 Y -> P0 又失效

ping-pong effect

让不同处理器频繁写的数据不要落在同一个 cache line。

加 padding
按 cache line 对齐
每个线程的数据分开放到不同 cache line

// 容易 false sharing
double sum[NUM_THREADS];

// 更安全：让每个线程隔开一个 cache line
double sum[NUM_THREADS][CACHE_LINE_SIZE / sizeof(double)];

第一次访问某个 block，cache 里肯定没有。

不可完全避免；
长时间运行程序中占比通常较小。

增大 block size

miss penalty 变大；
block 太大还可能增加 miss rate。

cache 总容量不够，
即使 fully associative + 完美替换策略，也装不下程序需要的所有 block。

增加 cache size

可能增加访问时间。

cache 总容量够，
但多个内存块映射到同一个 cache 位置，
互相挤掉。

增加 cache size
增加 associativity
改进替换策略，例如 LRU

由于其他处理器的一致性通信导致的 cache miss。

P0 有 A
P1 写 A
P0 的 A 被 invalid
P0 下次再读 A，miss

P0 写完数据
P1 要读这个数据

不断 invalid
不断 miss
不断重新取数据

Coherence miss
├── True sharing miss   真共享缺失
└── False sharing miss  伪共享缺失

P1 写 X = 10
P2 后面读 X

不同处理器真的通过同一个数据通信。

同一个 cache line 里有 X 和 Y

P1 只写 X
P2 只写 Y

真共享：别人改的正是我要用的数据。
伪共享：别人改的不是我要用的数据，但因为在同一 cache line，我也被误伤。

X 和 Y 在同一个 cache block / cache line 里。

P1 Cache State: Modified(X, Y)
P2 Cache State: Invalid(X, Y)

P1 拿到了整个 cache line (X, Y) 的写权限；
P2 中这一整行都被 invalid。

P1: Modified(X, Y)
P2: Invalid(X, Y)

P1 Invalidates block (X, Y) in P2

P1: Shared(X, Y)
P2: Shared(X, Y)
Explanation: Write-back & Copy block from P1 to P2

P1 原来有最新的 Modified block；
P2 想读；
P1 必须把最新 block 提供出来；
最后两边都变成 Shared。

P1 写 X -> P2 的 (X,Y) invalid
P2 写 Y -> P1 的 (X,Y) invalid
P1 写 X -> P2 的 (X,Y) invalid
...

Instruction
Capacity / Conflict
Cold
False Sharing
True Sharing

Cold miss
Capacity miss
Conflict miss

True sharing miss
False sharing miss

cache 变大后，
capacity/conflict miss 可能下降，
但 true sharing / false sharing 不一定消失。

coherence miss 不是因为 cache 太小，
而是因为别的处理器写共享数据，导致你的副本失效。

double x, pi, sum[NUM_THREADS];

#pragma omp parallel private(i, x)
{
    int id = omp_get_thread_num();

    for (i = id, sum[id] = 0.0; i < num_steps; i = i + NUM_THREADS) {
        x = (i + 0.5) * step;
        sum[id] += 4.0 / (1.0 + x * x);
    }
}

线程 0 写 sum[0]
线程 1 写 sum[1]
线程 2 写 sum[2]
线程 3 写 sum[3]

double = 8 bytes
sum[0] 和 sum[1] 在内存中相邻

64 / 8 = 8 个 double

sum[0], sum[1], ..., sum[7]

性能会很差。

double x, pi, sum[10000];

#pragma omp parallel private(i, x)
{
    int id = omp_get_thread_num(), fix = ________;

    for (i = id, sum[id] = 0.0; i < num_steps; i = i + NUM_THREADS) {
        x = (i + 0.5) * step;
        sum[id * fix] += 4.0 / (1.0 + x * x);
    }
}

YELLOW：Constant for size of blocks in doubles

fix = cache line 中能放多少个 double

fix = 64 / 8 = 8

线程 0 写 sum[0]
线程 1 写 sum[8]
线程 2 写 sum[16]
线程 3 写 sum[24]

ORANGE = block size in bytes

如果给机器增加 x 倍资源，
性能也接近提高 x 倍，
就叫可扩展性好。

处理器数量
内存容量
互连带宽

Problem constrained scaling
Time constrained scaling

问题规模固定；
增加处理器数量；
目标是减少执行时间。

同一个矩阵乘法任务
1 个处理器要 100 秒
10 个处理器希望接近 10 秒

S = Time(1 processor) / Time(p processors)

同一个任务，用 p 个处理器比用 1 个处理器快多少。

允许执行时间固定；
增加处理器数量；
目标是处理更大的问题。

1 个处理器 1 分钟处理 1GB 数据；
10 个处理器 1 分钟希望处理 10GB 数据。

S = Work(p processors) / Work(1 processor)

在相同时间内，多处理器能完成多少倍工作。

生产者先产生数据；
消费者必须等数据准备好之后才能使用。

P1 写 data
P1 设置 flag = 1

P2 看到 flag = 1
P2 读取 data

P2 看到 flag = 1 时，data 是否一定已经可见？

同一时间只允许一个处理器使用共享资源。

一次只允许一个线程进入临界区；
一次只允许一个人编辑文件。

Producer processor
Consumer processor
Shared Memory: flag, data

先写 data；
再写 flag = 1；
告诉消费者数据准备好了。

不断读取 flag；
如果 flag == 0，就继续等；
如果 flag == 1，就读取 data。

消费者一旦看到 flag = 1，
就一定能看到生产者写入的新 data。

flag 和 data 是两个不同地址。

Cache coherence
Memory consistency

P1 写 X = 1
P2 读 X
P3 写 X = 2

Producer 写 data
Producer 写 flag

Consumer 读 flag
Consumer 读 data

data
flag

Consumer 看到 flag = 1 时，
是否一定能看到新的 data？

sw xdata, (xdatap)
li xflag, 1
sw xflag, (xflagp)

先写 data；
再把 flag 设为 1。

spin:
    lw xflag, (xflagp)
    beqz xflag, spin
    lw xdata, (xdatap)

一直读 flag；
如果 flag 是 0，就继续等；
如果 flag 是 1，就读取 data。

flag = 0

消费者看到 flag = 1 之前，
生产者写入的 data 是否已经对消费者可见？

flag = 1 已经被消费者看到；
data 的新值还没有对消费者可见。

P1 的某条 store
P2 的某条 load
P1 的另一条 store
P3 的 load
...

store data
store flag

store data 在 store flag 前面

Producer: store data 发生在 store flag 前
Consumer: load flag 发生在 load data 前
Consumer 读到 flag = 1，说明 store flag 已经发生
因此 store data 也已经发生

写 data
写 flag

读 flag
读 data

Producer 写 data
Producer 写 flag = 1
Consumer 读到 flag = 1
Consumer 再读 data

store buffer
load/store 重排序
让不同地址的访存乱序完成

大多数真实机器都不是 Sequential Consistency。

store buffer
乱序执行
非阻塞 cache
load/store 优化
写合并

fence
memory barrier
atomic 操作
acquire / release
lock / unlock

这里的顺序不能乱。

生产者：data 写入必须在 flag 写入之前对外可见；
消费者：看到 flag 后，读取 data 不能被提前。

Consumer 看到 flag = 1
但读到旧 data

Cache coherence：管同一个地址的值是否一致。
Memory consistency：管不同地址的读写顺序是否符合程序员预期。

Store Buffer

CPU 执行：store X = 1

写入 cache
获得 cache line 独占权
完成一致性协议
其他 cache 副本失效

store X = 1 先进入 store buffer
CPU 继续执行后面的指令
稍后再慢慢把 X=1 写到 cache / memory 系统中

减少 store 阻塞 CPU 的时间；
隐藏 cache miss / coherence 操作延迟；
提高流水线性能。

本处理器以为自己已经写了；
其他处理器暂时还看不到这个写。

X = 0
Y = 0

P1:
X = 1
r1 = Y

P2:
Y = 1
r2 = X

P1.x2 = P1 最后读到的 Y
P2.x2 = P2 最后读到的 X

P1.x2 = 0
P2.x2 = 0

P1 的 X=1 先进入 P1 的 store buffer，还没被 P2 看到；
P2 的 Y=1 先进入 P2 的 store buffer，还没被 P1 看到；
P1 随后读 Y，看到旧值 0；
P2 随后读 X，也看到旧值 0。

每个处理器可以先看到自己的 store；
其他处理器稍后才看到这个 store。

SC，Sequential Consistency

所有处理器的内存操作按某个全局顺序一个一个执行；
每个处理器内部仍保持程序顺序。

编程简单；
推理简单；
更接近直觉。

硬件更难做快；
很多重排序优化不能随便使用；
可能需要复杂硬件检测顺序违规。

硬件更容易做高性能；
允许 store buffer；
允许 load/store 重排序；
允许更激进的乱序执行。

程序员或编译器必须显式加 fence；
并发程序更难理解；
不小心就会出现“flag 已经变了，但 data 还没看到”的问题。

fence
memory barrier
acquire / release
atomic operation

这里不能乱序。

sd xdata, (xdatap)
li xflag, 1
fence w,w
sd xflag, (xflagp)

spin:
    ld xflag, (xflagp)
    beqz xflag, spin
    fence r,r
    ld xdata, (xdatap)

前面的写操作，必须在后面的写操作之前完成 / 对外可见。

写 data 必须早于写 flag。

flag = 1 已经被消费者看到；
但 data 的新值还没对消费者可见。

前面的读操作，必须在后面的读操作之前完成。

先读 flag；
确认 flag = 1；
再读 data。

消费者提前读到了旧 data；
之后才看到 flag = 1。

生产者用 fence 保证 data 写在 flag 写之前；
消费者用 fence 保证 flag 读在 data 读之前。

所有处理器看到一个统一的全局内存操作顺序；
每个处理器自己的操作顺序保持程序顺序。

store 进入 store buffer 后，
后面的 load 可以先执行。

Store -> Load 可以表现得像被重排了。

同一个处理器的 store 顺序通常仍然按程序顺序对外可见；
其他处理器通常以相同顺序看到这些 store。

IBM-370 TSO
x86 TSO
SPARC TSO
RISC-V RVTSO

一个处理器的写操作一旦对其他处理器可见，
所有处理器看到这个写的顺序是一致的。

修改后的 ARMv8 memory model
RISC-V RVWMO

不同处理器可能以不同顺序看到另一个处理器的写操作。

ARMv7
原始 ARMv8
IBM POWER
DEC Alpha

Acquire
Critical
Release
Other Code

lock();      // Acquire
临界区;      // Critical section
unlock();    // Release

Acquire 之后的临界区读写，不能被提前到 Acquire 之前。

你必须先拿到锁，才能读写临界区里的共享数据。

临界区里的写操作，必须在 Release 对其他处理器可见之前完成。

你必须先把临界区里的更新做好，再告诉别人“我释放锁了”。

P1 Acquire
P1 Critical：修改共享数据
P1 Release

P2 Acquire
P2 Critical：读取共享数据
P2 Release

P1 在 Critical 中的更新，
必须在 P1 的 Release 之前对外可见；

P2 的 Critical 读取，
必须发生在 P2 的 Acquire 之后。

第 85 页：
Store buffer 提高性能，但让自己的写先被自己看到，别人稍后看到。

第 86 页：
TSO 允许两个处理器都读到旧值 0，这是 SC 不允许的。

第 87 页：
强模型更好理解但难实现高性能；弱模型更快但需要 fence。

第 88 页：
生产者-消费者需要 fence，保证 data 和 flag 的访问顺序。

第 89 页：
内存模型从强到弱可以分为 SC、TSO、弱 MCA、弱 non-MCA。

第 90 页：
Release consistency 只在 acquire/release 这类同步点保证必要顺序。