之前关于硬件 Fences的文章中简单提及了丢失 Multi-copy atomicity 之后可能带来的麻烦,本文具体讨论一下 Multi-copy atomicity,其硬件实现及后果。
定义
MCA 这个概念本身一开始其实大家不怎么集中讨论,直到 ARMv8 made it popular[1]。According to [1][2], Multi-copy atomicity (MCA) 的定义其实不是很统一,本文遵从 [2] 中的非正式定义,因为这是现在 ARMv8, RISC-V 和 x86 及 TL, CHI 和 ACE 都遵从的定义,即 Multi-copy atomicity 指:
- 除了本地以外,一个写在所有其他 Agent 看来同时生效。
- 执行这个写的 Agent 本身可以提前看到它。
在并行系统中,“同时”事实上是一个不太好定义的东西,因为实际上即使遵从 MCA 的系统在实际执行中对不同位置的写也是并行处理的,这好像不太“原子”。更形式化的说法应该是:
- 除了参与写的 Agent 以外,所有其他 Agent 对于多个写存在一个一致的观测顺序。
也就是某个写不能“出现在一个 Agent 处太晚,结果排到了另一个写后面”。
实现
首先,如果硬件本身拓扑足够简单,那么 MCA 是 Free 的。例如所有核心没有 L1,共享 L2,一个 Store buffer 打到 L2 上,那在核心看起来访存就是 MCA 的。当拓扑更加麻烦,例如存在多级缓存,或者存在 Slices,那就需要总线协议额外打补丁。
传统的 CPU 缓存层级中的一致性协议是最经典的在一个原生不支持 MCA 的拓扑上实现一个 MCA 系统的方式。最重要的观察是,因为 Writer 在执行写入的时候一定持有 Exclusive 权限,因此在一致性域内,除了 Agent 自用的局部 Store buffer 以外, 在某个特定时间,所有可以回应读取的器件里面,同一行的值肯定是一样的。 对于 Tilelink 而言,就是所有 Thunk Tip 和 Branch 状态的缓存。对于其他 MESI 缓存,所有的 M/E/S 状态并且自己上级没有 M/E 状态的缓存。
这样所有的写入的顺序可以被整个系统 Agrees on。准确来说,写生效的时刻可以认为是最终写穿透到达的缓存拿到 Grant 的时刻,原子性由任何时刻在整个缓存层级中同一行在任何地方读到的值都相同而保证。写生效的顺序也可以直接通过这件事情发生的 wall-clock 时间定义。
影响
如果一个系统保证 MCA,例如某个 ISA 对软件保证 MCA,或者某个总线协议对 Master 保证 MCA,那么内存模型会简化非常多。有两个很直接的结果:
-
所有访存存在一个 Global total order,除了 Local bypass 以外,Load 读到的值就是这个全局序下同一个地址最接近的前一个 Store 的值。[3]
以上面具体的 CPU 一致性协议实现为例,定义某个访存行为“发生”的时刻是这个行为穿透到的最下级缓存拿到所需的 Grant 的 wall-clock 时刻,通过这个 wall-clock 时刻可以定义一个 Global total order。
在这一定义下,忽然内存模型就 Sane 了很多,因为支持 MCA 的整个子系统可以当成一大块儿黑箱,这个黑箱的行为很像一个单独的,可能乱序处理的缓存。Operational model 也非常好定义了,每个 Agent 局部有个 store buffer,然后连接到一个共享存储上,Store buffer 到这个存储的请求发送可能乱序。因为用着方便,RVWMO 的形式化 Spec 直接就规定有这样一个 Global total order。
特别注意,这里虽然有个 Global total order,但这不是 Total store order,TSO 要求 Global total order 和 PO 一致,也就是上述这个看上去像单独一个缓存的黑箱不能乱序处理了。
-
Acq/Rel semantics mostly likely 好处理一些了。 MCA 是子系统顺序处理访存请求的前提,如果连 MCA 都没有,那肯定是不保序的。所以根据之前文章的讨论,如果 Master 现在要处理一个 Barrier,有两(三)个选择:
- 把 Barrier 通过总线灌下去,让下级缓存处理。
- 通过某种方式“等待访存结束”,并且等待的访存完成回应必须有效,也就是必须能保证这个访存真的执行完了,效果扩散足够广泛(e.g. 保证全局可见了)。
- 决定躺平,把自己也划成不支持 MCA 的一部分,让自身的 Master 通过(2)处理。
因此,在 Pre-ARMv8 时代,总线不一定有 MCA,所以 CHI 总线 (CHI-A 版本) 是有 Barrier 的
In contrast, 如果有 MCA,虽然因为可能请求还是会乱序因此还是需要进行额外同步,但是 (2) 中的有效“回应”会非常好构造,通常就是写入请求在总线上的回应信号,在 CPU 经典的一致性协议中,这个回应带有 Grant,也就保证了全局可见性。在 ARMv8 之后因为直接要求了所有外设和总线 IP 都必须保证 MCA,Barrier 就被 Deprecate 了[4],Barrier 全部在请求源头处理,处理方式是 (2)。
Remark: ARM 关于 MCA 的文档[1]中看似混淆了两个概念:缺乏 MCA 和缺乏有效的访存完成回应。这可能是由于通常的破坏 MCA 的方法同时也会破坏有效的访存完成回应,这些方法将在下面讨论。严格来说,即使缺乏 MCA,如果一个 Master 可以确定什么时候一个访存变得全局可见了,那么也可以通过等待达成全局可见来实现 Barrier,进而实现 Acq/Rel semantics。
放松
[5] 中讨论了两种可能破坏 MCA 的常见的优化方法:
-
允许在除了 L1DC 以外的更下级缓存添加 Store buffer。这样不仅发送写的核心本身可以提前观测到,相邻的共享同一级缓存的核心也可以提前看到这个写了。
为了让这个优化有用,请求进入 Store buffer 之后就会发送回应了,这个回应是无效的。如果要等待写真的进入缓存之后再发回应,那就和普通的总线上加个 Buffer 基本无异,只是多了一个对相邻核心的 S-L Bypass,而且还没有额外同步,很难想象什么时候这是有用的。
Remark: 这指明了一个坑:如果 SMT 共享了 Store buffer 但是没有做隔离,那么会破坏 MCA。所幸此时外面的缓存结构还是保证 MCA 的,所以访存回应还是有效的,可以通过传统的清空 Store buffer + 等待回应进行同步。
-
允许缓存在没有收到所有 Probe 的情况下提前回应 Grant。这会导致整个缓存层级中可能在同一时刻在不同位置对同一行读出来不同值,并且如果允许总线上消息乱序的话,是很容易打破 MCA 的。
此时,也许可以将写回应拆成两个:发送 Grant 以及完成 Probe,Barrier 可以通过后者同步。此外这也说明缓存如何 Co-operatively 处理 Barrier,也就是上面提到的方法 (1):等待下级缓存对之前所有请求完成 Probe 的回应,以及本级缓存自己收到了所有之前请求所需的 Probe。
总线上不允许消息换序的话,疑似是能够保持 MCA 的。但是这里有很多具体的细节,例如不同类别的消息(Grant vs. Probe)是否也必须保序传递(这会影响能不能不等待 GrantAck 就抢发 Probe),还是说只保证同一个类型,甚至同一个 ID。总之,需要确认的是进行 Grant 仲裁的器件所确定的序,能否反映到所有上级缓存上。
[1] https://developer.arm.com/documentation/ka002179/latest/
[2] https://github.com/riscv/riscv-isa-manual/issues/1205#issuecomment-1913698656
[3] 此事 A primer on memory consistency 亦有提及
[4] https://developer.arm.com/documentation/101569/0100/Functional-description/Transaction-handling/Barriers
[5] Christopher Pulte, Shaked Flur, Will Deacon, Jon French, Susmit Sarkar, and Peter Sewell. 2017. Simplifying ARM concurrency: multicopy-atomic axiomatic and operational models for ARMv8. Proc. ACM Program. Lang. 2, POPL, Article 19 (January 2018), 29 pages. https://doi.org/10.1145/3158107