ChMemoryConsistency

1、高等计算机系统结构计算机科学与技术系研究生课程高等计算机系统结构第一章 高等计算机的核心技术并行处理第二章 加速比性能模型与可扩展性分析第三章 互连与通信第四章 划分与调度第五章 并行存储器系统第六章 Cache Coherence第七章 Memory Consistency第八章 指令级并行处理第七章 Memory Consistency7.1 问题的提出7.1.1 存储器一致性问题7.1.2 存储器访问的原子性问题7.1.3 存储器访问操作的三个阶段7.1.4 一个例子7.1.5 多处理机存储器的行为7.2 四种存储器一致性模型7.1 问题的提出7.1.1 存储器一致性问题1.定义 存储器

2、一致性是指一个系统正确执行存储器操作的能力。各处理机看到存储器的值是一致的。2.顺序一致性程序次序执行次序存储器访问次序顺序一致性：存储器访问次序同程序执行次序一致。顺序不一致性：存储器访问次序同程序执行次序不一致。3. 实际系统中的问题在理想单机系统中，一个取数指令返回的总是对同一存储单元最近一次写指令所写的值。但实际系统中，采用Cache、写缓冲和pipeline等技术在不破坏数据相关性的同时，允许存储器操作不按程序指定的顺序发出。在多处理机环境下，一个存储单元可以被多个处理机访问，“最近一次写操作”、“下一次写操作”、“之后的读操作”这些概念的含义是不清楚的，可能出现多个处理机发出的多个

3、存储请求不按要求的顺序执行，这就要求重新定义存储器一致性模型：当n个处理机同时发出存储访问请求时，什么样的访问顺序是合法的？发出顺序 1 2 3 4 5实际执行的顺序？4. 多机系统中的难点在多机系统中，只检测多处理机的内部相关性是不够的，顺序一致性比较难维持，这是因为：（1）多个指令流的执行次序并不一定一样，如无同步，大量指令交叉执行可能发生。（2）如想改善性能，每台处理机中指令执行的次序与程序次序不同，则会发生更多的指令交叉执行。（3）由于互连网络对不同的存储器访问而引起不一样且无法预测的延迟（如冲突），可能存储器访问命令按程序次序发生，但到达存储器的次序不一样了。（4）存储器访问对Cac

4、he-based的系统就不是原子访问，如并非所有的Cache副本同时修改或失效，则可按程序发出访问命令并到达Memory，但完成不一定按程序次序，不同处理机观察到的将是不同的交叉。此时，一个程序可能会产生多种执行情况。7.1.2 存储器访问的原子性问题如果所有处理机同时看到一份数据拷贝，则系统中的存储器访问是原子性的。如果存操作所写的值对所有处理机同时可读，则此写操作是原子操作。如果存储器更新时为所有处理机所知道，那么这就是原子共享存储器访问。 所以原子存储器成为顺序一致的充分必要条件是要所有存储器访问的执行都必须保持所有各个程序的次序。因此：在Cache-based系统中，不存在原子性。例：

5、如下的程序。P1a: A=1b: Print B CP2c: B=1d: Print A CP3e: C=1f: Print A B假设指令执行的顺序为a，c，e，b，d，f，开始时，A=B=C=0，在非原子系统中：P1 executes b, P1s copy of B has not been updated, P1s copy of C has been updated.P2 executes d, P2s copy of C has not been updated, P2s copy of A has been updated.P3 executes f, P3s copy of A

6、 has not been updated, P3s copy of B has been updated. 这里指令按程序次序执行，但其他处理机并不按程序次序观察到结果，执行结果为0110017.1.3 存储器存取操作的三个阶段一个存储器存取操作可以分为三个不同的阶段：形成、发生和完成。形成：当一个处理机提出存储器访问请求，就说该存储器请求“形成”了，这个请求的完成不由该处理机控制。发生：当一个以形成的请求离开了处理机（包括CPU为本地缓冲），正在向存储器系统传送时，就说这个已形成的请求“发生”了。完成：对一个读操作，当对同一地址发出的写请求不会影响该读操作的返回值，就说该读操作在此刻“完成

7、”了；读在前，写在后，读出的是旧值对于写操作，在该写操作之后，在下一个对同一地址的写操作之前，所发出的对同一地址的读操作都返回该写操作所写的值，就说该写操作“完成”了。两个写之间的读都返回第一次写的值1. 如何确定write的结束点（1）对本台处理机（进程）而言，则是在处理机和Cache之间的写缓冲器中写入新值。 With respect to a process - writes the new value to a write buffer between processor and Cache.（2）对存储器而言，则是值进入Cache。With respect to memory - T

8、he value enters Cache. （3）对其它处理机而言，则是使其它Cache副本更新或失效。 With respect to other processor(s) - updates or invalidates other cached copies. （4）全局结束则是所有处理机对它们Cache的修改。换言之，当写修改值传给所有处理机时，则write全局完成。All processor finish updating the copies of their cache lines. In other words, a write is globally performance

9、d when its modification has been propagated to all processors.2. 如何确定read的结束点（1）对除了发出read之外的所有处理机而言，发read的处理机可访问并Cache命中，其它处理机不能改变回送值。 With respect to all processors other than the issueing processor the issueing processor is granted access and has a Cache hit, so no other processor can change the v

10、alue to be returned.（2）对指定处理机在Cache缺失时，供给Cache副本的指定处理机不能再改变回送值 With respect to a designated processor during Cache miss the designated processor to supply the cache copy is no longer able to change the value to be returned. （3）对所有处理机，则无处理机能改变回送值With respect to all processor No processor is able to c

11、hange the value to be returned.（4）全局结束，没有一台处理机发送对同一地址读命令，而得到此单元变量的前一个值。换言之，在读的值限定以及写此值的写操作全局完成时，read才全局完成。 Globally complete No processor that has a read to the same address will be able to see an earlier value of the variable.In other words, a read is globally performed when the value it returns is

12、 bound and the write that wrote this value is globally performed.3. 区分“对某个处理机完成”与“全局完成”对于非原子的存取操作，需要区分“对某个处理机来讲完成”和“全局完成”（1）处理机i的写操作对于处理机k来讲完成：当处理机k随后发出的对同一地址的读操作返回该写操作所写的值。（2）处理机i的读操作对于处理机k来讲完成：当处理机k随后发出的对同一地址的写操作不会影响该读操作返回的值。（3）一个写操作是全局完成的：如果它对于所有处理机来讲完成（即所有处理机随后发出的对同一地址的读操作返回该写操作所写的值）。（4）一个读操作是全局

13、完成的：如果它对于所有处理机来讲完成（即所有处理机对同一地址的写操作不会影响该读操作返回的值），并且决定该读操作返回值的写操作已经全局完成。7.1.4 例:多处理机中的存储器系统访问次序P1a: A=1b: Print B CP2c: B=1d: Print A CP3e: C=1f: Print A BShared MemoryA，B，C是存储器中的共享变量（初始时 A=B=C=0）开关在原子系统中：Print语句在同一周期内不可分割的输出二个变量。如果把三台处理机的输出按P1，P2，P3的次序串连起来，则输出就形成一个二进制向量的6元组。有26=64种可能的输出组合。 (1)如果所有处理机

14、按各自的程序次序执行指令：会出现的执行交叉为：a,b,c,d,e,f ，产生的输出向量为001011。会出现的执行交叉为：a,c,e,b,d,f ，产生的输出向量为111111。 (2)如果允许处理机不按程序次序执行指令（假设重新排序后指令之间不存在数据相关）如执行交叉为：b,d,f,e,a,c ，产生的输出向量为000000。这个例子一共有6！=720种交叉执行可能，其中90种可保持各自的程序次序。输出010101不可能，如下图：P1输出01b before ce before bP1输出01a before dd before eP1输出01f before ac before fe be

15、fore ca before ec before aa before c矛盾7.1.5 多处理机存储器的行为（1）所有处理机都保持程序次序，并且有相同的存储器执行次序。（2）所有处理机都可以不按程序次序执行，但有相同的存储器执行次序。（3）不同处理机都可以不按程序次序执行，并且有不同的存储器执行次序。 原子存储器成为顺序一致性的充分必要条件是所有存储器访问的执行都必须保持所有多个程序的次序。在非原子存储器访问的多处理机中，遵守各自的程序次序并不是顺序一致性的充分条件。第七章 Memory Consistency7.1 问题的提出7.2 四种存储器一致性模型7.2.1 顺序一致性模型7.2.2

16、弱一致性模型7.2.3 处理机一致性7.2.4 释放一致性7.2.5 四种模型的其它说明7.2 四种一致性模型7.2.1 顺序一致性模型1.定义顺序一致性存储模型（Sequential Consistency，SC）中，所有处理机的取、存和交换操作（原子取存）都可以看作是按一种单一的全局存储次序在顺序的执行，这种存储次序与处理机各自的程序次序是相符合的，如图所示：单端口存储器P1P2P3Pn存储器的访问次序与程序的执行次序一致Lamport定义（1979）：如果任意一次执行的结果都象所有处理机的（memory）操作是以某种顺序执行所得到的一样，而且就在这个序列中，多台处理机的（memory）操

17、作都按照它的程序所指定的次序出现，那么这样的多处理机是顺序一致性系统。A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operation of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order spec

18、ified by its program.在顺序一致性系统中：并行程序的执行情况好象是单机系统的多进程在执行一样，并且每台处理机的memory操作都按其程序所指定的顺序执行。说明：（1）每台处理机发出的指令执行的次序均与其它各台观察到的次序相同。+，写， ，写？（2）每台处理机的所有存储器访问都自动的进行并形成全局次序。统一（3）每台处理机的所有存储器访问均按其程序规定的次序执行。读写读读 读读写读？Lamport给出了保证顺序一致性所必须满足的两个条件：（1）每台处理机按其程序所指定的顺序发出存储器请求。（2）所有处理机对同一存储模块的存储器请求必须按先来先服务的方式进行处理，发出一个存储器

19、请求就是将这个请求插入该先进先服务队列。Scheurich和Dubois给出顺序一致性的充分条件：（1）所有处理机按程序所指定的顺序发出存储器请求。（2）一个处理机发出一写操作，直到所写的值可被其它所有处理机存取时，该处理机才允许发出下一个存储器请求。全局完成（3）一个处理机发出一读操作，直到该操作已全局完成，该处理机才可发出另一个存储器请求。顺序一致性模型要求并行程序的执行看起来象在一个顺序机器上执行一样，它对处理机的所发出的存取操作加了许多限制，导致了许多提高性能的硬件优化措施不能实现。2. 实现单端口存储器一次提供一个存储器操作服务，在每个存储器操作期间，开关将存储器接至一台处理机。开关

20、切换次序确定了所有处理机的所有存储器访问的全局次序。如下图：P1P2P3共享存储器所有处理机的全局存储器访问次序按程序次序按程序次序按程序次序开关上面的图中：一致性由H/W保证，存储器访问 是原子访问强排序。一台处理机发出的访问能被全局完成前，不能发另一次访问，即推迟访问。 顺序一致性模型对H/W的限制较大，因而也限制了许多提高性能的技术的应用，尤其在并行度比较高时。这种模型的可扩展性差。7.2.2 弱一致性模型弱一致性存储模型（Weak Consistency，WC）由Dubois等人提出：当一个处理机在临界区内对共享变量作修改时，由于在临界区内，其它处理机都不能对此变量作访问，因此，在临界

21、区内对共享变量的修改可以不立即被其它处理机见到，也就是不用保证顺序一致性，只需要退出临界区时，存储器一致就可以了，也就是保证在同步点上是顺序一致的，就可以保证存储器的一致性。临界区里面的不必全局完成，外面的必须顺序一致。弱一致性允许对多个存储器存取操作以流水线方式进行。弱一致性模型定义：（1）同步指令之间的关系具有顺序一致性，且有一个全局次序，与所有处理机观察到的一样。（2）在以前所有的全局访问完成之后才能允许一台处理机发出对同步变量访问的命令。（3）在对以前的同步变量完成全局访问之后，才能允许一台处理机访问全局数据。保证弱一致性的条件：（1）对全局同步变量的存取是顺序一致的。（2）在一个处理

22、机上，对一个全局数据发出存取之前，所有在它之前的同步变量存取已经完成。（3）在一个处理机上，对一个同步变量发出存取之前，所有在它之前的全局数据存取已经完成。 弱一致性需要硬件来识别同步操作。（1）一台处理机必须执行完所有的同步访问之后，才能允许任何其它处理机执行取或存操作。（2）一台处理机必须执行完所有的取和存访问之后，才能允许任何其它处理机执行同步访问。（3）同步访问相互之间是顺序一致的。例子：/*LOCK前必须执行的指令*/LOCK； /*H/W识别的同步操作，保证两台处理机不会同时上锁*/*关键段中的指令可弱排序，但与LOCK前UNLOCK之后执行的不同*/UNLOCK；/*原来的指令可

23、重新排序（以任何方式），如单机程序那样，只要不发生语句从关键段移进移出*/优缺点：（1）原有指令可按最高速度执行，同步指令执行速度较慢，服从顺序一致性。（2）存储器全局完成的测试开销，尤其是读较大，将使性能下降。优点是在允许对多个存储器存取以流水线方式进行的同时，为用户提供了一个正确的程序设计模型。缺点是程序员及编译器必须识别所有的同步点。用于SPARC-D体系结构的TSO（total store order）弱一致性模型：单端口存储器P1P2Pn取 存,交换取 存,交换取 存,交换开关上图中：由一台处理机发出的存和交换操作放在该处理机的一个专用的存缓冲器中，它是以先进先出方式工作的。这样，对

24、一台给定的处理机来说，存储器就按次序执行这些操作，而这一次序是和该处理机发出这些操作的次序相同的（即按程序次序）。存储次序是与开关从一台处理机到另一台处理机的切换次序相对应的。一台处理机的取操作首先要检查其缓冲器，看它是否有对同一单元的存操作存在。如有，则该取操作要回送这个最新存入的值；否则，该取操作就直接送到存储器。 在取操作回送一个值之前，处理机不能发新的操作，被逻辑阻塞。交换操作是做依次取和一次存。象存操作一样，它被放在存缓冲器里，象取操作一样，它使处理机阻塞。由于不是所有的取操作都立即送到存储器去，因而，通常取操作不按存储次序出现。 DBS（Dubois，Scheurich，Brigg

25、s(1986)）模型的弱化表现在同步点强制实施顺序一致性上。TSO模型的弱化表现在用FIFO缓冲器对读、存和交换操作实行不同的处理上。7.2.3 处理机一致性模型处理机一致性存储模型（Processor Consistency，PC）由Goodman提出： 一台处理机发出的写命令被观察到的次序与发出的相同。分别由两台处理机发出的写命令被它们或第三台处理机所观察到的次序可不同。如每台处理机的读命令不涉及其它处理机，则读的次序没有规定。每台处理机遵守写一致性。处理机一致性条件：在一个读操作被执行之前，所有在它之前的读操作必须已经完成。在一个写操作被执行之前，所有在它之前的读写操作必须已经完成。上面

26、的条件允许一个在写操作后面的读操作越过该写操作执行。与顺序一致性比较：顺序一致性是要求一台处理机发出访问命令前，所有以前的访问必须全局完成。PC比SC弱，但对大多数应用，能得到与SC 一样的结果。PC实际上也是程序员用显式同步来保证事件的顺序。7.2.4 释放一致性模型释放一致性存储模型（Release Consistency，RC）由Ghakachorloo等(1990) 提出。 是最不严格的存储器模型。基本思想：将访问分成两类（1）获得访问（acquire access）：一种为得到访问共享区许可的同步访问（如临界区上锁）。（2）释放访问（Release access）：是放弃这种许可的写

27、操作（如开锁）。定义：一次普通的读写完成前，要求所有以前的获得访问必须完成。一次释放访问完成前，要求所有以前的读写必须完成。这两类访问彼此都需要遵循处理机一致性。优点：弱一致性强加的排序限制不存在。获得一般是读同步操作，释放一般是写同步操作，跟在释放后面的访问不必延迟。获得之前的访问也不必延迟。解释：获得同步操作（上锁操作或一个进程循环测试一个标志是否被置位）是指企图获得一片共享区域的存取权。释放同步操作（解锁操作或一个进程置标志位）指获得了一片共享区域的存取权。获得操作是通过读一个共享单元直到读到满足条件的值，因此，获得一般是读同步操作。释放一般是写同步操作。释放操作是为了通知其它进程它前面的读已经全局完成，因此，直到它前面的读写已经全局完成，释放操作本身才能知心，处理机本身不必等到释放操作完成。如下图所示：共享访问竞争的非竞争的同步访问 非同步访问获得释放两个访问至同一个存储单元，并且至少其中一个是写操作，则称此两个访问是冲突的。如这对冲突的访问来自不同的处理机，如又是无序执行，有可能同时执行，产生竞争，这两个访问形成竞争对。如一个访问在任何执行下都进入某个竞争对，则称此访问为竞争访问。7