番茄花园-第九章多处理机.ppt

《番茄花园-第九章多处理机.ppt》由会员分享，可在线阅读，更多相关《番茄花园-第九章多处理机.ppt（31页珍藏版）》请在三一办公上搜索。

1、第九章 多处理机,多处理机系统由若干台独立的处理机组成，每台处理机能够独立执行自己的程序，处理机之间按某种形式互连，在统一的操作系统调度下，从而实现程序之间的数据交换和同步。Flynn称这种结构为多指令流多数据流（MIMD）结构。,并行性(parallelism)：指同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的工作。只要在时间上相互重叠，均存在并行性。并行性分：同时性、并发性。并行性等级（执行的角度，从低到高）：1）指令内部并行性，即指令内部的微操作之间的并行。2）指令间并行，即并行执行两条或多条指令。3）任务级或过程级并行，即并行执行两个或多个过程或任务（程序段）4）作业或程序

2、级并行，即在多个作业或程序间的并行。阵列处理机（SIMD）实现的是指令内部并行性（多数据流执行同一指令）。多处理机系统（MIMD）实现指令以上级（任务级、作业级）并行。,并行性概念,多处理机系统的基本结构,互连网络,处理机1,处理机2,处理机N,存储器,存储器,存储器,I/O,I/O,互连网络,处理机1,处理机2,处理机N,存储器,存储器,存储器,I/O,I/O,I/O,两种多处理机系统基本结构,2）分布式存储器多处理机结构（每台处理器有自己的处理器和I/O设备，处理器之间通过互连网络实现点对点信息交换）,1）共享存储器多处理机结构（存储器和I/O设备是独立的子系统，通过互连网络为所有处理器共

3、享，任何两台处理器可以通过共享存储器单元实现通信）,两种多处理机系统基本结构：1）共享存储器使多处理机拥有同一的寻址空间，一方面便于处理机之间的信息交换，另一方面使程序员无需在程序中显式地控制数据的分布和传输，因而易于编程。2）分布式存储器可以采用虚拟共享存储器技术。虚拟共享存储器（Virtual Shared Memory）对分布在各处理机的局部存储器在逻辑上统一编址，形成一个为所有处理机共享的虚拟地址空间（Virtual Address Space）。虚拟共享存储器技术方便了程序员编程，但是，处理机之间信息交换的物理实现仍然是通过点对点的通信。,多处理机系统的基本结构,MIMD结构特点（与

4、SIMD比较）：1）MIMD结构有多个控制器，至少有多个指令部件，对各个PE实现单独控制，而又相互协调配合。2）MIMD结构的外围设备要能够被多个PE分别调用，因而要通过互连网络转接。3）MIMD互连网络必须满足各个PE随机访问主存储器的要求，必须有存储映射部件，满足存储空间动态分配和处理机共享数据的需要。,共享存储器=共享存储器+虚拟共享存储器 共享存储多处理机(Shared Memory mulptiProcessors)，也称为对称多处理机SMP(Symmetry MultiProcessors)有三种模型：1)UMA多处理机 均匀存储器存取模型(Uniform Memory Acces

5、s)存储器被所有处理机均匀共享 所有处理机对所有存储单元具有相同的存取时间 每台处理机有局部Cache 外围设备可以共享2)NUMA多处理机 非均匀存储器存取(Nonuniform Memory Access)模型 存储器访问时间随存储单元的位置不同而变化。共享存储器在物理上是分布在所有处理机中的本地存储器。所有局部存储器地址空间的集合就组成了全局地址空间。处理机访问本地存储器比较快，访问属于另一台处理机的远程存储器则比较慢，因为通过互连网络会产生附加的时间延迟。,共享存储多处理机,3)COMA多处理机 只有Cache的存储器结构(Cache-Only Memory Architecture)

6、模型，COMA是一种只用Cache的多处理机系统，实际上，COMA模型是NUMA模型的一种特例。后者分布存储器换成了Cache。在每个处理机结点上没有主存储器，全部Cache组成了全局虚拟地址空间。远程Cache访问通过分布Cache目录进行。共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输。,多处理机系统的特点,1）结构灵活性 SIMD从解决专用问题发展而来，其结构针对数组向量处理算法而设计，特点是：处理单元很多，但只需设置有限和固定的互连通路，即可满足并行性很高的算法需要，是以解决大型数组计算问题为主的计算机。用库克分类标准，属于数组单执行（SEA）一类。MIMD有较强的通用性

7、，即使对数组运算，也可以同时对多个数组进行不同的处理，称为数组多执行（MEA）；它可以同时对多个标量数据进行处理，称为标量多执行（MES）。要求能适应更多样的算法，更灵活的结构，实现各种复杂的互连模式，同时解决共享资源冲突问题，因此，MIMD中处理单元数量不多。SIMD：专用，PE数很多（几千个），固定有限的通信MIMD：通用，PE几十个，高速灵活的通信2）程序并行性 SIMD实现操作级的并行，其并行性存在于指令内部，由于结构固定，加上系统专用，因此并行性易于实现。MIMD不限于解决数组向量问题，其并行性存在于指令外部，表现在多个任务之间，加上通用性要求，从而使程序并行性的识别难度较大，需要利

8、用多种途径，如算法、程序语言、编译、操作系统直至指令、硬件，尽量挖掘各种潜在的并行性，而且程序并行化的主要任务不应放在程序员肩上。,3）并行任务派生SIMD把同种操作集中在一起，由指令直接启动各PE同时工作。MIMD用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它并行执行的另一些任务，如果任务数多于处理机数，多余的任务进入排队器等待。4）进程同步 SIMD仅一个CU，自然是同步的 MIMD执行不同的指令，工作进度不会也不必保持相同，先做完的要停下来等待。有数据相关和控制相关也要停下来等待，要采取特殊的同步措施来保持程序所要求的正确顺序。,一个简单的例子：Y=A+B*C*D/E+F用

9、两个处理机：CPU1：CPU2：B*C，D/E，A+F，B*C*D/E，A+B*C*D/E+F,5）资源分配和进程调度 SIMD的PE数目固定，受同一控制器控制，程序员采用屏蔽手段改变实际参加操作的PE数目。MIMD执行并发任务，需用处理机的数目不固定，各个处理机进入或退出任务的时刻不相同，所需共享资源的品种、数量又随时变化。因此，如何进行资源分配和进程调度对整个系统的效率有直接的影响。,多处理机的Cache一致性问题,问题由来 由于一般的MIMD中处理机除了拥有共享存储器外，还有自己的Cache，因此，MIMD的一般模型可描述如下（假设两个处理机）：,P1,P2,总线,共享存储器,处理机,高

10、速缓冲存储器,数据分布在P1的Cache1、P2的Cache2和共享存储器中。多处理机的Cache的不一致包括Cache1与Cache2之间的数据不一致以及Cache1、Cache2与共享存储器之间的数据不一致。问题是有哪些因素会引起上述数据不一致？,1）共享可写数据引起的不一致 假设有两个处理机P1、P2，它们私有的Cache分别为C1、C2，C1、C2中保存共享存储器某个数据X的拷贝，其初始状态如下图所示。假设P1改写C1，使X变为X，如果P1采用“写通过WT(Write Through)”策略，那么，主存对应的数据也改为X，但是C2中的对应数据仍然为X，这时如果P2读C2，那么读取的数据

11、将是X，而非X，即与主存对应数据不一致；如果采用“写回WB(Write Back)”策略，即P1更新C1后主存数据不立即更新，而是当该数据从C1调出时才更新主存数据，那么，主存数据仍然是X，这就导致了C1中的数据与主存数据不一致。,多处理机的Cache一致性问题,P1,P2,X,X,X,共享存储器,处理机,高速缓冲存储器,初始状态,P1,P2,X,X,X,写通过,P1,P2,X,X,X,总线,写回,2）进程迁移引起的不一致 假设P1的C1保存共享数据X的拷贝，而P2的C2没有该共享数据。若P1的进程对C1中的X进行了修改，使其变为X，且采用“写回”策略，内存中的数据仍然是X。由于某种原因，该进

12、程从P1迁移到P2上运行，修改的X仍在P1的C1中，P2上的进程从主存读取数据X到C2，即迁移了的进程读取的数据是“过时”了的X，而非迁移前修改过的X。若C1、C2都有共享数据X的拷贝，P2进程修改了C2中X，使其变为X，且采用“写通过”策略，使主存中的X也修改为X。由于某种原因，该进程从P2迁移到P1上运行，此时，C1中仍然是X，而不是修改过的X。,P1,P2,X,X,X,共享存储器,处理机,调整缓冲存储器,迁移之前,P1,P2,X,X,X,写通过,P1,P2,X,X,X,总线,写回,3）I/O传输引起的不一致 若C1、C2都有共享数据X的拷贝，当I/O处理机将一个新的数据X输入内存时，导致

13、了主存与Cache之间的数据不一致。若C1、C2都有共享数据X的拷贝，当P1运行过程中修改了X的值，使其变为X，P1采用“写回”策略，那么，主存的X与C1中的X不一致。这时，若I/O处理机要求输出，输出的将是主存的X，而非修改后的X。,P1,P2,X,X,存储器,处理机,高速缓冲存储器,P1,P2,X,X,（写通过）,P1,P2,X,X,总线,（写回）,X,I/O,存储器,X,X,（输入）,存储器,X,X,（输出）,多处理机的Cache不一致性解决办法,1）监听协议(Snoopy Protocol)：适用基于总线互连结构的系统。2）基于目录的协议：适用非总线互连结构的系统。监听协议 通过总线监

14、听机制实现高速缓冲和共享存储器之间的数据一致性。策略：Cache与主存之间：“写通过WT”和“写回WB”Cache与Cache之间：“写无效WI(Write Invalidate)”和“写更新WU(Write Update)”1）“写通过WT”：改写Cache时同时改写主存数据。2）“写回WB”：改写Cache时不立即改写主存数据，而是等Cache数据调出时才改写主存数据。3）“写无效WI”：本地Cache数据改写时，使远程数据块拷贝无效。4）“写更新WU”：本地Cache数据改写时，通过总线把改写的数据块广播到含有该数据块拷贝的所有其它Cache。上述4中策略可组合起来使用，即：“写通过WT

15、”+“写无效WI”、“写通过WT”+“写更新WU”“写回WB”+“写无效WI”、“写回WB”+“写更新WU”,P1,P2,X,X,共享存储器,处理机,高速缓冲存储器,更新之前,P1,P2,X,I,写无效,P1,P2,X,X,总线,写更新,由于写更新策略在本地Cache修改时要通过总线将修改过的数据块内容广播给所有含有该数据块拷贝的其它Cache，增加了总线的负担，所以，一般系统中，很少使用写更新策略，而是采用写无效策略。基于此，以下只讨论写无效策略的监听协议。,1.采用写通过策略的Cache 1）数据块状态：有效和无效。有效表示数据块内容正确，无效表示数据块内容已“过时”或不在本地Cache中

16、。需要注意的是：有效和无效分别表示本地处理机对应数据块状态，而非整个Cache状态。2）状态图,有效,无效,R1,W1,Wr,Rr,Wr,R1,W1,Rr,说明（假设本地处理机P1，对应的Cache为C1；其它处理机Pr，对应的Cache为Cr）：R1本地读(P1读C1),W1本地写;RrPr读Cr,WrPr写Cr。,远程读，引起本地写回操作,2.采用写回策略的Cache 1）数据块状态：读写、只读和无效。只读状态表示整个系统中不止一个数据块拷贝是正确的；读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有被修改，即在整个系统中只有一个数据块拷贝是正确的。2）状态图,读写,无效,W1,

17、Rr,R1,Rr,R1,W1,只读,Rr,Wr,W1,Wr,Wr,R1,3.写一次(Writeonce)协议 结合写通过和写回的优点，为减少总线流量，Cache第一次写采用写通过策略，尔后的写采用写回策略，此时，整个系统只有一份正确的拷贝。1）数据块状态：有效、无效、保留、重写。为了区分是否第一次写，将读写状态分成“保留”和“重写”两种状态。其中，“保留”状态表示数据从存储器读入Cache后只修改过一次，这时，Cache中的拷贝与存储器中的拷贝一致，而且是正确的；“重写”状态表示数据块不止一次被修改过，此时，存储器中的数据块不正确。“有效”状态表示从存储器读入数据块，Cache中的数据与存储器

18、中的一致，相当于写回的“只读”状态。2）状态图,无效,重写,R1,Wr,R1,Rr,Rr,Wr,有效,Rr,W1,Wr,W1,R1,保留,W1,Rr,R1,W1,Wr,中心思想：1）使用Cache目录2）记录有关数据块拷贝驻留Cache位置和状态信息3）无效命令只发给保存有关数据块拷贝Cache基于目录的协议分类(目录如何维护和目录存放位置)：1）全映射(full-map)目录2）有限(limited)目录3）链式(chained)目录1.全映射目录协议数据结构1）共享存储器中目录项2）Cache状态位,基于目录的协议,C,-,-,-,-,数据,X,共享存储器,有效位,允许写,数据,X,Cac

19、he,重写位(数据是否已重写)1:已重写0:末重写,处理机位(每一位对应一台处理机)1:处理机有数据块拷贝0:处理机无数据块拷贝,注：Cache的一致性协议必须保证目录状态位与Cache数据块状态位一致。,P1,P2,PN,全映射目录协议保持Cache一致性原理,C,-,-,-,数据,X,共享存储器,C,1,1,1,数据,X,共享存储器,C,-,-,1,数据,X,共享存储器,C1,C2,C3,P1,P2,P3,C1,C2,C3,P1,P2,P3,C1,C2,C3,P1,P2,P3,Read X,Read X,Read X,Write X,从第二种状态到第三种状态（P3要写单元X时）：1)C3发

20、现包含X单元的块有效，但不允许写。2)C3向包含X单元的存储器模块发写请求，并暂停P3的工作。3)该存储器模块发无效请求至C1、C2。4)C1、C2接到无效请求后，将对应块置无效状态，并发回答信号给存储器模块。5)存储器模块接到C1、C2的回答信号后，置重写位为“1”，清除指向C1、C2的指针，发允许信号给C3。6)C3接到允许写信号，更新Cache状态，激活P3。,全映射目录特点：1）不具有可扩展性。2）效率高，但开销与处理器数目的平方成正比（因为目录项数与处理器数目成正比，项的大小也与处理器数目成正比）。,2.有限目录,C,数据,X,共享存储器,C,数据,X,共享存储器,C1,C2,C3,

21、P1,P2,P3,C1,C2,C3,P1,P2,P3,Read X,注：当目录项指针域均建立指针后，再有一处理机需要装入该数据，则目录项需要实施指针替换，指针替换过程称为驱逐。驱逐算法与Cache替换算法相似。,有限目录特点：1）目录指针域数目固定，但指针域并不与处理机一一对应，任何一个指针域可以为任何需要装如入该数据块的处理机建立指针，因此，具有可扩展性。3.链式目录 链式目录特点是既不限制共享数据块拷贝数目，又保持可扩展性。实现方法：通过建立目录指针链跟踪共享数据拷贝。1）单向链法 2）双向链法,C,数据,X,共享存储器,C1,C2,C3,P1,P2,P3,Read X,CT,X,C,数据

22、,X,共享存储器,C1,C2,C3,P1,P2,P3,CT,X,X,假设C1没有单元X的共享拷贝，这时处理机P1要读单元X，则：1）存储器送一份拷贝给C1，同时附加一个链结束指针（CT），存储器保持一个指向C1的指针。尔后，当P2要读单元X时，2）存储器送一个拷贝给C2，同时送给C2一个指向C1的指针，存储器保持一个指向C2的指针。,链式目录项目删除问题（假设删Ci目录）：1）沿链发消息，使得Ci+1的指针指向Ci-1，把Ci从链中去掉。2）使Ci及链中位于其后的所有Cache中的单元X无效。链式目录特点：1）可扩展性。,多处理机性能指标：1）程序并行度 一个程序在各时间范围内执行程序的处理机

23、数目称为程序的并行度（DOP）。DOP是在假设可对该程序提供无限数量的处理机和其它所需资源条件下确定的，因此，DOP表示程序本身并行化程度，由程序相关性决定。DOP是一个离散时间函数，DOP的时间函数曲线DOP(t)称为程序并行性分布图。平均并行性A表示程序单位时间平均可使用的处理机数目，其表达式如下：,A=,1t2-t1,DOP(t)dt,t2t1,若程序在时间段ti使用ji台处理机，那么：,A=(ti.ji)/(ti),mi=1,mi=1,2）调和均值加速比 加速比是衡量并行系统优劣的一个重要指标，等于一个程序在一台处理机上运行时间与在并行系统上运行时间的比值。包括多个加速比，调和均值加速

24、比是其中一种。在多处理机上，在不同时间段，程序可以不同执行模式运行，不同执行模式对应程序中的标量计算或向量计算、顺序处理或并行处理。假设程序以执行模式i执行时指令执行速率为Ri，程序以模式i执行的概率为fi，那么，程序指令加权均值速率为：,R*=(Ri.fi),ni=1,假设模式i每条指令平均执行时间Ti=1/Ri，则程序指令加权均值执行时间为：,T*=(fi/Ri),ni=1,假设程序在单台处理机上顺序执行时，每条指令的执行时间T1i=1，那么，在资源不受限制的情况下，程序调和均值加速比：,S=T1/T*=1/(fi/Ri),ni=1,题：设为一个计算机系统中n台处理机可同时执行的程序代码的

25、百分比，其余代码必须由单台处理机顺序执行。假设所有处理机的处理能力相同，每台处理机执行速率均为xMIPS。1）试用参数n、x推导出程序执行速率的表达式。2）假设n=16、x=4，要求程序执行速率达到40MIPS，求值。,解：1）设程序总工作量为W=W1+Wn，其中，W1是必须由一台处理机顺序执行的程序工作量，Wn是可由n台处理机并行执行的程序工作量。并行执行时每台处理机平均工作量Wn/n 程序执行总时间T=T1+Tn，其中，T1是W1在一台处理机顺序执行时间，Tn是Wn在n台处理机并行执行时间。已知每台处理机执行速率为xMIPS，故有：T1=W1/x Tn=(Wn/n)/x=Wn/nx T=T1+Tn=W1/x+Wn/nx=(nW1+Wn)/nx程序执行速率为：V=W/T=(W1+Wn)/(nW1+Wn)/nx=nx(W1+Wn)/(nW1+Wn)因为=Wn/(W1+Wn)，即Wn=W1/(1-)代入v表达式，可得v=nx/n+(1-n),2）将n=16，x=4，v=40MIPS代入v表达式，有：40=164/16+(1-16)可得：=90%,