计算机系统结构-第七章(多处理机)

多处理机,什么是多处理机？多处理机结构一致性问题同步程序并行化多处理机性能,什么是多处理机？,本章内容,2之1,具有若干台处理机，在统一的操作系统控制下，在硬件和软件各级上相互作用，来协同求解一个大而复杂的问题。根据Flynn分类法多处理机是MIMD。利用多任务处理可以提高处理速度，利用系统的重组能力可以提高可靠性。,提示,本章内容,2之2,因为多处理机系统结构是一个巨大而多样的领域，其中很多领域仍处于不成熟的阶段，所以本课程集中于多处理机设计的主流进行讨论：由少量到中等数量的处理机（128）组成的机器。,多处理机结构,本章内容,根据存储器的组织形式，多处理机有两种基本结构：,集中式共享存储器结构分布式共享存储器结构,集中式共享存储器结构多处理机,本章内容多处理机结构,存储器是一个独立的子系统，通过互连网络（交叉开关/总线）为所有的处理机共享，任何两台处理机都可以通过访问共享的存储器单元实现通信。由于共享存储器对每个处理机都是对称关系，而且所有处理机对共享存储器的访问时间都相同，这种结构的多处理机也称为对称多处理机（SMP）和均匀存储器存取（UMA）。,2之1,图示,本章内容多处理机结构,2之2,处理机,1级/多级Cache,存储器,处理机,1级/多级Cache,处理机,1级/多级Cache,处理机,1级/多级Cache,I/O系统,分布式共享存储器结构(DSM)多处理机,本章内容多处理机结构,存储器分布在各处理机中，但这些存储器在逻辑上统一编址，形成一个为所有处理机共享的虚拟共享存储器。处理机之间信息交换的物理实现仍然是通过点-点的通信。由于任何一个处理机访问本地存储器都较快，但是访问分布在其他处理机的远程存储器则较慢，这种结构的多处理机也称为非均匀存储器存取（NUMA）。,3之1,图示,本章内容多处理机结构,3之2,处理机+Cache,存储器,互连网络,I/O,处理机+Cache,存储器,I/O,处理机+Cache,存储器,I/O,处理机+Cache,存储器,I/O,处理机+Cache,存储器,I/O,处理机+Cache,存储器,I/O,比较,本章内容多处理机结构,3之3,一致性问题,本章内容,Cache一致性存储一致性,Cache一致性,本章内容一致性问题,问题现象原因分析解决方法,问题现象,本章内容一致性问题Cache一致性,Cache一致性是指私有Cache中共享数据的副本和共享存储器中共享数据之间的一致性。,P1,C,u:5主存,C,C,P2,P3,特征多处理器对相同存储单元的操作引起的一致性。,u:5,u:5,u:7,原因分析,本章内容一致性问题Cache一致性,共享可写数据引起的不一致性进程迁移引起的数据不一致性I/O传输造成的数据不一致性,共享可写数据引起的不一致性,不同处理器对相同单元在各自Cache的拷贝的异步写操作。,本章内容一致性问题Cache一致性原因分析,P1,X,X,P2,X,处理机,Cache,共享存储器,更新之前,P1,X,X,P2,X,更新之后（写通过）,P1,X,X,P2,X,更新之后（写回）,进程迁移引起的数据不一致性,本章内容一致性问题Cache一致性原因分析,多处理器中的进程迁移，而又不互相通报。,P1,X,X,P2,X,处理机,Cache,共享存储器,初始状态,P1,X,X,P2,X,迁移之前（写通过）,进程,P1,X,X,P2,X,迁移之后（写通过）,进程,进程,I/O传输造成的数据不一致性,本章内容一致性问题Cache一致性原因分析,绕过Cache拷贝拥有者的I/O操作。,P1,X,X,处理机,Cache,共享存储器,I/O前,P2,X,I/O,P1,X,X,I/O后,X,P2,X,P1,X,X,I/O后（写回）,X,P2,X,共享存储器,输入,共享存储器,输出,解决方法,前两种原因监听法目录法,第三种原因禁止法刷新法,本章内容一致性问题Cache一致性,监听协议,基本原理具体实现采用写通过策略的Cache采用写回策略的Cache写一次（Write-Once）协议,本章内容一致性问题Cache一致性解决方法,基本原理,本章内容一致性问题Cache一致性解决方法监听协议,4之1,本方法只适用于采用基于总线互连结构的系统中，由于系统中每个处理机都能觉察到存储器系统正在进行的活动，在某个活动破坏了Cache的一致性时，Cache控制器将采取相应的动作使有关的拷贝无效或更新。,写无效/写更新,本章内容一致性问题Cache一致性解决方法监听协议,4之2,使用监听协议来保持Cache一致性有两种方法：方法一：写无效（WriteInvalidate）策略在本地Cache的数据块修改时使远程数据块都无效。方法二：写更新（WriteUpdate）策略在本地Cache数据块修改时通过总线把新的数据块广播给含该块的所有其他Cache。提示：采用写无效或写更新策略与Cache采用写回还是写通过方式无关。,图示,本章内容一致性问题Cache一致性解决方法监听协议,4之3,P1,X,X,P2,X,处理机,Cache,共享存储器,更新之前,P1,X,I,P2,X,更新之后(Write-Invalidate),P1,X,X,P2,X,更新之后(Write-Update),应用情况,本章内容一致性问题Cache一致性解决方法监听协议,4之4,由于写更新法在本地Cache修改时需要通过总线把修改过的数据块的内容广播给所有含该数据块的其他Cache，增加了总线的负担，所以在一般的应用系统中，极少使用写更新法。本方法实现简单，但只适用于总线式互连的多处理机，而且写无效法和写更新法都要占用总线不少时间，因此只能用于机数少的多处理机中。,采用写通过策略的Cache,本章内容一致性问题Cache一致性解决方法监听协议,Cache数据块有两种状态:有效和无效，有效状态表示该数据块内容正确，无效状态表示该数据块内容已“过时”或不在Cache中。RL、WL表示本地处理机对Cache的读和写操作，RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。,采用写回策略的Cache,本章内容一致性问题Cache一致性解决方法监听协议,2之1,采用写回策略的Cache,Cache数据块有三种状态:只读、读写和无效。只读状态表示整个系统中有多个数据块拷贝是正确的；读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有修改，在整个系统中只有一个数据块拷贝是正确的；无效状态表示该数据块内容已“过时”或不在Cache中。RL、WL表示本地处理机对Cache的读和写操作，RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。,本章内容一致性问题Cache一致性解决方法监听协议,2之2,写一次协议,本章内容一致性问题Cache一致性解决方法监听协议,4之1,本方法为了降低总线流量，结合了写回和写通过策略的优点。在第一次写Cache采用写通过策略，以后写Cache采用写回策略，此时整个系统中只有一份正确的拷贝。,写一次协议,本章内容一致性问题Cache一致性解决方法监听协议,4之2,RR,写一次协议,本章内容一致性问题Cache一致性解决方法监听协议,4之3,Cache数据块有四种状态:有效、保留、重写和无效。有效状态表示整个系统中有多个数据块拷贝是正确的；保留状态表示数据从存储器读入Cache后只被写过一次，Cache和存储器中拷贝都正确；重写状态表示Cache中的数据块被写过多次，而且是唯一正确的数据块；无效状态表示该数据块内容已“过时”或不在Cache中。RL、WL表示本地处理机对Cache的读和写操作，RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。,写一次协议,本章内容一致性问题Cache一致性解决方法监听协议,4之4,主要优点：减少大量的无效操作，提高了总线效率。主要缺点：当主存储器的内容无效时,读缺失引起的总线读操作必须禁止主存储器的操作（以免造成总线冲突），而大多数总线不支持这种操作。IEEEFuturebus+总线支持该操作。,目录协议,基本原理具体实现全映射目录协议有限目录协议链式目录协议,本章内容一致性问题Cache一致性解决方法,基本原理,本章内容一致性问题Cache一致性解决方法目录协议,监听协议涉及大量广播通信及收集状态信息的任务，即使是总线型网络也会使总线流量大大增加。如果使无效信息只发给有关的数据块，可以避免广播，这需要有一套管理数据块的结构，这就是Cache一致性目录协议方案。,3之1,基本原理,建立目录表为Cache在共享存储器建立一个目录表，用于保存每个数据块的状态：包括用几个标志位分别指示这个信息块的副本在其他几个处理机的Cache中是否有，另外再设置一个标志位（重写位）用以指明是否有一个Cache允许将有关数据写入。,本章内容一致性问题Cache一致性解决方法目录协议,3之2,目录协议用在实现广播功能比较困难的网络。主要思想为：,基本原理,使用目录表在CPU对Cache进行写操作时，系统根据目录表中的信息将所有其它存有相同内容的Cache拷贝无效，并置重写位。在CPU对Cache进行读操作时，如果重写未置位，则说明该内容未经重写，此时若Cache读缺失，则从主存储器中或拥有正确内容的Cache中读入块并修改目录即可；如果读命中，则直接读即可。,本章内容一致性问题Cache一致性解决方法目录协议,3之3,全映射目录协议,本章内容一致性问题Cache一致性解决方法目录协议,5之1,目录项：重写位存在位数据块,C,1,0,1,X,共享存储器,CacheP2,V,CacheP1,V,X,CacheP3,V,X,V-有效位：0-无效；1-有效C-重写位：0-不许；1-允许存在位：0-不存在；1-存在位数等于处理机数,举例,本章内容一致性问题Cache一致性解决方法目录协议,5之2,目录项：重写位存在位数据块,0,0,0,0,X,共享存储器,CacheP2,0,CacheP1,0,CacheP3,0,所有Cache都没有块X的拷贝,有效位,有效位,有效位,举例,本章内容一致性问题Cache一致性解决方法目录协议,5之3,目录项：重写位存在位数据块,0,1,1,1,X,共享存储器,CacheP2,1,X,CacheP1,1,X,CacheP3,1,X,三个处理机都读过块X后,有效位,有效位,有效位,举例,本章内容一致性问题Cache一致性解决方法目录协议,5之4,目录项：重写位存在位数据块,1,0,0,1,X,共享存储器,CacheP2,0,CacheP1,0,CacheP3,1,X,P3获得写块X权力后,有效位,有效位,有效位,特点,全映射目录协议的效率比较高，但是其目录开销比较大，与处理器数平方成正比（因为目录项的多少与处理器数成正比，而且每个目录项的大小也与处理器数成正比），不具有可扩展性。,本章内容一致性问题Cache一致性解决方法目录协议,5之5,有限目录协议,本章内容一致性问题Cache一致性解决方法目录协议,4之1,目录项：重写位存在位数据块,C,1,1,X,共享存储器,CacheP2,V,CacheP1,V,X,CacheP3,V,X,V-有效位：0-无效；1-有效C-重写位：0-不许；1-允许存在位：0-不存在；1-存在位数等于log2处理机数,举例,本章内容一致性问题Cache一致性解决方法目录协议,4之2,目录项：重写位存在位数据块,0,1,1,X,共享存储器,CacheP2,0,CacheP1,1,X,CacheP3,1,X,当P1、P3的Cache中都有块X的拷贝时,举例,本章内容一致性问题Cache一致性解决方法目录协议,4之3,目录项：重写位存在位数据块,0,1,1,X,共享存储器,CacheP2,1,X,CacheP1,0,CacheP3,1,X,P2请求块X的拷贝（存在驱逐问题）,特点,有限目录协议解决了目录过大的问题，其目录开销与Nlog2N成正比，N为处理器数（因为目录项的多少与处理器数成正比，而且每个目录项的大小与log2N成正比），但效率有所下降。,本章内容一致性问题Cache一致性解决方法目录协议,4之4,链式目录协议,本章内容一致性问题Cache一致性解决方法目录协议,2之1,目录项：重写位指针数据块,C,X,共享存储器,CacheP2,CacheP1,V,X,CacheP3,V-有效位：0-无效；1-有效C-重写位：0-不许；1-允许,V,X,V,X,CT,特点,链式目录协议的复杂程度超过前两种目录协议，但它具有前两种目录协议所没有的重要特性：可扩展性。其指针的大小以处理机数目的对数关系增长，Cache的每个数据块的指针数目与处理机数目无关。,本章内容一致性问题Cache一致性解决方法目录协议,2之2,I/O与Cache的一致性,本章内容一致性问题Cache一致性解决方法,禁止法存储空间中的某些段不允许进入Cache。刷新法操作系统在I/O操作前，将有关的段先从Cache刷新过来，然后再进行I/O操作。,存储一致性,本章内容一致性问题,问题现象解决方法,问题现象,本章内容一致性问题存储一致性,存储一致性是指多个处理机程序的执行次序与共享存储器中共享数据存取次序之间的一致性。,特征不同处理机对不同存储单元的操作引起的一致性。,a.A:=1b.printB,C,c.B:=1d.printA,C,e.C:=1f.printA,B,A、B、C为共享变量(初始状态均为0),处理机1,处理机2,处理机3,共享存储器,解决方法,本章内容一致性问题存储一致性,顺序一致性（SC）任何执行结果认为是在多线程顺序机器上各操作交错执行的结果。处理机一致性（PC）每台处理机发出的写操作顺序不会乱，但两台处理机发出的写操作顺序可能会不一样。弱一致性（WC）程序员利用同步操作确保顺序一致性。释放一致性（RC）具有获得和释放两类同步操作的弱一致性，每类操作保证处理机一致性。,同步,本章内容,为什么要同步？在多处理机中，进程之间可以通过使用共享变量来实现信息交流，共享变量每次只能被一个进程访问，因此当两个或两个以上的进程同时访问某个共享变量时，必须采用同步措施来协调并行执行的进程。如何实现同步？一般来说，同步机制是通过用户级的软件例程来构造的，而这些例程要使用硬件提供的同步指令。,2之1,同步,本章内容,基本硬件原语用户级的同步操作,2之2,基本硬件原语,本章内容同步,在多处理机中实现同步，所需的主要功能是：一组能以原子操作的方式读出并修改存储单元的硬件原语。它们能够自动读修改单元。通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。,7之1,原子交换（atomicexchange）,本章内容同步,功能将一个存储单元的值和一个寄存器的值进行交换。例子可以利用它构建一个简单的锁：0表示该锁未被占用，1表示该锁已被占用。如果某处理机想占用该锁，将对应于该锁的存储单元的值与存放在某个寄存器中的1进行交换，返回结果为0则占用成功，为1则未占用成功。实现同步的关键操作的原子性（交换操作是不可再细分的）。,7之2,测试并置定（test_and_set）,本章内容同步,功能先测试一个存储单元的值，如果符合条件则修改其值。例子可以定义一个测试0和设置1的操作，该操作的使用方法与原子交换类似。,7之3,读取并加1（fetch_and_increment）,本章内容同步,功能返回存储器中的值并以原子操作的方式使存储器中的值增1。例子如果用0表示同步变量未被占用，就可以象使用原子交换一样使用“取并增1”操作。,7之4,使用指令对:LL/SC,本章内容同步,LL(loadlinked或loadlocked)：特殊的取指令SC(storeconditional)：特殊的存指令指令对功能：如果由LL指明的存储单元的内容在SC对其进行写之前已被其他指令改写过，则第二条指令SC执行失败。如果在两条指令间进行切换也会导致SC执行失败。SC将返回一个值来指出该指令操作是否成功：“1”表示成功，“0”表示不成功LL则返回该存储单元初始值。,7之5,LL/SC指令对举例,本章内容同步,利用LL和SC指令实现“原子交换”操作实现R4和由R1指出的存储单元进行原子交换操作。try：ORR3,R4,R0LLR2,0(R1)SCR3,0(R1)BEQZR3,tryMOVR4,R2,7之6,LL/SC指令对举例,本章内容同步,利用LL和SC指令实现“取并增1”操作LL/SC机制的一个优点：用来构造别的同步原语。try：LLR2,0(R1)DADDIUR2,R2,#1SCR2,0(R1)BEQZR2,try,7之7,用户级的同步操作,本章内容同步,旋转锁栅栏,旋转锁,本章内容同步用户级的同步操作,思想处理机环绕一个锁不停地旋转而请求获得该锁。即：处理机围绕该锁反复地执行循环程序，直至获得该锁。适合场合锁被占用的时间很少，在获得锁后加锁过程延迟很小，因为处理机一直在循环等待获得锁。,11之1,旋转锁的实现,本章内容同步用户级的同步操作,无Cache一致性机制在存储器中保存锁变量，处理机可以不断地通过一个原子交换请求使用权。占用锁DADDIUR2,R0,#1lockit：EXCHR2,0(R1)/原子交换BNEZR2,lockit释放锁处理机只需将0放入锁中即可。,11之2,旋转锁的实现,本章内容同步用户级的同步操作,无Cache一致性机制在存储器中保存锁变量，处理机可以不断地通过一个原子交换请求使用权。缺点每次交换（EXCH指令）都产生一次写操作，如果多个处理机试图占用一个锁时，则大多数写操作都会导致写无效，因为每个处理机都想以独占的方式获得锁变量。,11之3,旋转锁的实现,本章内容同步用户级的同步操作,支持Cache一致性将锁变量调入Cache，并通过一致性机制使锁值保持一致。优点：每次尝试占用锁都可以在本地Cache中进行，而不需进行全局存储访问；大多数对锁的访问有局限性，这样做可以大大减少获取锁所需的时间。,11之4,旋转锁的实现,本章内容同步用户级的同步操作,支持Cache一致性采用“原子交换”原语实现（改进）：只对本地Cache中锁的副本进行读取和检测，直到发现该锁已经被释放。然后，该程序立即进行交换操作，去跟在其他处理器上的进程争用该锁变量。lockit：LDR2,0(R1)BNEZR2,lockitDADDIUR2,R0,#1EXCHR2,0(R1)/原子交换BNEZR2,lockit,11之5,3个处理机利用原子交换争用旋转锁所进行的操作,11之6,旋转锁的实现,本章内容同步用户级的同步操作,支持Cache一致性采用LL/SC原语实现：读/写操作明显分开，而且LL原语不产生总线数据传送，这使下面代码与前面方法具有相同的特点。lockit：LLR2,0(R1)BNEZR2,lockitDADDIUR2,R0,#1SCR2,0(R1)BEQZR2,lockit,11之7,同步性能问题,本章内容同步用户级的同步操作,简单旋转锁不能很好地适应可扩缩性。大规模多处理机中，若所有的处理器都同时争用同一个锁，则会导致大量的争用和通信开销。,11之8,定量分析,本章内容同步用户级的同步操作,例：假设某条总线上有10个处理机同时准备对同一变量加锁。如果每个总线事务处理（读失效或写失效）的时间是100个时钟周期，而且忽略对已调入Cache中的锁进行读写的时间以及占用该锁的时间。(1)假设该锁在时间为0时被释放，并且所有处理机都在旋转等待该锁。问：所有10个处理机都获得该锁所需的总线事务数目是多少？(2)假设总线是非常公平的，在处理新请求之前，要先全部处理好已有的请求。并且各处理机的速度相同。问：处理10个请求大概需要多少时间？,11之9,定量分析,本章内容同步用户级的同步操作,解：当i个处理器争用锁的时候，它们都各自完成以下操作序列，每一个操作产生一个总线事务：访问该锁的i个LL指令操作试图占用该锁（并上锁）的i个SC指令操作1个释放锁的存操作指令因此对于i个处理器来说，一个处理器获得该锁所要进行的总线事务的个数为2i+1。由此可知，对n个处理器，总的总线事务个数为：对于10个处理器来说，其总线事务数为120个，需要12000个时钟周期。,11之10,问题分析,本章内容同步用户级的同步操作,本例中问题的根源：锁的争用、对锁进行访问的串行性以及总线访问的延迟。旋转锁的主要优点：总线开销或网络开销比较低，而且当一个锁被同一个处理器重用时具有很好的性能。旋转锁的两个主要优点在本例中都没有得到体现,11之11,栅栏,本章内容同步用户级的同步操作,栅栏思想栅栏强制所有到达该栅栏的进程进行等待，直到全部的进程到达栅栏，然后释放全部的进程，从而形成同步。典型实现用两个旋转锁：一个用来保护一个计数器，它记录已到达该栅栏的进程数；另一个用来封锁进程直至最后一个进程到达该栅栏。,6之1,一种典型的实现,本章内容同步用户级的同步操作,lock（counterlock）；/确保更新的原子性if（count=0）release=0；/