Lecture 13: Snooping-Based Multiprocessor Design
Lecture 13: Snooping-Based Multiprocessor Design
1. 章节标题与概述
Lecture 13: Snooping-Based Multiprocessor Design（基于侦听的多处理器设计：把一致性协议真正做进机器里）
本讲核心问题：上一讲（Snooping-Based Cache Coherence）讨论的 MESI（Modified / Exclusive / Shared / Invalid，修改/独占/共享/无效）状态机是抽象的——它假设每条一致性消息都是原子的（atomic）、瞬时完成的。本讲要回答的是：在真实机器里，如何高效地实现一个基于失效（invalidation-based）的侦听一致性协议？ 一旦承认”标签查找、总线仲裁、等待其他控制器响应、读写 DRAM 都不是原子操作”，正确性（死锁 deadlock、活锁 livelock、饥饿 starvation、竞态 race）与性能（总线带宽利用率、隐藏访存延迟）就会立刻互相拉扯。讲义的一句话总结是：in a real machine… efficiently ensuring coherence is complex（在真实机器中，高效地保证一致性是很复杂的）（slide 2）。
- 涉及的主要硬件/软件机制：
- 硬件侧：原子共享总线（atomic shared bus）与拆分事务总线（split-transaction bus）；处理器侧控制器（processor-side controller）与侦听控制器（snoop controller）对同一份 tag/state 的争用，以及用tag 复制（duplicate tags）或多端口 tag 存储（multi-ported tag memory）来缓解；侦听结果的三条”线与”信号（Shared / Dirty / Snoop-pending）；回写缓冲（write-back buffer）；请求表（request table）与 3 bit 事务标签（transaction tag = 表项索引）；响应分离的请求/响应队列；NACK（negative acknowledgement，否定确认）流控；多级缓存层次中的包含性（inclusion）。
- 软件侧：这一切最终要支撑的是普通程序中的一句
int x = 10;（slide 59）——一条被架构抽象成”原子”的 store，实际由十几个组件、二十来个步骤协同完成；讲义强调”这些概念远不止硬件实现”：简单性与性能的折中、并行系统中的正确性挑战，同样适用于写并行程序（slide 3）。
在并行计算知识体系中的角色：本讲是”缓存一致性三部曲”的第三部（Snooping-Based Cache Coherence → Directory-Based Cache Coherence → 本讲的实现），把协议层（protocol）下沉到微架构与总线协议层（implementation）。它同时也是全课程”共享资源 = 性能瓶颈“这条主线最纯粹的案例：总线是有限共享资源，仲裁是串行的，标签表大小决定了可达到的带宽；后面讲的互连网络、同步原语实现、无锁编程（
cmpxchg在总线上表现为独占事务）都直接建立在本讲的机制之上。它给出的思维方式——“把一个操作拆成更多更小的事务可以暴露更多并行性，但要付出更多硬件与更多正确性证明的代价”（slide 37）——是通用工程原则。- 配套材料：
lectures/12_snoopimpl.pdf（抽取文本extracted/12_snoopimpl.txt，共 60 页）：已公开，可在 https://www.cs.cmu.edu/~418/lectures/ 公开下载。Fall 2026 日程表（https://www.cs.cmu.edu/~418/schedule.html）把 Sep 23 排为第 13 讲 “Snooping-Based Multiprocessor Design”，其 slides 链接指向这份 PDF（日程表中该链接以 HTML 注释形式给出，PDF 本身在公开的lectures/目录下可直接下载）。讲义首页写的是 “Lecture 12: A Basic Snooping-Based Multi-Processor Implementation” 与 “CMU 15-418/15-618, Fall 2024”：这是讲义沿用历史学期版本的正常现象（讲次编号与学期字样随年度重排），不是错误。- 讲义中的部分插图注明 “Figure credit: Culler, Singh, and Gupta”，即经典教材《Parallel Computer Architecture: A Hardware/Software Approach》的图。
- 讲课录像（Panopto / YouTube）：Fall 2026 日程表中被注释隐藏，属未发布（历史学期在 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 创建。
2. 核心概念与硬件/软件架构图解
2.1 起点：MESI 状态机必须是”不变量清单”，而不是一张漂亮图片
- 定义与目的：一致性协议的不变量（invariants）是：对任一 cache line，(a) 任一时刻至多一个缓存持有 M 态（可写）副本；(b) 若存在 M 态副本，则其他所有副本都是 I；(c) 若存在 S 态副本，则没有 M 态副本。状态机只是维持这些不变量的策略描述（slide 4）。
- 直观解释（”它是什么？”）：把 cache line 想成一份图书馆里唯一的手稿。
M= 我把手稿借回家并在上面改，同时通知图书馆”所有其他复印件作废”；E= 我借回家但没改，且知道外面没有别的复印件；S= 手稿被复印了多份，大家都在读；I= 我手里那份已经被宣布作废。读 = “我要看手稿”，写 = “我要独占并涂改”。 - 图解（图 1）：MESI 状态迁移图（含总线事务标签，PrRd/PrWr = 处理器发起的读/写，BusRd/BusRdX/BusUpg = 总线事务）
PrRd / -- PrWr / BusUpg
+-----------------------------+ +----------------------------------+
| v | |
+---------+ +-----------+ +-----------+
| I | PrRd / BusRd | S | PrWr / BusUpg | E |
| Invalid |------------------>| Shared |---------------------->| Exclusive |
+---------+ +-----------+ +-----------+
^ ^ | | ^ |
| | | PrWr / BusRdX | | BusRd / -- (别人也要读, PrWr / --
| | +----------------------+ | 我保持 S) |
| | | v
| | BusRdX / -- (我被失效) | +-----------+
| +-------------------------------+ | M |
| | Modified |
| BusRdX / flush (我供数据并转 I) +-----------+
+--------------------------------------------------------------+ |
| | PrWr / --
BusRd / flush (别人读, 我供数据并转 S) | v
+--------------------------------------------------------------+ (保持 M)
| |
v v
S <------------------------------------------------------------ S
事件读法: "事件 / 在总线上产生的动作"
-- 表示不产生总线动作（本地命中）
- 关键操作与性能特征：命中（hit）的代价是 tag 查找延迟（1–4 周期）；
S→M只需要 BusUpg（upgrade，升级），不搬数据，因此比重读整条 line 便宜得多（少一次 128 B 数据传输）；M→S/M→I需要 flush（回写并供数据），如果对端要用的正是这条 line，则总线上的数据传输是”有用功”，否则是纯粹的额外带宽开销。 - 表 1：MESI 状态迁移表（以本处理器视角；”他人”= 侦听到的其他缓存）
| 当前状态 | 本地事件 | 侦听到的事件 | 下一状态 | 总线动作 | 备注 |
|---|---|---|---|---|---|
| I | PrRd | — | S 或 E | BusRd | 若无人 assert Shared 则进 E（独占） |
| I | PrWr | — | M | BusRdX | 独占取得所有权并失效他人 |
| S | PrRd | — | S | 无 | 普通命中 |
| S | PrWr | — | M | BusUpg | 只需升级，不必传数据 |
| S | — | BusRdX / BusUpg | I | 无 | 自己的副本被失效 |
| S | — | BusRd | S | 无 | 多副本共享读 |
| E | PrRd | — | E | 无 | 普通命中 |
| E | PrWr | — | M | 无 | 已经是独占，无需总线动作 |
| E | — | BusRd | S | flush | 有别人要读，降级为 S（也可选择不作声，见 §2.5 的 Dirty 线） |
| M | PrRd / PrWr | — | M | 无 | 命中且脏 |
| M | — | BusRd | S | flush | 供出最新数据，降级为 S |
| M | — | BusRdX / BusUpg | I | flush | 供出最新数据后失效 |
2.2 基本系统设计：原子总线 + 单级写回缓存 —— 一个”刻意幼稚”的出发点
- 定义与目的：讲义 Part 1（slide 19–37）先假设一个最简单的系统（slide 20）：每个处理器同时只有一个未完成的内存请求；单级、写回（write-back）缓存；缓存可以阻塞处理器去完成一致性操作；互连是一条原子共享总线（同一时刻只有一个客户端在通信）。在这个”温室”里先把正确性机制做对，再在 Part 2 逐条打破假设去找性能。
- 直观解释（”它是什么？”）：这就像一间只有一部电话的办公室。任何对外沟通（取数据）都必须先抢到电话（总线仲裁），说完命令后必须一直占着电话线等对方念完数据（原子事务：请求与响应之间不允许插入别的事务）。电话线是全办公室最稀缺的资源，而绝大部分时间它都在”等对方念”——这正是 Part 2 要解决的问题。
- 图解（图 2）：一个基于侦听的多处理器硬件结构（Part 1 的基本设计 + 写回缓冲 + 侦听结果线）
+---------------------+ +---------------------+
| Processor P0 | | Processor P1 |
| (load/store 发射) | | |
+----------+----------+ +----------+----------+
| 处理器侧请求 | 处理器侧请求
+----------v----------+ +----------v----------+
| Processor-side ctrl| | Processor-side ctrl|
| +-------------+ | | +-------------+ |
| | Tags |State | | | | Tags |State | |
| +-------------+ | | +-------------+ |
| | Data cache | | | | Data cache | |
| +-------------+ | | +-------------+ |
| +-------------+ | | +-------------+ |
| | Write-back | | | | Write-back | |
| | buffer | | | | buffer | |
| +-------------+ | | +-------------+ |
| Snoop controller | | Snoop controller |
+----------+----------+ +----------+----------+
| |
================|================================|=========================
| 原子共享总线 (Atomic Shared Bus) |
================|================================|=========================
Addr[..] Data[..] Shared Dirty Snoop-pending <-- 三条额外侦听结果线
| |
+----v--------------------------------v----+
| Memory Controller |
| (DRAM row buffer / 调度器 / 回写队列) |
+------------------------------------------+
关键争用点:
* 处理器侧控制器 vs 侦听控制器 -> 都要读写同一份 Tags/State
* 各缓存 vs 各缓存 -> 都要抢唯一的总线使用权（仲裁串行化）
- 关键操作与性能特征：
- 原子总线事务的 4 步（slide 21）：① 客户端在仲裁（arbitration）中获胜拿到总线；② 把命令（以及可能的数据）放上总线；③ 另一个总线客户端把响应放上总线；④ 下一个客户端拿到总线。注意第 ② 步到第 ③ 步之间总线被独占。
- 单处理器缓存缺失逻辑 7 步（slide 22）：定 cache set → 查 tag → 申请总线 → 等仲裁授权 → 发地址+命令 → 等命令被接受 → 从总线收数据。
- 原子总线在多处理器语境下的含义（slide 22 右下）：
BusRd/BusRdX一旦发出地址，直到收到数据为止，不允许有任何其他总线事务；flush则要求地址与数据同时上总线，并且在任何其他事务开始之前已被内存接收。 - 性能特征：响应等待期间总线完全空闲，有效总线带宽被严重浪费（slide 39 明确指出这一点，并把它作为进入 Part 2 的动机）。
2.3 争用之一：处理器侧控制器 vs 侦听控制器
- 定义与目的：多处理器缓存控制器要同时服务两个”客户”：来自处理器的 load/store，和来自总线的侦听请求。两者的第一步都是查 tag，于是产生争用（slide 23）。
- 直观解释（”它是什么？”）：一个柜台只有一个窗口，却排着两条队：顾客（处理器）和电话（总线）。要么电话优先——顾客一打电话就被”锁在门外”；要么顾客优先——电话响了你却接不了，导致整条总线的其他处理器都陪着你等（哪怕根本没有共享发生）。
- 两种缓解方案（slide 24）：① 复制 tag（duplicate tags）：给侦听控制器一份独立的 tag 副本；② 多端口 tag 存储（multi-ported tag memory）：一份 tag，两组端口。两者都能让”查”并行，但修改 tag 时仍必须互斥（否则不变量被破坏）；因为查 tag 远比改 tag 频繁，这个折中非常划算。讲义强调：性能的代价是硬件资源（cost of the additional performance is additional hardware resources）。
2.4 争用之二：侦听结果怎么汇报、什么时候汇报
- 定义与目的：一次
BusRd缺失，内存和请求者都需要知道”别人手里的状态”（slide 25）：line 是脏的吗？（脏则内存不该响应，应由持有者供数）line 是共享的吗？（共享则请求者应进入 S 而非 E）。 - 怎么汇报（how，slide 26）：增加三条线与（wired-OR）总线信号：
Shared：所有处理器侦听结果之 OR——有人有副本即置位；Dirty：所有处理器侦听结果之 OR——有人是 M 态即置位；Snoop-pending：所有处理器之 OR，全 0 表示所有处理器都已给出侦听结果（用作”集合点”）。 这三条线是额外的总线互连硬件，是”用硬件换正确性与性能”的又一例。
- 什么时候汇报（when，slide 27）：两种策略——
- 内存控制器立即开始访问 DRAM，但先压住响应（squelch），一旦有侦听结果指出别的缓存有更新数据，就取消自己的响应，由该缓存供数；
- 内存先假设一定有某个缓存会服务，直到侦听结果有效为止；若没人有，则内存必须响应。
- 直观解释（”它是什么？”）：像会议里问”谁手上有最新版文件？”。要么让档案室先跑去复印（预取），然后可能白跑一趟（被 squelch）；要么等举手统计结束再决定谁去拿（延迟更长，但不会白干）。前者省延迟、浪费 DRAM 带宽与能耗；后者反之。
2.5 争用之三：写回（write backs）与 write-back buffer
- 定义与目的：一次写回天然涉及两个总线事务（slide 28）：① 处理器的缺失带来的入线（incoming line）；② 被驱逐的脏行的出线（outgoing line，flush）。理想情况是处理器尽快继续执行，不必等 flush 完成。
- 直观解释（”它是什么？”）：你要往书架上放一本新书，但格子满了，得先把旧书搬走。write-back buffer 就是门口的暂存箱：先把旧书丢进箱子，立刻把新书放上架子继续干活（处理器不停顿），等有空再慢慢把箱子里的书送回图书馆（内存）。
- 图解（图 3）：带 write-back buffer 的缓存，以及侦听控制器必须同时查两处
处理器请求路径 (processor-related) 总线请求路径 (snooping-related)
| ^
v |
+----------------------+ +----------------------+
| Processor-side ctrl | | Snoop controller |
+----------+-----------+ +----------+-----------+
| (1) tag 查找 | (a) 查 cache tags
v v
+----------------------+ <-- 必须保持同步 --> +----------------------+
| Tags / State / Data | | (b) 查 write-back |
| (cache arrays) | | buffer 的地址 |
+----------+-----------+ +----------+-----------+
| (2) 被驱逐的脏行 | (c) 命中则:
v | - 用 buffer 里的数据响应
+----------------------+ | - 取消自己待发的写回事务
| Write-back buffer |<-------------------------------------+
+----------+-----------+
| (3) 稍后 flush 出总线
v
============================ Bus ============================
陷阱: 若只查 tags 不查 write-back buffer, 会把"已经被驱逐但还没写回的最新数据"漏掉,
别的处理器会读到内存里的旧值 —— 正确性直接被破坏。
- 关键操作与性能特征：写回缓冲把”两次串行总线事务”变成”一次立即完成 + 一次延后完成”，处理器停顿时间从
t_in + t_flush降到约t_in；代价是侦听逻辑复杂化（必须查 buffer 地址）以及buffer 是新的死锁/顺序风险点（若 buffer 满，处理器又得等）。
2.6 状态迁移不是原子的：竞态、取数死锁、活锁、饥饿
这是本讲的真正核心：slide 30 明说——状态迁移图假设迁移是原子的，但真实机器里”查 tag、仲裁总线、等其他控制器行动”这一整套都不是原子的。
- 竞态示例（slide 31）：P1 与 P2 同时写共享的 line A（两者都要发
BusUpg）。P1 赢得总线发出BusUpg；P2 在等总线，此时收到 P1 的BusUpg，按 MESI 必须失效自己line A——但 P2 自己那个待发的BusUpg现在语义过时了（它已经失去副本，应该变成BusRdX）。结论：缓存在等待总线期间必须仍能处理外来请求，并且必须能修改自己排队中的请求。这就是”抽象是原子的、实现不是”造成的第一类 bug。 - 取数死锁（fetch deadlock，slide 32）：P1 持有 line B 的 M 态副本，正在等总线以发出对 line A 的
BusRdX；此时总线上出现对 B 的BusRd——若 P1 坚持”我的请求没发出去之前不处理别的事”，那么它既不被服务、也不提供服务，总线被死锁。解法：等待自己请求的同时必须能服务外来事务。 - 活锁（livelock，slide 33）：P1 与 P2 反复写 line B：P1 拿到总线发
BusRdX，P2 失效；P1 还没来得及真正更新缓存行，P2 又拿到总线发BusRdX，P1 失效……系统一直在”运行”，但没人完成有效工作。解法：获得独占所有权的写，必须在所有权被放弃之前允许其完成（”commit 后再让别人抢”）。 - 饥饿（starvation，slide 35）：多个处理器竞争总线，若策略是”id 最小者胜”，低 id 者可能长期霸占总线。这是公平性（fairness）问题，而不是正确性问题。缓解策略：FIFO 仲裁、基于优先级的启发式（高频使用者优先级衰减，priority drop）。
- 直观解释（”它是什么？”）：死锁 = 匹兹堡窄巷里两辆车顶牛（slide 9–10），谁都动不了，除非有人倒车让出资源；活锁 = 两个人迎面走，同时往右让、又同时往左让，脚步不停但谁也没过去（slide 14–17 的三张连续漫画）；饥饿 = 十字路口黄车一直在等绿灯方向的车流，整体在通行（绿车一直在走），只是黄车永远排不上（slide 18）。
- 表 2：死锁 / 活锁 / 饥饿的对比与对策
| 现象 | 定义（讲义 slide 8–18） | 系统表现 | 一致性实现中的典型成因 | 对策 |
|---|---|---|---|---|
| 死锁 deadlock | 有未完成的操作，但没有任何操作能推进 | 系统彻底停住 | 等待自己的请求时不处理外来请求（fetch deadlock）；有限队列互相等待（buffer deadlock） | 允许”等待中仍服务”；把请求/响应队列分离；请求表冲突检查 |
| 活锁 livelock | 系统在执行大量操作，但没有线程取得有意义的进展 | CPU 与总线都很忙，但结果不推进 | 独占所有权被反复抢走，写永远 commit 不了 | 让获得独占所有权的写先完成再释放 |
| 饥饿 starvation | 系统整体在推进，但某些进程毫无进展 | 少数参与者长期得不到服务 | 仲裁策略不公平（固定优先级、最低 id 优先） | FIFO 仲裁、优先级衰减、请求老化（aging） |
| 死锁的 4 个必要条件（slide 13） | 互斥、持有并等待、不可抢占、循环等待 | 四者同时成立才可能死锁 | 资源依赖图中存在环 | 破坏其中任一条件 |
2.7 写何时”提交”：commit ≠ complete
- 定义与目的（slide 34）：写提交（commits）发生在”读独占事务（read-exclusive）出现在总线上并被其他所有缓存确认”的那一刻。此后所有未来的读都会反映这个写的值——即使数据还没写进 P 的脏行，也还没进内存。而写完成（complete）则是指更新后的值已经落到缓存行里。commit 与 complete 是两个不同的时刻。
- 为什么重要：这正是写串行化（write serialization）的来源——总线上的事务顺序定义了并行程序中写的全局顺序。硬件只要保证”上总线的顺序”，软件就能获得一个确定的、所有处理器都同意的写顺序。
- 为什么 write-back buffer 不影响 commit 时刻：因为 commit 的定义锚定在“总线上出现读独占事务并获得确认”这个可见事件上，而不是数据何时落到缓存行或内存里。把脏数据留在 write-back buffer 里，只是把”完成（complete）”推后，完全不改变”提交（commit）”的时点——所以处理器可以立刻继续执行，其他处理器之后读到的仍然是新值（由 write-back buffer 参与侦听供数）。
- 直观解释（”它是什么？”）：commit = 在会议纪要上签字（此后所有人都必须按这份纪要办事）；complete = 把手上的活真正干完。签字之后你可以先去干别的活（write-back buffer 里放着），但纪要已经生效。
2.8 Part 2：把原子总线拆成”请求 / 响应”——split-transaction bus
- 定义与目的（slide 39–41）：原子总线的问题是等待响应期间总线空闲，有效带宽被浪费；而互连是系统中有限且共享的资源，必须尽量高效使用。拆分事务总线把一次总线事务拆成两个独立事务：① 请求（request：命令 + 地址） 与 ② 响应（response：数据），两者之间允许插入其他事务。
- 直观解释（”它是什么？”）：从”打电话并一直握着话筒等对方查资料“改成”留个工单号，然后挂机；对方查好后凭工单号回拨“。电话线（总线）在等资料期间可以继续接别的活，只要你能凭工单号把回应匹配回去。
- 图解（图 4）：拆分事务总线的周期级时序（请求总线 + 响应总线，流水化与乱序完成）
周期: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
----------------------------------------------------------------------------
请求总线 (Addr/cmd) ARB RSLV ADDR DCD ACK |ARB RSLV ADDR DCD ACK |ARB RSLV ...
\___ txn1 请求阶段(5 周期) ___/ \__ txn2 请求阶段 __/
仲裁 解决 上地址 解码 确认
响应总线 (Data Arb/Data) ARB RSLV |D0 D1 D2 D3
等待 DRAM (100 周期,
总线不被独占!) ...
事务 1 (P1 read miss to A) [==== 请求阶段 ====]......(其他事务穿插)......[==== 数据 4 周期 ====]
事务 2 (P2 BusUpg B) [==== 请求阶段 ====] (无响应分量!)
事务 3 (P0 read miss to C) [=== 请求阶段 ===] ...
事务 4 (P3 read miss to D) [=== 请求阶段 ===]
要点:
* 请求阶段的 5 个周期: ARB(仲裁) RSLV(解决/分配 tag) ADDR(上地址/命令) DCD(解码) ACK(确认)
* 数据总线: 128 B line / 32 B(256 bit) 位宽 = 4 个周期
* "Memory operation commits here! (NO BUS TRAFFIC)" —— 提交点在侦听阶段, 但此时总线无流量
* 完成顺序 != 请求顺序 (out-of-order completion); 请求顺序定义系统的全序
* write back 与 BusUpg 没有响应分量 (它们在"请求"阶段就一并拿到数据总线使用权)
- 新出现的问题（slide 42）：
- 请求如何与响应匹配？ → 请求表（request table）+ 事务标签（tag）；
- 冲突请求如何处理？ → 每个缓存都保存请求表副本，禁止发出与表中已有的冲突请求；
- 流控（flow control）：同时允许多少未完成请求？缓冲满了怎么办？→ NACK + 重试；
- 侦听结果何时汇报？ 在请求阶段还是响应阶段。
- 一个基本设计（slide 43）：系统范围内最多 8 个未完成请求；响应不必按请求顺序返回，但请求顺序确立系统全序；流控用 NACK（否定确认）——缓冲满时客户端 NACK 该事务，触发稍后重试。
- 发起请求的机制（slide 44）：可把拆分事务总线看成两条总线——请求总线（命令 + 地址）与响应总线（数据）。步骤：① 请求者申请请求总线；② 仲裁器授权，并为事务分配一个 tag；③ 请求者把命令与地址放上总线。tag 就是请求表的索引（8 个表项 ⇒ 3 bit tag），每个总线客户端（缓存）都维护该表的副本。
- 表 3：原子总线 vs 拆分事务总线
| 维度 | 原子总线（Part 1） | 拆分事务总线（Part 2） |
|---|---|---|
| 请求与响应能否被其他事务穿插 | 不能 | 能（这就是全部意义） |
| 等待响应期间总线状态 | 空闲（带宽浪费） | 可被其他请求/响应占用 |
| 有效带宽（后文算例） | ≈ 3.5 GB/s（利用率 8.3%） | ≈ 28 GB/s（受 8 个表项限制） |
| 需要的额外硬件 | 侦听结果三条线 | 请求表 + tag + 请求/响应两套仲裁 + 缓冲 |
| 顺序保证 | 总线独占 ⇒ 天然串行 | 需显式规定：请求顺序 = 系统全序 |
| 新引入的正确性风险 | 竞态、取数死锁、活锁 | 响应对不上、冲突请求、NACK 风暴、缓冲死锁 |
| 主要性能限制来源 | 内存延迟直接暴露在总线上 | 请求表项数（Little 定律）、请求总线占用、NACK 重试 |
- 冲突请求的两个情形（slide 51–52）：
- 情形 1：P1 读缺失 X，而总线上已有读事务涉及 X ⇒ 不冲突：不必发新请求，监听那个已存在事务的响应即可（搭车，数据在总线上广播，谁能用谁用）。
- 情形 2：P1 读缺失 X，而总线上有写（BusRdX）事务涉及 X ⇒ 冲突：必须挂起请求直到冲突清除，否则会读到被失效过程中的旧数据/顺序错乱。
- 图解（图 5）：请求表、冲突检查与数据广播（软件视角的执行模型）
每个缓存都保存一份相同的请求表 (Request Table, 8 项)
+------+------------------+--------+---------------+
| tag | Addr (line) | Op | State |
+------+------------------+--------+---------------+
| 0 | 0xbeef | BusRd | promoted | <-- 数据在响应总线上广播,
| 1 | 0x2a00 | BusRdX | shared | 所有侦听者都采样(即使不是请求者)
| 2 | ... | ... | ... |
| ... | | | |
+------+------------------+--------+---------------+
缓存 C 的决策流程:
处理器缺失(addr X, op)
|
v
查本地的请求表副本 ---------------------------+
| |
有无同名地址表项? |
| | |
无 有 |
| | |
v v |
还有空闲表项? 是读事务吗? |
| | | | |
有 无 是 否(=写) |
| | | | |
| v v v |
| NACK: "搭车": 不发新请求, 挂起等待该 |
| 稍后重试 事务的响应; 数据广播时自然拿到 |
| | | |
| | v |
| | 冲突: 挂起, 等该表项完成后重试
| | |
+------------+-------------------------------+
v
申请请求总线 -> 仲裁器分配 tag(=索引) -> 命令+地址上总线
2.9 为什么并行系统里到处是队列？—— 用有界缓冲”熨平”速率波动
- 定义与目的（slide 53）：队列的作用是容纳生产速率与消费速率之间不可预测的波动。只要 A 与 B 的平均速率相同，有了队列（哪怕只有 2 格）双方都可以全速运行而不互相拖累。
- 直观解释（”它是什么？”）：快递驿站的暂存架。寄件人（生产者）时而一次抱来三箱，时而空手；快递员（消费者）时而一次收走四箱。没有暂存架，寄件人得等快递员到场才能交件（stall），快递员也得等人来才能取件（stall）；有了两格暂存架，双方各自按自己的节奏全速跑，波动被架子吸收了。
- 图解（图 6）：无队列 vs 有队列（queue depth = 2）的时间线
无队列 (rendezvous): A 生产 1 个就必须等 B 取走, B 也必须等 A 生产
时间 -> 1 2 3 4 5 6 7 8 9 10 11 12
A: [A1] ...... [A2] ...... [A3] ...... [A4] ...... [A5]
^stall ^stall ^stall ^stall
B: ...... [B1] ...... [B2] ...... [B3] ...... [B4] ......
^stall ^stall ^stall
总吞吐 = 1 个/2 时间单位 (双方都在等对方, 谁都跑不满)
有队列 (size = 2): A 可以先做 2 个再等; B 可以攒着慢慢取
时间 -> 1 2 3 4 5 6 7 8 9 10 11 12
A: [A1] [A2] [A3] [A4] [A5] [A6] [A7] [A8] [A9] [A10] (全速)
队列: A1 A1,A2 A2,A3 A3,A4 A4,A5 ... (深度在 0~2 之间浮动)
B: [B1] [B2] [B3] [B4] [B5] [B6] [B7] [B8] [B9] [B10] (全速)
总吞吐 = 1 个/1 时间单位 —— 平均速率匹配时, 队列深度 2 就足够让双方都不 stall
-> 这就是 NACK/重试、请求表、write-back buffer、总线客户端接收缓冲存在的理由
2.10 多级缓存层次带来的两个新难题
- 难题 A：谁负责侦听？（slide 5、54）真实机器（如 Intel Core i7）是 Core → L1(d) → L2 → 共享 L3（每个核一个 bank）→ Ring 互连 的层次结构。如果只有 L2 控制器去侦听互连，那么L1 里发生的数据修改可能对 L2 控制器不可见。两种做法：
- 所有层缓存各自独立侦听互连——低效（重复侦听、总线上设备过多）；
- 维护包含性（inclusion）：L1 的内容必须是 L2 内容的子集。这样”L2 侦听 + 失效 L1”就等价于全层次侦听。代价是 L2 容量被”浪费”一部分用于覆盖 L1，且 L2 驱逐必须连带失效 L1。 讲义也点出：层次结构还放大了响应延迟，使取数死锁问题更尖锐（slide 55）。
- 难题 B：缓冲区死锁（buffer deadlock）（slide 56）：设 L1→L2 与 L2→L1 各只有一个缓冲槽（buffer size = 1）。L1 有一个出向（outgoing）读请求（处理器发起）等着进 L2；同时 L2 有一个入向（incoming）读请求（别的缓存发起，因 L1 是 write-back 才会发生）等着进 L1。两个请求的响应都需要对方队列里的空间 ⇒ 循环依赖 ⇒ 死锁。
- 图解（图 7）：缓冲区死锁的环形依赖，以及”请求/响应分离队列”如何打破环
(a) 只有一对队列时 —— 循环依赖, 死锁
+-------------+ L1->L2 队列 (cap=1, 已满) +-------------+
| L1 Cache |------------------------------>| L2 Cache |
| |<------------------------------| |
+-------------+ L2->L1 队列 (cap=1, 已满) +-------------+
^ ^
| 入向读请求的**响应**需要 L2->L1 空间 |
| 出向读请求的**响应**需要 L1->L2 空间 |
+------------------- 环 --------------------------+
L1 要发请求 -> 需要 L1->L2 空位 -> 该空位要靠"处理完入向请求"腾出
L2 要发请求 -> 需要 L2->L1 空位 -> 该空位要靠"处理完出向请求"腾出
=> 双方都在等对方先动, 谁也不动 = DEADLOCK
(b) 把请求与响应分开成 4 条队列 —— 环被打断
+-------------+ L1->L2 request queue +-------------+
| L1 Cache |------------------------->| L2 Cache |
| | L2->L1 request queue | |
| |<-------------------------| |
| | L1->L2 response queue | |
| |------------------------->| |
| | L2->L1 response queue | |
| |<-------------------------| |
+-------------+ +-------------+
关键洞察 (slide 58):
* 请求 (request) 会**增加**队列长度; 响应 (response) 会**减少**队列长度
* 响应**不会再产生新的事务**, 因此响应的处理一定能推进到底
* 正在为"发不出请求"而卡住的缓存, 仍然必须能处理响应
=> 响应最终一定会腾出资源, 让请求得以发出 —— 不存在循环依赖
2.11 软件执行模型：一句 int x = 10; 的全过程
- 定义与目的（slide 59–60）：讲义用一个课堂练习收尾：
int x = 10;（假定这是一次写内存，值不保存在寄存器里）。把这句话在真实多处理器机器上可能引发的事情全列出来——它把”程序语义”和”硬件执行模型”缝合在一起。 - 直观解释（”它是什么？”）：程序员看到的是”赋值”这一件事；硬件看到的是一场需要 TLB、页表、OS、缓存、总线仲裁器、多个侦听控制器、内存控制器、DRAM 全部参与的接力赛。
- 图解（图 8）：软件语句 → 硬件执行模型的 20 步接力
程序层: int x = 10; (一次 store, 架构上"原子")
==========================================================================
微架构/系统层 (讲义 slide 60 列出的 20 步, *表示讲师注明"绝非完整列表"):
1 虚拟地址 -> 物理地址转换 (TLB 查找)
2 TLB miss
3 TLB 更新 (可能涉及操作系统)
4 OS 可能需要换页, 把页表从磁盘换入物理内存
5 缓存查找 (tag check)
6 判定 line 不在缓存 (需要产生 BusRdX)
7 仲裁总线
8 赢得总线, 放上地址与命令
9 所有缓存执行侦听 (例如失效自己对应的副本) <-- 写在此刻"提交" (commit)
10 另一个缓存或内存决定由谁响应 (此例假设是内存)
11 内存请求送入内存控制器
12 内存控制器本身也是一个调度器
13 检查 DRAM 行缓冲中是否有活跃的行 (可能需要激活新行, 此例假设需要)
14 DRAM 把数据读入行缓冲
15 内存仲裁数据总线
16 内存赢得总线
17 内存把数据放上总线
18 请求方缓存取走数据, 更新缓存行与 tag, 转入独占状态
19 通知处理器数据已就绪
20 指令继续执行
==========================================================================
结论: 一条被抽象为"原子"的访存, 实际由 ~20 个跨组件步骤实现;
其中任何一步的并行/非原子性都可能成为正确性或性能的问题来源
- 性能特征：这条链路上真正的长杆是第 2–4 步（TLB miss + 缺页，微秒级）、第 6–17 步（一致性事务 + DRAM，百纳秒级）；而第 9 步的侦听与”提交”发生在没有总线流量的窗口里（slide 45 标注 “Memory operation commits here! (NO BUS TRAFFIC)”）——这提醒我们：延迟与总线占用不是一回事，分析性能时要分清”关键路径延迟”和”共享资源占用”。
3. 代码示例与性能分析
3.1 示例 1：伪共享（false sharing）—— 一致性协议在软件层面最贵的账单
- 代码：
// 编译（release）: g++ -O3 -std=c++17 -pthread false_sharing.cpp -o false_sharing
// 运行: ./false_sharing packed # 4 个计数器挤在同一条 cache line
// ./false_sharing padded # 每个计数器独占一条 cache line
#include <pthread.h>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
static constexpr int kThreads = 4;
static constexpr uint64_t kIters = 50'000'000ULL; // 每线程自增次数
// ---- 布局 A: 4 个计数器共享同一条 64 B cache line（伪共享） ----
struct Packed {
alignas(64) volatile uint64_t c[kThreads];
};
// ---- 布局 B: 每个计数器独占一条 cache line（对齐 + 填充） ----
struct alignas(64) Padded {
volatile uint64_t v;
char pad[64 - sizeof(uint64_t)];
};
static Packed g_packed; // 4 个计数器 = 1 条 line
static Padded g_padded[kThreads]; // 4 个计数器 = 4 条 line
struct Arg { int id; int use_padded; };
static double now_sec() {
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return double(ts.tv_sec) + double(ts.tv_nsec) * 1e-9;
}
static void* worker(void* p) {
const Arg* a = static_cast<const Arg*>(p);
// 每个线程只访问自己的槽位: 逻辑上没有数据竞争
volatile uint64_t* target = a->use_padded ? &g_padded[a->id].v : &g_packed.c[a->id];
for (uint64_t i = 0; i < kIters; ++i) {
*target = *target + 1; // 读-改-写: 每次都需要该 line 处于 M 态
}
return nullptr;
}
int main(int argc, char** argv) {
const int use_padded = (argc > 1 && std::strcmp(argv[1], "padded") == 0) ? 1 : 0;
pthread_t t[kThreads];
Arg arg[kThreads];
const double t0 = now_sec();
for (int i = 0; i < kThreads; ++i) {
arg[i] = Arg{i, use_padded};
pthread_create(&t[i], nullptr, worker, &arg[i]);
}
for (int i = 0; i < kThreads; ++i) pthread_join(t[i], nullptr);
const double dt = now_sec() - t0;
uint64_t checksum = 0;
for (int i = 0; i < kThreads; ++i)
checksum += use_padded ? g_padded[i].v : g_packed.c[i];
std::printf("%-7s threads=%d iters/thread=%llu time=%.3f s %.1f Mops/s checksum=%llu\n",
use_padded ? "padded" : "packed", kThreads,
(unsigned long long)kIters, dt,
double(kThreads) * double(kIters) / dt / 1e6,
(unsigned long long)checksum);
return 0;
}
- 【代码做什么？】
main按命令行参数选择两种内存布局之一，创建kThreads个 pthread，每个线程用Arg{id, use_padded}携带自己的编号与模式。worker中每个线程只读写属于自己 id 的那个计数器：packed模式下 4 个uint64_t落在同一条 64 B line 内，padded模式下每个计数器被alignas(64)强制对齐到独立 cache line。- 每个线程做 5000 万次
*target = *target + 1（读-改-写），保证每次操作都要持有一条可写副本。 pthread_join后统计checksum（应为 4 × 5e7 = 2×10⁸），并打印墙钟时间与总操作率。- 逻辑上没有数据竞争（不同线程访问不同的内存位置），但结果差异巨大——这正是伪共享的本质。
- 【并行机制与性能解说】
- 硬件上如何执行：
packed模式下，4 个核的每次自增都要求同一条 cache line 处于 M 态。M 态是互斥的，于是每次自增都触发一次BusUpg/BusRdX（或用 MESI 的 upgrade 事务）并把上一位持有者的脏行 flush 出来再失效它——cache line 在核之间来回弹跳（ping-pong）。padded模式下每个核的 line 稳定停留在自己的缓存里（M 或 E 态），自增退化为纯本地操作。 - Work / Span / 并行度：
packed：Work = 4 × 5e7 = 2×10⁸ 次自增；Span = 2×10⁸ 次串行的 line 迁移（因为同一时刻只有一个核能持有可写副本，整条执行变成一条链）。并行度 = Work/Span = (2×10⁸ × C_increment) / (2×10⁸ × L_transfer) = C_increment / L_transfer ≈ 1/100 ≪ 1——即并行度比串行还差，多核反而放大开销。padded：Work = 2×10⁸ 次自增；Span = 每线程自己的 5e7 次依赖链（每线程一条），Span = 5e7 × C_increment。并行度 = Work/Span = (4 × 5e7 × C)/(5e7 × C) = 4（= 线程数），随核数线性可扩展。
- 瓶颈定位：
packed的瓶颈是一致性事务延迟 × 次数（每次操作一次 line 迁移），等价于”用总线延迟替代了 ALU 吞吐”；padded的瓶颈回到本地 store-to-load 依赖链与 ALU。 - Amdahl 视角：即使只有 1% 的内存操作落在共享行上，若每次都付出约 100 周期的迁移延迟而本地操作只值 1 周期，那么这 1% 的操作会吃掉总时间的
0.01×100 / (0.99×1 + 0.01×100) ≈ 50%——少数伪共享行足以主导整程序性能，这与”总线是共享资源”的硬件结论完全一致。
- 硬件上如何执行：
3.2 示例 2：拆分事务总线 + 请求表 + NACK 流控的周期级模拟器
这是本讲最”贴题”的实验：用 200 行 C 把 slide 41–52 的机制做成可跑的数字。
- 代码：
/* 周期级模拟: 原子总线 vs 拆分事务总线 (请求表 + tag + NACK 流控)
* 编译（release）: gcc -O3 -std=c11 split_bus_sim.c -o split_bus_sim
* 运行: ./split_bus_sim
*/
#include <stdio.h>
#include <string.h>
#define NCACHE 4 /* 处理器/缓存个数 P0..P3 */
#define TAG_COUNT 8 /* 请求表项数 = 同时最多 8 个未完成请求 */
#define REQ_CYCLES 5 /* ARB,RSLV,ADDR,DCD,ACK 请求阶段周期数 */
#define DATA_CYCLES 4 /* 128 B line / 32 B(256 bit) 数据总线 */
#define MEM_LATENCY 100 /* DRAM 取数延迟（周期） */
#define RETRY_DELAY 10 /* NACK / 冲突后的重试延迟 */
#define NUM_MISSES 100000 /* 每个缓存要发出的缺失次数 */
#define LINES_SPACE 4096 /* 地址空间（cache line 计），用于制造冲突 */
#define MAXPEND 32 /* 每缓存未完成缺失槽位数（容量上限） */
#define LINE_BYTES 128
#define CLOCK_GHZ 3.0
typedef struct { int valid, addr, data_ready, data_start, complete; } Req;
static Req rtab[TAG_COUNT];
static int outstanding;
static int pend_tag[NCACHE][MAXPEND]; /* 槽位 -> 正在等待的请求表 tag (-1 空) */
static unsigned lcg[NCACHE];
typedef struct {
long cycles, lines, nack, conflict, combined;
long req_bus_cycles, data_bus_cycles;
} Stats;
/* ---- 拆分事务总线模拟: mshr_limit = 每个缓存允许的未完成缺失数 ---- */
static Stats simulate_split(int mshr_limit)
{
Stats st; memset(&st, 0, sizeof st);
memset(rtab, 0, sizeof rtab);
for (int c = 0; c < NCACHE; c++) {
for (int s = 0; s < MAXPEND; s++) pend_tag[c][s] = -1;
lcg[c] = 12345u + 7919u * (unsigned)c;
}
outstanding = 0;
int issued[NCACHE] = {0}, inflight[NCACHE] = {0};
long next_try[NCACHE] = {0};
long req_bus_free = 0, data_bus_free = 0;
const long total = (long)NCACHE * NUM_MISSES;
long done = 0, cycle = 0;
for (cycle = 0; done < total && cycle < 200000000L; cycle++) {
/* (1) 数据总线上的响应在本周期完成 -> 释放请求表项 */
int freed[TAG_COUNT]; int nfreed = 0;
for (int i = 0; i < TAG_COUNT; i++)
if (rtab[i].valid && rtab[i].complete == (int)cycle) {
rtab[i].valid = 0; rtab[i].complete = -1;
freed[nfreed++] = i; outstanding--;
}
/* (2) 广播: 数据在响应总线上对所有侦听者可见(请求者与"搭车者"同时完成) */
for (int c = 0; c < NCACHE; c++)
for (int s = 0; s < MAXPEND; s++) {
int t = pend_tag[c][s];
if (t < 0) continue;
for (int k = 0; k < nfreed; k++)
if (freed[k] == t) { pend_tag[c][s] = -1; inflight[c]--; done++; break; }
}
/* (3) 各缓存尝试发起缺失(轮转起点随时间变化, 模拟公平仲裁) */
for (int k = 0; k < NCACHE; k++) {
int c = (int)((cycle + k) % NCACHE);
if (issued[c] >= NUM_MISSES || inflight[c] >= mshr_limit) continue;
if (cycle < next_try[c]) continue;
lcg[c] = lcg[c] * 1103515245u + 12345u;
int addr = (int)((lcg[c] >> 8) % LINES_SPACE);
/* 冲突检查: 每个缓存都持有请求表副本 (slide 50-52) */
int host = -1, conflict = 0;
for (int i = 0; i < TAG_COUNT; i++) {
if (!rtab[i].valid || rtab[i].addr != addr) continue;
host = i; conflict = 1; /* 同地址事务未完成 */
}
if (host >= 0) { /* 情形 1: 读-读可"搭车"(本模型统一按冲突处理) */
st.conflict++;
next_try[c] = rtab[host].complete > 0 ? rtab[host].complete : cycle + RETRY_DELAY;
continue;
}
(void)conflict;
if (outstanding >= TAG_COUNT) { /* 流控: 请求表满 -> NACK + 稍后重试 */
st.nack++;
next_try[c] = cycle + RETRY_DELAY;
continue;
}
int tag = -1;
for (int i = 0; i < TAG_COUNT; i++) if (!rtab[i].valid) { tag = i; break; }
long start = (req_bus_free > cycle) ? req_bus_free : cycle;
rtab[tag].valid = 1; rtab[tag].addr = addr;
rtab[tag].data_ready = (int)(start + REQ_CYCLES + MEM_LATENCY);
rtab[tag].data_start = -1; rtab[tag].complete = -1;
req_bus_free = start + REQ_CYCLES;
outstanding++;
st.req_bus_cycles += REQ_CYCLES;
issued[c]++; inflight[c]++;
for (int s = 0; s < MAXPEND; s++)
if (pend_tag[c][s] < 0) { pend_tag[c][s] = tag; break; }
}
/* (4) 响应总线仲裁: 数据就绪者中挑最早就绪的占用数据总线 */
if (data_bus_free <= cycle) {
int best = -1;
for (int i = 0; i < TAG_COUNT; i++) {
if (!rtab[i].valid || rtab[i].data_start >= 0) continue;
if (rtab[i].data_ready > (int)cycle) continue;
if (best < 0 || rtab[i].data_ready < rtab[best].data_ready) best = i;
}
if (best >= 0) {
rtab[best].data_start = (int)cycle;
rtab[best].complete = (int)(cycle + DATA_CYCLES);
data_bus_free = rtab[best].complete;
st.data_bus_cycles += DATA_CYCLES;
st.lines++;
}
}
}
st.cycles = cycle;
return st;
}
/* ---- 原子总线基线: 请求-响应之间不允许插入任何事务 ---- */
static Stats simulate_atomic(void)
{
Stats st; memset(&st, 0, sizeof st);
long per_txn = REQ_CYCLES + MEM_LATENCY + DATA_CYCLES; /* 总线被独占 */
st.lines = (long)NCACHE * NUM_MISSES;
st.cycles = st.lines * per_txn;
st.req_bus_cycles = st.lines * REQ_CYCLES;
st.data_bus_cycles = st.lines * DATA_CYCLES;
return st;
}
static void report(const char* name, Stats st)
{
double sec = (double)st.cycles / (CLOCK_GHZ * 1e9);
double bytes = (double)st.lines * LINE_BYTES;
double gbps = bytes / sec / 1e9;
double util_req = 100.0 * (double)st.req_bus_cycles / (double)st.cycles;
double util_data = 100.0 * (double)st.data_bus_cycles / (double)st.cycles;
printf("%-22s cycles=%10ld time=%8.3f ms xfer=%7.2f MB BW=%7.2f GB/s"
" reqbus=%5.1f%% databus=%5.1f%% NACK=%6ld conflict=%6ld\n",
name, st.cycles, sec * 1e3, bytes / 1e6, gbps,
util_req, util_data, st.nack, st.conflict);
}
int main(void)
{
printf("line=%d B, req phase=%d cyc, data phase=%d cyc, mem latency=%d cyc, "
"req-table=%d entries, %d caches x %d misses\n\n",
LINE_BYTES, REQ_CYCLES, DATA_CYCLES, MEM_LATENCY,
TAG_COUNT, NCACHE, NUM_MISSES);
report("atomic bus", simulate_atomic());
int ms[] = {1, 2, 4, 8};
char nm[64];
for (unsigned i = 0; i < sizeof ms / sizeof ms[0]; i++) {
snprintf(nm, sizeof nm, "split, MSHR=%d", ms[i]);
report(nm, simulate_split(ms[i]));
}
/* 理论上限 */
double peak_data = (double)(32 * CLOCK_GHZ); /* 32 B/cycle 数据总线 */
double peak_req = (double)LINE_BYTES * CLOCK_GHZ / REQ_CYCLES; /* 请求总线限制 */
double tag_limit = (double)TAG_COUNT * LINE_BYTES * CLOCK_GHZ
/ (REQ_CYCLES + MEM_LATENCY + DATA_CYCLES); /* 请求表项数限制 */
printf("\npeaks: data bus=%.1f GB/s, request bus=%.1f GB/s, %d-entry request table=%.1f GB/s\n",
peak_data, peak_req, TAG_COUNT, tag_limit);
return 0;
}
- 【代码做什么？】
- 建立一条请求表（8 项），每项记录地址、数据就绪周期、数据总线开始/完成周期；
pending槽位记录”哪个缓存正在等哪个 tag 的数据”。 - 主循环逐周期推进，每周期做四件事：(1) 释放本周期完成的数据响应所对应的表项；(2) 把完成事件广播给请求者与搭车者；(3) 让每个缓存尝试发起缺失（查冲突 → 查请求表是否满 → 分配 tag → 占用请求总线
REQ_CYCLES周期）；(4) 响应总线仲裁，从”数据已就绪”的请求中挑一个占用数据总线DATA_CYCLES周期。 - 地址用每个缓存独立的 LCG 在一个容量为 4096 条 line 的小地址空间里生成，用来产生”同地址事务未完成”的冲突；请求表满时打印 NACK 并延后
RETRY_DELAY周期重试（对应 slide 43/50 的流控）。 simulate_atomic()直接给出原子总线的解析基线：每个事务独占总线REQ_CYCLES + MEM_LATENCY + DATA_CYCLES = 109周期。main依次跑 MSHR = 1/2/4/8 四种”每缓存未完成缺失上限”，并打印三条理论上限（数据总线、请求总线、请求表项数）。
- 建立一条请求表（8 项），每项记录地址、数据就绪周期、数据总线开始/完成周期；
- 【并行机制与性能解说】
- 并行在哪里：4 个缓存并行地产生缺失、并行地侦听响应总线（数据广播，所有侦听者同时完成）；请求总线与数据总线两条总线并行工作；被打破的假设是原子总线的”请求到响应之间总线独占”。
- Work / Span / 并行度（针对被建模的机器，单位是”周期”）：
- Work（总线必须付出的总工作） = 每个请求的请求阶段 + 数据阶段 =
N × (REQ_CYCLES + DATA_CYCLES)= 4×10⁵ × 9 = 3.6×10⁶ 周期（串行占用等价量）。 - Span（单个缺失的关键路径） =
REQ_CYCLES + MEM_LATENCY + DATA_CYCLES= 5 + 100 + 4 = 109 周期（再加排队与 NACK 重试）。 - 并行度上限 = 请求表项数 = 8；由 Little 定律，要打满请求总线上限需要的未完成请求数 =
rate × latency = (1/5) × 109 ≈ 22。所以 8 项请求表天然只能达到请求总线峰值的约 8/22 ≈ 36%——这是”用少量硬件换顺序保证”的直接代价。
- Work（总线必须付出的总工作） = 每个请求的请求阶段 + 数据阶段 =
- 瓶颈识别：MSHR 从 1 涨到 2 时带宽翻倍（从”每缓存一个缺失、延迟受限”进入”全系统并发”）；继续增大 MSHR 则由请求表项数封顶，NACK/重试开始出现，收益饱和甚至因重试延迟而略降。这正是讲义”性能优化使正确性变复杂”的定量体现：MSHR 越多 → 未完成请求越多 → 冲突、NACK、缓冲压力越大。
3.3 示例 3：有界队列如何”熨平”生产/消费速率波动（队列存在的理由）
- 代码：
// 编译: g++ -O3 -std=c++17 -pthread bounded_queue.cpp -o bounded_queue
// 运行: ./bounded_queue 1 # 队列容量 1（近似 rendezvous）
// ./bounded_queue 2 # 队列容量 2（讲义 slide 53 的"刚好够用"）
// ./bounded_queue 64 # 深队列
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <cstdio>
#include <cstdlib>
#include <mutex>
#include <thread>
#include <vector>
template <typename T>
class BoundedQueue { // 有界队列 ≈ 总线客户端的请求/响应缓冲
public:
explicit BoundedQueue(size_t cap)
: cap_(cap), buf_(cap), head_(0), tail_(0), n_(0), closed_(false) {}
void push(T v, std::atomic<long>& producer_stall) {
std::unique_lock<std::mutex> lk(m_);
if (n_ == cap_) ++producer_stall; // 队列满: 生产者等待(= NACK)
not_full_.wait(lk, [&] { return n_ < cap_ || closed_; });
if (closed_) return;
buf_[tail_] = v;
tail_ = (tail_ + 1) % cap_;
++n_;
not_empty_.notify_one();
}
bool pop(T& out, std::atomic<long>& consumer_stall) {
std::unique_lock<std::mutex> lk(m_);
if (n_ == 0) ++consumer_stall; // 队列空: 消费者等待(= 总线空闲无数据)
not_empty_.wait(lk, [&] { return n_ > 0 || closed_; });
if (n_ == 0 && closed_) return false;
out = buf_[head_];
head_ = (head_ + 1) % cap_;
--n_;
not_full_.notify_one();
return true;
}
void close() {
std::lock_guard<std::mutex> lk(m_);
closed_ = true;
not_empty_.notify_all();
not_full_.notify_all();
}
private:
size_t cap_, head_, tail_, n_;
std::vector<T> buf_;
std::mutex m_;
std::condition_variable not_full_, not_empty_;
bool closed_;
};
int main(int argc, char** argv) {
const size_t cap = (argc > 1) ? std::strtoul(argv[1], nullptr, 10) : 1;
const long kItems = 2000000;
const int kProducers = 2, kConsumers = 2;
BoundedQueue<long> q(cap ? cap : 1);
std::atomic<long> produced{0}, consumed{0}, pstall{0}, cstall{0};
const auto t0 = std::chrono::steady_clock::now();
std::vector<std::thread> producers;
for (int p = 0; p < kProducers; ++p)
producers.emplace_back([&, p] {
for (;;) {
const long i = produced.fetch_add(1); // 原子取号: 工作分配
if (i >= kItems) { produced.fetch_sub(1); break; }
if ((i % 64) == 0) // 制造速率波动(bursty)
std::this_thread::yield();
q.push(i, pstall);
}
});
std::vector<std::thread> consumers;
for (int c = 0; c < kConsumers; ++c)
consumers.emplace_back([&] {
long v;
while (q.pop(v, cstall)) consumed.fetch_add(1);
});
for (auto& t : producers) t.join();
q.close();
for (auto& t : consumers) t.join();
const double dt = std::chrono::duration<double>(
std::chrono::steady_clock::now() - t0).count();
std::printf("queue cap=%-3zu consumed=%ld time=%.3f s %.2f Mitems/s "
"producer_stalls=%ld consumer_stalls=%ld\n",
cap, consumed.load(), dt, kItems / dt / 1e6,
pstall.load(), cstall.load());
return 0;
}
- 【代码做什么？】
kProducers个线程用produced.fetch_add(1)原子取号拿到工作项（这是 slide 53 里”队列”的另一种形态：原子计数器本身也是一条被争用的 cache line），每 64 项yield()一次制造速率波动，然后push进容量为cap的有界队列；kConsumers个线程pop直到队列关闭。程序统计生产者因队列满而等待的次数与消费者因队列空而等待的次数，这正是讲义 slide 53 中 A、B 是否 stall 的度量。编译时用-O3保证push/pop的簿记代码不成为瓶颈。 - 【并行机制与性能解说】
- 硬件上如何执行：
std::mutex与condition_variable的等待/唤醒依赖 futex（内核）与缓存行上的原子操作；produced/pstall等原子计数器在同一 cache line 上被多个核更新时会伪共享，本身成为串行化点。队列中的元素在生产者核上写、在消费者核上读，会发生cache line 迁移（ping-pong）——因此增大队列并不免费，深度越大、line 迁移越多。 - Work / Span / 并行度：
- Work =
N × (t_produce + t_consume) + N × t_queue_bookkeeping。 - Span（无 stall、队列足够深时）=
N × max(t_produce, t_consume) + t_consume（流水线填充）。 - 并行度 = Work/Span ≈ (t_p + t_c)/max(t_p, t_c) ≤ 2：两阶段流水线的并行度上限是 2，与队列深度无关。队列只能消除”速率波动造成的 stall”，不能增加阶段数——这是理解 slide 53 的关键：队列解决的是抖动（jitter），不是吞吐上限。要更高吞吐必须增加流水线级数或复制阶段（例如多缓冲、多总线通道）。
- 当
cap = 1时，队列退化为近 rendezvous，producer_stalls + consumer_stalls显著大于 0；cap = 2时按讲义结论 stall 应大幅下降；继续增大cap收益递减（因为平均速率已经匹配，剩余 stall 只来自初始相位差与调度抖动）。
- Work =
- 硬件上如何执行：
4. 性能模型与复杂度分析
4.1 三个必须同时写的”预算约束”
对任何一致性实现，都要同时满足三类约束，任何一类被突破就是实际瓶颈：
- 延迟约束（latency）：一次缺失的关键路径
T_miss = T_req_bus + T_mem + T_data_bus + T_queue + T_retry（本讲参数：5 + 100 + 4 + 排队 + NACK 重试） - 带宽约束（bandwidth）：共享资源的上限
BW_max = min(请求总线带宽, 数据总线带宽, 请求表项数 / T_miss × line_size, 队列深度 / T_miss × line_size) - 并发约束（Little 定律）：要隐藏延迟
L并达到吞吐R，需要并发数 N = R × L——这是”MSHR 数 / 请求表项数”必须够大的原因，也是 8 项请求表成为硬上限的原因。
4.2 数值算例：原子总线 vs 拆分事务总线的有效带宽
假设参数（与讲义 slide 47 一致）：数据总线 256 bit = 32 B/周期；cache line = 128 B ⇒ 数据阶段 4 周期；时钟 3.0 GHz；请求阶段 5 周期（ARB/RSLV/ADDR/DCD/ACK）；DRAM 延迟 100 周期；4 个处理器/缓存，各发出 100,000 次缺失（合计 400,000 次，每次传输 128 B ⇒ 共 51.2 MB）。
(a) 原子总线（Part 1）：每事务独占总线 5 + 100 + 4 = 109 周期。
- 总周期 = 400,000 × 109 = 4.36×10⁷ 周期
- 时间 = 4.36×10⁷ / 3.0×10⁹ = 14.53 ms
- 有效带宽 = 51.2 MB / 14.53 ms = 3.52 GB/s
- 总线利用率 =
(5 + 4) / 109= 8.3%（其余 91.7% 的时间总线在等 DRAM 响应）
(b) 拆分事务总线、每缓存 MSHR = 1（T_miss ≈ 109，无排队、无 NACK）：
- 每缓存的缺失速率 =
1 / 109条/周期；系统 =4 / 109条/周期 - 带宽 =
(4 / 109) × 128 B × 3.0×10⁹= 14.1 GB/s - 相对原子总线提升 4.0×（≈ 缓存的并发缺失数）
- 时间 = 400,000 × 109 / 4 周期 = 1.09×10⁷ 周期 = 3.63 ms
(c) 拆分事务总线、请求表 8 项被填满（T_miss ≈ 109）：
- 系统缺失速率 ≤
8 / 109条/周期（表项数限制） - 带宽 =
(8 / 109) × 128 × 3.0×10⁹= 28.2 GB/s（相对原子总线 8.0×） - 时间 = 400,000 × 109 / 8 = 5.45×10⁶ 周期 = 1.82 ms
(d) 三条理论上限（用示例 2 的公式计算）：
- 数据总线上限 =
32 B/周期 × 3.0 GHz= 96.0 GB/s - 请求总线上限 =
128 B / 5 周期 × 3.0 GHz= 76.8 GB/s - 请求表项数上限 = 8 × 128 B × 3.0 GHz / 109 周期 = 28.2 GB/s ← 最紧的约束
(e) Little 定律反推：要打满请求总线上限需要多少并发？
N = R × L = (1 条 / 5 周期) × 109 周期 ≈ 21.8 ⇒ 约 22 个未完成请求。 8 项请求表只能支撑 8/22 ≈ 36% 的请求总线峰值。结论：把请求表从 8 项扩到 24 项，才可能让带宽再提升约 2.7 倍——这正是”性能优化需要更多硬件”的量化版本。
- 表 4：性能模型汇总（上述算例的数值）
| 配置 | 关键路径 T_miss | 并发数上限 | 有效带宽 | 相对原子总线 | 总线/表项利用率 |
|---|---|---|---|---|---|
| 原子总线 | 109 周期（独占） | 1 | 3.52 GB/s | 1.0× | 请求线 4.6% / 数据线 3.7% |
| 拆分事务，MSHR=1/缓存 | 109 周期 | 4 | 14.1 GB/s | 4.0× | 请求线 18% / 数据线 15% |
| 拆分事务，请求表 8 项打满 | 109 周期 | 8 | 28.2 GB/s | 8.0× | 请求线 37% / 数据线 29% |
| 请求总线理论峰值 | — | 22 | 76.8 GB/s | 21.8× | 100% |
| 数据总线理论峰值 | — | 27 | 96.0 GB/s | 27.3× | 100% |
（利用率一列按 并发数 × 阶段周期 / T_miss 估算：如 MSHR=1 时请求线 4×5/109 = 18.3%。）
4.3 伪共享的定量代价（示例 1 的模型）
假设：4 核，L3/跨核 cache line 迁移一次往返成本 L_ping ≈ 60 ns（约 180 周期 @3 GHz）；本地自增（volatile load+store 往返）C_inc ≈ 5 周期 ≈ 1.7 ns；每线程 5×10⁷ 次。
packed：每次操作一次迁移 ⇒ 时间 ≈2×10⁸ × 60 ns = 12 s；总操作率 ≈ 16.7 Mops/s（4 个核加起来还不如单核本地速度）。padded：时间 ≈5×10⁷ × 1.7 ns = 85 ms；总操作率 ≈ 2.35 Gops/s。- 比值 ≈ 140×——两边代码”算法上完全一样”，差别只在 4 个计数器是否落在同一 64 B 行内。
- 算术强度（arithmetic intensity）视角：把每次 line 迁移的 128 B 流量算进去，
packed的”每次自增 1 个操作却要搬 128 B”⇒ 算术强度 ≈ 0.008 op/B。若内存/互连带宽为 28 GB/s（见 §4.2），则带宽可支持的速率上限 =28e9 × 0.008 ≈ 2.2×10⁸ ops/s，与实测的 1.7×10⁷ ops/s 同量级（更慢，因为还要算延迟而非纯带宽）——用 Roofline 的思路看：packed版本被钉在”带宽/延迟天花板”上，而padded版本才回到 ALU 屋顶。
4.4 用 Amdahl 定律看”共享资源串行化”
总线仲裁、请求表分配、数据总线仲裁在物理上都是串行段（同一时刻只能一个赢家）。
- 设某程序总执行时间里，必须走总线且无法与其他核重叠的比例为
s。 - Amdahl：
Speedup(N) = 1 / (s + (1-s)/N)。若s = 0.20（对总线密集型负载很常见），则 N→∞ 时加速比上限为 5×，N = 8 时只有1/(0.2 + 0.1) = 3.3×（并行效率 42%）。 - 这也解释了 §4.2 的结论：在 4 核系统上，把有效带宽从 3.52 GB/s 提到 28.2 GB/s（8×），本质上是把那 91.7% 的”闲置串行段”回收成可用的并发窗口。原子总线版本里，每次缺失有
100/109 = 91.7%的时间总线被事务独占却什么也不传——等价于把串行比例s抬到接近 1，于是Speedup(N) → 1（加核没有用）；拆分成 8 项请求表后这段闲置被填上，多核才有可能拿到接近线性的加速。 - 同步/仲裁开销的代价公式：
T(N) = T_work/N + T_serial，其中T_serial ≈ (# misses) × (REQ_CYCLES / 表项数)；对 4×10⁵ 次缺失、8 项表：4×10⁵ × 5/8 ≈ 2.5×10⁵ 周期 = 0.083 ms（相对 1.82 ms 的总时间约占 4.6%），而原子总线版本这一项退化为4×10⁵ × 109 = 4.36×10⁷ 周期，占总时间 100%。
4.5 表 5：各类缓存与互连延迟/占用的量级参考（用于建立”预算感”）
| 层次 | 典型延迟（周期 @3 GHz） | 典型延迟（时间） | 是否可与其他核重叠 |
|---|---|---|---|
| L1 命中 | 4 | ~1.3 ns | 是（每核私有） |
| L2 命中 | 12 | ~4 ns | 是（每核私有） |
| L3 命中（共享 bank） | 40 | ~13 ns | 部分（bank 可并行） |
| 同 socket 缓存间 line 迁移 | ~180 | ~60 ns | 否（占用互连） |
| DRAM | ~100–300 | 33–100 ns | 部分（多 bank 可并行） |
| 一片 TLB miss / 缺页 | 10³–10⁶ | 0.3 µs–0.3 ms | 否（关键路径） |
5. 关键要点
- 正确性不变量必须写下来，性能优化必须证明它没被破坏。 MESI 的三个不变量（至多一个 M；M 存在则他人全 I；S 存在则无 M）才是真正要维护的东西；状态机、总线信号、请求表都是实现手段。讲义的例子（P2 的待发
BusUpg在收到他人BusUpg后必须改写成BusRdX）说明：只要引入”等待期间仍能接收事件”，就必须允许修改已经排队的操作。 - 共享资源（总线、请求表、数据总线、仲裁器）天然是串行段，它的容量直接决定可扩展性上限。 原子总线的总线利用率只有
(5+4)/109 ≈ 8.3%；拆分成请求/响应两条总线、并配上 8 项请求表后可达 28 GB/s，而请求总线峰值 76.8 GB/s 需要约 22 个并发请求（Little 定律）。并发数上限是硬件给的天花板，不是软件调优能突破的。 - 性能优化 = 把大操作拆成更多小事务 + 用队列吸收速率波动；代价永远是额外硬件与新的正确性风险。 拆分事务带来”请求-响应匹配、冲突请求、NACK 流控”；write-back buffer 带来”侦听必须查 buffer”；多级层次带来”包含性”与”缓冲死锁”。讲义的核心句式：Techniques that pursue high performance tend to make ensuring correctness tricky（追求高性能的技术往往让保证正确性变得棘手）。
- 死锁/活锁/饥饿是三种不同的病，必须对症下药。 死锁 = 循环等待（用”等待中也服务外来请求”和”请求/响应队列分离”打断环）；活锁 = 独占所有权被反复抢走（让获得所有权的写先完成）；饥饿 = 公平性问题（FIFO 仲裁、优先级衰减）。响应不会再产生新事务，因此响应一定能推进——这是打破队列死锁的理论基础。
- commit（提交）≠ complete（完成）；总线上的请求顺序定义了并行程序的写序（write serialization）。 写提交于”读独占事务出现在总线上并被所有缓存确认”的时刻；write-back buffer 只推迟”完成”，不改变”提交”。这条区分是后面讨论内存一致性模型（memory consistency）的地基。
6. 常见陷阱与注意事项
- 把协议状态机当成分步执行的原子操作来推理。 讲义 slide 30 明确警告：查 tag、仲裁总线、等待其他控制器都不是原子的。若在代码/验证中假定”发完
BusUpg就一定能进 M 态”，就会错过 slide 31 那类竞态（请求语义需要中途改写）。 - 在设计/使用缓存控制器时忘记”等待中仍要服务”。 只等自己的请求、不处理外来侦听，直接导致 fetch deadlock（slide 32）；同样的错误在软件层表现为”持锁时阻塞在另一个需要该锁的调用上”（例如持锁做阻塞 I/O，而 I/O 回调又要取同一把锁）。排队时不能停止服务，这是硬件与软件共通的准则。
- 忽视伪共享（false sharing）。 每个线程只写自己的变量、逻辑上零竞争，仍可能因共享同一条 64 B line 而让性能下降百倍（示例 1 的模型给出约 140×）。对策：
alignas(64)隔离热点计数器、线程本地归约（reduction）后再合并、按行分块（padding/padding-free 布局重构）。 - 误以为”更深的队列/更多缓冲能提高吞吐”，同时忽略公平性。 队列只吸收速率波动，它让双方各自全速跑，但不增加流水线级数——两阶段流水线的并行度上限是 2（示例 3）。同理，把 MSHR 从 4 加到 8 而请求表仍是 8 项时，收益会饱和甚至因 NACK 重试而变差（示例 2）。而”优先级固定”的仲裁策略（例如”谁 id 小谁赢”）在功能上正确、在性能上可能让某个核永远拿不到总线，即饥饿（starvation）；必须用 FIFO 仲裁、优先级衰减或请求老化（aging）来保证公平。先确认瓶颈是延迟、带宽还是并发容量，再决定加什么，并检查策略的公平性。
- 忽略写回缓冲的一致性责任。 只侦听 tags 而不侦听 write-back buffer，会让其他处理器读到内存里的旧值——这是静默的数据错误，不是性能问题（讲义 slide 29）。同理，缓冲区尺寸取 1 而不做请求/响应队列分离会导致缓冲死锁（slide 56–58）。
- 把”总线”当成互连的全部，并混淆”延迟”与”占用”。 讲义特意提醒：现代机器大多不用总线（有专门的互连网络讲座）。多级层次（L1/L2/L3 + ring）意味着”侦听谁、失效谁、包含性怎么维护”都要重新设计；把总线的直觉直接套到 NoC/目录式系统上会得出错误结论。另外，侦听与 commit 发生在总线上没有流量的窗口（slide 45 的 “NO BUS TRAFFIC”），把”延迟长”直接当成”带宽被占满”会找错瓶颈。
7. 思考题（带答案）
问题 1. 讲义中把原子总线换成拆分事务总线后，性能提升来自哪里？为什么讲义又说”响应不必按请求顺序返回，但请求顺序确立系统全序”？如果让你把请求表从 8 项扩到 24 项，会发生什么，代价是什么？
【答案】 提升来自把”等待响应”的时间从总线独占变成可被其他事务利用。原子总线下一次缺失占用总线 5 + 100 + 4 = 109 周期，其中 100 周期总线在空转，利用率只有 9/109 ≈ 8.3%，有效带宽约 3.52 GB/s；拆分成请求总线与响应总线后，8 项请求表被打满时缺失速率上限为 8/109 条/周期，带宽升到 28.2 GB/s（8×）。 “请求顺序 = 系统全序”的原因是：顺序必须由某个所有人都能观察到的事件来定义，而在拆分设计中，唯一全局串行的就是请求总线上的地址/命令仲裁顺序（数据可以乱序到达，因为它只影响”什么时候拿到值”，不影响”哪个写先发生”）。只要所有缓存都按请求总线的顺序解释失效/升级，写串行化（write serialization）就成立——这正是 commit 定义（”读独占事务出现在总线上并被所有缓存确认”）的基础。 把请求表扩到 24 项：按 Little 定律，N = R × L = (1/5) × 109 ≈ 22，所以 24 项足以逼近请求总线上限 76.8 GB/s（128 B / 5 周期 × 3 GHz），带宽可从 28.2 GB/s 再提升约 2.7 倍；但代价是：(a) 硬件面积与功耗（每项要存地址、状态，每个总线客户端还要维持一份副本）；(b) 冲突检查组合逻辑变复杂（要与 24 项全比较，时序压力大）；(c) 正确性风险上升：更多未完成事务意味着更多冲突请求、更多 NACK 重试，以及更大的”响应到达顺序与请求顺序不一致”的处理窗口（例如必须记录每个表项的侦听结果何时有效）。
问题 2. 在 §3.2 的模拟器里，把每缓存 MSHR 从 1 提高到 2、4、8 时，带宽先翻倍后趋于饱和（约 28 GB/s）。请解释两个阶段的瓶颈分别是什么，并说明如果此时把每缓存的 L1 换成两级缓存层次（L1+L2，L2 才连总线），还需要额外解决什么问题？
【答案】 第一阶段（MSHR=1 → 2）：MSHR=1 时每个缓存同时只有一个未完成缺失，其缺失速率被自身的关键路径延迟限制在 1/T_miss ≈ 1/109 条/周期，4 个缓存合计 4/109，带宽约 14.1 GB/s。这是一种延迟受限（latency-bound）状态：总线上明明还有余量，但每个处理器”只有一个未完成的洞”，无法隐藏 DRAM 延迟。MSHR 提到 2 后并发数翻倍，带宽翻倍——这就是 Little 定律的直接体现（吞吐 = 并发数 / 延迟）。 第二阶段（MSHR ≥ 2）：并发数继续增加已无用，因为全局请求表只有 8 项，成为硬上限：8 × 128 B × 3 GHz / 109 = 28.2 GB/s。此时是容量受限（capacity-bound）状态，多余的请求尝试被 NACK 并以 RETRY_DELAY 重试，制造额外延迟却换不来吞吐（模拟器中 NACK 计数显著上升）。要再提升必须扩大请求表或减少每缺失的占用，而不是继续加 MSHR。 换成 L1+L2 层次后需要额外解决：(a) 谁侦听总线——若只让 L2 控制器侦听，L1 里的脏数据对总线不可见，必须维护包含性（inclusion）（L1 ⊆ L2，L2 驱逐时连带失效 L1），或让所有层独立侦听（低效）；(b) 响应延迟变长（L1 缺失要走 L1→L2→总线→L2→L1），使 fetch deadlock 更危险——L1 在等自己请求的响应期间必须仍能服务外来侦听请求；(c) 缓冲死锁：L1↔L2 之间若只有一对队列（每个容量 1），出向请求的响应需要对方队列空间、入向请求的响应需要本地队列空间，形成环——必须把所有事务分类为请求与响应并使用分离的请求/响应队列（响应不产生新事务，因此一定能推进并腾出资源）；(d) 表项/缓冲尺寸要按”总线上最大未完成请求数”配足，否则层次越深越容易死锁——讲义指出这是一种正确但昂贵的解法（slide 57）。
问题 3. 有这样一段”多核计数器”代码：4 个线程各写 count[tid]++，其中 long count[4]。测得时间是从单线程版本的约 100 倍。请解释原因、用讲义中的概念命名它，并给出两种修复方案及其代价；同时说明如果这些计数器被改成”每个线程先累加到私有变量、最后合并”，为什么能得到接近 4× 的加速。
【答案】 原因是伪共享（false sharing），其硬件机制是一致性协议的所有权迁移：long count[4] 共 32 B，全部落在同一条 64 B cache line 内。每次 count[tid]++ 都是读-改-写，要求该 line 处于 M 态；而 M 态在任一时刻至多一个缓存持有（MESI 不变量），因此每个核的每次自增都要发出 BusUpg/BusRdX，把别的核的脏行 flush 出来再失效，line 在核之间反复弹跳（ping-pong）。有效执行被串行化成一条”line 迁移链”：按 §4.3 的模型，Work/Span = C_inc/L_ping ≈ 5/180 ≈ 1/36 < 1，即并行度低于串行版本，因此出现约 100 倍（模型估计约 140 倍）的劣化。这不是数据竞争（各线程访问的是不同内存位置，结果也正确），而是共享一条 line 造成的额外一致性事务。 修复方案一：填充/对齐隔离——把每个计数器放到独立 cache line（struct alignas(64) { volatile long v; char pad[56]; } cnt[4];）。代价是内存占用放大 8 倍、可能降低缓存有效容量与空间局部性，且把”每线程一个计数器”变成硬编码的布局约束（核数变化时要重新布局）。 修复方案二：改变访问模式为分块/线程本地归约——每个线程在自己的私有数组（或栈变量）上累加，最后用一次原子加法或临界区合并到全局计数器。代价是多了一次归约（O(线程数) 的同步），且要求算法允许”部分和”这种分解（不是所有算子都满足，例如非结合/非交换的更新就不行）。 “私有变量 + 最后合并”能得到接近 4× 加速，是因为它把每次操作的通信彻底消除：整个自增循环期间，工作集是本核私有且独占的 cache line（保持在 M 态不迁移），每一步只是本地 ALU/store-to-load 依赖链（C_inc 很小）；只有最后 N 次合并才触碰共享行，事务次数从 2×10⁸ 次降到 4 次。用 Work/Span 说：Work 仍为 2×10⁸ 次自增，Span 变成”单个线程的 5×10⁷ 次本地依赖链 + 一次归约同步”，并行度回到 ≈ 4（线程数），因此理想加速比接近 4×（受最后归约与 Amdahl 中极小串行段限制，实际略低于 4）。这也验证了讲义的总结：并行程序里的”通信”既包括显式消息/锁，也包括你没意识到的一致性流量。
附：本讲一句话地图
目标 (slide 6): 正确 + 高性能 + 低硬件成本
|
+--> Part 1 (slide 19-37): 原子总线 + 单级写回缓存
| 争用: 处理器侧 vs 侦听控制器 (复制 tag / 多端口 tag)
| 信号: Shared / Dirty / Snoop-pending (线与)
| 优化: write-back buffer -> 侦听必须查 buffer
| 正确性: 竞态 / fetch deadlock / livelock / starvation
| 语义: commit (总线上确认) != complete (数据落到行里)
|
+--> Part 2 (slide 38-53): 拆分事务总线 (请求/响应分离)
| 机制: 请求表 + 3-bit tag + 两条总线 + NACK 流控
| 冲突: 读-读可搭车; 读写冲突必须挂起等待
| 队列: 吸收速率波动 (深度 2 即够), 但不增加并行度上限
|
+--> 层次与收尾 (slide 54-60): 包含性 / 缓冲死锁 / 请求-响应队列分离
最终审判: 一句 `int x = 10;` 的 20 个步骤