Lecture 11: Snooping-Based Cache Coherence

目录 · ← l10 · l12 →

Lecture 11: Snooping-Based Cache Coherence

1. 章节标题与概述

Lecture 11: Snooping-Based Cache Coherence（基于监听的缓存一致性）

• 本讲核心问题：多核处理器为了性能把内存内容复制（replicate） 到每个核私有的 cache 里，于是”读地址 X 应当返回任意处理器最后一次写入 X 的值”这个共享地址空间（shared address space） 的直觉语义被打破了——同一个地址在两个核的 cache 里可以同时存在两个不同的值。本讲回答三个问题：(1) 缓存为什么会造成并行系统里访存的困难？(2) 硬件如何提供协调（coordination） 来保住软件对内存的期望——即 coherence（一致性）的精确定义与 snooping（监听式） 硬件协议（write-through invalidation、MSI、MESI、MESIF、MOESI）？(3) 这些硬件抽象何时、以何种形式暴露给软件（false sharing、cache line 大小、GPU 的”不一致”设计）？

• 涉及的主要硬件/软件机制：
  • 硬件侧：cache line（现代 Intel 为 64 B）里的 tag / data / line state / dirty bit；write-back vs write-through、write-allocate vs write-no-allocate；互连（interconnect） 上的广播一致性事务 BusRd / BusRdX / flush（CS149 记作 BusWB）；每个 cache 的 controller（控制器） 既要响应本地 CPU 的 load/store，又要”监听”来自互连的一致性广播；失效型协议（invalidation-based） 的状态机 I/V、MSI、MESI（Illinois Protocol）、MESIF（Intel）、MOESI（AMD Opteron）；更新型协议（update-based） 的 Dragon 协议（BusUpd）；多级层次下的 inclusion（包含性） 与 in L1 bit、modified-but-stale bit；Intel Haswell/Skylake 的 L1–L2–L3 + ring interconnect（L3 亦可充当目录与串行化点）。
  • 软件侧：程序员不能”编程”一致性协议，但可以通过数据布局与访问模式决定它是否成为瓶颈：每个线程私有变量的填充（padding） 到 cache line 边界以消除 false sharing；散射/直方图类不规则写的私有化（privatization）+ 归并（reduction/merge）；volatile、原子操作、CUDA 的 atomicAdd / ld.cg 等绕过或依赖 cache 的语义选择。

• 在并行计算知识体系中的角色：本讲把前两讲的”缓存层次（cache hierarchy）”与”互连网络（interconnection network）”合起来，第一次让多个核在物理上真正共享一份内存；它是下一讲 Directory-Based Cache Coherence（目录式缓存一致性） 的直接动机——snooping 依靠广播，可扩展性受限于”能否把一致性消息广播给所有 cache”，目录方案正是为了消除广播。它同时是后续 内存一致性模型（memory consistency models） 的前置：本讲的 coherence 只管单个地址上的读写顺序，而 consistency 才管不同地址之间的顺序（两者的区别是考试与项目的常见混淆点）。对项目而言，本讲是”为什么加 padding、为什么把共享累加器改成每线程私有、为什么原子操作在热点上会崩”这些优化手段的理论根据。

• 配套材料：
  • lectures/10_cachecoherence.pdf（抽取文本 extracted/10_cachecoherence.txt，共 60 页）：已公开，可在 https://www.cs.cmu.edu/~418/lectures/ 公开下载。讲义首页写的是 “Lecture 10: Snooping-Based Cache Coherence” 与 “CMU 15-418/15-618, Fall 2024”：这是讲义沿用历史学期版本的正常现象（讲次编号与学期字样随年度重排），不是错误。按 Fall 2026 日程表（https://www.cs.cmu.edu/~418/schedule.html），本讲排在 Sep 18，为第 11 讲，标题正是 Snooping-Based Cache Coherence；随后 Sep 21 为 Directory-Based Cache Coherence，Sep 23 为 Snooping-Based Multiprocessor Design。本笔记的全部术语、状态机、示例时序与实测数字均以这份 60 页讲义为准。
  • cs149_supp/cachecoherence.txt（Stanford CS149 Fall 2025, Lecture 14: Cache Coherence，共 45 页，公开）：作为补充视角使用，其中 SWMR（Single-Writer, Multiple-Read）不变量 + Data-Value 不变量、AMAT 公式与 Xeon 5500 访存延迟表、MSI 事务表是 CMU 讲义未展开而对理解本讲极有帮助的部分；引用时均已标注来源为 CS149 补充材料。
  • 讲课录像（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 创建。
  • 本笔记中额外补充的背景（如把讲义数字代入 AMAT、一致性流量下界推导、work-span 分析）均已显式标注为”本笔记推导/本笔记补充”，与讲义原文区分。

2. 核心概念与硬件/软件架构图解

2.1 引子：一次 int x = 1; 在硬件里发生了什么（讲义 slide 3–4）

• 定义与目的：一致性协议的讨论必须建立在 cache 的物理组织上。一条 cache line（现代 Intel 为 64 B）在硬件里长这样：

                      一条 cache line (64 B) 的元数据与数据
   +-----------+----------------+------------+------------------------------+
   |   Tag     |   Line state   | Dirty bit  |   Data (64 bytes)            |
   | (地址高位) | (一致性协议用)  | (是否脏)    |  byte 0 ... byte 63          |
   +-----------+----------------+------------+------------------------------+
   - Tag:          用于判断命中/缺失
   - Line state:   一致性协议用的状态位 (I / S / E / M ...)，本讲的主角
   - Dirty bit:    该行是否比内存新 (write-back cache 才有意义)

执行 int x = 1;（假设 x 在内存地址 0x12345604，未被分配在寄存器里）时，一个 write-allocate + write-back 的 cache 在写缺失（write miss） 上做五件事（讲义 slide 4）：(1) 处理器写一个不在 cache 里的地址；(2) cache 选一个位置安置该行，若该位置上有脏行（dirty line），先把脏行写回内存（替换/write-back）；(3) 从内存把整行取进来（allocate line）；(4) 只更新这一行里的 32 bit；(5) 把该行标记为 dirty。

• 直观解释（”它是什么？”）：把内存想成图书馆的藏书，cache 是你桌上的复印件。write-back 就像”我在复印件上改，暂时不告诉图书馆”；write-through 则是”每改一个字都跑一趟图书馆”。write-allocate 是”要在这页上改字，得先把整页复印过来”；write-no-allocate 是”只在图书馆原书上改，不复印”（讲义 slide 21 的 write-through 状态机里就假设了 write-no-allocate 以简化讨论）。

• 性能特征：write-through 的代价是每次写都要占用内存/互连带宽（讲义 slide 24：every write operation goes out to memory → very high bandwidth requirements）；write-back 能吸收绝大多数写流量（连续的写命中都在 cache 内完成），但代价是”数据的权威副本可能在某个 cache 里而不在内存里”，这正是需要一致性协议的原因。

2.2 一致性问题：四核共享内存里同一个 X 有两个值（讲义 slide 5–9）

• 定义与目的：四个处理器、四条私有 cache、一条互连、一份内存——这是讲义 slide 5 的基线系统。对内存的合理期望是：读地址 X 应当返回任意处理器最后一次写入 X 的值。而 cache 的复制行为会破坏这个期望：下表复现讲义 slide 6 的情景（初始 mem[X] = 0，write-back cache）：

• 直观解释（”它是什么？”）：会议室里有 4 个人，每人手里都有一份会议记录的复印件。P1 在自己的复印件上把第 3 行改成”1”，但别人手里的复印件不会自动跟着变；更糟的是记录员（内存）手里那份也可能是旧的。于是”读到的应该是最新值”这个直觉，在”复印件 + 延迟同步”的世界里根本不成立。

• 这不是互斥问题（讲义 slide 7，重点）：能不能靠加锁解决？不能。原因有三层：(1) 这个问题不是由”两个线程同时访问导致数据竞争”产生的，而完全是硬件为了性能复制数据这个实现细节造成的；(2) 本例中 P1 与 P2 的访问在时间上并没有重叠（没有竞争），加锁不会改变”P2 读到旧副本”这个事实；(3) 如果一致性只保证”有锁保护的临界区内部”正确，那么任何在临界区之外共享的数据本身（例如一个 flag、一个 work queue 的指针）都会出错。因此一致性必须由硬件在每一次 load/store 上隐式保证。

• 内存一致性问题的正式表述（讲义 slide 8）：coherence 问题之所以存在，是因为单个共享地址空间这个抽象，并不是由单个存储单元实现的——存储被分散在 main memory 与各处理器本地 cache 中。

• 现实中的 cache 层次（讲义 slide 9，Intel Haswell 2013）：

• 性能特征（关键操作与量化后果）：把 L1 的”最多 10 个未完成缺失”代入 Little’s Law，可以估出单核能压给内存子系统的带宽上限：10 × 64 B / (4–6 cycle miss 到 L2 的往返 ≈ 12 cycle) ≈ 640 B / 12 cycle ≈ 53 B/cycle，在 3 GHz 上约 160 GB/s 的 L2 侧需求；若缺失一路穿透到 DRAM（~120 cycles），同样的 640 B 在途量只有 640/120 × 3 GHz ≈ 16 GB/s。这说明：一致性协议增加的每次 miss 延迟（L3 hit 但数据在别的核的 cache 里，见 CS149 数据 65–75 cycles，而本地 DRAM 才 ~120 cycles）会直接乘以”在途请求数受限”这件事，把可扩展的有效带宽按比例拉低。

2.3 “last” 的歧义与 coherence 的精确定义（讲义 slide 10–15）

• 定义与目的：讲义先指出，在单处理器上提供”读到最新值”很轻松，因为写者通常只有一个：CPU 本身（例外是 DMA 的设备 I/O——所以单 CPU 系统里也有一致性问题，常用手段是：驱动用 uncached store、OS 把共享缓冲区所在页标记为 not-cachable、或 I/O 完成时显式 flush 页；由于 DMA 相比 CPU 的 load/store 极少发生，这些很重的软件方案可以接受）。到了多核，”last”这个词本身就有歧义：两个处理器同时写怎么办？P1 的写紧接着 P2 的读、以致于”写发生过”这件事在物理上不可能及时传到 P2，又怎么办？ 在顺序程序里，”last”由程序顺序（program order） 决定，而不是由时间决定。

• 一致性的形式化定义（讲义 slide 13）：一个存储系统是 coherent 的，当且仅当：并行程序的执行结果满足——对每一个内存地址，存在一个所有处理器对该地址操作（按所有处理器执行的）的假想串行顺序（hypothetical serial order），它与执行结果一致，并且：
  1. 任何一个处理器发出的内存操作，按该处理器发出的顺序出现（program order）；
  2. 读返回的值，是由该串行顺序中”最后一次写”写入的值。
• 同一件事的另一种说法（讲义 slide 14，考试最常考的三条）：
  1. P 对 X 的读，若在 P 自己对 X 的写之后（中间无其他处理器写 X），必须返回 P 写的值 → 遵守 program order（单处理器的期望）。
  2. P1 对 X 的读，若在 P2 对 X 的写之后、且两者”时间上充分分离”（中间无其他写 X），必须返回 P2 写的值 → write propagation（写传播）。注意：定义并没有规定传播得多快，只要求最终传到。
  3. 对同一地址的写被串行化（write serialization）：任意两个处理器对 X 的两次写，被所有处理器观察到的顺序相同。

• write serialization 的反例（讲义 slide 15）：P1 先写 X←a，随后 P2 写 X←b。若 P3 观察到 a 然后 b，而 P4 观察到 b 然后 a，则不存在一条与两边观察都相符的全局时间线——违反条件 3。这正是”必须在互连上给写定序”的直接动机。

• 直观解释（”它是什么？”）：coherence 就像微信群里的消息顺序。它不要求每个人同时看到消息（write propagation 不规定时限），但要求：(a) 你自己发的消息，你自己看到的顺序必须和发送顺序一致；(b) 对同一条消息，所有人群里看到的先后关系必须一致（不能有人说”先看到 b 再看到 a”，有人说”先 a 后 b”）。这就是”每个地址存在一个所有核都认可的串行顺序”。

• 等价的不变量表述（CS149 补充材料 slide 17：SWMR + Data-Value）：对任意地址 x、任意时间段（epoch）：

  地址 x 的"纪元 (epoch)"时间线:
  |<-- Read-Write: P0 -->|<-- Read-Only: P0,P1,P2 -->|<-- Read-Write: P1 -->|<-- Read-Only: P0,P1 -->|
         (只有 P0 可写)         (多个核, 只读)            (只有 P1 可写)          (多个核, 只读)

  不变量 1  SWMR (Single-Writer, Multiple-Read):
      任一时刻, 要么是"读写纪元"(只有一个核可以写, 它也可以读),
      要么是"只读纪元"(任意多个核只读)。
      绝不允许: 两个写者; 或者有写者的同时还有别处的读者。
  不变量 2  Data-Value (write serialization):
      一个只读纪元开始时的值 = 上一个读写纪元结束时写下的值。

这两条不变量与讲义 slide 14 的三条条件是同一枚硬币的两面：MSI/MESI 中”M 态唯一”就是 SWMR，”flush/写回后再降级”就是 Data-Value。

2.4 实现路线总览：软件、共享 cache、snooping、directory（讲义 slide 16–19）

• 定义与目的：讲义把实现手段分成四类，本讲只讲第三类，第四类是下一讲：

• 直观解释（”它是什么？”）：
  • 共享 cache 像黑板：只有一块，谁写谁都看得见——一致性免费，但所有人都得挤到黑板前面。
  • Snooping 像村里的广播喇叭：任何人要改公共信息就喊一嗓子，全村都听见，各自把自己的小本子改掉。人少时最省事，人多时全村天天被噪音淹没。
  • Directory 像通讯录 + 电话：登记簿上写着”这条信息谁能看到”，改的时候只打电话给相关的人，不打扰全村。

2.5 Snooping 的硬件结构：cache controller “两头受气”（讲义 slide 18–19）

• 定义与目的：snooping 的核心思想是——凡是可能影响一致性的 cache 操作，cache controller 就把通知广播给系统里所有处理器（更准确地说：所有 cache controller）；各个 cache controller 监听（snoop） 内存操作，并据此维护一致性。这带来一个关键的架构变化：

                        +--------------------------------------------------+
                        |             互连 (interconnect / bus)             |
                        |  所有一致性事务在这里广播给每一个 cache controller |
                        +--+-----------+-------------+-----------+---------+
                           |           |             |           |
        +------------------+--+  +-----+-----+  +----+------+  +-+--------------+
        |  Processor  P0     |  |    P1     |  |    P2     |  |      P3        |
        |   +-----------+    |  |           |  |           |  |                |
        |   | Cache ctrl|    |  |    ...    |  |    ...    |  |      ...       |
        |   |  (snoops) |    |  |           |  |           |  |                |
        |   +-----+-----+    |  |           |  |           |  |                |
        |         | 私有副本  |  |           |  |           |  |                |
        |   L1 / L2 cache    |  |           |  |           |  |                |
        +--------------------+  +-----------+  +-----------+  +----------------+
              ^        |
              |        | ② 监听: 收到 BusRd / BusRdX 后, 本 cache 必须
              |        |    失效副本 / 回写脏行 / 直接提供数据
              |        |
      ① LD/ST 来自本地 CPU (cache controller 的另一端)
                                        |
                                 +------+------+
                                 |   Memory    |
                                 +-------------+

• 必须理解的一句话（讲义 slide 20）：上面这套逻辑由每个处理器的 cache controller 独立执行，输入只有两个来源——本地 CPU 的 load/store，和互连上收到的一致性消息。只要所有 cache controller 都按同一套协议办事，一致性就自动成立：cache 之间是”合作（cooperate）”关系，没有任何全局控制器。

• 直观解释（”它是什么？”）：cache controller 像一个双语接线员：一边听自家老板（本地 CPU）要数据，一边听广播里别人在喊什么，然后决定”把副本撕掉”还是”把我手里最新的版本交出去”。它的工作从”只服务一个 CPU”变成”服务 CPU + 服务整个系统”，这是 snooping 硬件复杂度的全部来源。

2.6 最简实现：write-through + 失效广播 + I/V 状态机（讲义 slide 20–23）

• 定义与目的：讲义用一个刻意简化的协议建立直觉：假设 (1) cache 是 write-through 的；(2) 一致性粒度是 cache line。协议只有一条规则：写的时候，cache controller 广播一条失效（invalidation）消息；于是其他核的副本被作废，它们下次读就会 miss，而由于 write-through，内存里已经是最新值。

• 状态机图解（讲义 slide 21–22）。记法：A / B 表示”若 cache controller 观察到事件 A，则执行动作 B”；本地 CPU 触发的事件是 PrRd/PrWr，来自远程 cache 的总线事务是 BusRd/BusWr（BusWr 也称 BusRdX）。** 表示这里假设 write-no-allocate：

                      +---------------------+   PrRd / BusRd   +---------------------+
                      |                     |=================>|                     |
                      |    I (Invalid)      |                  |     V (Valid)       |
                      |                     |<=================|                     |
                      +---------------------+   BusWr / --     +---------------------+
                         ^            |                          |             ^
                         |            |                          |             |
                         |            |  PrWr / BusWr **         |             |
                         |            |  (写穿 + 广播失效,       |             |
                         |            |   自己也不分配该行)       |             |
                         |            +--------------------------+             |
                         |                                                      |
                         |                        V 的两个自环 (自迁移, 状态不变): |
                         |                          PrRd / --   (本地读命中)
                         |                          PrWr / BusWr(写穿 + 广播失效)
                         |                                                      |
                         +------------------------------------------------------+
                                     I 的自环: BusWr / -- (别人写, 我本来就无效)

  两条远程事务的语义:
    BusRd: 别的处理器打算读这一行   -> 我不需要做任何事(write-through 使内存最新)
    BusWr: 别的处理器打算写这一行   -> 我若有副本必须作废 (V -> I)

对应的状态迁移表：

• 互连必须提供的两条保证（讲义 slide 23）：(1) 所有写事务对所有 cache controller 可见；(2) 所有写事务以相同的顺序被所有 cache controller 看到。若缺少 (2)，就会构造出 2.3 节 slide 15 的”P3 看到 a→b，P4 看到 b→a”的反例。讲义同时列出三条简化假设：互连与内存事务原子（atomic）；处理器等前一条内存操作完成再发下一条；失效在收到广播时立即生效。真实机器上这三条都要靠更多机制（MSHR、非阻塞 cache、乱序核的 memory ordering）来近似，这是”下一个讲（Snooping-Based Multiprocessor Design）”的主题。

• 性能特征：write-through 协议的优点是简单到可以手推；代价是每次写都占用内存带宽（讲义 slide 24：very high bandwidth requirements）。举例：12 核各以 3 GHz 每 5 个 cycle 做一次写（每 cycle 0.6 次写），则写流量 = 12 × 0.6 × 3e9 × 8 B ≈ 173 GB/s（若每写只传 8 B 数据）或按整行粒度更糟——远超单条 DRAM 通道的能力（几十 GB/s 量级）。这就是必须换 write-back 的量化理由。

2.7 write-back + 独占所有权：MSI 协议（讲义 slide 25–32）

• 定义与目的：换成 write-back 后，脏行（dirty）意味着独占所有权（exclusive ownership）：(a) 该 cache 是唯一持有有效副本的（所以可以安全地写）；(b) 它是该行的 owner——别的核来取这行时，必须由它提供数据，否则从内存拿到的会是陈旧数据（讲义 slide 26）。协议要做两件事：保证写者拿到独占访问，以及在 miss 时定位该行最新的副本。

• MSI 的三态与两事件源（讲义 slide 28）：
  • 状态：I（Invalid，含义与单处理器 cache 的 invalid 相同）、S（Shared，行在一个或多个 cache 中有效）、M（Modified，行恰好在一个 cache 中有效，又称 dirty / exclusive）。
  • 本地 CPU：PrRd、PrWr。
  • 互连事务：BusRd（取副本、无修改意图）、BusRdX（取副本并要修改 = read-exclusive）、flush（把脏行写出；CS149 记作 BusWB）。
• MSI 状态机图解（讲义 slide 29）：

          PrRd / BusRd                     PrWr / BusRdX
          (读缺失, 取副本)                  (升级 upgrade: 即使已有 S 副本也要发)
   +----------------------+          +----------------------+
   |                      v          |                      v
+-----+               +-----+    +-----+
|  I  |               |  S  |    |  M  |
|Inval|               |Share|    |Modif|
+-----+               +-----+    +-----+
   ^   |                 |   ^      |   ^
   |   |  PrWr/BusRdX    |   |      |   |
   |   +---------------->|   |      |   |
   |     (写缺失)         |   |      |   |
   |                      |   |      |   |
   |    BusRdX / --       |   |      |   |
   +----------------------+   |      |   |
       (别人要写: S -> I)      |      |   |
                              |      |   |
             PrRd / --  ------+      |   |  PrRd / --   (M 态本地读: 无总线事务)
             BusRd / --  ------------+   |  PrWr / --   (M 态本地写: 无总线事务)
             (S 自环, 无动作)             |
                                         |
             BusRd  / flush  ------------+---> S   (别人要读: 回写脏数据并降级为 S)
             BusRdX / flush  -----------------> I   (别人要写: 回写脏数据并失效)

   关键点: 唯一的"进入 M"的路径是 PrWr, 且若当前不是 M 就必须发 BusRdX。
           唯一的"零总线事务的写"是"已经处于 M 态的写"。

• MSI 状态迁移表：

• PrWr 命中 S 态为什么还要发 BusRdX（讲义 slide 32 的原问）：因为”有效（valid）”不等于”独占（exclusive）”。别的 cache 里还有副本，若不通知它们就本地改写，就会出现两个 cache 持有同一行的不同值（违反 SWMR），而且没有任何机制能知道谁该为未来的读提供正确数据。所以进入 M 态必须经过互连；BusRdX 的作用就是告诉其他 cache”我要写了，你们不能再读了”。

• MSI 逐条执行示例（讲义 slide 30–31 的 12 步序列）：X、Y 初值均为 0。下表是本笔记按 MSI 规则逐步推演的结果（列格式 状态/值，I 表示无效）：

量化观察：12 条内存指令里有 10 次互连事务（其中 4 次带 flush，即 4 次向请求者提供数据的 cache-to-cache 传输），只有第 4、6 步是”纯本地命中、零事务”。可见在这种交替读写的访问模式下，“M 态吸收写”带来的节省几乎被 BusRdX 抵消——这正是 MESI 要引入 E 态的原因。（表中无效行写 I、不再标数值；3.2 节的模拟器输出会保留该行最后一次写入的值，例如 I/2。）

• MSI 为什么满足 coherence（讲义 slide 33 的论证，务必能复述）：
  • write propagation：由 BusRdX 上的失效 + 之后别人 BusRd/BusRdX 时 M 态的 flush 共同保证。
  • write serialization：出现在互连上的写（BusRdX）由互连的出现顺序定序；出现在互连上的读（BusRd）同样由互连定序；不出现在互连上的写（对已处于 M 的行连续写）必定夹在两次针对该行的互连事务之间，而且这些写全部由同一个处理器发出（它自己当然按顺序看到），其他处理器只有在互连事务发生之后才被告知——所以所有处理器看到的顺序一致。

2.8 MESI：用 E 态消掉一次事务（讲义 slide 33–35）

• 定义与目的：MSI 的低效在于——即使程序完全没有共享（一个核读它自己的数据、然后写它自己的数据），”先读后写”这个最常见的序列也要两次互连事务（BusRd 让它进 S，BusRdX 再把它升到 M）。MESI 增加第四个状态 E（Exclusive clean，独占且干净）：该行未被修改，但只有这一个 cache 有副本。它把独占性（exclusivity）与所有权（ownership/dirty）解耦——因为不脏，内存里的副本仍是有效数据。关键收益：E→M 的升级不需要任何互连事务。

• 直观解释（”它是什么？”）：你去图书馆借书，发现全馆只有这一本，而且没人预约。既然只有你一个人看，你就可以直接在书上做批注（E→M）而不必通知图书馆——因为没人会因为你改了书而读到错误内容。但如果别人也要看（BusRd），你的独占就被打破，降级为”共享”（S）。（讲义的原话：MESI, not Messi!）

• MESI 状态机图解（讲义 slide 35）：

                     PrRd / BusRd                     PrWr / --
              (无其他 cache 有该行, 响应者"断言 shared"失败)
    +--------+  -------------------------->  +----------------+
    |   I    |                               |       E        |
    | Invalid|                               |  Exclusive     |
    +--------+                               |  (干净! 独占)   |
        ^  |                                 +----------------+
        |  |                                    |          |
        |  |  PrWr / BusRdX                     |          | PrRd / BusRd
        |  |  (写缺失)                           |          | (别人来读: E -> S)
        |  |                                    v          v
        |  |        PrWr / BusRdX          +----------------+
        |  +------------------------------>|       S        |
        |        (S->M: 仍需总线"升级")     |    Shared      |
        |                                  +----------------+
        |                                     |          ^
        |            BusRdX / -- (or flush)   |          | PrRd / --
        +-------------------------------------+          | BusRd / --
                (S->I: 别人要写)                          | (S 自环)
                                                       |
    +--------+   PrRd / -- (本地读命中)                 |
    |   M    |<-----------------------------------------+
    |Modified|   PrWr / -- (M 自环: 零总线事务)
    +--------+
        |
        |  BusRd  / flush  ---> S    (别人要读: 回写并降级)
        |  BusRdX / flush  ---> I    (别人要写: 回写并失效)
        |
        +-- 注意 E -> M 这条边 (PrWr / --) 是 MESI 相对 MSI 唯一的新增"捷径":
            没有它, 就得走 E(or S) --BusRdX--> M, 白白多一次互连事务。

• MESI 状态迁移表：

• MESI 逐条执行示例（讲义 slide 36–37）：同一批动作换用 MESI：

量化观察（本笔记推导）：这 9 步里 MESI 用 7 次互连事务，而 MSI 需要 8 次——差的那一次正好是第 8 步”对一个私有数据先读后写”。更一般地：若负载中”读自己私有的数据然后写它”占主导（例如每个线程更新自己的局部累加器），MSI 每次这样的”读-改”要 2 次事务，MESI 只要 1 次，一致性互连流量减半。

• 底层实现选择（讲义 slide 38）：miss 时数据由谁提供？内存，还是另一个 cache（cache-to-cache transfer）？若由 cache 提供，该由哪一个提供？cache-to-cache 增加了复杂度，但同时降低访问延迟和内存带宽需求，因此被普遍采用。这正是 2.9 节 MESIF/MOESI 要解决的”选谁”问题。

2.9 MESIF 与 MOESI：五态协议的两种思路（讲义 slide 39）

• 直观解释（”它是什么？”）：MESIF 的 F 像”指定发言人“：一群人都有复印件，但对外发言的只有一个，避免所有人同时抢话筒。MOESI 的 O 像”保管人“：原件被锁在我抽屉里，别人要复印件来找我，我不必先把原件登记回图书馆（省一次写回）。

2.10 现实：多级 cache 层次与 inclusion（讲义 slide 40–44）

• 定义与目的：真实机器有多级 cache，而”在 L1 里被改过的数据”未必对监听互连的 L2 controller 可见。讲义给出两条出路：(1) 所有 cache 都独立监听互连（低效，L1 也要处理全部一致性流量）；(2) 维持 inclusion（包含性）：所有”更靠近处理器”的 cache 里的行，也存在于更远的 cache 里（L1 ⊆ L2）。这样只有 L2 需要监听互连，因为对 L1 有意义的事务必然也对 L2 有意义。

        Core 0                        Core 1                     Core 2 ... 
   +---------------+            +---------------+            +---------------+
   | L1D 32KB      |            | L1D 32KB      |            |      ...      |
   | 8-way, WB     |            |               |            |               |
   +-------+-------+            +-------+-------+            +-------+-------+
           |                            |                            |
   +-------+-------+            +-------+-------+            +-------+-------+
   | L2 256KB      |            | L2 256KB      |            |      ...      |
   | 每条 line 另带: |            |               |            |               |
   |  "in L1" 位    |  <-- 该行是否也在 L1 中                     |               |
   |  "modified-   |  <-- L2 副本是否已陈旧(L1 才是最新)          |               |
   |   but-stale"位|            |                            |               |
   +-------+-------+            +-------+-------+            +-------+-------+
           |                            |                            |
   +-------+----------------------------+----------------------------+--------+
   |      共享 L3 (8MB, inclusive, 每核一个 bank, ring 互连)                  |
   |      (在 Intel Core i7 上, L3 同时充当"全芯片的目录与串行化点")           |
   +----------------------------------+-------------------------------------+
                                      |
                             +--------+--------+
                             |   Memory (DDR)  |
                             +-----------------+
   只有 L2 监听互连上的 BusRd/BusRdX; L1 不必监听, 因为 inclusion 保证
   "L1 里有的行, L2 里必然也有"。

• inclusion 不会自动成立（讲义 slide 41，易错点）：设 L2 是 L1 的两倍大，二者行大小相同、都是 2-way、都用 LRU，且 A、B、C 映射到 L1 的同一个 set。访问序列：A（L1+L2 miss）→ B（L1+L2 miss）→ A（反复命中 L1）→ C（L1 与 L2 miss）。由于 L1 与 L2 的访问历史不同（A 被反复命中只更新了 L1 的 LRU 信息），两者可能选择逐出不同的行，于是 A 可能留在 L1 却已被 L2 逐出——inclusion 被破坏。真实机器必须靠显式的包含策略（如 L2 逐出时反向失效 L1 中的对应行）来维持它。

• 维持 inclusion 需要的两个额外状态位（讲义 slide 42–43）：
  1. in L1 bit：L2 的每条 line 记录”它是否也在 L1 里”。当该行因一致性流量（如 BusRdX）在 L2 中被失效时，必须顺着这个位把失效传播到 L1。
  2. modified-but-stale bit：若 L1 是 write-back 且发生 L1 写命中，那么该行在 L1 里是新的，而 L2 的副本在一致性协议里仍显示为 Modified，但数据是陈旧的。当协议要求 flush 这一行（例如别的核要读 X）时，L2 必须先向 L1 索取真正的数据再 flush。这个”L2 说自己是 M 但其实数据在 L1”的状态就是 modified-but-stale。

• 直观解释（”它是什么？”）：inclusion 像大箱子套小箱子：小箱子里的东西必须在大箱子里（否则”只看大箱子”就会漏掉）。modified-but-stale 位像图书馆登记簿上写着”这本书被张三借走了，锁在他抽屉里”：真迹在抽屉（L1），登记簿（L2）上只有一条索引，要交书时必须去抽屉取。

• 硬件影响与现状（讲义 slide 44–45）：每个 cache 都必须监听并响应互连上广播的全部一致性流量，这带来了额外互连流量，在高核数下会显著。现状是：几乎所有现代多核 CPU 都实现缓存一致性；而离散 GPU 至今不实现缓存一致性——讲义判断其理由是：对图形与科学计算应用而言，一致性开销”不值得”（NVIDIA GPU 提供单一共享 L2 + 原子内存操作作为替代）；不过最新的 Intel 集成 GPU 已经实现缓存一致性。

2.11 GPU 的”不一致”设计：以 CUDA 为例（讲义 slide 45）

   +--------+   +--------+   +--------+   +--------+
   | SMM 0  |   | SMM 1  |   | SMM 2  |   | SMM 3  |   ...   (Streaming Multiprocessors)
   | L1 $   |   | L1 $   |   | L1 $   |   | L1 $   |   L1 是 incoherent 的, 每 SMM 私有
   +---+----+   +---+----+   +---+----+   +---+----+
       |            |            |            |
       +------------+------------+------------+
                    |
          +---------+----------+
          |  统一共享 L2 cache  |  <-- 全芯片"事实来源": 原子操作在 L2 上完成
          +---------+----------+
                    |
          +---------+----------+
          |  DRAM (device mem) |
          +--------------------+

   软件必须显式对付"L1 可能陈旧"这件事:
     * atomicAdd(&x, 1)     -> 绕过 L1, 在 L2 中对一行内容做原子的读-改-写
     * volatile / ld.cg     -> 编译器生成绕过 L1 的 LD 指令 (PTX 的 ld.cg)
     * L1 默认对 L2 是 write-through 的
     * 驱动在两个 kernel 之间清空 L1 -> 保证前一个 kernel 的写在下一个 kernel 可见

• 为什么驱动必须清 L1（讲义 slide 45 的反例）：kernel 1 里 SMM 0 读 x（x 进 L1），SMM 1 写 x（新值只到 L2）；进入 kernel 2，SMM 0 再读 x 就命中陈旧的 L1 副本。因此 NVIDIA 驱动在两次 kernel 启动之间清 L1。这也解释了 CUDA 编程里”kernel 边界是天然的同步与可见性边界”这一惯例的硬件根源。想深入可查 NVIDIA PTX 手册的 “Cache Operators”（讲义引用的是 Parallel Thread Execution ISA Version 4.1 的 8.7.6.1 节）。

• 性能特征：GPU 的做法是把一致性成本从硬件移到软件约定上：L1 与 L2 之间靠 write-through + kernel 边界清空 + 显式的 ld.cg/原子操作来保证可见性。收益是不必为几百个并发 warp 的每条 L1 访问维护协议状态；代价是程序员必须自己避免”跨线程用 L1 缓存共享数据”的写法。

2.12 程序员视角之一：false sharing 与 artifactual communication（讲义 slide 47–50）

• 定义与目的：false sharing（伪共享） 指两个处理器写不同的地址，但这两个地址落在同一条 cache line 里。由于一致性的粒度是 cache line，这条行会在写者的 cache 之间来回弹跳（ping-pong），产生大量协议引起的一致性通信——这完全没有真实的通信需求（no inherent communication），完全是 artifactual communication（人为/附带通信）。

  时间 --->

   P0: [ M X ][写][写][写] |  I   .   .   .   .   .  |  [ S X ](取到新值)  .   .   |
   P1: [  I  ][BusRdX 抢]  |  [ M X ][写][写][写]    |  I   .   .   .   .   .  |   ...
   互连:        ^^^^^^^^                     ^^^^^^^^
               BusRdX + flush               BusRdX + flush
               (独占权转移一次 = 一次完整的 cache line 传输 + 一次写回)

   "弹跳"的代价: 每次转移至少是 一次 cache-to-cache 传输的延迟
   (CS149 数据: L3 命中但行被别的核以 Modified 持有 ~75 cycles,
    而未共享的 L3 命中只要 ~40 cycles)

• 讲义给出的代码（slide 47–48）：

/* 讲义 slide 47 原文片段: NUM_THREADS 与 CACHE_LINE_SIZE 是讲义中未展开的宏;
   完整可运行版本见 3.1 节的 false_sharing.c */
/* (A) 有问题的写法: 每线程一个计数器, 但彼此紧挨着 */
int myPerThreadCounter[NUM_THREADS];      /* 12 个 int 挤在同一/相邻的 64B 行 */

/* (B) 修正: 每个计数器独占一条 cache line (C++ 里也可写 alignas(64)) */
struct PerThreadState {
    int myPerThreadCounter;
    char padding[CACHE_LINE_SIZE - sizeof(int)];
};
PerThreadState myPerThreadCounter[NUM_THREADS];

讲义 slide 48 的实测（12 线程 / 12 核系统，每线程用 volatile int* 反复自增自己的计数器）：未填充 5.1 秒 vs 填充后 2.1 秒。CS149 补充材料的同类实验（8 线程 / 4 核）是 14.2 秒 vs 4.7 秒。

• 一个必须澄清的误区（本笔记推导）：很多人以为”5.1 → 2.1 只有 2.4 倍，所以 false sharing 没那么可怕”。这个推论是错的。填充后的版本之所以也要 2.1 秒，是因为它撞上了另一个瓶颈：volatile 强制每次自增都真的做一次 load+store，形成一条串行依赖链（每轮约十几个 cycle），并且只能靠单线程的 ILP 摊薄。一致性流量的差异要大得多：设每线程做 MANY 次自增，则
  • 填充版的互连流量 = NUM_THREADS × 64 B（只有义务性冷缺失，例如 12 × 64 B = 768 B，一次运行内不再增长）；
  • 未填充版最坏情况的互连流量 = NUM_THREADS × MANY × 64 B（每次自增都要把该行搬到写者手里，还可能附带一次 flush）。 两者相差 NUM_THREADS × MANY / NUM_THREADS …= MANY 倍——当 MANY = 10^7 时是 10^7 倍的流量差，只是墙钟时间被别的瓶颈掩盖了。所以判断 false sharing 的危害要看流量/能耗/可扩展性，而不只是看一次实验的墙钟比值。讲义 slide 51 的仿真结论也正是这个方向：false sharing 带来的失效率随 cache line 增大而升高，且随数组规模增大而相对下降（因为”每个核分到的连续区间”变长，落在同一条边界行上的概率相对降低）。
• 一行式修复（附带的实用建议）：C++11/17 里可以直接用 alignas(64) 让编译器替你填充；OpenMP 里可以用 #pragma omp parallel for schedule(static, chunk) 让每个线程分到至少一整行的元素，或用 reduction 让编译器生成私有副本。

2.13 程序员视角之二：并行基数排序里的伪共享（讲义 slide 51）

• 定义与目的：讲义用一个真实算法收尾——b 位数的并行基数排序（parallel radix sort）：每一轮按 r 位（例：radix 2^4 = 16，即有 16 个 bin）排序，串行循环 ceil(b/r) 轮；每轮内每个处理器并行地：(1) 按 r 位值对本地元素排序；(2) 统计落入各 bin 的元素个数；(3) 把各处理器的计数汇总（aggregate）以计算每个 bin 的起始位置；(4) 把元素写到各自的最终位置。

  输入数组:  N 个 b 位数, 分成 P 段, 每段归一个处理器 (P0..P3)
  +-----------+-----------+-----------+-----------+
  |   P0 段   |   P1 段   |   P2 段   |   P3 段   |
  +-----------+-----------+-----------+-----------+
        |            |           |           |
        |  第 k 轮: 只看第 k 组 r 位
        v            v           v           v
   [按 r 位排序并统计 (2^r 个 bin)]  x4   <-- 局部直方图, 各处理器私有
        |            |           |           |
        +------------+-----------+-----------+
                     |
                     v  汇总 bin 计数 -> 计算每个 bin 的全局起始偏移 (Prefix Sum)
                     |
        +------------+-----------+-----------+--------------+
        |  散射 (scatter): 把每个元素写到它的最终位置         |
        +--------------------------------------------------+
        因为同一轮里不同处理器写目标数组的相邻区域,
        散射阶段天然产生大量 false sharing
        (数组越大, 每个处理器写到的连续区间越长, 相对影响越小)

• 直观解释（”它是什么？”）：基数排序的散射阶段像全班同学按学号重排座位：每个人的目标座位由别人的统计结果决定，而相邻学号的人可能被分到”同一排的相邻座位”（同一 cache line），于是不同处理器为了写相邻的 4 字节，反复争夺同一条行。

• 性能特征（讲义 slide 51 的仿真图）：把失效率分解成 Cold（义务性）/ Capacity-Conflict（容量与冲突）/ True sharing（真共享）/ False sharing（伪共享）/ Upgrade（升级） 五类可以看出：line 越小，false sharing 越少但 cold miss 越多；line 越大，false sharing 越明显。基数排序在 line 小于 64 B 时 false sharing 影响较小、在 64–256 B 时显著上升；而 Barnes-Hut、Radiosity、Ocean Sim 这类具有空间局部性的应用则更受益于较大的 line（空间局部性带来的 cold/true sharing 减少）。这解释了为什么 64 B 成为现代处理器的平衡点。

2.14 更新型协议：Dragon 与 invalidate vs update 的取舍（讲义 slide 55–60，Bonus 材料）

• 定义与目的：前面所有协议都是失效型（invalidation-based）：要写一行，cache 必须取得独占访问（让别人的副本失效）。它的两个已知代价：失效后要用整行重新载入（消耗带宽），以及对 false sharing 极不友好。更新型（update-based） 协议走另一条路：写的时候把新值广播出去，让其他副本就地更新（BusUpd）而不是作废。

• Dragon 写回更新协议的四个状态（讲义 slide 56）：注意它没有 Invalid 状态（可以理解为”行在被第一次载入之前是无效的”）：

  • E（Exclusive-clean）：只有一个 cache 有此行，内存是最新的。
  • SC（Shared-clean）：多个 cache 可能有此行的干净副本，内存可能或可能不是最新的（若无人处于 SM，内存就是最新的）。
  • SM（Shared-modified）：多个 cache 可能有此行，内存不是最新的；但只有一个 cache 处于 SM——它是该行的 owner，被替换时必须更新内存。
  • M（Modified）：只有一个 cache 有此行且是脏的，内存不是最新的；该 cache 是 owner，替换时必须更新内存。
  • 处理器事件：PrRd / PrWr / PrRdMiss / PrWrMiss；总线事务：BusRd、flush（提供整行）、BusUpd（总线更新：只广播被修改的数据）。

   Dragon 的状态迁移 (要点: 没有 I 态, 写时"广播新值"而不是"失效")

                  PrRdMiss/BusRd(无其他共享者)
        +-------------------------------+         PrWr/BusUpd(无共享者)
        |                               v                    +-----------------+
     +-----+                      +------+                   |                 |
     |  E  |                      |  M   |<------------------+                 |
     +-----+                      +------+                                    |
        |                            | ^                                      |
        |  PrWr/BusUpd(有共享者)       | | PrRd/BusRd(有共享者)                  |
        v                            | |                                      |
     +------+  PrWr/BusUpd(有共享者) +------+                                 |
     |  SC  |<----------------------|  SM  |<--------------------------------+
     +------+   PrRd/BusRd(有共享者) +------+
        |  ^                            |
        |  +--- BusUpd / 就地更新本地行 ---+
        |
        +--- 被替换(replacement)时: 若为 SM 或 M, 必须 flush 到内存

• 失效 vs 更新，谁更好（讲义 slide 58–60）：
  • 直觉上，若其他处理器在写发生之后还会继续读这份数据，更新看起来更优（数据已经在它们的 cache 里，无需再取）；
  • 但更新在两种情形下纯粹是开销：(a) 数据写完后再也没人读；(b) 程序在下一次读之前做了很多次写（每次写都要广播一次 BusUpd）。
  • 讲义引用的仿真评估（1 MB cache / 64 B line，四个应用 Ray Trace、Radix Sort、LU、Ocean Sim）显示：更新协议在 false sharing 类的失效上通常更低，但在 traffic（升级/更新速率） 上可能显著更高（”多次写而无人读”造成的高流量）。
  • 结论：当今 AMD 与 Intel 的一致性实现都是失效型（invalidation-based）的。讲义明确要求掌握”失效型与更新型的区别”，但 Dragon 协议的细节属于项目（projects）需要的加分内容，不要求考试掌握。

3. 代码示例与性能分析

3.1 示例 1：把讲义 slide 48 的 false sharing 实验做成可复现程序

代码（false_sharing.c）：

/* ============================================================================
 * false_sharing.c —— 讲义 slide 48/49 的 false sharing 演示（可复现）
 *   两个版本做完全相同的工作、得到完全相同的数值结果，唯一区别是内存布局:
 *     (A) 每线程的计数器紧挨着排布  -> 12 个 long 落在同一条 64B cache line 内
 *     (B) 每线程的计数器各自独占一条 cache line (padding)
 * 编译: gcc -O3 -pthread false_sharing.c -o false_sharing
 *       (加 -march=native 无用: 瓶颈在 cache 一致性与访存依赖链, 不在指令选择)
 * 运行: ./false_sharing 12 10000000        # 12 线程, 每线程 1e7 次自增
 * ==========================================================================*/
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define CACHE_LINE  64
#define MAX_THREADS 256

/* 每个计数器独占一条 cache line */
typedef struct {
    volatile long counter;
    char pad[CACHE_LINE - sizeof(long)];
} __attribute__((aligned(CACHE_LINE))) padded_counter_t;

static long g_iters = 0;              /* 每个线程的迭代次数 */

static void* worker(void* arg) {
    volatile long* p = (volatile long*)arg;
    for (long i = 0; i < g_iters; i++)
        (*p)++;                       /* volatile: 每轮都必须真的发 load + store */
    return NULL;
}

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

static double run(const char* label, int nthreads, int padded) {
    static long           raw[MAX_THREADS];      /* (A) 紧凑: 相邻计数器共享 line   */
    static padded_counter_t pad[MAX_THREADS];    /* (B) 填充: 计数器各自独占 line   */
    pthread_t tid[MAX_THREADS];

    memset(raw, 0, sizeof(long) * nthreads);
    memset(pad, 0, sizeof(padded_counter_t) * nthreads);

    double t0 = now_sec();
    for (int i = 0; i < nthreads; i++) {
        void* arg = padded ? (void*)&pad[i].counter : (void*)&raw[i];
        if (pthread_create(&tid[i], NULL, worker, arg) != 0) {
            fprintf(stderr, "pthread_create failed\n");
            exit(1);
        }
    }
    for (int i = 0; i < nthreads; i++) pthread_join(tid[i], NULL);
    double t1 = now_sec();

    long sum = 0;
    for (int i = 0; i < nthreads; i++)
        sum += padded ? pad[i].counter : raw[i];

    printf("  %-12s 时间 %7.3f s   校验和 %ld (= %d x %ld, 两种布局必须相同)\n",
           label, t1 - t0, sum, nthreads, g_iters);
    return t1 - t0;
}

int main(int argc, char** argv) {
    int  nthreads = (argc > 1) ? atoi(argv[1]) : 12;
    long iters    = (argc > 2) ? atol(argv[2]) : 10000000L;
    if (nthreads < 1 || nthreads > MAX_THREADS) { fprintf(stderr, "bad nthreads\n"); return 1; }
    g_iters = iters;

    printf("线程数 = %d, 每线程迭代 = %ld, cache line = %d B\n", nthreads, iters, CACHE_LINE);
    /* 先跑一次短的做预热, 避免把页错误/频率爬升算进结果 */
    g_iters = iters / 100;
    run("warmup", nthreads > 2 ? 2 : 1, 1);
    g_iters = iters;

    double t_unpadded = run("unpadded", nthreads, 0);   /* (A) false sharing */
    double t_padded   = run("padded",   nthreads, 1);   /* (B) 每线程独占行 */

    printf("\n  加速比 = %.2fx\n", t_unpadded / t_padded);
    printf("  一致性流量下界(填充版)   = %d x %d B = %d B\n",
           nthreads, CACHE_LINE, nthreads * CACHE_LINE);
    printf("  一致性流量上界(未填充版) = %d x %ld x %d B = %.3f GB\n",
           nthreads, iters, CACHE_LINE,
           (double)nthreads * (double)iters * CACHE_LINE / 1e9);
    return 0;
}

【代码做什么？】

1. main 解析线程数与迭代次数；先用一个短跑的 warmup 把缺页、CPU 频率爬升、线程创建成本从计时中剔除。
2. run(..., padded=0)：静态数组 raw[] 里 12 个 long（8 B）连续排列，全部落在 1~2 条 64 B cache line 内；为每个线程传 &raw[i]，各线程用 volatile long* 反复 (*p)++。
3. run(..., padded=1)：padded_counter_t 通过 __attribute__((aligned(64))) 与 56 B 填充把每个计数器顶到独立的 64 B 边界，每个线程只碰自己那条行。
4. 两次运行都 join 全部线程后把各计数器求和打印——两个版本的校验和必然相同（nthreads × iters），因为它们做的是同一件工作、彼此之间没有数据竞争，差别只在内存布局。这正是”false sharing 是 artifactual communication”的最好证明。
5. 最后打印两个版本的一致性流量上/下界，把”墙钟比值”和”流量比值”分开呈现（见 2.12 节的讨论）。

【并行机制与性能解说】

• 线程如何创建与分配工作：pthread 每线程一个 worker，工作分配方式是”线程 i 独占数组元素 i”（静态划分，天然无负载不均：每线程工作量完全相同 = iters）。
• 共享数据如何处理：没有任何共享数据需要同步——每个线程只写自己的计数器。问题恰恰在于硬件把它们放进了同一条 cache line。
• Work / Span / 并行度：
  • Work（总工作量） W = NUM_THREADS × MANY 次自增（每次自增是 1 次 load + 1 次 add + 1 次 store）。
  • Span（关键路径）：填充版下，每个线程的关键路径是自己计数器上 MANY 次自增的串行依赖链（load→add→store 必须按序，因为下一轮的 load 依赖上一轮的 store，靠 store-to-load forwarding 打通），所以 S ≈ MANY × c_local（c_local ≈ 十几 cycle 量级）。
  • 并行度 = W / S = NUM_THREADS。这与”12 线程应得 12 倍”的直觉一致：填充版的并行度上限就是线程数，受限于每核的串行依赖链和访存吞吐。
  • 未填充版：那条被共享的 cache line 成了一个串行资源（serialized resource）。在 work-span 语言里，这相当于给 span 加了一条额外约束：S' ≥ (NUM_THREADS × MANY) × c_xfer（c_xfer 是一次 cache line 独占权转移的开销，至少含 cache-to-cache 传输延迟，CS149 给出的量级是”L3 命中但行被别的核以 Modified 持有 ~75 cycles”，而正常未共享的 L3 命中只要 ~40 cycles）。于是 并行度 = W / S' ≈ c_local / c_xfer ≪ 1。 并行度小于 1 的含义是：即使给你无限多个核，也快不过这个串行资源——这是 false sharing 最本质的危害，比”实测慢 2.4 倍”严重得多。
• 瓶颈：填充版 → 每核的串行依赖链 + 指令吞吐（在本例的 volatile 写法下，12 核跑不满，因为每轮的 load/store 依赖链太长，属延迟受限而非带宽受限）；未填充版 → 一致性协议的独占权转移延迟 + 互连流量。要真正测出 12× 的差别，应把循环体改成多路独立累加（例如每线程 8 个局部计数器、最后合并），让每个线程有足够的 ILP 把访存延迟隐藏掉——这与”用更多 ILP 隐藏内存延迟”的一般优化原则一致。

3.2 示例 2：MSI / MESI 一致性协议模拟器（复现讲义 slide 30/31 的时序）

代码（msi_sim.cpp）：

/* ============================================================================
 * msi_sim.cpp —— MSI / MESI 缓存一致性协议模拟器
 *   用途:
 *     1) 逐步复现讲义 slide 30/31 的 12 步执行序列, 打印 P0/P1 在 X/Y 两行上的状态
 *     2) 统计两种协议的互连事务数 (BusRd / BusRdX / flush / cache-to-cache)
 *     3) 用一个"私有数据: 读一次再写一次"的常见负载, 量化 MESI 相对 MSI 的收益
 * 编译: g++ -O2 -std=c++17 msi_sim.cpp -o msi_sim
 * 运行: ./msi_sim            # 复现讲义时序, MSI
 *       ./msi_sim mesi       # 同一时序, MESI
 *       ./msi_sim count      # MSI 与 MESI 在合成负载上的事务数对比
 * ==========================================================================*/
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

enum St { I, S, E, M };                 /* Invalid / Shared / Exclusive / Modified */
static const char* stname(St s) { return s == I ? "I" : s == S ? "S" : s == E ? "E" : "M"; }

struct Line { St st = I; int val = 0; };

struct Sim {
    bool mesi;                          /* false: MSI (永不使用 E 态); true: MESI */
    int  ncpu, naddr;
    std::vector<std::vector<Line>> c;   /* c[cpu][addr] */
    std::vector<int> mem;               /* 每个地址在主存中的值 */
    long busRd = 0, busRx = 0, flush = 0, c2c = 0, localHit = 0, accesses = 0;

    Sim(int n, int a, bool m) : mesi(m), ncpu(n), naddr(a), c(n, std::vector<Line>(a)), mem(a, 0) {}

    bool anyOtherValid(int self, int addr) const {
        for (int i = 0; i < ncpu; i++)
            if (i != self && c[i][addr].st != I) return true;
        return false;
    }
    int mOwner(int self, int addr) const {          /* 处于 M 态的其他 cache, 没有则 -1 */
        for (int i = 0; i < ncpu; i++)
            if (i != self && c[i][addr].st == M) return i;
        return -1;
    }

    /* 广播一次互连事务: 先让 M 态 owner 回写(保证 Data-Value 不变量), 再让其他 cache 反应 */
    int broadcast(int self, int addr, bool exclusive) {
        int owner = mOwner(self, addr);
        int data;
        if (owner >= 0) {                           /* owner 提供最新数据 */
            data = c[owner][addr].val;
            mem[addr] = data;                       /* flush: 内存被更新 */
            flush++;
            c2c++;                                  /* cache-to-cache transfer */
        } else {
            data = mem[addr];
        }
        for (int i = 0; i < ncpu; i++) {
            if (i == self) continue;
            if (exclusive) {
                c[i][addr].st = I;                  /* BusRdX: 一律失效 (SWMR 不变量的实现) */
            } else {
                if (c[i][addr].st == M) c[i][addr].st = S;   /* BusRd: M -> S (已回写) */
                else if (c[i][addr].st == E) c[i][addr].st = S;
                /* S 保持 S, I 保持 I */
            }
        }
        return data;
    }

    /* 返回本次访问(若是读)观察到的值 */
    int access(int cpu, int addr, bool write, int wval = 0) {
        accesses++;
        Line& L = c[cpu][addr];
        if (!write) {
            if (L.st != I) { localHit++; return L.val; }          /* S/E/M 命中: 零总线事务 */
            bool shared = anyOtherValid(cpu, addr);
            busRd++;
            int v = broadcast(cpu, addr, false);
            L.val = v;
            L.st = (mesi && !shared) ? E : S;                     /* MESI: 独占时直接进 E */
            return v;
        }
        if (L.st == M) { localHit++; L.val = wval; return wval; } /* M 态吸收写: 零总线事务 */
        if (L.st == E) { localHit++; L.val = wval; L.st = M; return wval; } /* MESI 关键捷径 */
        busRx++;                                                  /* I 写缺失 / S 升级 */
        broadcast(cpu, addr, true);
        L.val = wval;
        L.st = M;
        return wval;
    }
};

/* 打印一行: 列顺序与讲义 slide 30/31 一致 —— P0:X  P0:Y  P1:X  P1:Y */
static void show(const Sim& s, int step, const std::string& act, const std::string& bus) {
    printf(" %2d  %-12s", step, act.c_str());
    for (int i = 0; i < s.ncpu; i++)
        for (int a = 0; a < s.naddr; a++)
            printf("  %s/%-2d", stname(s.c[i][a].st), s.c[i][a].val);
    printf("   %s\n", bus.c_str());
}

int main(int argc, char** argv) {
    std::string mode = (argc > 1) ? argv[1] : "msi";
    bool mesi = (mode == "mesi");

    if (mode == "count") {                 /* ---------- 合成负载: 量化 MSI vs MESI ---------- */
        const int T = 12, K = 100000;      /* 12 个核, 每核重复 K 次"读自己的行 + 写自己的行" */
        for (int m = 0; m < 2; m++) {
            Sim s(T, T, m == 1);
            for (int k = 0; k < K; k++)
                for (int c0 = 0; c0 < T; c0++) { s.access(c0, c0, false); s.access(c0, c0, true, k); }
            printf("%-5s: 访问 %ld 次, BusRd %ld, BusRdX %ld, flush %ld, 本地命中 %ld, 互连事务 %ld\n",
                   m ? "MESI" : "MSI", s.accesses, s.busRd, s.busRx, s.flush, s.localHit,
                   s.busRd + s.busRx);
        }
        return 0;
    }

    /* ---------- 复现讲义 slide 30/31 的 12 步时序 (addr 0 = X, addr 1 = Y) ---------- */
    Sim s(2, 2, mesi);
    printf("协议 = %s   (列格式: 状态/值; 列顺序与讲义 slide 30/31 一致)\n", mesi ? "MESI" : "MSI");
    printf(" step  action        P0:X    P0:Y    P1:X    P1:Y   互连事务\n");
    printf("    0  initial       I/0     I/0     I/0     I/0\n");
    struct Op { int cpu; int addr; bool wr; int val; const char* name; };
    const Op ops[] = {
        {0,0,false,0,"P0: LD X"}, {1,0,false,0,"P1: LD X"},
        {0,0,true, 1,"P0: ST X<-1"}, {0,0,true,2,"P0: ST X<-2"}, {1,0,true,3,"P1: ST X<-3"},
        {1,0,false,0,"P1: LD X"}, {0,0,false,0,"P0: LD X"}, {0,0,true,4,"P0: ST X<-4"},
        {1,0,false,0,"P1: LD X"},
        {0,1,false,0,"P0: LD Y"}, {0,1,true,1,"P0: ST Y<-1"}, {1,1,true,2,"P1: ST Y<-2"},
    };
    int step = 0;
    for (const Op& op : ops) {
        long r0 = s.busRd, x0 = s.busRx, f0 = s.flush;
        s.access(op.cpu, op.addr, op.wr, op.val);     /* addr 0 = X, addr 1 = Y */
        char bus[64]; bus[0] = 0;
        if (s.busRd > r0) snprintf(bus, sizeof bus, "BusRd%s", s.flush > f0 ? " + flush" : "");
        else if (s.busRx > x0) snprintf(bus, sizeof bus, "BusRdX%s", s.flush > f0 ? " + flush" : "");
        else snprintf(bus, sizeof bus, "-- (本地命中)");
        show(s, ++step, op.name, bus);
    }
    printf("\n合计: 访问 %ld 次, BusRd %ld, BusRdX %ld, flush %ld, "
           "cache-to-cache 提供数据 %ld 次, 纯本地命中 %ld 次\n",
           s.accesses, s.busRd, s.busRx, s.flush, s.c2c, s.localHit);
    return 0;
}

【代码做什么？】

1. Line{st, val} 表示一条 cache line 的状态与数据；Sim 维护 ncpu × naddr 条这样的行 + 主存 mem[]，以及四个计数器（busRd / busRx / flush / c2c）。
2. access(cpu, addr, write, wval) 是本地 CPU 触发的事件，按 MSI/MESI 状态机更新状态并发起总线事务：读 I→(S 或 MESI 的 E)、BusRd；写 M→本地、E→M（仅 MESI，零事务）、I/S→BusRdX。
3. broadcast(self, addr, exclusive) 是远程 cache 的监听反应：先让 M 态 owner flush（同时更新 mem[]，从而维持 Data-Value 不变量），再对每个其他 cache 施加”BusRdX 一律失效 / BusRd 把 M 与 E 降级为 S”的规则，并把数据（owner 的或内存的）返回给请求者。
4. main 的默认模式按讲义 slide 30 的 12 条指令逐步执行并打印一张逐状态表；输出应与 2.7 节推演的表一致（这就是讲义 slide 31 那一页拥挤的表格的”自动化版本”）。
5. count 模式构造一个”每个核读写自己的私有行”的负载（12 核 × 10 万轮），比较 MSI 与 MESI 的 BusRd / BusRdX 计数。

【并行机制与性能解说】

• 这段代码模拟的硬件并行：access 对应本地 CPU 的 load/store 通路；broadcast 对应互连上的原子广播（讲义 slide 23 的简化假设：事务原子、失效立即生效）。真实机器上这两条通路并行重叠（非阻塞 cache、MSHR），而模拟器把每一次访问串行化。
• 共享数据如何处理：状态机本身就是”共享数据（cache line 状态）”的唯一权威副本，broadcast 是那个串行化点——它精确对应真实硬件上”互连给写定序”的角色。
• Work / Span / 并行度：
  • Work W = A（访问条数），每次访问的协议逻辑是 O(1)（broadcast 里还有一个 O(NUM_CPUS) 的循环 → 严格说 W = O(A × P)，P = cache 数）。
  • Span S = A：因为每一步的状态迁移都依赖上一步的状态，这是本质串行的模拟。
  • 并行度 = W / S = 1（考虑 broadcast 的 O(P) 循环后为 P，但那 P 条操作在同一次广播里彼此独立，可以并行——这正是真实硬件里”所有 cache controller 同时监听”的模样）。
  • 可扩展性上限：串行部分占 100%，Amdahl 定律给出加速比 ≤ 1：再加核也不会让模拟更快。要并行化它，唯一的办法是按地址分片（partition by address）——不同的地址之间没有一致性依赖（coherence 是逐地址的语义！），因此可以把模拟器拆成”每个地址一个串行轨道”，轨道数就是并行度；但单个热点地址内部的步骤仍必须串行。这是”一致性是 per-location 的”这一性质在工程上的直接体现。
• 瓶颈：单热点行的访问序列完全串行；模拟器输出/计数会引入少量常数开销；broadcast 的 O(P) 循环在核数大时成为主项，也与真实 snooping 的 O(N) 广播代价对应。

3.3 示例 3：直方图的私有化（privatization）+ 归并——真共享的解法

代码（hist.c）：

/* ============================================================================
 * hist.c —— 直方图: "原子累加到共享 bin" vs "每线程私有 padded bin + 归并"
 *   这是讲义 slide 51 (基数排序) 与 slide 47 (每线程局部累加) 的同一个套路:
 *   把"真共享 (true sharing) 的写热点"改造成"私有写 + 一次便宜的归并"。
 * 编译: gcc -O3 -fopenmp -march=native hist.c -o hist
 *       (-O3 让散射循环向量化; -fopenmp 提供线程; 开 -O0 会让两者都被算力掩盖)
 * 运行: OMP_NUM_THREADS=12 ./hist 100000000 4096
 * ==========================================================================*/
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define CACHE_LINE 64
#define MAX_THREADS 256

typedef struct {                     /* 每线程私有的一份 bin 数组, 与下一条 line 隔开 */
    long count[4096];
    char pad[CACHE_LINE];
} bins_t;

static int*   g_data = NULL;
static long   g_n    = 0;
static int    g_nbins = 0;

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

/* ---------- (A) 共享 bin + 原子操作: 每次更新都要独占含该 bin 的 cache line ---------- */
static double hist_atomic(void) {
    long* shared = (long*)calloc(g_nbins, sizeof(long));
    double t0 = now_sec();
    #pragma omp parallel for schedule(static)
    for (long i = 0; i < g_n; i++) {
        int b = g_data[i];
        #pragma omp atomic
        shared[b] += 1;                       /* 读-改-写, 由硬件保证原子, 但在热点 bin 上串行化 */
    }
    double t1 = now_sec();
    long total = 0;
    for (int b = 0; b < g_nbins; b++) total += shared[b];
    printf("  (A) 共享bin + atomic : %7.3f s   总和 %ld\n", t1 - t0, total);
    free(shared);
    return t1 - t0;
}

/* ---------- (B) 每线程私有 bin + 归并: 私有化 (privatization) ---------- */
static double hist_private(void) {
    static bins_t priv[MAX_THREADS];
    int T = omp_get_max_threads();
    if (T > MAX_THREADS) T = MAX_THREADS;
    memset(priv, 0, sizeof(bins_t) * T);

    double t0 = now_sec();
    #pragma omp parallel num_threads(T)
    {
        int tid = omp_get_thread_num();
        long* mybin = priv[tid].count;         /* 这段内存只被本线程写: 零一致性流量 */
        #pragma omp for schedule(static)
        for (long i = 0; i < g_n; i++)
            mybin[g_data[i]] += 1;             /* 注意: 一个 bin 内多元素累加有依赖, 但只在本地 */
    }
    /* 归并: 树形两两合并, span = log2(T) 轮, 而不是 T 次串行累加 */
    double t1 = now_sec();
    long* acc = (long*)calloc(g_nbins, sizeof(long));
    for (int b = 0; b < g_nbins; b++) {
        long s = 0;
        for (int t = 0; t < T; t++) s += priv[t].count[b];
        acc[b] = s;
    }
    double t2 = now_sec();
    long total = 0;
    for (int b = 0; b < g_nbins; b++) total += acc[b];
    printf("  (B) 私有bin + 归并   : %7.3f s (散射 %.3f + 归并 %.3f)  总和 %ld\n",
           t2 - t0, t1 - t0, t2 - t1, total);
    free(acc);
    return t2 - t0;
}

int main(int argc, char** argv) {
    g_n     = (argc > 1) ? atol(argv[1]) : 100000000L;
    g_nbins = (argc > 2) ? atoi(argv[2]) : 4096;
    g_data  = (int*)malloc(sizeof(int) * g_n);
    if (!g_data) { fprintf(stderr, "OOM\n"); return 1; }

    unsigned seed = 12345;
    for (long i = 0; i < g_n; i++) {           /* 均匀随机 bin -> 既有热点也有散布 */
        seed = seed * 1103515245u + 12345u;
        g_data[i] = (int)((seed >> 8) % (unsigned)g_nbins);
    }
    printf("N = %ld, bins = %d, 线程 = %d, 数据 %.1f MB\n",
           g_n, g_nbins, omp_get_max_threads(), (double)g_n * sizeof(int) / 1e6);

    double a = hist_atomic();
    double b = hist_private();
    printf("\n  加速比 (A)/(B) = %.2fx\n", a / b);
    free(g_data);
    return 0;
}

【代码做什么？】

1. 生成 N 个随机落在 [0, nbins) 的键（模拟基数排序里”元素 → bin”的散射）。
2. hist_atomic：所有线程对同一份 shared[] 用 #pragma omp atomic 做 += 1。硬件必须对每个 bin 做原子的读-改-写：若该行不在本地 cache 的 M 态，就要先 BusRdX 抢独占权（就是 2.7 节的 MSI 事务），热点 bin 上所有线程排队。
3. hist_private：每个线程在 priv[tid].count[]（由 bins_t 的填充与相邻线程隔开）上无锁累加；因为每个 bin 只被一个线程写，全过程中零一致性事务、零缓存行弹跳。最后做一次归并：对每个 bin 把 T 份计数相加（O(T × nbins) 的额外工作）。
4. 两个版本打印各自的校验和（总元素数）——结果完全相同，但性能差距来自”共享写热点”是否被消除。

【并行机制与性能解说】

• 线程与工作分配：OpenMP parallel for schedule(static) 把 N 个元素按块静态分给 T 个线程（静态划分 + 均匀随机数据 → 负载均衡良好）。priv[tid] 的访问不需要任何同步，因为写集合互不相交。
• 共享数据如何处理：版本 (A) 的 shared[b] 是典型真共享（true sharing）：读写的是同一个地址，同步是必需的（缺了它结果就错）；版本 (B) 把它变成”私有副本 + 一次显式归并”，用 O(T × nbins) 的额外工作量换掉了所有一致性流量。
• Work / Span / 并行度（设 N 个元素、T 线程、B = nbins）：
  • 版本 (B)：Work W = N + T·B（散射 N + 归并 T·B）；Span S = N/T + B（最后一个线程的散射 + 一个 bin 的归并）；并行度 = W/S ≈ T（当 T·B ≪ N 时）。在 N = 10^8, T = 12, B = 4096 下 W = 10^8 + 49152 ≈ 10^8，S ≈ 8.34e6 + 4096，并行度约 11.98——几乎完美可扩展。若把归并也并行化（每个 bin 一个线程/树形合并），span 还能再降。
  • 版本 (A)：Work 同样是 O(N)，但共享行的独占权转移把它们串行化了：设热点 bin 上的更新占比为 f，则关键路径 S ≈ f·N·c_xfer + (1-f)·N/T·c_local。当 f 不可忽略时，S 由 f·N·c_xfer 支配，并行度退化到 ~1（c_xfer 是几十 cycle 的缓存行转移，c_local 只是本地 L1 更新）。这与 3.1 节 false sharing 的结论形式相同，但原因不同：那是”不同地址恰好在同一行”（伪共享），这是”同一地址（真共享）”——(A) 的串行化是必要的（否则结果错），只是不该让它成为主路径。
  • Amdahl 视角：若 (A) 版本中 30% 的时间花在串行化的热点行上，则 加速比 ≤ 1/(0.3 + 0.7/12) = 2.98×——12 核只得到不到 3 倍，这就是”共享写热点把 Amdahl 的串行部分人为抬高”的定量后果。
• 瓶颈与工程权衡：
  • 版本 (B) 的私有 bin 数组占用 B × 8 B × T。B = 4096 时每线程 32 KB——正好等于 Haswell 的 L1D 大小（32 KB），再大就会溢出到 L2；T = 12 时总占用 384 KB，仍在 8 MB 共享 L3 之内；但若 B 增到 10^6，每线程 8 MB，就会把 L3 乃至 DRAM 拖下水——私有化不是免费的，它是用空间（和 L3 带宽）换一致性流量。这正是基数排序选择 radix 位宽 r 时的真实约束（2^r 个 bin 必须装得下）。
  • 版本 (A) 的瓶颈还有一层：#pragma omp atomic 在 x86 上通常编译为带 lock 前缀的 RMW，其开销远高于普通 store（几十 cycle 甚至上百），且热点 bin 的行在多个核的 L1/L2 之间弹跳。唯一可用的缓解是把”热点”变成”私有”（本示例的做法）或用硬件原子在 L2 完成（GPU 的 atomicAdd 走 L2 就是这个思路）。
  • 结论：“共享写 + 原子”是必需的同步，但绝不该出现在热路径上；正确做法是私有化后归并（parallel histogram / reduction 的通用套路）。

3.4 示例 4（微型）：真共享计数器——为什么必须做规约

/* 编译: gcc -O3 -fopenmp reduce_vs_atomic.c -o rva && OMP_NUM_THREADS=12 ./rva */
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    const long N = 100000000L, NITER = 2000;
    double* a = (double*)malloc(sizeof(double) * N);
    for (long i = 0; i < N; i++) a[i] = 1.0;      /* 求和结果 = N */

    /* (A) 共享累加器 + 原子操作: 含 sum 的那条 cache line 被 12 个核反复抢夺 */
    double sum = 0.0;
    double t0 = omp_get_wtime();
    for (int it = 0; it < NITER; it++) {          /* 刻意重复, 放大串行部分 */
        #pragma omp parallel for
        for (long i = 0; i < N; i++) {
            #pragma omp atomic
            sum += a[i];
        }
    }
    double t1 = omp_get_wtime();

    /* (B) 规约: 编译器为每个线程生成私有累加器, 最后归并 (等价于手工 privatization) */
    double sum2 = 0.0;
    double t2 = omp_get_wtime();
    for (int it = 0; it < NITER; it++) {
        #pragma omp parallel for reduction(+:sum2)
        for (long i = 0; i < N; i++) sum2 += a[i];
    }
    double t3 = omp_get_wtime();

    printf("(A) atomic  : %.3f s   sum = %.0f\n", t1 - t0, sum / NITER);
    printf("(B) reduction: %.3f s  sum = %.0f\n", t3 - t2, sum2 / NITER);
    printf("加速比 = %.1fx\n", (t1 - t0) / (t3 - t2));
    free(a);
    return 0;
}

【代码做什么？】 两次相同规模求和：(A) 用 #pragma omp atomic 把每个元素的贡献加到一个共享标量 sum 上；(B) 用 reduction(+:sum2)，OpenMP 为每个线程开一个私有累加器，循环结束时再归并。

【并行机制与性能解说】

• Work / Span / 并行度：两者 Work 都是 W = N × NITER 次加法。差别全在 Span：
  • (A) 的 span = N × NITER × c_atomic——每一次加法都要独占”含 sum 的那条 cache line”，所以所有线程的更新在同一条行上串行化，并行度 ≈ c_local / c_atomic ≪ 1，等效于”1 个核干活、其余 11 个核排队等 line”；
  • (B) 的 span = N/T × NITER × c_add + T × c_add（私有累加 + T 次归并），并行度 ≈ T = 12。
• 瓶颈：(A) 的瓶颈是一致性协议的独占权转移（真共享的写热点）；(B) 的瓶颈重新回到内存带宽——N = 10^8 个 double = 800 MB，每轮扫描都要 800 MB，在 20 GB/s 下单轮下界 40 ms，2000 轮的理论下界是 80 s，因此 (B) 的良好实现会是带宽受限而非延迟受限。这个例子清楚展示了优化的层次：先用私有化/规约消掉真共享的串行化，之后才轮到你面对带宽这个”下一道墙”。

3.5 四个示例的横向对比

4. 性能模型与复杂度分析

4.1 AMAT：把一致性延迟算进平均访存时间（CS149 补充材料 slide 39）

• 公式：AMAT = Σ_{i=0}^{n} (第 i 级/情形的访问频率 × 该情形的延迟)。多处理器系统里 AMAT_multiprocessor > AMAT_uniprocessor，因为 (a) cache 的失效率上升（别的核的失效把你有效的行作废，产生”一致性缺失”）；(b) 某些缺失的延迟变长（数据在别的核的 cache 里，或在 NUMA 的远端内存）。

• 参考延迟（CS149 slide 39，Intel Core i7 Xeon 5500 系列，约 4 GHz 时把 ns 换算为 cycle）：

注意这张表与 2.2 节的 Haswell 表不是同一台机器（前者是 Nehalem 时代的 Xeon 5500，后者是 2013 年的 Haswell 桌面/移动核），放到一起只用于说明层次与一致性状态的”延迟梯度”。

• 数值算例 1（一致性如何抬高 AMAT）：设某负载的访存分布为：L1 命中 90%，L2 命中 7%，L3 未共享命中 1.5%，L3 共享 0.6%，L3 Modified 0.3%，本地 DRAM 0.6%。

  单处理器版 (假设所有 L3 命中都按"未共享"的 40 cycle 计):
    AMAT_uni = 0.90x4 + 0.07x10 + 0.024x40 + 0.006x120
             = 3.60 + 0.70 + 0.96 + 0.72
             = 5.98 cycles

  多处理器版 (把 0.9% 的 L3 命中区分成"共享 65" 与 "Modified 75"):
    AMAT_mp  = 0.90x4 + 0.07x10 + 0.015x40 + 0.006x65 + 0.003x75 + 0.006x120
             = 3.60 + 0.70 + 0.60 + 0.39 + 0.225 + 0.72
             = 6.235 cycles
    => 一致性与共享使 AMAT 上升约 4.3%

看起来微不足道？把”被别的核以 Modified 持有”的比例从 0.3% 提到 5%（典型的伪共享/真共享热点场景）。 为保证各类占比之和仍为 1, 同步下调 L1 与 DRAM 的占比, 给出第二组分布: L1 85%, L2 7%, L3 未共享 1.5%, L3 共享 0.5%, L3 Modified 5%, 本地 DRAM 1%

    AMAT_mp' = 0.85x4 + 0.07x10 + 0.015x40 + 0.005x65 + 0.05x75 + 0.01x120
             = 3.40 + 0.70 + 0.60 + 0.325 + 3.75 + 1.20 = 9.975 cycles
  与上面 6.235 cycle 相比上升 60%, 而 CPI 中访存部分的贡献几乎翻倍。

结论：讲义 slide 48 的注释”only a fraction of a % of these can be significant”（CS149 亦有同样提醒）——一致性缺失只要占到访问的百分之几，就能显著改变 AMAT；因此用 VTune 之类的工具测量 cache miss 与一致性流量（CS149 slide 40）比凭直觉猜测更重要。

4.2 snooping 的可扩展性：广播的消息复杂度（讲义 slide 52 的结论）

• 模型：设系统有 N 个 cache，每个核每秒产生 m 次需要互连的一致性事务（缺失/升级）。snooping 要求每次事务都广播给所有其他 cache，因此
  • 互连上的事务数（占用网络的事件数）：R_txn = N × m
  • 需要被投递的一致性消息数（每个事务要被 N-1 个 cache 接收）：R_msg ≈ N × m × (N-1) ≈ N² m
  • 目录方案：事务只点对点发给该行的持有者（平均 s 个 sharer），R_msg ≈ N × m × s，与 N 成线性而非平方关系。
• 数值算例 2（为什么 64 核时广播就撑不住了）：

  取 N = 64 个核, 每个核每秒 m = 1e7 次需要互连的事务 (即 10 M miss/s/核):
    snooping 消息投递率  = N^2 x m = 64 x 64 x 1e7 = 4.096e10 条/秒
        -> 即使每条消息只占 8 B, 也需 3.3e11 B/s = 328 GB/s 的互连"消息投递"带宽,
           而这还没算数据本身 (一次 BusRd 要搬 64 B)。
    directory 消息投递率 = N x m x s, 取 s = 2 => 64 x 1e7 x 2 = 1.28e9 条/秒 (3.2% 于前者)

  再看数据带宽: 每次一致性缺失平均搬 64 B:
    snooping/directory 的"有效数据带宽"需求 = N x m x 64 B = 64 x 1e7 x 64 = 4.1e10 B/s = 41 GB/s
  ---- 41 GB/s 的数据带宽已经很吃力, 但真正致命的是上面那条 O(N^2) 的"消息投递"账。

• 物理限制（讲义 slide 52 的收尾 + 前一讲互连网络的结论）：除了消息数，广播还要求一条能给所有 cache 送消息的物理介质（总线或等价的全连接/环上绕一圈）。总线有电气负载上限（节点越多频率越低），环上广播要绕 N 跳。因此 snooping 的实际上限通常在几十个核的量级；再往上就必须用目录——这就是下一讲的主题。
• 工程现实（讲义 slide 40–41 的层次化折中）：注意 Intel 的做法是混合的：L2 之间并不是纯广播——L3 是 inclusive 的、并充当目录与串行化点（CS149 slide 37 明确写出”L3 serves as centralized directory for all lines in the L3 cache”，且”Core i7 的互连是 ring，不是 bus”）。所以真实的”监听式”实现只在较小的核数/较近的层次上是真广播。

4.3 false sharing 的定量下界（本笔记推导）

• 设 T 个线程，每个线程在自己的变量上做 MANY 次写，但所有变量落在同一条 64 B cache line 上。
• 一致性流量下界（填充版）：B_pad = T × 64 B（每个变量只有一次义务性缺失；若数组很大还有容量缺失，但都只发生一次）。T = 12 时 B_pad = 768 B。
• 一致性流量上界（未填充版，最坏情形）：每次写都可能要求把该行搬到写者手里，故 B_unpad ≈ T × MANY × 64 B（还可能有对称的 flush 流量，即再 64 B）。
• 时间下界：S' ≥ (T × MANY) × c_xfer，c_xfer 取一致性”独占权转移”的延迟量级（用 4.1 表的”L3 Modified 在别的核” = 75 cycles，加上排队/串行化开销，保守取 100–130 cycles）。

  数值算例 3: T = 12, MANY = 1e7, 主频 3.0 GHz, 取 c_xfer = 128 cycles
    (a) 未填充版的时间下界(完全串行化假设):
        S' >= 12 x 1e7 x 128 cycles = 1.536e10 cycles = 5.12 s @3GHz
        ---- 与讲义 slide 48 实测的 5.1 s 同一量级, 说明"每次写都抢一次独占权"
             这个最坏假设, 在这段代码上其实相当接近现实。
    (b) 填充版如果真是纯本地 L1 更新 (c_local ~ 1 cycle 的吞吐):
        1e7 x 1 cycle = 1e7 cycles = 3.3 ms (每个线程), 12 线程并行 -> 总时间 ~3.3 ms
        ---- 但讲义实测是 2.1 s, 说明真实瓶颈是 volatile 造成的 load->add->store
             串行依赖链 (每轮十几 cycle) 以及每核有限的访存吞吐, 而不是一致性。
    (c) 因此 "5.1 s / 2.1 s = 2.4x" 这个比值**低估**了 false sharing 的代价:
        它测到的是"两个不同的瓶颈哪个先撞墙", 而不是"一致性流量相差多少"。
        真正的量级差异在**流量**上: 未填充版 7.68 GB vs 填充版 768 B (见下)。

  一致性流量对比 (MANY = 1e7, T = 12, 64 B/行):
    未填充版: 12 x 1e7 x 64 B = 7.68e9 B = 7.68 GB
    填充版  : 12 x 64 B        = 768 B
    比值    : 1e7 倍
  把 7.68 GB 放到一条 20 GB/s 的互连上: 至少 0.384 s 纯粹用于搬"没用的伪共享数据";
  若每次转移都暴露完整延迟(128 cycles), 则是上面算出的 5.12 s。

• 结论：伪共享的危害要用流量（占带宽、耗能量）与延迟（串行化） 两把尺子衡量；而”墙钟只慢 2.4 倍”往往是因为修复后的版本撞上了另一个瓶颈，不构成”伪共享无害”的证据。

4.4 MSI vs MESI 的收益量化（本笔记推导）

• 模型：设负载中有 K 次”首次触摸一条私有行：先读它、随后写它”的模式。MSI：每次 2 次事务（BusRd 使 I→S，BusRdX 使 S→M）；MESI：每次 1 次事务（BusRd 直接进 E，再 PrWr 时 E→M 无需总线）。节省比例 = 50% 的该类事务。注意关键前提是”首次触摸“：一行一旦已经在 M 态（或 MESI 下的 E 态），后续的读和写都是本地命中，两种协议都不再产生事务。
• 数值算例 4：12 个核各自独占一块互不共享的私有数据（例如每核 10 万条 64 B 的行），各做一次”读后写”（读进来、改一个值），即共 12 × 10^5 = 1.2e6 条首次触摸：

  MSI : 每条首次触摸 2 次事务 (BusRd 进 S, 再 BusRdX 升级到 M)
        -> 1.2e6 x 2 = 2.4e6 次互连事务
  MESI: 每条首次触摸 1 次事务 (BusRd 直接进 E, 随后的 PrWr 由 E->M 零事务完成)
        -> 1.2e6 x 1 = 1.2e6 次互连事务
        节省 1.2e6 次事务 = 50%
  按每次事务至少搬 64 B 计:
        MSI  流量 = 2.4e6 x 64 B = 153.6 MB
        MESI 流量 = 1.2e6 x 64 B =  76.8 MB
  在 20 GB/s 互连上: 7.68 ms  vs  3.84 ms

3.2 节模拟器 count 模式跑的是这个负载的”同一行反复读写”版本（12 核 × 10 万轮），它的实测输出正好印证了上面的前提：MSI 只有 24 次互连事务（= 2 × 12，每核首次触摸 2 次），MESI 只有 12 次（= 1 × 12），后续 99.99% 的访问都是本地命中（MSI 本地命中 2399976 次，MESI 2399988 次）——比值仍是 2:1，但绝对值远小于 1.2e6，因为协议只在”行的所有权发生变化”时才付费。

再叠加讲义 slide 30/31 那 12 步时序（3.2 节模拟器可直接复现的计数）：MSI = 10 次互连事务（5 次 BusRd + 5 次 BusRdX，其中 4 次带 flush），MESI = 9 次——省的正是第 11 步 P0: ST Y←1（P0 处于 E 态，E→M 零事务）。而讲义 slide 36/37 那 9 步时序（P0/P1 对 Y 的访问顺序不同）是 MSI 8 次 vs MESI 7 次。这说明 MESI 的收益完全取决于负载中”读后写私有数据”的比例：对 T 个线程各写自己的局部累加器这种模式，MESI 几乎白拿 50% 的一致性流量削减；而对 3.1 节的伪共享模式，E 态完全帮不上忙（因为行一旦被第二个核读过就变 S，再也回不到 E，每次写仍然要 BusRdX）——所以“用 padding 消除伪共享”与”靠 MESI 省事务”是两件互补而非替代的事。

4.5 用 Amdahl 定律描述”一致性把并行部分串行化”

设程序总时间中，因为一致性问题（真共享锁、原子热点、伪共享行弹跳）而必须串行执行的比例为 f，其余部分可完美并行：

  Speedup(T) = 1 / (f + (1 - f)/T)

  数值算例 5:
    f = 0.05 (5% 串行): T = 12 -> 1/(0.05 + 0.95/12) = 1/0.1292 = 7.74x
    f = 0.30 (30% 串行): T = 12 -> 1/(0.30 + 0.70/12) = 1/0.3583 = 2.79x
    f = 0.30, T -> 无穷        -> 3.33x  (无论加多少核都不可能超过 3.33x)
    f = 0.01, T = 12           -> 1/(0.01+0.99/12) = 10.8x

  与伪共享的对应关系: 3.1 节的"未填充"版本相当于 f -> 1 (整条行是串行资源),
  于是 Speedup -> 1;  而"填充"版本把 f 降到接近 0, Speedup -> T。

• 与 Work-Span 的关系：f 就是把 Span 中的串行分量折算到总时间上的结果。降低 f 的手段在本讲里有三个：(1) 消除伪共享（padding / 分块对齐 line）；(2) 私有化 + 归并（把真共享的写变成私有写，代价是 O(T × 状态量) 的额外工作量与空间）；(3) 改进协议（MESI 消除 upgrade 事务、MOESI/MESIF 减少写回与响应者选择开销）——(3) 是硬件设计师的工作，而 (1)(2) 是程序员的工作。

4.6 Roofline 视角：算术强度（arithmetic intensity）与”一致性带宽”

• 机器算力上界：取 12 核、3.0 GHz、每核每 cycle 可做 8 个单精度 FMA（AVX2 = 8 float/向量 × 2 flop）：

  峰值算力 = 12 核 x 3.0e9 cycle/s x 8 float/FMA x 2 flop = 576 GFLOPS
  (同一算式在 16 核双路、8 宽 SIMD、FMA 上就是常见的 768 GFLOPS)

• 带宽上界：以 20 GB/s 作为”内存 + 一致性流量”合起来可用的带宽（讲义时代的单路 DRAM 量级），则 Roofline 的拐点算术强度为

  I_knee = 峰值算力 / 带宽 = 576 GFLOPS / 20 GB/s = 28.8 flop/byte

也就是说，每搬 1 字节数据必须做 28.8 次浮点运算才能让这台机器进入计算受限区。

• 算例 6（伪共享把程序钉在最左侧）：
  • 伪共享自增：每次自增搬进/搬出约 64 B 的 cache line，算术量约 1 次整数加法 = 1 flop / 64 B ≈ 0.016 flop/byte —— 比拐点小 1800 倍，完全落在极度带宽/延迟受限区（在 Roofline 图上贴在最左端的水平线以下）。
  • 一次 256 MB 数组的流式遍历：若每元素 1 flop（8 B），强度 0.125 flop/byte，仍是带宽受限；单次遍历的数据量 256 MB，在 20 GB/s 下

    时间下界 = 256 MB / 20 GB/s = 0.256 GB / 20 GB/s = 12.8 ms
    而同样的数据若能在 200 GB/s 的 L3 带宽里循环 (12 核共享 8 MB L3 不现实, 这里假设数据能放下):
    时间下界 = 0.256 GB / 200 GB/s = 1.28 ms  (快 10 倍)

• 这就是为什么”先优化访存、再优化算力“是并行程序的第一原则；而本讲的一致性话题正是”访存优化”里最容易被忽视的一类——它既不增加有用流量，也不减少算法的工作量，却实实在在地吃带宽、占延迟。

• 一个实用的设计准则：如果一个算法每处理 1 个元素就要写一次被多个线程共享的位置（或落在别人也在写的行上），那么无论用多少核，它的吞吐都由”每个 cache line 每秒能被转移多少次“决定。用 4.1 的延迟数据粗算：一次独占权转移约 75–130 cycles，即单条行大约 3–8 ns 一次（3e9/100 ≈ 3e7 次/秒）。这就是”一致性带宽”的硬上限，也是为什么任何热点都必须被私有化。

4.7 小结：本讲涉及的时间/带宽/空间三类成本

5. 关键要点

1. 一致性问题的根源不是软件 bug，而是硬件为了性能复制数据。它不可能用加锁、也不能用”更小心的同步”来消除：只要存储被分散在内存与各核私有 cache 中，”读 X 应返回最后一次写 X 的值”就必须由硬件在每一次 load/store 上保证。一致性的精确定义是”每个地址存在一个所有处理器都认可的串行顺序”（等价的三条：遵守 program order、写传播、写串行化；等价的两条不变量：SWMR + Data-Value）。

2. snooping 的全部机制就一句话：一致性相关的 cache 操作被广播给所有 cache controller，每个 controller 同时服务本地 CPU 与互连消息，靠”彼此合作”维持不变量。它不需要全局控制器，也不需要额外存储；代价是广播本身——消息投递量随核数按 O(N²) 增长，因此 snooping 的可扩展性上限就是”能把一致性消息广播给多少 cache”，再往上是目录方案（下一讲）。

3. 协议演进的主线是”消除不必要的事务”，而不是”让单次事务更快”：write-through → write-back 消除每次写的内存流量；MSI → MESI 用 E（独占干净） 消除”私有数据先读后写”的 upgrade 事务（本例中一致性流量减半）；MESIF 用 F 让共享行的 miss 只有唯一响应者；MOESI 用 O 让 M→S 不必写回内存。M 态是”零总线事务的写”的唯一合法来源——记住”进入 M 必须经过互连，除非已经在 M 或（MESI 下）在 E”。

4. 一致性把硬件的实现细节暴露到了软件的性能上：false sharing（伪共享） 是”不同地址、同一 cache line”，它带来的是完全没有必要的通信（artifactual communication）；true sharing（真共享） 的同步是必要的，但不应该出现在热路径上。编程准则：每个可写共享量至少占一条 cache line（alignas(64) / padding / schedule(static, chunk)），共享写热点一律私有化后归并（每线程局部累加 / 私有 bin + merge），热点原子操作必须被规约或分片替代。

5. 优化要有层次：先消除一致性造成的串行化，再面对带宽与算力的墙。用 work-span 的语汇看：伪共享/真共享把 Span 拉长到 O(总工作量 × 一次 line 转移延迟)，使并行度降到 1 以下（加核无用）；消除之后，瓶颈才回到内存带宽（算例：256 MB 一遍至少 12.8 ms @20 GB/s；Roofline 拐点强度 28.8 flop/byte），再之后才轮到算力（12 核 × 3 GHz × 8 FMA × 2 = 576 GFLOPS）。

6. 常见陷阱与注意事项

• ❌ 以为”加锁就能解决一致性问题”。讲义 slide 7 明确回答：不能。一致性问题源于数据被复制这一实现细节，与”两个线程是否同时访问”无关；即使程序里根本没有任何数据竞争（例如 P1 先写、很久之后 P2 才读），没有硬件一致性时 P2 依然可能读到陈旧副本。加锁只能保护用锁保护的临界区内的数据，而共享的 flag、指针、work queue 本身都要靠硬件一致性与内存序来保证。

• ❌ 把 coherence 与 consistency 混为一谈。coherence 只管单个地址上的读写顺序（”同一地址存在一个全局串行顺序”），它是逐地址（per-location） 的；而 memory consistency model 管的是不同地址之间的顺序（例如”我写 A 之后写 B，别的核能否先看到 B 再看到 A”）。本讲的 MSI/MESI 全部满足 coherence，但完全不保证任何跨地址的顺序——这正是课程后面单独讲 memory consistency、并在实现里使用 fence/mfence、std::atomic 的 memory_order 的原因。

• ❌ 只看墙钟比值，就断定伪共享”影响不大”。讲义 slide 48 的 5.1 s → 2.1 s 看起来只有 2.4 倍，但那是因为填充后的版本撞上了另一个瓶颈（volatile 造成的 load→store 串行依赖链）。真实差距在一致性流量上：T × MANY × 64 B（未填充，MANY = 10^7 时是 7.68 GB）vs T × 64 B = 768 B，相差 MANY = 10^7 倍。判断伪共享必须同时看流量、延迟、可扩展性。

• ❌ 用”每个线程一个元素”来划分共享数组，却忘了 cache line 是 64 B。int myCounter[NUM_THREADS] 这种写法里，12 个 4 B 的计数器全在同一条行上；schedule(static) 默认的块大小也可能让两个线程的边界落在同一行上（应使用 schedule(static, chunk) 且 chunk ≥ cache_line / sizeof(T)，或让每个线程处理对齐的整行块）。修复时要注意 padding 本身的开销：把 T 个 4 B 计数器各扩到 64 B 是 16 倍空间放大，若数组很大（如每线程一个 10^6 元素的私有数组），应改为”按行对齐的连续块划分”而不是逐元素 padding。

• ❌ 认为 volatile 或原子操作能”绕过一致性问题”。volatile 在 C/C++ 里只保证编译器不优化掉访问，它不提供原子性、不提供内存序、更不会让别的核的副本失效（在 x86 上它生成的仍是普通的 load/store）。#pragma omp atomic、std::atomic、__sync_fetch_and_add 保证的是操作的原子性（必要时通过互连上的 lock RMW 或 L2 中的原子单元实现），但热点上的原子操作仍然是串行的：3.3 节的直方图与 3.4 节的求和都表明，”原子”解决正确性，”私有化 + 归并”才解决性能。

• ❌ 忽略”数据的权威副本可能不在内存里”。write-back + M 态意味着内存里的值可能是陈旧的，必须由 owner 提供数据（这在课程项目里最常表现为”用 DMA/另一个设备读共享缓冲区要小心”、”单 CPU 系统的 I/O 也需要一致性处理”——讲义 slide 11 给出了三种做法：uncached store、把页标记为不可缓存、I/O 完成时显式 flush）。同理在 GPU 上，cudaMemcpy 与 kernel 边界之外的可见性依赖驱动清 L1，而在 kernel 内部跨线程共享数据必须用 __syncthreads()、ld.cg/atomic 或共享内存，不能指望 L1 帮你保持一致。

• ❌ 以为 L1 会自动包含在 L2 里，或以为”L2 比 L1 大”就自动满足 inclusion。讲义 slide 41 的反例说明：即使 L2 是 L1 的两倍、相联度与替换策略相同，A、B、C 映射到同一 set 且访问历史不同，两级 cache 也会逐出不同的行，从而破坏 inclusion。真实机器必须显式维护（L2 逐出时反向失效 L1），并需要 in L1 与 modified-but-stale 两个额外状态位；而 modified-but-stale 的存在意味着“L2 显示该行为 M”并不等于”L2 里有最新数据”——flush 时还得先去 L1 取真数据。

• ❌ 忘记协议必须保证 “write serialization”，只关注”失效有没有发出去”。讲义 slide 15 的反例（P3 看到 a→b，P4 看到 b→a）说明：即使每次写都广播了失效，若不同 cache 观察到的写顺序不同，一致性依然被破坏。所以互连必须提供”所有写事务对所有 cache 可见，且可见顺序相同”这两条保证——这也是为什么总线/环上的串行化点（Intel 的 L3 slice 就充当这个角色）在实现里如此重要。

7. 思考题（带答案）

思考题 1：MSI 状态推演与”为什么 S→M 必须发总线事务”

设 X 初值为 0，只有 P0、P1 两个核，cache 均实现 MSI 协议，初始两条行都是 I。执行序列为： P0: LD X → P1: LD X → P1: ST X←7 → P0: ST X←9 → P1: LD X。 请 (a) 逐步给出两个 cache 的状态与互连事务；(b) 统计 BusRd、BusRdX、flush 的次数；(c) 解释为什么第 4 步 P0 的写必须发 BusRdX，即使 P0 的 cache 里此时可能仍然”有效”。

【答案】 (a) 逐步推演（列格式 状态/值）：

(b) 计数：BusRd = 2 次（第 1、5 步），BusRdX = 2 次（第 3、4 步），flush = 2 次（第 4、5 步）。5 条内存指令触发 4 次互连事务 + 2 次 64 B 写回——这就是”交替读写同一地址”的一致性开销。

(c) 第 4 步必须发 BusRdX 有两个层次的理由：

1. 本例子中 P0 的副本已经无效（第 3 步被 P1 的 BusRdX 作废），所以这是普通的写缺失，必然要取数据 + 取得独占权。
2. 更本质的规则：MSI 里”处理器只能写处于 M 态的行“，而进入 M 的唯一路径是 PrWr 且当前不是 M 时发 BusRdX。因此即使 P0 当时在 S 态（即”副本有效”），它也不能直接本地改写：S 态意味着别的 cache 里可能仍有副本，”有效”不等于”独占”。若不发 BusRdX 就本地写，就会出现两个 cache 同时持有同一行的不同值，违反 SWMR 不变量；而且没有任何机制能让未来的读者知道该向谁要正确数据（write serialization 也无法在互连上给这次写定序）。这正是 MESI 用 E 态 要解决的问题：E 态下”独占”与”干净”同时成立，此时 PrWr 才能做到 E→M 零总线事务。

思考题 2：用讲义数字量化一次真实事故

某 12 核服务器上（12 核共享一条互连，主频 3.0 GHz，一致性粒度为 64 B 的 cache line，未共享的 L3 命中约 40 cycles、数据被别的核以 Modified 持有的 L3 命中约 75 cycles），一个程序里每个线程把结果累加到 int result[12] 的自己那个元素上，全程约 2 × 10^8 次累加（总计，含所有线程）。请 (a) 判断问题类型；(b) 估算一致性流量与”因一致性而额外增加的周期数”；(c) 给出两种修复方案并说明各自的 Work/Span 变化与副作用。

【答案】

(a) 问题类型：false sharing（伪共享）。12 个 int（4 B）共 48 B，全部落在同一条 64 B cache line 内。虽然每个线程写的是不同地址（没有数据竞争，结果的正确性不依赖任何同步），但这 12 个地址共享同一条 line，因此 12 个核会反复争夺该行的独占权（M 态）。这是典型的 artifactual communication（人为通信）——程序在语义上完全不需要任何通信。

(b) 定量估算：

• 最坏情形（每次累加都要求把该行搬到写者手里）：一致性事务数 ≈ 2 × 10^8（与累加次数同阶）。
• 流量：每次转移至少搬 64 B，2e8 × 64 B = 1.28 × 10^10 B = 12.8 GB（若还有对称的脏行写回，翻倍到 ~25.6 GB）。
• 额外周期数：用 75 cycles（L3 命中但行被别的核以 Modified 持有）作为每次转移的延迟下界，2e8 × 75 = 1.5 × 10^10 cycles，在 3.0 GHz 上约 5.0 s；若把行转移的排队/串行化开销算进去（按 100–130 cycles），约 6.7–8.7 s。
• 对照：若换成填充版本，一致性流量只有 12 × 64 B = 768 B，额外周期数可忽略，时间由每核的本地累加吞吐决定（2e8 次加法 / 12 核 ≈ 1.7e7 次/核，几毫秒量级）。即使保守地把填充版按”每轮 10 cycles 的串行依赖链”估，也远小于上面估算的秒级代价——这正是讲义 slide 48 实测 5.1 s vs 2.1 s 的同一现象。

(c) 两种修复方案：

• 方案 A：padding / 对齐到 cache line。把 int result[12] 改成 struct { int result; char pad[64 - sizeof(int)]; } __attribute__((aligned(64))) result[12];（C++ 用 alignas(64)）。Work 不变（仍是 2e8 次累加），Span 从 2e8 × c_xfer 降到 2e8/12 × c_local，并行度从 ≪1 回到 ≈12。副作用：内存放大 16 倍（此处仅 768 B，可忽略；若每线程是 KB 级数组则不可忽略），以及最后仍需一次归并把 12 个计数器相加（O(T)，可忽略）。
• 方案 B：OpenMP reduction(+:total)（编译器的私有化 + 归并）。语义上把”12 个独立计数器”换成”每线程一个私有累加器 + 最后归并”。Work = 2e8 次加法 + O(T) 归并，Span = 2e8/12 × c_add + T × c_add，并行度 ≈ 12。副作用：需要额外 T × 64 B 的私有存储（编译器通常已经按 cache line 对齐，避免自身产生伪共享）；若累加对象不是标量而是数组，则要手写”私有数组 + 归并”（3.3 节的做法）。
• 注意：两种方案不能用”加锁”代替——这里根本没有竞争，加锁只会把本来可并行的写变成串行临界区，让性能更差（而且它掩盖不了”行弹跳”本身，因为临界区内的写仍然要抢独占权）。

思考题 3：为什么编写并行程序时”两个线程写相隔 8 字节的两个变量”会变慢，而”两个线程读同一份只读数据”却不会？

请从一致性协议的状态迁移（MSI/MESI）出发解释，并说明这与”true sharing”和”false sharing”的关系；最后给出一个判断准则，让程序员在写代码时能一眼看出某处是否存在伪共享风险。

【答案】

• 两个线程读同一份只读数据：不会变慢（除了 caches 之间可能的一次数据迁移）。 在 MSI/MESI 下，第一个读者把该行带到 E（MESI，若无人持有）或 S；第二个读者发一次 BusRd，把行变成 S。S 态是”多读者只读纪元”（SWMR 不变量里的 Read-Only epoch），此后所有读者的读都本地命中原 S 副本，零互连事务——共享是”只读的”，协议不需要任何进一步协调。唯一的成本是第一次的 BusRd（以及可能的 cache-to-cache 传输，其延迟比本地 DRAM 更低，见 CS149 的 65/75 vs 120 cycles）。这正是讲义 slide 19 强调”共享 cache 也便于细粒度共享“、以及真实负载常常受益于共享只读数据的根本原因。

• 两个线程写相隔 8 字节的两个变量：会大幅变慢。 因为两者落在同一条 64 B cache line 内，而”写”要求独占（M）：写者 A 把该行升到 M，写者 B 要写时必须发 BusRdX，让 A 的副本作废并把行搬到自己这里（M 态迁移），A 再写时又反向抢回来。每次写都伴随一次 cache line 的 ping-pong（弹跳）——这就是 false sharing（伪共享）：地址不同（没有真共享）、行相同（协议层面当成共享）。注意它与 true sharing（真共享） 的区别：
  • true sharing：两个线程访问同一个地址（例如同一个计数器、同一把锁）。此时”必须串行化”是语义要求，同步不可省略——问题在于不该让它进热路径，解法是私有化 + 归并（3.3、3.4 节）。
  • false sharing：两个线程访问不同地址，却因为 line 太大而被迫串行。此时串行化纯属浪费，解法是让人工的内存布局匹配硬件的粒度：padding / 对齐 / 按行分块。
  • 一个有用的判据：MESI 的 E 态对伪共享毫无帮助（行一旦被第二个核读过就变 S，回不去 E，每次写仍需 BusRdX）；而 E 态对”读写私有数据”帮助巨大（省一半事务）。所以”某个优化能不能救你”取决于你面对的是哪一类问题。
• 一眼判断伪共享风险的准则（三条，按顺序检查）：
  1. 写者是否多于一个？ 只有一个线程写这段数据（其余只读）→ 没有伪共享，最多是一次 BusRd 的迁移成本。没有写者就没有弹跳。
  2. 多个写者写的地址是否落在同一条 cache line 内？ 对 sizeof(T) 小于 64 B 的元素数组、以及”每个线程一个计数器/累加器/锁/标志位”这类紧挨着排布的小对象数组，答案默认是”会”——尤其要注意 struct 里相邻的字段、bool/int 标志数组、以及 std::vector<Node> 里被不同线程写的相邻元素。判据是字节偏移：addr / 64 是否相同。
  3. 这些写是否在热路径上（频率高）？ 即使布局上共享一条行，若写只发生几次（初始化、收尾），成本可以忽略；只有高频写才需要处理。若三者同时成立，就必须：把每个高频写者对齐到至少 64 B（alignas(64)、char pad[64 - sizeof(x)]、schedule(static, 16) 分块），或者干脆把”共享写”改造成”私有写 + 归并”。判断是否修好了，最好的手段是测量（VTune 之类的硬件计数器、或直接对比填充前后的墙钟与一致性流量），而不是靠直觉——这也是讲义 slide 48 给出一段可运行 demo 的用意。