Lecture 12: Directory-Based Cache Coherence
Lecture 12: Directory-Based Cache Coherence
1. 章节标题与概述
Lecture 12: Directory-Based Cache Coherence（基于目录的缓存一致性）
本讲核心问题：上一讲的监听式一致性（snooping-based coherence）把每一次 cache miss 的一致性信息广播（broadcast）给所有 cache，这在”一条共享总线 + 4 个核”上又便宜又简单，但在 64、256、1024 个节点的机器上，广播本身成了不可扩展的瓶颈。本讲要回答三件事：(1) 广播到底卡在哪里（总线争用、带宽不随节点数增长、电气负载、以及”就近访问内存”的 NUMA 好处被”仍要全网广播”抵消）；(2) 目录（directory）如何用点对点消息取代广播——目录项记录”这一行现在被哪些 node 缓存、是否有脏副本”，miss 只发给需要知道的节点（need to know）；(3) 目录自己带来的两个新问题怎么解——目录存储开销（full bit vector、limited pointer schemes、sparse directories）与消息数/关键路径（critical path）（intervention forwarding、request forwarding），最后落到真实芯片（Intel Core i7 的 L3 目录、多 socket 的 home agent + in-memory directory）与 cc-NUMA 上的软件行为。
- 涉及的主要硬件/软件机制：
- 硬件侧：目录项（directory entry） =
P个 presence bit（存在位） + 1 个 dirty bit；home node（主节点） 与 requesting node（请求节点） 的角色划分；目录分区与内存同址部署（co-located） 的分布式目录；三种消息序列（read miss 到 clean line / read miss 到 dirty line / write miss 的”失效 + 应答”四步）；cache-to-cache transfer（cache 到 cache 直接传数据）；intervention forwarding 与 request forwarding 两种转发策略对关键路径的影响；limited pointer（1 + k·log₂P位）与 sparse directory（稀疏目录，链表串在 cache line 的 tag 里）；Intel Core i7 的 L3 兼作集中式目录（依赖 inclusion property（包含属性））与 环形互连（ring interconnect）；多 socket 的 home agent / cache agent / memory controller / QPI / 16 KB dir cache。 - 软件侧：程序员写不出目录，但访问模式决定了目录记不记得住： migratory object（迁移型对象）、mostly-read object（多读少写）、频繁读写对象、高低争用锁，四种模式对应完全不同的目录压力；在 cc-NUMA 上，数据落在哪个 node（first touch / 页分配） 与 线程跑在哪个 node（亲和性 affinity） 共同决定了 3~4 跳的远程延迟要不要付；伪共享（false sharing） 会把一条 64 B 行变成跨 node 的失效链。
- 硬件侧：目录项（directory entry） =
在并行计算知识体系中的角色：本讲是”缓存一致性”这条线的收尾与可扩展性转折点：上一讲给出 MSI/MESI 这套协议语义，本讲给出把它扩展到大规模多核/多 socket 所需要的数据结构（目录）与消息路径（点对点 + 转发）。它同时是后面几讲的前置知识：同步（synchronization） 讲的 test-and-set、ticket lock、以及”锁释放时一堆读者都在场”的高争用问题，本质就是目录里的 sharer 列表长度问题（讲义 slide 21 明确点出）；内存一致性（memory consistency） 需要一个”写入何时对谁可见”的定序机制，而目录提供了这个定序的物理载体；互连网络（interconnection networks） 讲的所有拓扑（ring / mesh / fat tree）正是目录协议跑的”路”；消息传递实现（under the hood: message passing） 则是同一套 3 跳/4 跳消息路径在软件层的翻版。
- 配套材料：
lectures/11_directorycoherence.pdf（抽取文本extracted/11_directorycoherence.txt，共 47 页 / 约 25 KB）：已公开，可在 https://www.cs.cmu.edu/~418/lectures/ 公开下载。讲义首页写的是 “Lecture 11: Directory-Based Cache Coherence” 与 “CMU 15-418/15-618, Fall 2024”——这是讲义沿用历史学期版本的正常现象（讲次编号与学期字样随年度重排），不是错误。按 Fall 2026 日程表（https://www.cs.cmu.edu/~418/schedule.html），本讲排在 Sep 21，是第 12 讲，主题即 Directory-Based Cache Coherence；上一讲（Sep 18）是 Snooping-Based Cache Coherence，对应讲义lectures/10_cachecoherence.pdf。本笔记的术语（presence bit、dirty bit、home node、intervention/request forwarding、limited pointer、sparse directory）、示例（read miss 到 clean/dirty line、write miss 的失效与应答、64 节点 Barnes-Hut / LU / Ocean 的 sharer 直方图）与数字（12% / 50% / 200% 存储开销、5.8% / 7.8% / 9.7% 的 limited pointer 开销、1 MB cache 对 1 GB 内存的 99.9% 空目录项）全部以这份 47 页讲义为准。- 讲课录像（Panopto / YouTube）：Fall 2026 日程表中被注释隐藏，属未发布。
- Ed 讨论区、Autolab、Canvas：需登录，非公开。
- 部分讲座在 Fall 2026 尚未发布公开讲义（Performance Analysis / Profiling、Transactional Memory、AI in System Design 等）；其历史学期 PDF 位于
/afs/cs/academic/class/15418-*/public/之下，需要 CMU 登录，属未公开。 - Fall 2026 授课教师为 Brian Railing 与 Dimitrios Skarlatos；课程由 Kayvon Fatahalian 创建。
- 本笔记中的延迟/带宽假设（每跳 30 ns、链路 20 GB/s、缓存控制器 tag 查询 2 ns 等）、实测数据（在 8 线程 Linux 机器上一次运行的结果）与目录开销的精确百分比推导，均已显式标注为”本笔记补充“，与讲义原文区分。
2. 核心概念与硬件/软件架构图解
2.1 出发点：广播为什么会在”大机器”上撞墙
定义与目的：讲义 slide 3 回顾了监听式一致性的实现方式——“每一次 cache miss，触发的 cache 都要和所有其他 cache 通信”；一致性信息的传播靠广播（broadcast），而广播最典型的实现就是共享总线（shared bus）。它的目的是让协议极简：不需要知道”谁有这一行的副本”，因为每个人都听得见每一次请求；状态机（MSI/MESI）只需关心自己的 cache 就行。问题出在”每个人都听得见”这件事的代价上：消息数、被卷入的 cache 数、总线上占用的周期数，全都随节点数
P线性甚至更差地增长。直观解释（”它是什么？”）：监听式一致性像村里的广播喇叭——全村 5 户人家时，谁家要找一样东西就喊一嗓子，所有人放下手里的活听一遍（snoop 一次 tag），又便宜又省事。可村子变成 1000 户以后：(1) 喇叭只有一条信道，所有人必须排队喊（总线争用 contention）；(2) 喇叭的响度/信道容量不随户数增加（带宽不 scale）；(3) 喇叭线越拉越长、挂的喇叭越多，电气负载（电容）越大，只能降频、加功耗；(4) 最荒唐的是——你只是想去隔壁邻居家借个东西（访问本地 NUMA 内存），也得先对着全村喊一遍（为了一致性必须广播）。目录（directory）就是”电话簿 + 只打该打的电话“：先把”这东西现在在谁手里”记在一个地方（目录），然后点对点（point-to-point） 打给需要知道的人。
图 1：监听式广播 vs 目录的点对点（讲义 slide 3、7、19 的核心对比）
(A) SNOOPING: every miss is broadcast to EVERY cache -> traffic O(P) per event
+--------+ +--------+ +--------+ +--------+
| P0 $ | | P1 $ | | P2 $ | | P3 $ | ... P caches
+---+----+ +---+----+ +---+----+ +---+----+
| | | |
=========+============+============+============+===========> shared bus
: : : : (one talker at a time)
v v v v
[tag chk] [tag chk] [tag chk] [tag chk] P tag lookups and
P possible reactions
for ONE miss
(B) DIRECTORY: point-to-point, "need to know" only -> traffic O(k) per event
k = number of sharers
+--------+ +--------+ +--------+ +--------+
| P0 $ | | P1 $ | | P2 $ | | P3 $ |
+---+----+ +---+----+ +---+----+ +---+----+
| | | |
+--------+------------+------------+------------+---------+
| scalable interconnect (ring/mesh/...) |
+-----+---------------------+---------------------+-------+
| | |
+-----v------+ +-----v------+ +-----v------+
| Dir + Mem | | Dir + Mem | | Dir + Mem | directory partition
| node 0 | | node 1 | | node 2 | lives with the memory
+------------+ +------------+ +------------+ it describes
read miss: 1 request to home + 1 reply (from memory OR from the owner)
write miss: 1 request + 1 reply + k invalidations + k acks
- 性能特征（延迟、带宽、吞吐量、可扩展性）：
- 监听式：延迟低（一次广播事务就能定序）、实现简单（总线本身就提供了原子性的广播定序）；但带宽固定——总线上所有数据（读回复、写回、失效）共享同一条信道，与
P无关；电气负载随P上升导致频率下降；每个 cache 都要为别人的流量做 tag 查询，P越大浪费越多。 - 目录式：引入一次间接（indirection）——先问 home，所以 clean 读 miss 是 2 跳、dirty 读 miss 是 3~4 跳，单次 miss 延迟可能比广播还高；换来的是流量与被卷入的 cache 数与
k（实际 sharer 数）成正比，而不是与P成正比，并且数据可以直接从 owner 的 cache 传到请求方（cache-to-cache），不必经过内存。 - 结论：目录不是”更快的协议”，而是”更可扩展的协议”；在小机器上广播赢，在大机器上目录赢，判据是”每个事件消耗的全局资源是 O(P) 还是 O(k)”。
- 监听式：延迟低（一次广播事务就能定序）、实现简单（总线本身就提供了原子性的广播定序）；但带宽固定——总线上所有数据（读回复、写回、失效）共享同一条信道，与
2.2 NUMA / cc-NUMA / DSM：目录协议真正的动机
- 定义与目的：讲义 slide 4 先回顾 NUMA（non-uniform memory access，非一致内存访问） 共享内存系统——把内存切分、就近放在处理器旁边（讲义举的例子是 PSC Blacklight 这类机器）。这样做能带来更高的聚合带宽与更低的延迟（尤其是应用有局部性时）。但紧接着给出关键论断：“如果一致性协议本身不能扩展，NUMA 的高效就白搭”——处理器访问近处内存本来是好事，可是为了保证一致性仍然必须广播给所有其他处理器，那”就近”省下的时间又赔进去了。讲义给出了两个术语：
- cc-NUMA（cache-coherent NUMA）：带缓存一致性的非一致内存访问系统。
- DSM（distributed shared memory system，分布式共享内存系统）：cache coherent + shared address space（共享地址空间），但物理实现是分布式的内存。
- 与之配套的目录术语（slide 8~9）：home node（主节点） = 持有该 cache line 对应数据的内存所在的 node；requesting node（请求节点） = 发起请求的处理器所在 node；目录分区与它描述的内存同址（co-located）。
直观解释（”它是什么？”）：cc-NUMA 像一栋有多个厨房的大楼。每个厨房（node）旁边都有冰箱（内存），住得近的人拿东西当然快——这就是 NUMA 的好处。但”谁手里有那本大家都可能改的账本”（一致性）如果还得靠全楼广播，那住得再近也没用：每次翻账本都要通知全楼 64 户。目录相当于在每台冰箱门上贴一张”借出记录”：这本账本现在在谁手里、有没有被改过，一看就知道，只给真正持有副本的人打电话。
- 图 2：cc-NUMA 系统与”home node / requesting node”的角色划分（讲义 slide 4、8、9）
cc-NUMA / DSM SYSTEM WITH A DISTRIBUTED DIRECTORY (P nodes)
+---------------------+ +---------------------+ +---------------------+
| Node 0 | | Node 1 | | Node 2 |
| +-------+ +-----+ | | +-------+ +-----+ | | +-------+ +-----+ |
| | Proc | | L1$ | | | | Proc | | L1$ | | | | Proc | | L1$ | |
| +---+---+ +--+--+ | | +---+---+ +--+--+ | | +---+---+ +--+--+ |
| | | | | | | | | | | |
| +---v--------v--+ | | +---v--------v--+ | | +---v--------v--+ |
| | Memory + | | | | Memory + | | | | Memory + | |
| | Directory| | | | | Directory| | | | | Directory| | |
| +-----------+---+ | | +-----------+---+ | | | +-----------+--+ |
+----------+----------+ +----------+----------+ +----------+----------+
| | |
+-------------+-------------+-------------+-------------+
| scalable interconnect |
+-----------------------------+
the BLUE line's home node is node 1 -> every coherence event for that line
is arbitrated by node 1's directory
the YELLOW line's home node is node 0
a request from node 2 for the blue line ==> 2-hop (clean) or 3~4-hop (dirty)
local traffic (node 1 read/write of blue line) still needs no broadcast at all
- 性能特征：NUMA 提供的是带宽的可扩展性（每加一个 node 就多一份本地内存带宽），目录提供的是一致性流量的可扩展性（每加一个 node 不会让每个事件多消耗全局资源）。两者必须同时成立，cc-NUMA 才真的可扩展——这正是讲义 slide 4 那句”efficiency of NUMA system does little good if the coherence protocol can’t also be scaled”的定量含义。
2.3 中间方案：分层监听（hierarchical snooping）
- 定义与目的：讲义 slide 5~6 给出”先别急着上目录”的一种解法：在每一层都用监听（snooping）。把处理器先分成若干簇（cluster），簇内用总线/监听保持一致，簇间再挂一条上层互连，上层也用监听保持一致——多层总线树。另一变体是内存跟着簇走（memory localized with the groups of processors），而不是集中在顶层。
- 直观解释（”它是什么？”）：像公司里的多级会议：小组内部（4 人）开个短会就能对齐；跨组的事情才上升到部门会议，再上升到全公司大会。层级越往上，参会的人越多、越慢、越容易堵。
- 讲义明确给出的优缺点（slide 6）：
- 优点：相对容易实现——因为多级 cache 本身就要处理类似的问题（已经在做层级化的 tag/状态维护）。
- 缺点：(1) 网络根部（root of the network）会成为瓶颈，所有跨簇流量都要过它；(2) 延迟比直接通信更大（要走多级）；(3) 不能套用到更一般的网络拓扑上（mesh、cube 这类拓扑里没有天然的”层”）。
- 它在知识体系里的位置：分层监听是”用层次换简单“，目录是”用间接换可扩展“。讲义把它作为对照方案列出，随后 slide 7 才正式引入目录。
2.4 目录的基本结构：presence bits + dirty bit
- 定义与目的：讲义 slide 7 把目录的思想一句话讲清：监听方案靠广播去”问出”某一行在其他 cache 里的状态；替代思路是把”这一行的状态”集中存在一个地方——目录（directory）。
- 目录项的内容：一个 cache line 在所有 cache 中的状态；
- 访问方式：cache 按需（as necessary） 查询目录；
- 维护方式：cache 之间用点对点消息、按需知道（need to know） 的方式维护一致性，不再使用广播。
- slide 8 给出最简目录（very simple directory）：每个 cache line 一个目录项，项里是
P个 presence bit（存在位，表示处理器 P 是否在它的 cache 里持有这一行） + 1 个 dirty bit（脏位，表示这一行在其中某个 cache 里是脏的/被改过）。 - slide 9 给出分布式目录（a distributed directory）：目录分区与它描述的内存放在同一个 node（“目录分区与内存同址部署”），于是”home node”这个概念落到物理位置上。
直观解释（”它是什么？”）：目录项像图书馆某本书的借阅卡：卡片上有一排格子（presence bits），格子上打勾表示”这一位对应的读者手里有复印本”；另有一个”已被涂改”标记（dirty bit），表示”目前有一份复印本被改动过，原书（内存）已经过期”。管理员（home node）只看卡片就能回答两个问题：”谁能给我数据？”（dry 就直接从书架取，dirty 就找那位涂改过的读者）和”我需要通知谁作废？”（所有打勾的格子）。
- 图 3：目录项位布局 + 集中式目录 / 分布式目录（讲义 slide 8、9、23、30）
DIRECTORY ENTRY FOR ONE CACHE LINE (full bit-vector scheme)
bit: P-1 ... 1 0
+----+----+----+----------------+----+----+----+----+
|p |p |p | ... | p1 | p0 | D | | D = dirty bit
|P-1 |P-2 |P-3 | | | | | | 1 = exactly ONE cache
+----+----+----+----------------+----+----+----+----+ holds it modified
^ ^
| presence bit i = 1 <=> node i holds a valid copy of this line
+----------------------------------------------+
memory array layout (per node):
data : M lines x 512 bit (64 B line) <-- the payload
dir : M entries x (P+1) bit <-- the overhead
overhead = (P+1)/512 -> P=64: 12.5% P=256: 50% P=1024: 200%
TWO DEPLOYMENTS
(a) CENTRALIZED / L3-INTEGRATED (Intel Core i7) (b) DISTRIBUTED (cc-NUMA)
+-------------------------------+ node0 node1 node2
| shared L3: one bank / core | | | |
| directory for ALL L3 lines | +--+---+---+--+
+-------------------------------+ | net |
| ring interconnect (not bus) | dir+mem dir+mem dir+mem
+-------------------------------+ (home node = memory owner)
inclusion: any line in an L2 has
an entry in the L3 directory
- 性能特征：目录查询本身是一次额外的内存/目录访问（这也是”目录 miss 延迟高于广播”的原因），但它是并行可扩展的——因为目录分区和内存一样是分布式切片（sliced） 的，
P个 node 可以同时服务P个不冲突的目录查询；而广播总线的仲裁是全局串行的。
2.5 三种典型事件的消息序列（本讲最需要背下来的部分）
讲义用 slide 10~18 完整走通了三个例子。以下”消息编号”完全对应讲义图上的编号。
(a) read miss 到 clean line（slide 10~11）
- request：请求节点向该行的 home node 发 read miss 消息；home 目录查这一行的目录项。
- response：若该行 dirty bit = OFF，home 直接从内存返回数据，并把
presence[requestor]置为 true（表示请求节点现在缓存了这一行）。
- 代价：2 条消息，关键路径 2 跳。只有 home 一个 cache 参与。
(b) read miss 到 dirty line（slide 12~14）
情形：处理器 0 读 blue line，该行是 dirty 的（最新内容在 P2 的 cache 里）。
- request：read miss 消息到 home。
- response：owner id：home 发现 dirty bit = ON，于是数据必须由另一个处理器提供（它持有最新副本），home 只能告诉请求方”去 P2 拿“。
- request: data：请求节点向 owner（P2） 请求数据。
- response: data：owner 把数据发给请求节点，并把自己 cache 中该行的状态改为 SHARED（只读）。
- response: data + dir revision：owner 同时给 home 回一条消息，home 据此清 dirty、更新 presence bits、并把数据写回内存（update memory）。
- 代价：5 条网络事务，其中 4 条在关键路径上（事务 4 和 5 可以并行，所以事务 5 不算关键路径）。讲义在 slide 37 给出关键路径的定义：“critical path：完成这个操作必须依次发生的一串依赖操作（sequence of dependent operations）”。
(c) write miss（slide 15~18）
情形：处理器 0 要写一行，该行是 clean 的，但同时驻留在 P1 和 P2 的 cache 里。
- request: write miss msg：P0 向 home 发写 miss。
- response: sharer ids + data：home 返回共享者列表与数据（P0 拿到数据与”要通知谁”）。
- request: invalidate：home（按讲义图上的编号由目录发起）分别向 P1、P2 发失效消息（2 条消息，可以并行发出）。
- 4a / 4b: ack：P2、P1 各自应答（ack）。
- P0 收到两个失效应答之后才可以真正执行写（after receiving both invalidation acks, P0 can perform write）。
- 代价：2 + 2k 条消息（
k= 共享者数），关键路径 4 跳（request → response → invalidate → ack）。关键点：失效消息可以并行发给所有 sharer（这是 full bit vector 的优势，见 §2.9 与 sparse directory 的对比）。
- 表 1：三种事件在”目录 vs 监听”下的消息数、关键路径、被卷入的 cache 数
| 事件 | 方案 | 消息/事务数 | 关键路径（跳） | 必须做动作的 cache 数 | 说明 |
|---|---|---|---|---|---|
| read miss，clean | 目录（点对点） | 2 | 2 | 1（home） | 数据从内存来（slide 11） |
| read miss，clean | 监听（广播） | 2 个总线事务 | 2 | P（每人都 snoop） | 总线仲裁串行 |
| read miss，dirty | 目录（原始 5 消息） | 5 | 4 | 2（home + owner） | 事务 4、5 并行（slide 14、37） |
| read miss，dirty | 目录 + intervention fwd | 4 | 4 | 2 | 流量少 1 条，关键路径不变（slide 38~40） |
| read miss，dirty | 目录 + request fwd | 4 | 3 | 2 | 请求方直接向 owner 要数据（slide 41~43） |
| write miss，k 个 sharer | 目录 | 2 + 2k | 4 | k + 1 | 失效与 ack 各 k 条，可并行（slide 17、18） |
| write miss，k 个 sharer | 监听（BusRdX 广播） | 2~3 个总线事务 | 2~3 | P + 1 | 广播到全部 cache（上一讲 MSI） |
表 1 中”目录”一行是讲义 slide 10~18、37~43 的直接结论；”监听”一行是上一讲 MSI 协议的对照（
P为系统节点/核数，k为当前 sharer 数）。
- 图 4：read miss 到 dirty line 的完整时序与关键路径（讲义 slide 12~14、37）
READ MISS TO A DIRTY LINE (original scheme: 5 network transactions)
P0 (requesting) H = home node (dir + memory) P2 (owner)
| | |
(1) |---- read miss msg --------->| |
| dir entry: presence={P2}, D=1 |
(2) |<--- response: "owner=P2" ---| |
| | |
(3) |----------- request: data ---------------------------> |
| | |
(4) |<---------- data (cache-to-cache transfer) ------------ | (4) and (5)
| | | run in PARALLEL
(5) | |<-- data + dir revision --| P2 sets its copy
| | D=0, presence += P0 | to SHARED; H
v v v updates memory
critical path (dependent messages): (1) -> (2) -> (3) -> (4) = 4 hops
total transactions: 5 (message (5) is OFF the critical path)
caches that must react: 2 (a broadcast would involve all P caches)
WHY THIS MATTERS: the "5" counts bandwidth, the "4" counts latency.
optimizations in slide 38-43 attack these two numbers SEPARATELY.
- 图 5：write miss（k = 2 个 sharer）的失效与应答 + “并行失效 vs 串行失效”（讲义 slide 17、18、32~34）
WRITE MISS; line is CLEAN but resident in P1 and P2 (k = 2 sharers)
P0 (writer) H (home / dir) P1 $ P2 $
| | | |
(1) |--- write miss ------>| | |
(2) |<-- sharer ids + data-| | |
(3) | |--- invalidate ----> | | both
| |--- invalidate ---------------------> | independent
(4a) |<------------------------------ ack ------- | | => parallel
(4b) |<---------------------------------------------- ack --------- |
|
after BOTH acks arrive, P0 writes; dir: presence={P0}, D=1; P1,P2 -> I
messages = 2 + 2k ; critical path = 4 hops
FULL BIT VECTOR: invalidations are independent -> all k go out at once
H ===> n1 latency ~ O(1) hops (slide 34)
H ===> n2 traffic ~ O(k) msgs
H ===> n3
SPARSE DIRECTORY (linked list): the directory only knows the HEAD
H --> n1 --> n2 --> n3 latency ~ O(k) hops (slide 33)
(each hop needs a pointer stored in the previous cache's line)
2.6 失效模式（invalidation patterns）：为什么”目录真的有用”
- 定义与目的：目录的整个立论基础是“写的时候共享者其实很少”。讲义 slide 20~21 用 64 处理器系统上的 Barnes-Hut、LU、Ocean 三个应用的直方图来支撑这个论断：图的横轴是”一次写发生时该行的 sharer 数“，纵轴是频率；结论是 “in general only a few processors share the line（一般来说只有少数处理器共享该行）”，只有少数处理器需要被告知写操作。讲义还指出（图未显示）：sharer 的期望数量随 P 增长得非常慢（expected number of sharers typically increases slowly with P），这是好消息。
slide 21 把访问模式分成五类，这是本讲”为什么目录能省”的最重要定性依据：
- 表 2：访问模式 vs 目录压力（讲义 slide 21）
| 访问模式 | sharer 数 | 失效频率 | 对性能的影响 / 结论 |
|---|---|---|---|
| Mostly-read objects（多读少写） | 很多 sharer | 写很少 | 影响极小（讲义举例：Barnes-Hut 的根节点） |
| Migratory objects（迁移型对象） | 极少 sharer | 中 | sharer 数不随处理器数增长（一个处理器读/写一阵，再换下一个） |
| Frequently read/written objects（频繁读写） | 少 | 非常频繁 | 失效频繁，但 sharer 数来不及build up（两次失效之间时间太短，例如共享任务队列） |
| 低争用锁（low-contention locks） | 少 | 不频繁 | 无性能问题 |
| 高争用锁（high-contention locks） | 多 | — | 是难题：锁释放时恰好有很多读者在场（讲义原文） |
- 两条推论（讲义 slide 21 明确写出）：
- Implication 1：目录对限制一致性流量很有用——不需要广播机制去”告诉所有人”。
- Implication 2：这个观察暗示了目录实现可以怎么优化（尤其是降低存储开销）——因为 sharer 少，就可以不必为每个 node 都存一位。
- 直观解释（”它是什么？”）：想象一个 64 人的微信群（64 个核共享一行数据）。如果每次有人改一份文件都要 @全体成员（广播），群里就永远在响；而实际上多数时候只有 1~2 个人在改这份文件（migratory / 任务队列 / 低争用锁），所以正确做法是私聊那 1~2 个人（点对点失效）。唯一真正难的是抢红包式的热点锁：锁一释放，64 个人同时伸手，这时”要通知的人”确实很多——但那种情况在广播方案下更糟（所有人本来就在被通知）。
2.7 目录的存储开销：full bit vector 的账
- 定义与目的：full bit vector（全位向量）目录每个 cache line 需要 P 个 presence bit，存储量与 P × M 成正比（M = 内存中的行数）。讲义 slide 23 直接算账（按 64 B cache line = 512 bit）：
- P = 64 → 12% 开销；P = 256 → 50% 开销；P = 1024 → 200% 开销（即目录内存是数据内存的两倍）。
- 精确值为
P/512：12.5% / 50% / 200%（讲义把 12.5% 写成 12%，本笔记补充了精确值）。
- 减少开销的四条思路（slide 24 + 26 + 28~33）：
- 增大 cache line 尺寸（减小
M项）——讲义提醒要”考虑上一讲的直方图/曲线”，即行变大意味着一次失效作废更多数据、伪共享代价更大； - 把多个处理器合并成一个目录”节点”（减小
P项）——一个节点只需一位目录位，可以分层：节点内用监听，节点间用目录； - limited pointer schemes（有限指针方案）：用”少量指针的列表”代替位向量；
- sparse directories（稀疏目录）：只为当前真的在 cache 里的行保留目录信息。
- 增大 cache line 尺寸（减小
- 图 6：limited pointer 的”常见情况优化”与溢出处理（讲义 slide 25~28）
LIMITED POINTER SCHEME (exploit: only a FEW caches hold the line)
entry layout, k = 5 pointers, P = 1024:
+----+---------+---------+---------+---------+---------+
| D | ptr 0 | ptr 1 | ptr 2 | ptr 3 | ptr 4 |
+----+---------+---------+---------+---------+---------+
\___ 10 bits each = log2(1024) ___/
bits per entry = 1 + k*log2(P) = 1 + 5*10 = 51 bits (vs 1024 bits full vector)
OVERFLOW (more than k sharers) -- slide 26 gives three answers:
(a) FALL BACK TO BROADCAST
H ---> ALL CACHES "if a broadcast mechanism exists"
(b) CAP THE NUMBER OF SHARERS
newest sharer REPLACES an existing one
-> must INVALIDATE the line in the old sharer's cache
(c) COARSE VECTOR FALLBACK
revert to a bit vector, but each bit covers K nodes
-> on a write, invalidate ALL nodes mapped to that bit
THE DESIGN LESSON (slide 27, four steps):
1. workload-driven observation: sharer count is usually LOW
2. make the common case simple and fast: pointer array for the first N sharers
3. uncommon case is still CORRECT, just slower/more complex (program still works!)
4. the expensive path is tolerable because it happens rarely
- 表 3：三种目录表示法的存储与代价对比
| 方案 | 每个 cache line 的目录存储 | P=64 | P=256 | P=1024 | 优点 | 代价 |
|---|---|---|---|---|---|---|
| Full bit vector | P bit | 12.5% | 50% | 200% | 失效可并行发给所有 sharer，实现最简单 | 存储随 P 线性增长，P 大时不可接受 |
| Limited pointer（k=5） | 1 + k·log₂P bit | 6.05%（讲义写 5.8%） | 8.01%（7.8%） | 9.96%（9.7%） | 存储几乎与 P 无关 | 需要溢出处理（广播 / 顶替 / 粗向量） |
| Limited pointer（k=100） | 1 + 100·log₂P bit | 117.4% | 156.5% | 195.5% | —— | k 太大时比全位向量还差（P=1024 时临界点 k ≈ 102） |
| Sparse directory（链表） | 每行 1 个 head 指针（内存侧）+ cache line 里的 next 指针（SRAM 侧） | —— | —— | —— | 存储随 cache 大小而非内存大小扩展 | 失效串行沿链表传播，O(k) 延迟；实现复杂 |
讲义数字与公式的差异说明（本笔记补充）：讲义 slide 28 写
entry size = 1 + k log P，同时给出 k=5 时 5.8% / 7.8% / 9.7%。这三个数恰好等于k·log₂P / 512（5×6/512 = 5.86%、5×8/512 = 7.81%、5×10/512 = 9.77%），即讲义在算百分比时略去了那 1 位状态/脏位。带上+1位的精确值是 6.05% / 8.01% / 9.96%。两种口径都能说明同一件事：limited pointer 的存储开销几乎不随 P 增长（200% → 10%，20 倍改善）。另一个有用的临界点（本笔记补充）：
1 + k·log₂P < P ⟺ k < (P−1)/log₂P。P=1024 时k < 102.3，即指针数超过约 102 个就失去意义；讲义 slide 25 举的”~100 个指针”正好贴着这个临界点，所以它紧接着补充”in practice, our workload evaluation says we can get by with far less than this“（实践中远用不到这么多）。
2.8 稀疏目录（sparse directories）：只在”真的在 cache 里”的行上花内存
- 定义与目的：讲义 slide 29~31 的关键观察：绝大多数内存并不驻留在 cache 中，而一致性协议只需要”当前在 cache 里的行”的共享信息——所以大多数目录项在大多数时候是空的。讲义给的量化例子：每 node 1 MB cache、1 GB memory → 99.9% 的目录项是空的。于是：目录尺寸应该随 cache 大小（C）扩展，而不是随内存大小（M）扩展（
P·C位每处理器），每行只留一个 tag（标签）。 - 进一步压缩（slide 32~33）：home node 的目录只保存一个指向”链表中某个 node”的指针，而不是 sharer 列表；“指向下一个 node 的指针”被存在 cache line 的额外信息里（就像这一行的 tag、dirty bit 一样）。三项操作规则：
- read miss：把请求节点插到链表头（add requesting node to head of list）；
- write miss：沿链表传播失效（propagate invalidations along list）；
- evict（换出）：需要修补链表（linked list removal）。
- 讲义 slide 33 明确列出的好坏两面：
- Good：内存侧存储开销低（每行一个 head 指针）；额外的目录存储与 cache 大小成正比（链表存在 SRAM 里）；写时的流量仍与 sharer 数成正比。
- Bad：写的延迟与 sharer 数成正比（失效是串行的 invalidation of lines is serial）；实现复杂度更高。
- 与 full bit vector 的对照（slide 34）：位向量方案发送的失效消息数量相同，但失效消息可以并行发给所有处理器。
- 图 7：sparse directory 的链表结构（讲义 slide 32~33）
SPARSE DIRECTORY: a LINKED LIST threaded through the caches
home node's memory (DRAM) tag array (SRAM) of each cache
+---------------------------+ (one extra field per cached line)
| directory entry (1 per |
| line, often EMPTY) | n0: +------+------+
| head ptr ---------------)|---------------------->| tag | next |----+
+---------------------------+ +------+------+ |
| |
| most entries are EMPTY v
| (1MB cache vs 1GB memory -> 99.9% empty) n1: +------+------+
v | tag | next |---+
directory size scales with CACHE size, not memory size +------+------+ |
v
n2 (last): +------+------+
| tag | NULL |
+------+------+
read miss : splice requester at LIST HEAD O(1)
write miss : walk head -> ... -> tail, invalidate O(k) message latency <-- BAD
eviction : unlink the node from the list needs bookkeeping <-- COMPLEX
- 性能特征小结：
full bit vector是”空间换并行失效“（O(k)消息但O(1)跳数）；sparse list是”空间换串行失效“（存储降到极低，但延迟O(k)跳）。这正是讲义 slide 35 分出的两条优化主线：一路压目录数据结构的存储（limited pointer、sparse directory），一路压协议消息数/关键路径（下一节）。
2.9 减少消息数与关键路径：intervention forwarding 与 request forwarding
- 定义与目的：讲义 slide 35 把优化分成两类：减少目录结构的存储开销，以及减少实现一致性协议所需发送的消息数（messages sent）。后者给出两种转发策略，都是从 slide 12~14 那个”5 条消息 / 4 跳关键路径”的 dirty 读 miss 改进而来。
- intervention forwarding（干预转发，slide 38~40）：
- 请求 read miss 消息 → home；
- home 主动向 owner（P2）发 intervention read 请求；
- owner 把 data + dir revision 回给 home；
- home 更新目录，再把数据转发给请求节点。
- 结果：总共 4 条网络事务（流量更少），但四条全部在关键路径上。讲义在这一页直接追问：”Can we do better?”
- request forwarding（请求转发，slide 41~43）：
- 请求 read miss → home；
- home 只发一条”send data to requestor”给 owner；
- owner 把数据同时发给 home 和请求节点（”3/4. Response: data (2 msgs: sent to both home node and requestor)”）。
- 结果：总共 4 条网络事务，只有 3 条在关键路径上（事务 3 和 4 可以并行）。
- 讲义特别标注了一条重要性质：“系统不再是纯粹的请求/响应（pure request/response）”——因为 P0 把请求发给了 home，却从 owner 收到了应答。这一点对实现者非常重要：请求方必须能接受”非请求对象发来的应答”，这在互连网络与 MSHR（miss status holding register）设计上都要额外支持。
- 表 4：三种 dirty 读 miss 处理方案的对比（讲义 slide 12~14、38~43）
| 方案 | 网络事务数 | 关键路径（跳） | 关键路径上的事务 | 数据从哪来 | 额外性质 |
|---|---|---|---|---|---|
| 原始（5 消息） | 5 | 4 | 1→2→3→4 | owner → 请求方 | 事务 5（owner→home）不在关键路径 |
| intervention forwarding | 4 | 4 | 全部 4 条 | owner → home → 请求方 | 流量少 1 条，延迟不变 |
| request forwarding | 4 | 3 | 1→2→3（3、4 并行里的 3） | owner → 请求方（并抄送 home） | 不再是纯请求/响应，需要支持”非对称应答” |
- 图 8：两种转发策略的时间线（讲义 slide 37、40、43）
TIMELINE OF "READ MISS TO A DIRTY LINE": where the hops go
hop #: 1 2 3 4
--------------------------------------------------------------------------
original: P0 --> H H --> P0 P0 --> P2 P2 --> P0
(read miss) (owner id) (req data) (data)
msgs = 5 crit = 4 plus P2 --> H (off the critical path)
intervention:
P0 --> H H --> P2 P2 --> H H --> P0
msgs = 4 crit = 4 home stays in the middle: +1 traffic hop,
no latency gain
request fwd:
P0 --> H H --> P2 P2 --> P0 || P2 --> H
(data to requestor) (dir revision)
msgs = 4 crit = 3 <-- shortest critical path
reply does NOT come from H
SUMMARY: messages : 5 -> 4 -> 4 (bandwidth / traffic)
crit hops : 4 -> 4 -> 3 (latency)
an optimization that shortens the critical path may need NEW protocol
machinery (here: accept a reply from a node you never asked)
2.10 真实硬件：Intel Core i7 的 L3 目录与多 socket 的 home agent
- 讲义 slide 44（单 socket）：
- L3 cache 充当所有 L3 中行的集中式目录（L3 serves as centralized directory for all lines in the L3 cache）；讲义强调inclusion property（包含属性） 的重要性——任何在 L2 中的行，在 L3 目录里必定有目录项（否则目录会漏掉 sharer，协议就不正确了）。
- 目录维护“哪些 L2 cache 持有该行”的列表；因此不再向所有 L2 广播一致性流量，只给持有该行的 L2 发一致性消息。
- 讲义还点明：“Core i7 的互连是环形（ring），不是总线（bus）”——所以广播在这里本来就不自然。
- 目录维度：P = 4（4 个核），C = L3 的 cache line 数（这正是 sparse directory 的”随 cache 大小扩展”的思路！）。
- 讲义 slide 45（多 socket）：
- 单 socket 内的 L3 目录减少片上一致性流量（上一页）；
- 内存中的目录（in-memory directory） 由 home agent / memory controller 缓存（dir cache，16 KB），减少核与核之间（跨 socket）的一致性流量；
- 关键角色：cache agent（片上，说监听/一致性协议的那一端）、home agent（拥有本 socket DRAM 的目录）、memory controller、QPI（QuickPath Interconnect） 连接两个 socket，DRAM 侧则是 in-memory directory。
- 图 9：Core i7 的环形互连 + L3 目录，以及多 socket 的目录层次（讲义 slide 44、45）
(A) SINGLE SOCKET: shared L3 = the directory (slide 44)
+-------+ +-------+ +-------+ +-------+
| Core | | Core | | Core | | Core | P = 4
| L1D$ | | L1D$ | | L1D$ | | L1D$ |
| L2 $ | | L2 $ | | L2 $ | | L2 $ | each L2 is private
+---+---+ +---+---+ +---+---+ +---+---+
| | | |
+---v----------v----------v----------v-----------------+
| SHARED L3, one bank per core, DIRECTORY for all L3 | <- inclusion:
| lines: "which L2s hold this line?" | any line in an L2
+------------------------------------------------------+ HAS a dir entry
| RING INTERCONNECT (not a bus!) | (4 rings in
+------------------------------------------------------+ Sandy Bridge:
req/snoop/ack/data)
(B) MULTI-SOCKET: two directory levels (slide 45)
+----------------------------+ QPI +----------------------------+
| Socket 0 |<-------->| Socket 1 |
| 4 x (Core + L1 + L2) | | 4 x (Core + L1 + L2) |
| L3 cache + L3 DIRECTORY | | L3 cache + L3 DIRECTORY | on-chip dir:
| (cuts on-chip traffic)| | (cuts on-chip traffic)| only notify
| Cache Agent | | Cache Agent | the L2s that
| Home Agent + 16KB dir$ | | Home Agent + 16KB dir$ | hold the line
| Memory Controller | | Memory Controller | in-memory dir:
+-------------+--------------+ +--------------+-------------+ cuts traffic
| | BETWEEN cores
to DRAM to DRAM
(IN-MEMORY DIRECTORY) (IN-MEMORY DIRECTORY)
- 性能特征（本笔记补充的量化视角）：16 KB 的 dir cache 是内存目录的 cache。若每个目录项压缩到约 4 B，则 16 KB ≈ 4096 个目录项；64 GB DRAM 按 64 B 行算有 10.7 亿行，即 dir cache 只能覆盖约 0.0004% 的行。它的价值完全来自局部性：应用反复访问同一批行时，目录查询在 home agent 的 SRAM 里命中，省掉一次 DRAM 往返（约 70~100 ns，本笔记补充假设），跨 socket 的失效因此不会被 DRAM 目录访问拖成瓶颈。这也解释了两级目录的分工：L3 目录解决”片上要不要广播”，in-memory directory 解决”socket 之间要不要广播”。
2.11 软件侧的执行模型：cc-NUMA 上”数据落在哪、线程跑在哪”
- 定义与目的：硬件给出的是”谁 home、谁 sharer、谁 owner”；软件要控制的只有两件事：数据的 home node（由首次触碰决定） 与线程所在的 node（由调度/亲和性决定）。这两者错配时，程序就要付 3~4 跳的远程延迟；而伪共享会把两条本该互不相干的数据变成同一条 cache line 上的来回迁移。
- 直观解释（”它是什么？”）：把 cc-NUMA 想成一栋楼里 4 个厨房 + 4 张书桌。
first touch规则像”谁先把锅端进哪个厨房，这口锅以后就归那个厨房保管“（home node）；如果你的书桌在 0 层而锅在 3 层，每次做饭都要坐电梯（远程访问）。伪共享更像”两个人的牙刷被绑在同一根绳子上“：明明各用各的，但一个人动一下，另一个人手里的东西就被判为作废（invalidate），绳子在两人之间来回传。 - 图 10：软件执行模型（线程亲和 + first touch + 伪共享）（本笔记补充示意，机制依据讲义 slide 4、8、9、20、21）
SOFTWARE VIEW OF A 4-NODE cc-NUMA MACHINE (directory = home of each line)
node 0 node 2
+-------------+ +-------------+
| thread 0 | <--- remote ---> | thread 1 |
| A[0 .. N/4) | 3~4 hop dirty | A[N/4 ..N/2)|
| home: node 0| read miss | home: node 2|
+-------------+ +-------------+
WHO DECIDES THE HOME NODE? "FIRST TOUCH"
for (i=0;i<N;i++) A[i] = 0; // master only
-> ALL pages of A get home node 0
-> 7 of 8 threads always pay remote latency
#pragma omp parallel for schedule(static)
for (i=0;i<N;i++) A[i] = 0; // every thread touches its own slice
-> pages are spread over the nodes that run the threads (LOCAL)
TWO SEPARATE PROBLEMS, TWO SEPARATE FIXES
(1) placement: parallel first touch / memory interleaving / numactl
(2) coherence: even with perfect placement, a line written by several
nodes still costs O(k) invalidation messages
-> pad to cache lines, privatize, or reduce sharing
FALSE SHARING (worst case of "nobody shares anything, but the line does")
two nodes write DIFFERENT variables that live in ONE 64 B line:
node 0 writes x | 64 B line: [ x ][ y ][ pad .................. ]
node 2 writes y |
-> the LINE ping-pongs: each write is a write miss / invalidation
-> directory is correct but useless: real sharers = 2, forever
-> fix: align each hot variable to 64 B (alignas(64) / padding)
2.12 目录协议的状态机（directory 视角与 cache 视角）
- 定义与目的：上一讲的 MSI/MESI 描述的是单个 cache 里的行状态；这一讲要补上目录里的行状态，因为协议是否正确取决于两者严格对应。讲义给出的三种目录状态对应：UNCACHED（没有任何 cache 持有，presence 全 0，D=0）、SHARED（presence 非 0，D=0）、DIRTY（正好一个 node 持有 M 副本，D=1）。不变量：目录中 D=1 ⟺ 恰好一个 cache 把该行保持在 M 状态。
直观解释（”它是什么？”）：目录状态机像图书借阅卡片的状态：
UNCACHED= 书在书架上没人借；SHARED= 有人借去复印（可以多人同时有复印件，原书没被改）；DIRTY= 有一个人把书拿去改了（原书已过期，复印/归还前必须找他要最新版）。- 图 11：目录行状态机 + 与 per-cache MSI 状态的对应（依据讲义 slide 8、11~18、32~34 与上一讲 MSI）
DIRECTORY'S VIEW OF ONE LINE
read miss (D=0): reply from memory, set presence[req]
+-----------------------+ <-------------------------------------------+
| UNCACHED | |
| presence = 00...0 | |
| D = 0 | |
+-----------+-----------+ |
| |
| read miss -> SHARED | last sharer
v | evicts
+-----------------------+ write miss: |
| SHARED | invalidate all sharers, |
| presence != 0, D = 0 | grant exclusive +--------+--------+
+-----------+-----------+ ------------------------------------->| DIRTY |
^ | presence={owner}|
| read miss from ANOTHER node: | D = 1 |
| D := 0, presence += requester, +--------+--------+
| owner's cache: M -> S |
+-------------------------------------------------------------+
(the owner must send data + dir revision to home)
PER-CACHE LINE STATE (MSI, previous lecture) -- what the directory is tracking
I : Invalid -- no valid copy
S : Shared -- read-only copy, line is also CLEAN in memory (dir D = 0)
M : Modified -- the ONLY copy, dirty; the directory records this node as OWNER
INVARIANT (must hold at all times):
dir.D == 1 <=> exactly one cache holds the line in M
presence[i] == 1 for every cache i holding the line in S or M
- 性能特征：三种目录状态之间的迁移代价差别极大——
UNCACHED → SHARED（2 条消息）、SHARED → DIRTY（2 + 2k条消息、4 跳）、DIRTY → SHARED（4~5 条消息、3~4 跳）。协议设计者的任务就是把最常见的那条迁移路径变短（这正是 limited pointer 与 request forwarding 在做的事）。
3. 代码示例与性能分析
目录协议本身是硬件行为，但它的每一条消息、每一跳延迟、每一个 presence bit 都可以在软件里精确建模。下面三个例子分别回答三个问题：(1) 目录协议到底发多少消息、关键路径多长、目录要多大的存储；(2) 一致性流量在真实多核机器上值多少纳秒；(3) cc-NUMA 上”数据放在哪个 node“值多少带宽。
3.1 示例 1：目录协议模拟器（消息数 / 关键路径 / 存储开销）
- 代码（完整可运行，模拟讲义 slide 10~18、37~43 的协议并统计开销）：
// ===========================================================================
// dir_sim.cpp -- directory coherence protocol simulator
// 统计每种一致性事件的: 消息条数(msgs) / 关键路径跳数(crit hops) /
// 必须做动作的 cache 数(caches-involved)，并计算目录存储开销
// 编译 (release): g++ -O3 -std=c++17 dir_sim.cpp -o dir_sim
// 运行: ./dir_sim
// ===========================================================================
#include <cstdint>
#include <cstdio>
#include <vector>
#include <cmath>
enum class CS : uint8_t { I, S, M }; // 一条 line 在某个 node 私有 cache 中的 MSI 状态
// 一次一致性操作消耗的网络资源
struct Net {
long msgs = 0; // 网络消息条数 -> 决定流量/带宽占用
long hops = 0; // 关键路径跳数 -> 决定延迟(critical path)
long snooped = 0; // 必须检查/动作的 cache 数 -> 决定 snoop 工作量
};
struct DirEntry { // 每个 cache line 一个目录项 (full bit vector)
uint64_t presence = 0; // presence bits: 哪些 node 持有该行
bool dirty = false; // dirty bit: 是否有一个 node 持有 M 副本
int owner = -1; // dirty 时的 owner node (数据源头)
};
class Machine {
public:
Machine(int nodes, int lines)
: P(nodes), L(lines),
cache(nodes, std::vector<CS>(lines, CS::I)), dir(lines) {}
int sharers(int line) const { return __builtin_popcountll(dir[line].presence); }
// ---- 事件 (a): read miss 到 CLEAN line (讲义 slide 10-11): 2 msgs / 2 hops
Net readMissClean(int req, int line) {
Net n;
n.msgs = 1; n.hops = 1; n.snooped = 1; // (1) request -> home
dir[line].presence |= (1ull << req); // home: presence[req] = 1
cache[req][line] = CS::S; // (2) data from memory
n.msgs += 1; n.hops += 1;
return n;
}
void finishReadDirty(int req, int line, int own) { // owner M -> S, D := 0
cache[own][line] = CS::S;
cache[req][line] = CS::S;
dir[line].dirty = false;
dir[line].owner = -1;
dir[line].presence |= (1ull << req);
}
// ---- 事件 (b1): read miss 到 DIRTY line, 原始 5 消息版 (slide 12-14)
// 1 request -> home | 2 home->req (owner id) | 3 req->owner
// 4 owner->req (data, 关键路径) | 5 owner->home (data+rev, 与 4 并行)
Net readMissDirty_original(int req, int line) {
Net n; const int own = dir[line].owner;
n.msgs += 1; n.hops += 1; // 1
n.msgs += 1; n.hops += 1; // 2
n.msgs += 1; n.hops += 1; // 3
n.msgs += 1; n.hops += 1; // 4 <- 关键路径到此结束 (4 hops)
n.msgs += 1; // 5 <- off the critical path
n.snooped = 2; // home + owner
finishReadDirty(req, line, own);
return n;
}
// ---- 事件 (b2): intervention forwarding (slide 38-40): 4 msgs, 4 hops (all on path)
// home 先去 owner 取数据、更新目录, 再转发给请求方
Net readMissDirty_intervention(int req, int line) {
Net n; const int own = dir[line].owner;
n.msgs += 1; n.hops += 1; // 1 req -> home
n.msgs += 1; n.hops += 1; // 2 home -> owner (intervention read)
n.msgs += 1; n.hops += 1; // 3 owner-> home (data + dir revision)
n.msgs += 1; n.hops += 1; // 4 home -> req (data)
n.snooped = 2;
finishReadDirty(req, line, own);
return n;
}
// ---- 事件 (b3): request forwarding (slide 41-43): 4 msgs, 3 hops
// home 只让 owner 把数据"发给请求方"(并抄送 home 更新目录)
Net readMissDirty_forward(int req, int line) {
Net n; const int own = dir[line].owner;
n.msgs += 1; n.hops += 1; // 1 req -> home
n.msgs += 1; n.hops += 1; // 2 home -> owner ("send data to requestor")
n.msgs += 2; n.hops += 1; // 3+4 owner -> req 数据, owner -> home 目录修订
n.snooped = 2; // 两条并行 => 只算 1 跳
finishReadDirty(req, line, own);
return n;
}
// ---- 事件 (c): write miss, line clean, k 个 sharer (slide 15-18)
// msgs = 2 + 2k (k 条失效 + k 条 ack), 关键路径 4 跳 (失效/应答可并行)
Net writeMissClean(int req, int line) {
Net n; const int k = sharers(line) - ((dir[line].presence >> req) & 1ull);
n.msgs += 2; n.hops += 2; // 1 request, 2 sharer ids + data
n.snooped = k + 1; // 请求方 + 所有被失效的 sharer
n.msgs += 2 * (long)k; n.hops += 2; // 3 invalidate x k, 4 ack x k
for (int p = 0; p < P; ++p) // 被失效的 cache: -> I
if (p != req && ((dir[line].presence >> p) & 1ull)) cache[p][line] = CS::I;
dir[line].presence = (1ull << req); // 目录: presence={req}, D=1
dir[line].dirty = true;
dir[line].owner = req;
cache[req][line] = CS::M;
return n;
}
// ---- 事件 (c'): write miss 到 DIRTY line (讲义未展开, 本示例按同一套规则推导:
// 先用 request forwarding 拿到脏数据(3 跳), 再失效其余 sharer (2 跳) = 5 跳)
Net writeMissDirty_forward(int req, int line) {
Net n; const int own = dir[line].owner;
const int k = sharers(line) - 1; // 除 owner 以外的 sharer
n.msgs += 4; n.hops += 3; n.snooped = 2;
cache[own][line] = CS::I; // owner 交出独占权, 自己的副本失效
n.msgs += 2 * (long)k; n.hops += 2; n.snooped += k;
for (int p = 0; p < P; ++p)
if (p != req && p != own && ((dir[line].presence >> p) & 1ull)) cache[p][line] = CS::I;
dir[line].presence = (1ull << req);
dir[line].dirty = true;
dir[line].owner = req;
cache[req][line] = CS::M;
return n;
}
int P, L;
std::vector<std::vector<CS>> cache; // [node][line]
std::vector<DirEntry> dir; // [line]
};
static void report(const char* what, Net d) {
printf("%-42s | msgs %3ld | crit-hop %2ld | caches-involved %3ld\n",
what, d.msgs, d.hops, d.snooped);
}
int main() {
const int P = 64, L = 1024; // 64 个 node (讲义 slide 20 的规模)
printf("== directory vs snooping : cost of ONE coherence event (P=%d) ==\n", P);
Machine m0(P, L);
report("read miss, clean (directory)", m0.readMissClean(0, 0));
printf("%-42s | msgs %3d | crit-hop %2d | caches-involved %3d\n",
"read miss, clean (snooping broadcast)", 2, 2, P);
Machine a(P, L); a.cache[2][1] = CS::M;
a.dir[1].dirty = true; a.dir[1].owner = 2; a.dir[1].presence = (1ull << 2);
report("read miss, dirty (5-msg original)", a.readMissDirty_original(0, 1));
Machine b(P, L); b.cache[2][1] = CS::M;
b.dir[1].dirty = true; b.dir[1].owner = 2; b.dir[1].presence = (1ull << 2);
report("read miss, dirty (intervention fwd)", b.readMissDirty_intervention(0, 1));
Machine c(P, L); c.cache[2][1] = CS::M;
c.dir[1].dirty = true; c.dir[1].owner = 2; c.dir[1].presence = (1ull << 2);
report("read miss, dirty (request fwd)", c.readMissDirty_forward(0, 1));
Machine d(P, L); d.dir[1].presence = (1ull << 1) | (1ull << 2);
d.cache[1][1] = CS::S; d.cache[2][1] = CS::S;
report("write miss, k=2 sharers (directory)", d.writeMissClean(0, 1));
printf("%-42s | msgs %3d | crit-hop %2d | caches-involved %3d\n",
"write miss, k=2 (snooping BusRdX)", 2, 2, P + 1);
Machine e(P, L); e.dir[1].presence = (1ull << 2) | (1ull << 3);
e.cache[2][1] = CS::M; e.cache[3][1] = CS::S;
e.dir[1].dirty = true; e.dir[1].owner = 2;
report("write miss, k=2 (dirty, request fwd)", e.writeMissDirty_forward(0, 1));
printf("\n== directory storage overhead (64 B line = 512 bit) ==\n");
for (int n : {64, 256, 1024}) {
const double lg = std::log2((double)n);
printf("P=%4d : full vector %6.1f%% | limited ptr k=5 %5.2f%% | k=100 %6.2f%%\n",
n,
100.0 * n / 512.0,
100.0 * (1.0 + 5.0 * lg) / 512.0,
100.0 * (1.0 + 100.0 * lg) / 512.0);
}
printf("breakeven pointer count at P=1024 : k < (P-1)/log2(P) = %.1f\n",
(1024.0 - 1.0) / 10.0);
return 0;
}
【代码做什么？】
- 用
enum class CS { I, S, M }表示每条 cache line 在每个 node 私有 cache 里的 MSI 状态；DirEntry就是讲义 slide 8 的目录项：presence（64 位位向量，P = 64时正好够用）+dirty+owner。 - 每个
readMiss*/writeMiss*函数对应讲义的一个 slide：函数体里逐步累加msgs（消息条数）、hops（关键路径跳数）、snooped（必须做动作的 cache 数），并同步更新目录与各 cache 的状态——所以它既是”计数器”也是一个可执行的协议状态机（跑完之后目录与 cache 的状态与讲义图的最终状态一致）。 readMissDirty_original与readMissDirty_forward的差别只有消息的接收方：前者owner → 请求方、home再被通知一次（5 条消息、4 跳）；后者owner同时发给请求方和 home（4 条消息、3 跳），这正是讲义 slide 43 的”3/4. Response: data（2 msgs: sent to both home node and requestor）”。main()复现讲义 slide 10~18 的三类事件并打印表 1的数字，然后用storage overhead = (P+1)/512打印讲义 slide 23、28 的百分比，最后算出”limited pointer 在多大规模下失去意义”的临界指针数。
【实测输出（本笔记写作机器上 g++ -O3 运行结果）】
== directory vs snooping : cost of ONE coherence event (P=64) ==
read miss, clean (directory) | msgs 2 | crit-hop 2 | caches-involved 1
read miss, clean (snooping bcast) | msgs 2 | crit-hop 2 | caches-involved 64
read miss, dirty (5-msg original) | msgs 5 | crit-hop 4 | caches-involved 2
read miss, dirty (intervention fwd) | msgs 4 | crit-hop 4 | caches-involved 2
read miss, dirty (request fwd) | msgs 4 | crit-hop 3 | caches-involved 2
write miss, k=2 sharers (directory) | msgs 6 | crit-hop 4 | caches-involved 3
write miss, k=2 (snooping BusRdX) | msgs 2 | crit-hop 2 | caches-involved 65
write miss, k=2 (dirty, request fwd) | msgs 6 | crit-hop 5 | caches-involved 3
== directory storage overhead (64 B line = 512 bit) ==
P= 64 : full vector 12.5% | limited ptr k=5 6.05% | k=100 117.38%
P= 256 : full vector 50.0% | limited ptr k=5 8.01% | k=100 156.45%
P=1024 : full vector 200.0% | limited ptr k=5 9.96% | k=100 195.51%
breakeven pointer count at P=1024 : k < (P-1)/log2(P) = 102.3
【并行机制与性能解说】
- 模拟器本身的并行性 = 1：这是串行分析工具，
Work = Θ(Σᵢ (kᵢ + 2))（每个事件要构造/统计k+2条消息），Span = Θ(E)（E 个事件串行处理），并行度 ≈ k̄ + 2，所以它只适合作为”记账器”，不适合当性能测试。被建模的机器才是并行的：P个 node 可以同时发起各自的一致性事件，只要它们打到的目录分区不冲突——这正是目录”分区（sliced）”带来的并行度≈ P。 - 消息数决定带宽，跳数决定延迟：
msgs影响互连网络的吞吐量上限（每条消息占用链路周期与 cache 控制器时间），hops影响单次 miss 的延迟，snooped影响每个 cache 的 snoop 工作量。三者必须分开优化：intervention forwarding 只降msgs（5→4），request forwarding 只降hops（4→3）。 - 瓶颈在哪：真机上，
hops直接乘上每跳延迟（下面 §4.1 算例用 30 ns/跳）；msgs × k决定了写密集负载的流量墙；snooped = P说明了广播方案在P增大时被”卷入”的 cache 数线性增长，而目录方案只有k + 1（P=64、k=2 时是 3 vs 65，差 21 倍）。
3.2 示例 2：pthreads 一致性流量探针（共享一行在真实机器上值多少纳秒）
- 代码（完整可运行；三种写法只差在”几个线程碰同一条 cache line”）：
// ===========================================================================
// coherence_probe.c -- 量化"一条 cache line 被多个核同时写"的代价
// A: 每个线程写自己独占的 line (无一致性流量)
// B: 所有线程写同一条 line (每次写都可能触发独占 + 失效)
// C: 所有线程对同一条 line 做原子 RMW (每次操作都要所有权迁移)
// 编译 (release): gcc -O3 -pthread -std=c11 coherence_probe.c -o coherence_probe
// 运行: ./coherence_probe <threads> <total_increments>
// ===========================================================================
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LINE_LONGS 8 /* 8 x 8 B = 64 B = 一条 cache line */
#define MAX_THREADS 32
static long g_rounds; /* 每个线程的增量次数 */
static long g_threads;
static volatile long private_slots[MAX_THREADS * LINE_LONGS]; /* 每线程一条私有 line */
static volatile long shared_line_slots[MAX_THREADS]; /* 所有线程挤在 line 0 */
static volatile long g_counter; /* 原子 RMW 的目标 */
typedef struct { int tid; } arg_t;
static double now_s(void) {
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return (double)ts.tv_sec + 1e-9 * (double)ts.tv_nsec;
}
/* A: 私有 line —— 写命中本核的 M 副本, 不产生任何一致性流量 */
static void* worker_private(void* p) {
const int tid = ((arg_t*)p)->tid;
volatile long* slot = &private_slots[(size_t)tid * LINE_LONGS];
for (long i = 0; i < g_rounds; ++i) *slot += 1;
return NULL;
}
/* B: 所有线程写同一条 line —— 每次所有权迁移都要让其他 sharer 的副本失效 */
static void* worker_shared(void* p) {
volatile long* slot = &shared_line_slots[0];
for (long i = 0; i < g_rounds; ++i) *slot += 1;
(void)p;
return NULL;
}
/* C: 原子 RMW —— 每次操作都必须拿到独占权, 成本 = 一次所有权迁移 */
static void* worker_rmw(void* p) {
const long per = g_rounds / g_threads;
for (long i = 0; i < per; ++i) __sync_fetch_and_add((long*)&g_counter, 1);
(void)p;
return NULL;
}
static double run(void* (*fn)(void*)) {
pthread_t th[MAX_THREADS];
arg_t a[MAX_THREADS];
const double t0 = now_s();
for (long i = 0; i < g_threads; ++i) { a[i].tid = (int)i; pthread_create(&th[i], NULL, fn, &a[i]); }
for (long i = 0; i < g_threads; ++i) pthread_join(th[i], NULL);
return now_s() - t0;
}
int main(int argc, char** argv) {
g_threads = (argc > 1) ? atol(argv[1]) : 8;
g_rounds = (argc > 2) ? atol(argv[2]) : 40000000L;
if (g_threads < 1) g_threads = 1;
if (g_threads > MAX_THREADS) g_threads = MAX_THREADS;
const long per = g_rounds / g_threads;
const long total = per * g_threads;
const double tp = run(worker_private);
const double ts = run(worker_shared);
const double tr = run(worker_rmw);
printf("threads=%ld ops/thread=%ld total=%ld\n", g_threads, per, total);
printf("A private line : %7.3fs -> %6.2f ns/op (no coherence traffic)\n",
tp, 1e9 * tp / total);
printf("B one shared line : %7.3fs -> %6.2f ns/op (%ld threads fight)\n",
ts, 1e9 * ts / total, g_threads);
printf("C atomic RMW on line : %7.3fs -> %6.2f ns/op (ownership transfer)\n",
tr, 1e9 * tr / total);
printf("B/A = %.1fx C/A = %.1fx\n", ts / tp, tr / tp);
return 0;
}
【代码做什么？】 三个 worker 做完全相同数量的增量操作（每个线程 per 次，总共 total = per × g_threads 次），唯一区别是这些操作打在几条 cache line 上：
- A：
private_slots[tid*8]，每个线程写自己独占的 64 B 行（volatile阻止编译器把循环优化掉，也保证每次都是真正的 load-add-store）→ 每次写都是本地 cache 命中； - B：所有线程写
shared_line_slots[0]，同一条 line 被 8 个核反复争抢； - C：
__sync_fetch_and_add对同一条 line 做原子读改写（RMW），每次操作都必须先拿到独占所有权（read-exclusive），即每次操作都要一次”失效 → 授权 → 数据搬运”的所有权迁移——这正是目录协议里SHARED → DIRTY（2 + 2k条消息、4 跳）或监听协议里BusRdX广播的软件可见成本。
【实测数据（本笔记写作机器，8M 次总操作，取一次运行）】
| 线程数 | A 私有 line (ns/op) | B 同一条 line (ns/op) | C 原子 RMW (ns/op) | B/A | C/A |
|---|---|---|---|---|---|
| 1 | 0.48 | 0.40 | 2.45 | 1.0× | 6.1× |
| 2 | 0.44 | 1.38 | 6.44 | 3.1× | 14.6× |
| 4 | 0.48 | 6.57 | 5.96 | 13.7× | 12.4× |
| 8 | 0.53 | 16.22 | 10.51 | 30.6× | 19.8× |
| 16 | 0.57 | 87.30 | 26.20 | 153× | 46× |
- 三个现象与讲义的对应关系：
- 单线程时 B 与 A 一样快（0.40 vs 0.48 ns）——因为此时没有别的 sharer，写命中已独占的 M 副本，一致性协议完全不出现在关键路径上。这与讲义 slide 8”目录项记录 sharer”的前提一致：共享者少 = 协议几乎免费。
- B 随线程数急剧恶化（0.40 → 87 ns/op，153 倍）：每多一个 sharer，每一次所有权迁移就要多发一条失效并等一个 ack，即
k直接进入成本。这正是讲义 slide 21 里 “frequently read/written objects: frequent invalidations” 与 “high-contention locks: can be a challenge, because many readers present when lock released” 的实证。 - C 的增长比 B 缓和（16 线程时 26 vs 87 ns）：原子 RMW 只要求”独占”，不要求其他核先读到旧值，失效/授权在硬件里流水化处理；而 B 的普通 load-add-store 会出现读写交替的震荡（thrashing）。
- Work / Span / 并行度（取 8 线程、总操作 8M）：
- A（私有行）：
Work = 8,000,000次增量；Span = 500,000 × t_store_forward（每个线程一条依赖链，t_store_forward ≈ 3~5 cycle ≈ 1 ns）→Span ≈ 0.5 ms；并行度 = Work/Span = 8 = T，完全可扩展；实测 0.004 s（含线程创建/调度开销），每个线程 0.53 ns/op ≈ 2 cycle。 - B（同一行）：
Work仍是 8M 次写，但所有写必须串行地拥有那一条 line：Span = 8,000,000 × t_transfer，其中t_transfer ≈ 16.2 ns→Span ≈ 130 ms= 实测 0.130 s。并行度 = 1，加线程只会变慢（16 线程 87 ns/op 说明t_transfer本身还随k变大而上升）。可扩展性上限 = 1/(t_transfer × k̄)。 - C（原子 RMW）：
Span = 8,000,000 × t_transfer ≈ 8M × 10.5 ns ≈ 84 ms= 实测 0.084 s；并行度 = 1，单行吞吐上限 ≈1/10.5 ns ≈ 95 M ops/s。
- A（私有行）：
- 瓶颈：延迟受限（latency-bound），不是带宽受限。用 Little’s law 验证：要让 8 个线程各以 1 op/ns 推进（8 G ops/s），在
t_transfer = 16.2 ns下需要同时在飞的迁移数 = 8 G/s × 16.2 ns ≈ 130；但一条 cache line 上同一时刻只允许一次迁移，所以上限只能是1/16.2 ns ≈ 61.7 M ops/s——实测 8M/0.130 s = 61.5 M ops/s，与预测几乎完全一致。这就是”每行每时刻一次迁移“这个硬件约束的直接后果，也是为什么目录协议要把k压小、把失效并行发出。
3.3 示例 3：OpenMP first-touch —— cc-NUMA 上”数据放在哪个 node”
- 代码（完整可运行；对比”串行 first touch”与”并行 first touch”两种数据布局）：
// ===========================================================================
// numa_first_touch.c -- cc-NUMA 上数据放置(first touch)对带宽的影响
// 串行初始化 -> 所有页的 home node = master 所在 node
// 并行初始化 -> 每个线程触碰自己的那份 -> 页分散到各 node (LOCAL)
// 编译 (release): gcc -O3 -fopenmp -std=c11 numa_first_touch.c -o numa_first_touch
// 运行: OMP_NUM_THREADS=8 ./numa_first_touch 8000000
// ===========================================================================
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char** argv) {
const size_t N = (argc > 1) ? strtoull(argv[1], NULL, 10) : (size_t)8 * 1024 * 1024;
const size_t bytes = N * sizeof(double);
double *as = malloc(bytes), *bs = malloc(bytes), *cs = malloc(bytes); /* serial placement */
double *ap = malloc(bytes), *bp = malloc(bytes), *cp = malloc(bytes); /* parallel placement */
if (!as || !bs || !cs || !ap || !bp || !cp) { fprintf(stderr, "alloc failed\n"); return 1; }
const int P = omp_get_max_threads();
double t0 = omp_get_wtime();
for (size_t i = 0; i < N; ++i) as[i] = 1.0; /* 单线程 first touch: 页全落在 master 的 node */
for (size_t i = 0; i < N; ++i) bs[i] = 2.0;
for (size_t i = 0; i < N; ++i) cs[i] = 0.0;
const double t_place_serial = omp_get_wtime() - t0;
t0 = omp_get_wtime();
#pragma omp parallel for schedule(static)
for (size_t i = 0; i < N; ++i) ap[i] = 1.0; /* 并行 first touch: 页落在触碰它的线程所在 node */
#pragma omp parallel for schedule(static)
for (size_t i = 0; i < N; ++i) bp[i] = 2.0;
#pragma omp parallel for schedule(static)
for (size_t i = 0; i < N; ++i) cp[i] = 0.0;
const double t_place_par = omp_get_wtime() - t0;
double best_s = 1e30, best_p = 1e30;
for (int rep = 0; rep < 5; ++rep) { /* triad: c[i] = a[i] + 2*b[i] */
t0 = omp_get_wtime();
#pragma omp parallel for schedule(static)
for (size_t i = 0; i < N; ++i) cs[i] = as[i] + 2.0 * bs[i];
double t = omp_get_wtime() - t0; if (t < best_s) best_s = t;
t0 = omp_get_wtime();
#pragma omp parallel for schedule(static)
for (size_t i = 0; i < N; ++i) cp[i] = ap[i] + 2.0 * bp[i];
t = omp_get_wtime() - t0; if (t < best_p) best_p = t;
}
const double triad_bytes = 3.0 * (double)bytes; /* 2 读 + 1 写 */
printf("threads=%d N=%zu (%.1f MB/array)\n", P, N, bytes / 1048576.0);
printf("placement : serial %.4fs | parallel %.4fs\n", t_place_serial, t_place_par);
printf("triad serial-placement : %.4fs -> %7.2f GB/s\n", best_s, triad_bytes / best_s / 1e9);
printf("triad parallel-placement: %.4fs -> %7.2f GB/s\n", best_p, triad_bytes / best_p / 1e9);
printf("locality gain = %.2fx\n", best_s / best_p);
free(as); free(bs); free(cs); free(ap); free(bp); free(cp);
return 0;
}
【代码做什么？】 分配两组同样的向量三元组（a/b/c）。第一组用单线程循环初始化：Linux/大多数 OS 采用 first touch（首次触碰） 页分配策略，因此所有页都落在 master 线程所在的 node（讲义 slide 4 的 cc-NUMA 语义：home node 由内存物理位置决定）。第二组用 #pragma omp parallel for schedule(static) 并行初始化：每份页由将来使用它的线程触碰，于是页分散到各自 node，成为本地内存（local）。随后分别对两组跑 5 次 triad（c = a + 2b），取最快的一次，用 3 × N × 8 B 计算实测带宽并给出 locality gain。
【实测数据（本笔记写作机器，OMP_NUM_THREADS=8，N = 8M，每数组 61 MB，超出一级/二级 cache，是真实 DRAM 带宽测试）】
threads=8 N=8000000 (61.0 MB/array)
placement : serial 0.0903s | parallel 0.0192s
triad serial-placement : 0.0014s -> 139.00 GB/s
triad parallel-placement: 0.0009s -> 211.85 GB/s
locality gain = 1.52x
- 说明：这台机器是多 socket 的大内存机器，因此串行放置确实付出了跨 node 访问的代价：139 GB/s → 212 GB/s，1.52 倍。如果在单 socket（非 NUMA）或虚拟机上运行，两个数字会几乎相同——这恰好就是讲义 slide 4 的第二个要点：只有”就近访问”这一半做好了还不够，一致性协议本身也必须可扩展（否则每次 miss 的广播会把 locality 省下的时间吃掉）。
- Work / Span / 并行度：
- 放置阶段（并行）：
Work = 3N次写（每数组 N 次），Span = O(N/P + t_sync)（每个线程负责连续的一段，schedule(static)块大小 ≈N/P），并行度 = P = 8，实测 0.0192 s（串行 0.0903 s，加速 4.7×，低于 8× 是因为单线程也受单核 store 带宽限制，而 first touch 本身要分配页（page fault））； - 计算阶段（triad）：
Work = 3N次内存操作 + N 次 FMA，Span = O(N/P + t_barrier)，并行度 = P；但真正的上限是内存带宽而不是并行度（见下）。
- 放置阶段（并行）：
- 瓶颈与算术强度：
c[i] = a[i] + 2*b[i]每个元素 = 2 flops、24 B 流量（读 8 B + 读 8 B + 写 8 B，写分配时可能还要读一次），算术强度 AI = 2/24 ≈ 0.083 flop/B。在这台机器实测 212 GB/s 的带宽下，Roofline 上限 ≈212 × 0.083 ≈ 17.6 GFLOP/s；而 8 个核的算力上限（按每核每周期 16 个双精度 flop、3.5 GHz 估算）≈8 × 16 × 3.5 = 448 GFLOP/s。结论：这类负载是 25 倍以上的带宽受限——所以 cc-NUMA 优化的正确顺序是：先把数据放对 node（本例 1.52×），再压一致性流量（伪共享/padding），最后才考虑计算侧优化。
4. 性能模型与复杂度分析
4.1 一致性事件的延迟模型：hops 模型 + 数值算例
- 模型：讲义 slide 37 自己给出了这个模型的骨架——关键路径 = 一串必须依次发生的依赖操作。把它写成公式：
T_event = (关键路径跳数 H) x t_hop <- 网络延迟（消息必须按序往返）
+ (目录查询次数 n_dir) x t_dir <- 目录 bank 的访问时间
+ t_cache <- owner/请求方 cache 的数据访问
+ payload_bytes / link_bw <- 数据串行化(带宽项)
吞吐量视角（Little's law）:
sustained_misses/s = in_flight_misses / T_event
（in_flight 受 MSHR 数量限制：每核每级 cache 通常 8~16 个未完成 miss）
- 表 5：数值算例的参数假设（本笔记补充，取值量级参考现代多核/多 socket 机器与讲义 slide 37~43 的跳数结构）
| 参数 | 取值 | 含义 |
|---|---|---|
t_hop | 30 ns | 一跳点对点消息的延迟（含路由器/链路） |
t_dir | 10 ns | home 目录 bank 的一次查询/更新（SRAM 命中） |
t_cache | 5 ns | 请求方 cache 接收数据的开销 |
t_owner | 10 ns | owner cache 取出脏数据的开销 |
link_bw | 20 GB/s/方向 | 每条链路的带宽 |
| payload | 64 B（数据）/ 8 B（控制消息头） | 数据线大小与控制消息 |
- 算例 1：三种 dirty 读 miss 的延迟与流量（H 取讲义的关键路径跳数）
| 方案 | 关键路径（跳） | 目录访问次数 | 延迟计算 | 延迟 | 消息数 | 线上字节数 |
|---|---|---|---|---|---|---|
| 原始 5 消息 | 4 | 1 | 4×30 + 10 + 10(owner) + 3.2 | 143 ns | 5 | 8+8+8+72+72 = 168 B |
| intervention forwarding | 4 | 2 | 4×30 + 2×10 + 10 + 3.2 | 153 ns | 4 | 8+8+72+72 = 160 B |
| request forwarding | 3 | 1 | 3×30 + 10 + 10 + 3.2 | 113 ns | 4 | 8+8+72+72 = 160 B |
重要细节（本笔记对讲义 slide 38~40 的定量解读）：intervention forwarding 只减流量、不减延迟——因为 home 变成数据中转站，它要访问两次目录（一次查、一次改），关键路径仍然是 4 跳，算下来延迟反而比原始方案高约 7%（153 vs 143 ns）。这正是讲义在 slide 40 追问 “But all four of the transactions are on the critical path. Can we do better?” 的原因。request forwarding 把 home 移出数据通路（关键路径 3 跳），延迟降低 21%，流量与 intervention 相同（160 B），代价是打破了纯请求/响应模型（请求方要接受来自第三方的应答）。
算 clean 读 miss 作为对照：
2×30 + 10 + 5 + 3.2 ≈ 73 ns，即clean 读比 dirty 读快近一倍——这也解释了为什么”把数据尽快写回内存/共享化”（owner 从 M 降到 S）对后续读者很值：一次DIRTY → SHARED的 owner 更新，能让之后所有读 miss 从 143 ns 降到 73 ns。吞吐量视角：若
T_miss ≈ 100 ns、每核 10 个 MSHR、64 核，则同时在飞的 miss = 640 → 系统可持续 miss 吞吐 ≈640 / 100 ns = 6.4 G miss/s。所以延迟本身通常不是墙；真正的墙是 §4.3 的”每事件工作量随 P 增长”与 §3.2 的”每条 line 每时刻只允许一次所有权迁移“。
4.2 目录存储开销模型：精确算例
full bit vector : overhead = (P + 1) / line_bits <- line_bits = 512 (64 B)
limited pointer : overhead = (1 + k * log2(P)) / line_bits
sparse (list) : memory side : 1 pointer per line, but ONLY for lines present in some cache
cache side : (next pointer) bits per CACHED line -> scales with C, not M
sparse (vector) : cache side : P bits per CACHED line (P * C bits per node)
- 算例 2（讲义 slide 29~33 的量级，本笔记补齐算术）：设 P = 64 个 node，每 node 1 MB 私有 cache、1 GB DRAM，64 B 行：
| 方案 | 每 node 目录存储 | 占 DRAM 比例 | 相对 full vector |
|---|---|---|---|
| full bit vector | 16,777,216 行 × 64 bit = 1.07 Gbit = 128 MiB | 12.5% | 1× |
| limited pointer（k=5） | 16,777,216 × 31 bit = 62 MiB | 6.05% | 2.1× 更省 |
sparse，每缓存行存 P 位向量（P·C） | 16,384 行 × 64 bit = 128 KiB（在 SRAM 里） | —— | 1024× 更省 |
sparse，链表指针（C·log₂P） | 16,384 × 6 bit = 12 KiB（+ 每行 6 bit 的 next 指针） | —— | ≈10,900× 更省 |
算例 2 的关键在于分母不同：full vector 与 limited pointer 的分母是内存行数 M（1 GB/64 B = 1677 万行），sparse 的分母是在 cache 里的行数 C（1 MB/64 B = 16384 行）。M/C = 1024，这就是讲义 slide 29 说”1 MB cache、1 GB memory → 99.9% 的目录项是空的“的算术来源（
1 − 16384/16777216 = 99.90%）。Sparse 目录”用延迟换空间”：写失效沿链表串行传播，延迟从O(1)跳变成O(k)跳。
4.3 一致性的”工作量”模型：O(P) vs O(k)，以及 Amdahl 算例
每个一致性事件消耗的全局资源（讲义的核心判据）:
snooping (broadcast) : P 个 cache 各做一次 tag 查询 + 总线仲裁
directory (point-2-pt): k 个 sharer + 1 个 home 参与, 其余 node 完全不知道
系统级一致性的"工作量速率"（每秒钟的 snoop/协议工作）:
snooping : W_snoop = R x P x t_lookup / P 个 cache = R x t_lookup 每个 cache
directory : W_dir = R x (k_bar + 1) x t_lookup / P 个 cache ≈ R x (k_bar+1) x t / P
R = 全系统一致性事件速率; t_lookup = 一次 tag 查询/协议状态机的 cache 控制器时间
- 算例 3（本笔记补充的假设：每核每秒产生 1 M 个一致性事件、
t_lookup = 2 ns、k̄ = 2、平均每条事件 100 B 线上流量、总线 32 GB/s）：
| 系统 | R（事件/秒） | 每个 cache 控制器的协议工作量 | 互连需求 | 结论 |
|---|---|---|---|---|
| P=64，监听广播 | 64 M | 64 M × 2 ns = 0.128 s/s = 12.8% | 64 M × 72 B = 4.6 GB/s（占 32 GB/s 总线的 14%） | 还能用 |
| P=1024，监听广播 | 1024 M | 1024 M × 2 ns = 2.05 s/s = 205% | 1024 M × 72 B = 73.7 GB/s = 总线的 230% | 不可实现（两条墙同时撞上） |
| P=1024，目录 | 1024 M | 自己的 1 M × 2 ns + 作为 sharer 的 2 M × 2 ns = 6 ms/s = 0.6% | ≈1024 M × 100 B = 102 GB/s，但分摊在可扩展网络上（如 32 条 × 20 GB/s = 640 GB/s，利用率 16%） | 可行 |
这张表的含义就是讲义 slide 19、35、46 的定量版本：监听式的问题不是”延迟高”，而是”每个事件要被 P 个 cache 处理、所有流量挤在同一条介质上”，于是 P 增大时 per-cache 工作量与总线带宽同时爆掉（205% / 230%）；而目录把每个事件的参与者从
P降到k + 1，在 P=1024 时每个失效路径的节点只花 0.6% 的时间，流量分摊到可扩展的拓扑上。
- Amdahl 算例（本笔记补充）：设某应用时间中 80% 是可完美并行的计算、20% 是一致性处理。
- 广播方案下，一致性单事件成本随
P增长（O(P)）：从 P=64 到 P=256（4 倍核）时，一致性部分变成0.20 × 4 = 0.80，于是T(256)/T(64) = 0.80/4 + 0.80 = 0.20 + 0.80 = 1.00→ 4 倍核数带来 0 倍加速（全部收益被一致性吞掉）。 - 目录方案下，一致性成本近似不随
P增长（O(k)，而k增长很慢，讲义 slide 20）：T(256)/T(64) = 0.80/4 + 0.20 = 0.40→ 2.5× 加速（受 Amdahl 限制，理想上限 4×）。 - 反过来看单机优化：若一致性占 30%，把它优化 4 倍，则
T = 0.70 + 0.30/4 = 0.775→ 加速 1.29×；而不管一致性优化到多快，总加速上限是1/0.70 = 1.43×——这提醒我们：协议优化无法拯救”共享本身太多”的程序。
- 广播方案下，一致性单事件成本随
4.4 算术强度与 Roofline：伪共享吃掉的带宽
伪共享/热点计数器的"算术强度"（每字节一致性流量能做多少 flop）:
packed 8 counters in ONE 64 B line, 8 threads:
每次更新 = 1 次所有权迁移 -> 搬 64 B
AI = 2 flop / 64 B = 0.031 flop/B
Roofline 上限 = BW_coherence x AI = 50 GB/s x 0.031 = 1.56 GFLOP/s
padded (each counter in its own line):
更新命中本核 M 副本 -> 一致性搬移 ~ 0 B
AI 不再是限制; 上限回到计算/流式带宽
- 算例 4（把 §3.2 的实测串起来）：
- 单行打包：实测 16.2 ns/op（8 线程）→ 单行吞吐上限
1/16.2 ns = 61.7 M ops/s；一致性数据搬运 =61.7 M × 64 B = 3.95 GB/s（全部集中在一条 line 的迁移上）。 - 若这个打包结构是”任务队列的 8 个计数器”，每个 push/pop 触发一次
k=8的写 miss：msgs = 2 + 2k = 18→ 需要的消息速率 =61.7 M × 18 = 1.11 G msgs/s。这个数字超过多数互连网络的报文速率上限（本笔记假设 0.5 G msgs/s）——所以再优化协议也没用，必须消除伪共享。 - padding 之后：每线程写自己的 64 B 行，实测 0.53 ns/op，8 线程聚合 ≈
15.1 G ops/s，一致性流量 ≈ 0 → 吞吐提升 ≈ 245×（15.1 G / 61.7 M）。 - 边界型伪共享（stencil 的分块边界）则没有那么可怕：
N = 10⁸个 double、8 个 node、每个 node 100 MB，每次迭代只有相邻 node 交界处的 2 条 line 会来回迁移；1000 次迭代的边界一致性流量 ≈1000 × 2 × 64 B × 8 = 1 MB，相对1000 × 3 × 800 MB = 2.4 TB的流式流量可忽略。结论：伪共享的代价与”该行被访问的频率 × 参与 node 数”成正比，而与”它属于哪个数据结构”无关。
- 单行打包：实测 16.2 ns/op（8 线程）→ 单行吞吐上限
4.5 Work-Span 与可扩展性上限（三个代码示例的统一视角）
| 代码/场景 | Work（总工作量） | Span（关键路径） | 并行度 = Work/Span | 真正的瓶颈 |
|---|---|---|---|---|
| 示例 1 目录模拟器（本身） | Θ(Σ(kᵢ+2)) 消息记账 | Θ(E) 串行事件 | ≈ k̄ + 2（很小） | 单线程记账；价值在计数而非速度 |
| 示例 1 建模的机器 | P 个 node 各自的 miss 可并行 | 单次 miss 的 3~4 跳 | ≈ P（目录分区可并行服务） | 目录 bank 冲突、网络带宽 |
| 示例 2A 私有 line | T × per 次增量 | per × t_store_forward | T（完美） | store-to-load forwarding 延迟 |
| 示例 2B 同一条 line | 同上 | 总量 × t_transfer（= 全部工作量串行） | 1 | 每条 line 每时刻仅一次迁移 + O(k) 失效 |
| 示例 2C 原子 RMW | 同上 | 总量 × t_transfer | 1 | 同上（RMW 请求独占所有权） |
| 示例 3 并行 first touch | 3N 次触碰（+ 页分配） | N/P + t_sync | P | 页分配开销、单核 store 带宽 |
| 示例 3 triad | 3N 次访存 + N 次 FMA | N/P + t_barrier | P | 内存带宽（AI = 0.083 flop/B） |
- 可扩展性上限的一般判据（本笔记总结）：
- 只读/clean 读路径：目录下
O(1)跳、O(1)消息 → 可扩展性与P无关，这是目录最强的场景（讲义 slide 19：”On reads, directory tells requesting node exactly where to get the line from”，全程点对点）。 - 写路径：目录需要通知
k个 sharer →O(k)消息；在极限情况下（所有 cache 都共享这一行，k = P）它与广播一样糟（讲义 slide 19 明确写了这一点）。所以目录的优点完全建立在”k小且随 P 增长慢”这一经验事实之上（slide 20~21）。 - 每条 line 的串行化：不论协议怎么优化，一条 line 上同一时刻只能有一次所有权迁移 → 热点行吞吐上限
1/t_transfer（实测 61.7 M ops/s）→ 高争用结构的正确解法是分片（sharding）/ padding，不是更快的协议。 - 存储：
full vector = O(P·M)、limited pointer = O(k̄ log P·M)、sparse = O(P·C)或O(C log P)——目录的存储在 P 大时必须换表示法，这是本讲后半部分的全部内容（slide 23~34）。
- 只读/clean 读路径：目录下
4.6 复杂度汇总
| 维度 | 监听式（snooping） | 目录式（full vector） | 目录式（limited pointer） | 目录式（sparse list） |
|---|---|---|---|---|
| 每次事件的消息数 | O(P) 个观察者 | 2（读）/2+2k（写） | 同左 + 溢出路径 | 同左，但失效串行 |
| 事件关键路径 | O(1) 事务（但仲裁/负载差） | clean 2 跳 / dirty 3~4 跳 | 同左 | O(k) 跳（写） |
| 目录存储 | 0 | O(P·M) 位 | O(k̄ log P · M) 位 | O(P·C) 或 O(C log P) |
P 增大时 | per-cache 工作量 ×P、总线饱和 | 存储爆掉 | 溢出频繁 | 写延迟变长 |
| 实现复杂度 | 最低（总线天然广播） | 低 | 中 | 高（链表插入/删除/换出修补） |
5. 关键要点
- “广播不 scale，但我们并不需要广播”（讲义 slide 46 的第一句话）：一致性只需要”该知道的人“知道——把 sharer 列表存在目录里、按需查询、点对点通信，就把每个事件的参与者从
O(P)降到O(k)。目录的收益不是更低的单次 miss 延迟（clean 2 跳、dirty 3~4 跳，往往比广播还慢），而是流量与协议工作量不再随机器规模爆炸（§4.3 算例：P=1024 时 per-cache 协议工作量 205% → 0.6%）。 - 目录设计有两条正交的优化主线（讲义 slide 35）：(a) 目录结构的存储开销——增大 line、把多个处理器并成一个 directory node、limited pointer schemes（
1 + k log P位，k=5 时开销 5.8%~9.7%，几乎与 P 无关）、sparse directories（只给”在 cache 里”的行留信息，1 MB cache / 1 GB memory 下 99.9% 的目录项为空，存储从 128 MiB 降到 12 KiB）；(b) 协议的消息数与关键路径——intervention forwarding（5→4 条消息，关键路径不变）、request forwarding（关键路径 4→3 跳，代价是打破纯请求/响应模型）。 - 所有压缩方案都用”常见情况优化”的同一套方法论（讲义 slide 27）：① 用 workload 观察事实（sharer 很少）作依据；② 让常见情况既简单又快（前 N 个 sharer 用指针数组）；③ 罕见情况仍然正确，只是更慢更复杂（溢出时广播 / 顶替 / 粗向量回退）；④ 罕见路径的开销可以容忍，因为它很少发生。同理，sparse directory 优化的是”大多数行不在 cache“这个事实，代价是写失效变成
O(k)的串行链表遍历 + 更高的实现复杂度（换出时要修补链表）。 - 失效的代价与”谁真的持有这一行”直接挂钩（讲义 slide 20~21 的直方图 + §3.2 实测）：migratory 对象、任务队列、低争用锁的 sharer 极少，目录几乎免费；高争用锁（锁释放时一堆读者在场）是唯一真正的难题；而伪共享把”没人共享的数据”变成”永远有 2 个 sharer 的热点 line”，实测（8 线程同一条 line）每次操作成本 16.2 ns，是私有行（0.53 ns）的 30 倍，16 线程时恶化到 153 倍，且 padding 后可提升约 245 倍吞吐。
- 真实机器是”两级目录 + 分层协议”（讲义 slide 44、45）：Intel Core i7 用 L3 兼作集中式目录（依赖 inclusion property：L2 里有的行在 L3 目录里必有条目），目录维度是 P=4、C=L3 行数（sparse 思路）；多 socket 在 home agent / memory controller 侧再加一层 in-memory directory（16 KB dir cache 缓存目录项），用 QPI 相连。软件侧能控制的只有 first touch 决定 home node 与 线程亲和性：实测把”串行初始化”改成”并行首次触碰”，同一段 triad 的带宽从 139 GB/s 升到 212 GB/s（1.52×）——local 访问省下的是延迟与带宽，而一致性协议本身的可扩展性才决定这份收益能不能保住。
6. 常见陷阱与注意事项
- 陷阱 1：以为”目录方案 = 更低的延迟”。 目录引入一次间接访问（indirection）：clean 读 miss 2 跳、dirty 读 miss 3~4 跳（§4.1 算例：73 ns / 113~153 ns），而广播在同一总线上可能只要 2 个事务。目录赢在流量与可扩展性，不在单次延迟；在小规模机器（4 核、单 socket）上，L3 目录看似”多余”，但它是阻止所有 L2 被广播淹没的唯一办法。
- 陷阱 2：忽略 “
k = P的极限”。 讲义 slide 19 明说：写操作的目录优势取决于 sharer 数，若所有 cache 都共享该行，目录必须与所有 cache 通信，和广播一样糟。很多人只记住”目录 = 好”，忘了它的前提是”sharer 少且随 P 增长慢“（slide 20~21 的直方图）。高争用锁 + 大量读者会让这个前提失效。 - 陷阱 3：只优化消息数、忘了关键路径（或反之）。 intervention forwarding 把消息从 5 降到 4，但关键路径仍是 4 跳且 home 多访问一次目录，延迟反而略升（143 → 153 ns）；request forwarding 才是同时改善两者的做法（3 跳、4 条消息、160 B），但它打破了请求/响应模型——请求方必须接受”我没问过的节点发来的数据”，MSHR/网络接口要额外支持；实现时若仍按”请求-响应配对”写状态机，会出现死锁或错误的状态等待。
- 陷阱 4：用 full bit vector 硬撑大规模系统。
P位/行 的开销是P/512：P=64 时 12.5%（尚可）、P=256 时 50%（昂贵）、P=1024 时 200%（比数据本身还大）。此时必须换表示法，而每种压缩都有代价：limited pointer 需要溢出处理（广播回退/顶替并失效旧 sharer/粗向量），sparse list 把写失效变成串行 O(k) 延迟并要求换出时修补链表（容易出 bug：插入、删除、多头/尾指针不一致都会导致漏失效 → 一致性被破坏）。另外注意 limited pointer 的临界点k < (P−1)/log₂P（P=1024 时约 102 个指针）——超过它，指针方案比位向量还费空间。 - 陷阱 5：忘了 inclusion property。 L3 目录要能代表所有 L2 中的行，前提是”任何 L2 里的行在 L3 里也有一份（或至少有目录项）”。如果 L3 采用非包含（non-inclusive）策略又没有额外机制，目录就可能漏掉某个 L2 里的 sharer → 该 L2 的副本不会被失效 → 读到陈旧数据。这是实现级 bug，不是性能问题。
- 陷阱 6：把伪共享当成”协议问题”去优化协议。 实测表明：同一条 line 被 8 个核写时，每次操作 16.2 ns、单行吞吐被”每条 line 每时刻一次迁移“硬性限制在
1/t_transfer；此时若做k=8的写 miss，需要18条消息 × 61.7 M/s = 1.11 G msgs/s，任何目录实现都扛不住。正确做法是结构层面消除共享：按 cache line 对齐/padding（alignas(64)）、每线程私有累加后再归约（privatization）、把热点计数器分片（sharding） 到多条 line；同理，在 cc-NUMA 上还要注意 first touch 决定了 home node——malloc之后由单线程初始化会把所有页钉在一个 node，之后所有远程访问都要付 3~4 跳的代价。 - 陷阱 7（实现细节）：忘记”收到全部 ack 才能写”。 讲义 slide 18 强调：“After receiving both invalidation acks, P0 can perform write”。写者必须等所有失效应答到齐（否则其他 cache 可能仍持有旧副本并继续读旧值）。这要求写者维护”未完成失效计数”，并与 memory consistency 的定序规则配合——这也是为什么高争用写比高争用读更昂贵：读可以并行满足（多个 sharer 共存），写必须串行地收齐所有 ack。
7. 思考题（带答案）
思考题 1：request forwarding 把 dirty 读 miss 的关键路径从 4 跳压到 3 跳，消息数仍然是 4 条（与 intervention forwarding 相同）。请说明：(a) 数据与目录修订分别走了哪条路径？(b) 为什么讲义特别强调”系统不再是纯请求/响应（no longer pure request/response）”？(c) 如果 owner 把数据只发给请求方、忘了给 home 发目录修订，会造成什么后果？
【答案】 (a) 路径（对应讲义 slide 41~43 的编号）：
- ① 请求节点 P0 → home：read miss 消息；
- ② home → owner：一条”send data to requestor“的转发请求（home 不再亲自去取数据）；
- ③ owner → 请求方 P0：数据（这条在关键路径上）；
- ④ owner → home：data + dir revision（与 ③ 并行，所以只增加流量、不增加关键路径跳数）。 所以关键路径 = ①→②→③ = 3 跳，总消息数 = 4 条；而 intervention forwarding 是 ①P0→home、②home→owner、③owner→home、④home→P0，四条全部串在关键路径上（4 跳），home 还多做一次目录更新访问——方向相反：数据绕了一大圈。 (b) 因为 P0 发出的请求对象是 home，但收到的数据来自 owner：请求方必须能处理”应答者 ≠ 被请求者”的情况。这会影响：(1) 网络/NoC 的路由与事务标签（transaction id）设计——应答必须能正确匹配到原来的未完成 miss，而不是被当成”未请求的数据”丢弃；(2) MSHR/状态机的实现——收到数据时该行可能处于 IS（in-flight shared）状态并等待”来源可能是 home 或 owner”的任一数据；(3) 调试与验证更难（报文流的因果链不再是简单的请求-应答配对）。 (c) 后果：home 的目录项永远停留在
presence={old owner}, D=1，且内存里的数据是陈旧的。之后若有第三个节点发 read miss，home 会再次告诉它”去找原 owner”；而原 owner 的副本已经改成 S（或已被换出），于是要么多绕一跳（性能损失），要么在 owner 已换出该行时找不到数据（协议死锁/错误）；更严重的是 home 认为行仍是 dirty，内存永远不会被更新，一旦 owner 的副本被静默丢弃（例如 cache 被作废/复位），系统就永久丢失了最新写值 → 一致性被破坏。因此 owner 必须把 dir revision 发给 home，让 home 清 dirty、更新 presence、并把最新数据写回内存（这正是讲义 slide 14 的第 5 步”home clears dirty, updates presence bits, updates memory”）。
思考题 2：设 P = 256 个 node，每个 node 1 MB 私有 cache、1 GB DRAM，cache line 64 B。(1) 计算 full bit vector 目录的存储量与占内存百分比；(2) 计算 limited pointer（k = 5）的每行目录位数与百分比；(3) 计算 sparse directory（链表指针方案）在内存侧与 SRAM 侧的存储量；(4) 解释为什么 sparse 方案的”写延迟”是 O(k) 跳，并给出 k = 16 时的具体跳数。
【答案】 (1) Full bit vector：每行需要 P = 256 bit。64 B 行 = 512 bit，故开销 = 256/512 = 50%（与讲义 slide 23 一致）。每 node 内存 1 GB = 2³⁰ B → 行数 M = 2³⁰/64 = 2²⁴ = 16,777,216 行；目录存储 = 16,777,216 × 256 bit = 4,294,967,296 bit = 512 MiB（= 0.5 GB，正好是 1 GB 内存的 50%）。这就是 P=256 时位向量方案不再可接受的原因。 (2) Limited pointer（k = 5，log₂256 = 8）：每行 1 + 5×8 = 41 bit（若按讲义 slide 28 略去那 1 位状态位，则为 5×8 = 40 bit）。百分比 = 41/512 = 8.01%（讲义口径 40/512 = 7.81%，与 slide 28 的 “P = 256: 7.8% overhead” 完全一致）。存储 = 16,777,216 × 41 bit ≈ 86 MiB（对比位向量的 512 MiB，省 6 倍），而且这个开销几乎不随 P 增长（P 从 64 到 1024，只从 6.05% 涨到 9.96%）。 (3) Sparse directory（链表）：
- 内存侧（home node 的 DRAM）：每行一个 head 指针，但只为当前被缓存的行保留——本例只有
C = 1 MB/64 B = 16,384行在 cache 里，C × log₂P = 16,384 × 8 bit = 131,072 bit = 16 KiB； - SRAM 侧（各 cache 的 tag 数组）：每个被缓存的行需要额外
log₂P = 8bit 的 “next” 指针 → 共16,384 × 8 bit = 16 KiB，这是与 cache 大小成正比的（P·C 的向量变体则是16,384 × 256 bit = 512 KiB）。 - 与 (1) 的 512 MiB 相比，内存侧降低了约 32,768 倍，原因是分母从”内存行数 M = 1677 万”变成了”cache 行数 C = 16384”（
M/C = 1024，再叠加每行 256 bit → 8 bit 的压缩）。 (4) 因为 sparse 目录只在 home 保存链表头，其余 sharer 的指针存在各自 cache line 的额外字段里：写 miss 时 home 只能先失效 head，head 失效后才知道下一个是谁，每一跳都要等上一次失效到达并回读指针，因此失效是串行的。跳数（消息链）≈2 × k量级：k = 16时 —— 1 跳 request→home，然后 16 次 “invalidate→ack” 串行往返 =1 + 2×16 = 33跳（若把 home 更新目录与请求方拿数据算进去还要再加）。对比 full bit vector：失效消息并行发出，无论 k 多大，关键路径都只有 4 跳（request → response → invalidate → ack）。结论：sparse 用”存储”换”写延迟”，所以它适合”sharer 极少、写不频繁”的负载，而高争用场景必须用位向量/粗向量来并行失效。
思考题 3：某 8 线程数据结构的 8 个 long 计数器被放在同一个 64 B cache line 中；实测每次更新耗时 16.2 ns（单线程时是 0.40 ns）。(1) 用”每条 line 每时刻只允许一次所有权迁移”的原理算出单行吞吐上限；(2) 若改成每个计数器独占一条 line，估计吞吐提升倍数（已知独占行的实测是 0.53 ns/op）；(3) 如果这个结构是共享任务队列（每次操作触发 k = 7 的写 miss），按讲义的消息公式算出所需的报文速率，并说明为什么”换用更好的目录协议”救不了它、(4) 你会怎么改这个程序？
【答案】 (1) 打包时 8 个计数器共享一条 line，每次更新都要拿到该行的独占所有权，即每次更新一次所有权迁移。所有更新序列化在同一条 line 上，故单行吞吐上限 = 1 / t_transfer = 1 / 16.2 ns ≈ 61.7 M 次更新/秒。用 Little’s law 交叉验证：要让 8 个线程各以 1 op/ns 推进（8 G op/s），需要同时有 8 G/s × 16.2 ns ≈ 130 次迁移在飞，而硬件对一条 line只允许 1 次迁移在飞 → 上限 1/16.2 ns = 61.7 M op/s，与实测 8 M / 0.130 s = 61.5 M op/s 吻合（误差 < 0.5%）。这也解释了为什么线程数从 1 增到 16 时 B 方案的每操作耗时从 0.40 ns 恶化到 87 ns：sharer 越多，每次迁移要失效/等待的对象越多，t_transfer 自身也变大。 (2) 每个计数器独占一条 line 后，每个线程在自己的 line 上反复写，命中本地 M 副本，不再产生一致性流量（前提：这些 line 不与其他线程共享）。8 条 line 的聚合吞吐 ≈ 8 × (1 / 0.53 ns) ≈ 15.1 G op/s（实测 A 方案各线程耗时基本不随线程数变化：0.48 → 0.57 ns/op，说明确实完全并行）。相对打包的 61.7 M op/s，提升 ≈ 15.1 G / 61.7 M ≈ 245×（保守说法：两个数量级以上）。注意这仍是上界：真实程序还要受内存带宽、总线上限与其他共享结构限制。 (3) k = 7 个其他 sharer 时，一次写 miss 的消息数 = 2 + 2k = 2 + 14 = 16 条（1 条 write miss + 1 条 sharer ids+data + 7 条 invalidate + 7 条 ack，见讲义 slide 17、18）。按单行吞吐 61.7 M op/s 计算，所需报文速率 = 61.7 M × 16 ≈ 0.99 G msgs/s（约每秒十亿条一致性报文）。这远超互连网络的报文处理能力（本笔记假设 0.5 G msgs/s 量级），而且每条报文还要占用 cache 控制器的状态机时间。换协议救不了它：因为瓶颈是”这一行被 8 个核以高频率写“这个结构性事实——目录已经只通知真正的 7 个 sharer（而不是广播给全部 P 个核），信息论上再也无法减少”必须让 7 个副本失效”这件事；除非改变数据布局（把计数器分开）或访问模式（减少写频率，例如本地批量累加后再合并）。 (4) 具体改法（按收益从高到低）：
- padding / 对齐：
struct Counter { alignas(64) long v; } c[8];或long v[8*8]（每 8 个 long 一个计数器），让每个线程写自己独占的 line； - privatization（私有化 + 归约）：每个线程在栈上或私有数组里累加，最后用一次归约合并——把
O(ops)次一致性事件降到O(P)次； - 分片（sharding）：把全局计数器拆成每 node 一份，读时求和（”分布式计数器”模式）；
- 如果必须共享，就降低争用频率：批量交付（每次锁/原子操作处理 K 个任务）、用无锁队列的 head/tail 分离布局（避免同一行被生产者和消费者同时写）；
- 最后才考虑协议/硬件层面：把该行钉在某个 node（例如通过内存交错或把做该工作的线程绑到同一 socket），让所有权迁移尽量在片内 L3 目录里完成而不是跨 QPI。