xixi's blog

life is so beautiful!

0%

Relaxed(Weaker) Memory Consistency Model

Posted on In , ,
Relaxed(Weaker) Memory Consistency Model 松散内存模型简介

首次提出:
M. Dubois, C. Scheurich, and F. A. Briggs. Memory access buffering in multiprocessors. In Proc. of the 13th Annual International Symposium on Computer Architecture, pp. 434–42, June 1986. DOI: 10.1145/285930.285991. 81

1990s综述:
S. V. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer, 29(12):66–76, December 1996. DOI: 10.1109/2.546611. 81

正确性证明
A. Meixner and D. J. Sorin. Dynamic verification of memory consistency in cachecoherent multithreaded computer architectures. In Proc. of the International Conference on Dependable Systems and Networks, pp. 73–82, June 2006. DOI: 10.1109/dsn.2006.29. 81

提出的动机：优化性能
如果一些访存操作的顺序不影响最后程序执行结果的正确性，可以允许这些访存操作之间重排序以获得更高的性能

  1. Non-FIFO, 写合并的 write buffer
    • 违反了 TSO
    • 要求 store 之间不能有 FENCE
  2. 预测执行的实现更简单
    • 预测乱序执行时不需要检查预测指令最终的正确性 (由程序员保证)

relaxed memory models:

  1. eXample relaxed Consistency model (XC)
  2. Release Consistency (RC)
  3. RISC-V Weak Memory Order (RVWMO)
  4. IBM Power Memory Model
  5. Alpha
    • 类似 XC
    • R. L. Sites, Ed. Alpha Architecture Reference Manual. Digital Press, 1992. 58, 81
  6. SPARC Relaxed Memory Order (RMO)
    • 类似 XC ，支持 TSO, PSO, RMO ，大部分实现使用 TSO
    • D. L. Weaver and T. Germond, Eds. SPARC Architecture Manual (Version 9). PTR Prentice Hall, 1994. 58, 81, 82
  7. ARM
    • ARM v7 类似 IBM Power
    • ARM. ARM Architecture Reference Manual, ARMv7-A and ARMv7-R Edition Errata Markup. Downloaded January 13, 2011. 81, 82
    • ARM. ARM v7A+R Architectural Reference Manual. Available from ARM Ltd.
    • ARM v8 类似 RVWMO
    • ARM. ARM v8 Architectural Reference Manual. Available from ARM Ltd

eXample relaxed Consistency model (XC)

  • 使用 FENCE 指令来定序，默认情况下 load/store 都是不定序指令
  • FENCE 只作用于当前的核，不会影响其他核的访存顺序

XC execution 的要求:

  1. 所有核将自己的 load, store, Fence 插入 global order <m 的时候需满足:
    • if L(a) <p FENCE => L(a) <m FENCE
    • if S(a) <p FENCE => S(a) <m FENCE
    • if FENCE <p FENCE => FENCE <m FENCE
    • if FENCE <p L(a) => FENCE <m L(a)
    • if FENCE <p S(a) => FENCE <m S(a)
  2. 所有核将自己的地址相同的 load, store 插入 global order <m 的时候需满足:
    • if L(a) <p L’(a) => L(a) <m L’(a)
    • if S(a) <p S(a) => S(a) <m S(a)
    • if S(a) <p S’(a) => S(a) <m S’(a)
  3. 每次 load 拿到的值是该 load 之前的相同地址的最后一次 store 的值
    • Value of L(a) = Value of $MAX_{<m} {S(a) | S(a) <m L(a) or S(a) <p L(a) }$

XC ordering rules (X 表示强制定序, B 表示需要 bypass, A 表示地址相同时需要定序)

Operation 2
Operation 1 Load Store RMW FENCE
Load A A A X
Store B A A X
RWM A A A X
FENCE X X X X

实现

System

The Switch
xc_switch

cache-coherence system
xc_basic_impl

原子指令

简易实现

  1. 执行原子指令前排空 write buffer
  2. 获取相应 block 的读写 coherence 状态
  3. 执行 load 和 store ，在二者的执行之间 cache 将该 block 踢出

为优化性能，可以不排空 write buffer (XC 模型允许重排序)

因此， XC 模型下的原子指令并不能保证同步，需要在原子指令后添加 FENCE 指令实现同步。

FENCE

3种实现:

  1. nop
  2. draining: 等待所有前序访存指令完成， Xi -> FENCE ->Yi
  3. without draining: 满足 Xi -> FENCE ->Yi 的前提下不去排空前序访存指令

同步原语

锁的实现需要在每次获取锁或者释放锁的前后都加上 FENCE 指令

Release Consistency (RC)

K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta, and J. Hennessy. Memory consistency and event ordering in scalable shared-memory. In Proc. of the 17th Annual International Symposium on Computer Architecture, pp. 15–26, May 1990. DOI: 10.1109/isca.1990.134503. 72, 81

相比于 XC, RC 认为每个同步操作都被 FENCE 包围过于浪费性能

因此提供了 ACQUIER 和 RELEASE 的同步原语用于获取和释放锁 (相比于 XC 的 FENCE 会排序其前后两个方向的访存操作, ACQUIRE 和 RELEASE 只会排序某一个方向的访存指令)

RC rules:

  1. ACQUIRE -> Load, Store (but not Load, Store -> ACQUIRE)
  2. Load, Store -> RELEASE (but not RELEASE -> Load, Store)
  3. SC ordering of ACQUIREs and RELEASEs:
    • ACQUIRE -> ACQUIRE
    • ACQUIRE -> RELEASE
    • RELEASE -> ACQUIRE
    • RELEASE -> RELEASE

relaxed models 属性

  1. causality 因果
  2. write atomicity / store atomicity / multi-copy atomicity 写原子性
    • 一个核的 store 可以被所有其他核一次看到
    • 必要不充分条件: 正确处理 Independent Read Independent Write (IRIW)
    • 隐含了 causality 因果性

RISC-V Weak Memory Order (RVWMO)

融合了 XC 和 RC:

  1. 定义了 global memory order ，存在多条 FENCE 指令变体
  2. load / store 可以带 RELEASE/ACQUIRE 标记

RELEASE/ACQUIRE orderings

  • ACQUIRE 标记: $ACQUIRE-RC_{PC}$ , $ACQUIRE-RC_{SC}$
  • RELEASE 标记: $RELEASE-RC_{PC}$ , $RELEASE-RC_{SC}$

load/store 可以带任意的标记， RMW 指令只能带 $RC_{SC}$ 标记

ordering

  1. ACQUIRE -> Load,Store
  2. Load,Store -> RELEASE
  3. $RELEASE-RC_{SC}$ -> $ACQUIRE-RC_{SC}$

FENCE orderings

FENCE 指令

  1. FENCE RW,RW
    • load, store -> load, store
  2. FENCE RW,W
    • load, store -> store
  3. FENCE R,RW
    • load -> load, store
  4. FENCE R,R
    • load -> load
  5. FENCE W,W
    • store -> store
  6. FENCE.TSO
    • load -> load, store
    • store -> store

Dependency-induced orderings

对于存在数据依赖/地址依赖的访存指令， RVWMO 会隐式地强制定序

Same address orderings

对于相同地址的访存指令， RVWMO 规定了：

  1. Load -> Store
  2. Store -> Store
  3. 部分情况下的 Load -> Load
    • 相同地址的两条 load 之间没有对同一地址的 store
    • 两条 load 返回的值来自于不同的 store

RWM

RISC-V 支持 2 种 RMW 指令：

  1. Atomic Memory Operations (AMO)
  2. Load Reserved/Store Conditionals (LdR/StC) (成对使用)
    1. LdR 将取出值之后保留
    2. StC 在保留值依然有效时才可成功执行

IBM Power Memory Model

IBM. Power ISA Version 2.06 Revision B. http://www.power.org/resources/ downloads/ PowerISA_V2.06B_V2_PUBLIC.pdf, July 2010. 78, 81

cumulative:
定义 FENCE 之前的所有访存操作为集合 X, 之后的所有访存操作为集合 Y

  1. 将其他核排在 FENCE 之前的操作加入集合 X
  2. 将其他核排在 FENCE 之后的操作加入集合 Y (可能是由于数据依赖、控制依赖或其他 FENCE )
  3. 递归地执行前两项

Power model

  1. store 相对与其他核而言，而非内存，所以不保证 total memory order
    • 一个核需要使用 FENCE 对 store 定序之后，其他核才可以看到相同的 store 顺序
  2. 部分 FENCE 具有累积效果 <>
  3. 有 3 种 FENCE:
    • SYNC or HWSYNC (cumulative): 将 X 的所有操作排到 Y 前
    • LWSYNC (cumulative)
      • loads in X -> loads in Y
      • loads in X -> stores in Y
      • stores in X -> stores in Y
    • ISYNC (not cumulative): 用于排序两条来自同一核的 load 指令
  4. 某些情况尽管没有 FENCE 依旧会排序
    • 如：前序 load 计算后序访存指令的地址，此时会隐式排序