中国科学技术大学：《计算机体系结构》课程教学资源（PPT课件讲稿）顺序同一性的存储器模型

05/29-Review 分布式共享存储的 Cache一致性协议 Cache块的状态: 私有 Cache中块的状态/目录中 Cache块的状态 StateTag Block data Block in a Private Cache Presence bits State Tag Block data Block in a Shared Cache 状态迁移过程:状态迁移图 存储同一性问题 若理发森高荐檐段律序 地址)的全 Coherence研究不同处理器访问存储器相同地址 作的定序问题,即访问每个 Cache块的局部序 2021/2/11 计算机体系结构

05/29-Review • 分布式共享存储的Cache一致性协议 – Cache块的状态： • 私有Cache中块的状态 /目录中Cache块的状态 – 状态迁移过程：状态迁移图 • 存储同一性问题 – Consistency研究不同处理器访问存储器操作的定序 问题，即所有处理器发出的所有访问存储器操作 (所有地址）的全序 – Coherence研究不同处理器访问存储器相同地址操 作的定序问题，即访问每个Cache块的局部序问题 2021/2/11 计算机体系结构 2

顺序同一性的存储器模型 PPPP a system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in the order specified by the program Leslie Lamport Sequential consistency 多个进程之间的存储器操作可以任意交叉 每个进程的存储器操作按照程序序 2021/2/11 计算机体系结构

顺序同一性的存储器模型 2021/2/11 计算机体系结构 3 “ A system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in the order specified by the program” Leslie Lamport Sequential Consistency = 多个进程之间的存储器操作可以任意交叉 每个进程的存储器操作按照程序序 M P P P P P P

顺序同一性的充分条件 多个进程可以交织执行,但顺序同一性模 型没有定义具体的交织方式,满足每个进 程程序序的总体执行序可能会很多。因此 有下列定义 顺序同一性的执行:如果程序的一次执行产生 的结果与前面定义的任意一种可能的总体序产 生的结果一致,那么程序的这次执行就称为是 顺序同一的 顺序同一性的系统:如果在一个系统上的任何 可能的执行都是顺序同一的,那么这个系统就 是顺序同一的 2021/2/11 计算机体系结构

顺序同一性的充分条件 • 多个进程可以交织执行，但顺序同一性模 型没有定义具体的交织方式，满足每个进 程程序序的总体执行序可能会很多。因此 有下列定义： – 顺序同一性的执行：如果程序的一次执行产生 的结果与前面定义的任意一种可能的总体序产 生的结果一致，那么程序的这次执行就称为是 顺序同一的。 – 顺序同一性的系统：如果在一个系统上的任何 可能的执行都是顺序同一的，那么这个系统就 是顺序同一的 2021/2/11 计算机体系结构 4

顺序同一性的充分条件 ·毎个进程按照程序执行序发出存储操作 ·发出写操作后,进程要等待写的完成,才能发 出它的下一个操作 发出读操作后,进程不仅要等待读的完成,还 要等待产生所读数据的那个写操作完成,才能 发出它的下个操作。即:如果该写操作对这个 处理器来说完成了,那么这个处理应该等待 该写操作对所有处理器都完成了。 第三个条件保证了写操作的原子性。即读操作 必须等待逻辑上先前的写操作变得全局可见 2021/2/11 计算机体系结构

顺序同一性的充分条件 • 每个进程按照程序执行序发出存储操作 • 发出写操作后，进程要等待写的完成，才能发 出它的下一个操作 • 发出读操作后，进程不仅要等待读的完成，还 要等待产生所读数据的那个写操作完成，才能 发出它的下个操作。即：如果该写操作对这个 处理器来说完成了，那么这个处理器应该等待 该写操作对所有处理器都完成了。 • 第三个条件保证了写操作的原子性。即读操作 必须等待逻辑上先前的写操作变得全局可见 2021/2/11 计算机体系结构 5

TABLE 3. 1: Should r2 Always be Set to new? Core cl Core C2 Comments SI: Store data= NEW: /*Initially, data=0& flag* SET*/ S2: Store flag= SET LI: Load rl= flag / LI bi may repeat many times * Bl:if(rl≠SET) goto LI L2: Load r2= data 所有coe执行的Load/ Store满足程序序 program order(l(a) Store * LI: rl =flag:/0/ SI: data= NEW: A NEW"/ If L(al(a)Store * If s(a) s(a)Load为 LI: rl = flag: /SET/ If s(a s(a)<m L(b) L2: r2= data: /NEw (2)对同一存储单元的Load操作的值来源于最近 一次写操作( global memory order)) lue of l(a)= value of Maxam[s(a)<m FIGURE3. 1: A Sequentially Consistent Execution of Table 3. 1I's Program L(a)}, MaXm表示最近的 memory order 2021/2/11 计算机体系结构 6

2021/2/11 计算机体系结构 6 (1) 所有core执行的Load/Store满足程序序 /* Load -> Load */ If L(a) L(a) Store */ If L(a) L(a) Store */ If S(a) S(a) Load */ If S(a) S(a) <m L(b) (2) 对同一存储单元的Load操作的值来源于最近 一次写操作(global memory order) Value of L(a) = Value of Max<m{S(a) <m L(a)}, Max<m表示最近的memory order

Sequential Consistency ·SC约束了所有的存储器操作的序 Write→Read Write→ Write ·Read→)Read ·Read→) Write 是有关并行程序执行的简单模型 但是,直觉上在单处理器上的合理的存储器操作的重排 序会违反SC模型 现代微处理器设计中一直都在应用重排序操作来获得性 能提升 (write buffers, overlapped writes,non- blocking reads .). Question:如何协调性能提升与SC的约束? 2021/2/11 计算机体系结构

Sequential Consistency • SC 约束了所有的存储器操作的序: • Write → Read • Write → Write • Read → Read • Read → Write • 是有关并行程序执行的简单模型 • 但是, 直觉上在单处理器上的合理的存储器操作的重排 序会违反SC模型 • 现代微处理器设计中一直都在应用重排序操作来获得性 能提升(write buffers, overlapped writes, non￾blocking reads…). • Question: 如何协调性能提升与SC的约束？ 2021/2/11 计算机体系结构 7

sues in Implementing Sequential Consistency IPPPPIPI M 现代计算机系统实现SC的两个问题 Out-of-order execution capability oad(a; Load(b) yes Load(a): store(b) yes if a* b Store(a; Load(b yes if a* b Store(a: store(b) yes if a* b o Caches, write buffer Cache使得某一处理器的 store操作不能被另一处理器即时看到 No common commercial architecture has a sequentially consistent memory model!!! 2021/2/11 计算机体系结构 8

Issues in Implementing Sequential Consistency 8 现代计算机系统实现SC 的两个问题 • Out-of-order execution capability Load(a); Load(b) yes Load(a); Store(b) yes if a  b Store(a); Load(b) yes if a  b Store(a); Store(b) yes if a  b • Caches. Write buffer Cache使得某一处理器的store操作不能被另一处理器即时看到 M P P P P P P No common commercial architecture has a sequentially consistent memory model ！！！ 2021/2/11 计算机体系结构

Relaxed Consistency Models Rules. X-Y: Operation X must complete before operation y is done Sequential consistency requires(sC): R→W,R→R.W→R.W→W IBM-370 Relax w→R(TSO) TSO Total store ordering"(X86) PS Relax W→W(Pso) 1---------- “ Partia| store order (V RMO PowerPC RCI Re|axR→ Wandr→R Figure 2.24: Relationship among models according to the "stricter"relation Weak ordering" and"release consistency Relax→R,R→W,W-R,W→W(RMO) Release Memory Ordering Maintains the program order to access the same location W→R.W→W 2021/2/11 计算机体系结构

Relaxed Consistency Models • Rules: – X → Y :Operation X must complete before operation Y is done 2021/2/11 计算机体系结构 9 Relax R → W and R → R “Weak ordering” and “release consistency” Relax R → R , R → W , W-R, W → W (RMO) “Release Memory Ordering” Maintains the program order to access the same location: W →R, W → W Relax W → R (TSO) “Total store ordering” (X86) Relax W → W (PSO) “Partial store order” Sequential consistency requires (SC) : R → W, R → R, W → R, W → W

O Simple categorization of relaxed models Relaxation W→R|W→W|R→RW‖ Read Others, Read Own‖ Safety net Order Order Order Write Early Write Early SC[6] IBM370[4] serialization instructions TSO [20] RMW RMW 匚Psop0 ‖RMw, STBAR synchronization RCsc[13,12] release, acquire, nsync, RMW RCpc[13,12] I release, acquire, nsync, RMW Alpha 19 MB. WMB RMO [21] various members PowerPC[7,4]√ SYNC Figure 8: Simple categorization of relaxed models. AV indicates that the corresponding relaxation is allowed by straightforward implementations of the corresponding model. It also indicates that the relaxation can be detected by the programmer(by affecting the results of the program) except for the following cases. The"Read Own Write early?relaxation is not detectable with the SC, wo. alpha, and powerPC models. The "Read Others'Write early" relaxation is possible and detectable with complex implementations of RCsc 2021/2/11 计算机体系结构

Simple categorization of relaxed models 2021/2/11 计算机体系结构 10

TABLE 4.1: Can both rl and r2 be Set to o? Core cl Core c2 Comments SI: x= NEW: S2: y=NEW: Initially, x=0&y=0*/ LI: rl=y L2:r2 program order(<p) of Core CI memory order(<m program order(<p) of Core C2 SI:x=NEw:体NEW S2: y= NEW; /*NEW%/ LI: rl =y: /NEW*/ L2 n2=x:/* NEw 8/ Outcome:(rl r2)= (NEW, NEW) (a) TSO SC Execution 1 SI: X=NEW: F NEW # LI: rl=y: /0/ S2y= NEW: A NEW材 L2:2=x,体NEW Outcome:(rl, r2)=(0, NEw) (b) Tso SC Execution 2 2021/2/11 计算机体系结构 11

2021/2/11 计算机体系结构 11