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(<p) of Core CI memory order (<m) program order (<p) of Core C2 If l(a<p l(b)=>l(a) <m L(b) /*Load -> Store * LI: rl =flag:/0/ SI: data= NEW: A NEW"/ If L(a<p s(b)=>l(a)<m L(b) LI: rl s nae:/o' / Store ->Store * If s(a)<p s(b)=> s(a)<m s(b) LI: rl s nng: /0"/ SET: /SET/ /* Store→>Load为 LI: rl = flag: /SET/ If s(a <p l(b=> 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) <p L(b) => L(a) <m L(b) /*Load -> Store */ If L(a) <p S(b) => L(a) <m L(b) /* Store ->Store */ If S(a) <p S(b) => S(a) <m S(b) /* Store -> Load */ If S(a) <p L(b) => 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