【教学课件】第九章多处理机.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章 多处理机,多处理机系统由若干台独立的处理机组成，每台处理机能够独立执行自己的程序，处理机之间按某种形式互连，在统一的操作系统调度下，从而实现程序之间的数据交换和同步Flynn称这种结构为多指令流多数据流（MIMD）结构并行性(parallelism),：指同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的工作只要在时间上相互重叠，均存在并行性并行性分：同时性、并发性并行性等级（执行的角度，从低到高）：,1）指令内部并行性，即指令内部的微操作之间的并行2）指令间并行，即并行执行两条或多条指令3）任务级或过程级并行，即并行执行两个或多个过程或任务（程序段）,4）作业或程序级并行，即在多个作业或程序间的并行阵列处理机（SIMD）实现的是指令内部并行性（多数据流执行同一指令）多处理机系统（MIMD）,实现指令以上级（任务级、作业级）并行并行性概念,多处理机系统的基本结构,互连网络,处理机1,处理机2,处理机N,存储器,存储器,存储器,I/O,I/O,互连网络,处理机1,处理机2,处理机N,存储器,存储器,存储器,I/O,I/O,I/O,两种多处理机系统基本结构,2）分布式存储器多处理机结构,（每台处理器有自己的处理器和I/O设备，处理器之间通过互连网络实现点对点信息交换）,1）共享存储器多处理机结构,（存储器和I/O设备是独立的子系统，通过互连网络为所有处理器共享，任何两台处理器可以通过共享存储器单元实现通信）,两种多处理机系统基本结构：,1）共享存储器使多处理机拥有同一的寻址空间，一方面便于处理机之间的信息交换，另一方面使程序员无需在程序中显式地控制数据的分布和传输，因而易于编程。

2）分布式存储器可以采用虚拟共享存储器技术虚拟共享存储器（Virtual Shared Memory）对分布在各处理机的局部存储器在逻辑上统一编址，形成一个为所有处理机共享的虚拟地址空间（Virtual Address Space）虚拟共享存储器技术方便了程序员编程，但是，处理机之间信息交换的物理实现仍然是通过点对点的通信多处理机系统的基本结构,MIMD结构特点（与SIMD比较）：,1）MIMD结构有多个控制器，至少有多个指令部件，对各个PE实现单独控制，而又相互协调配合2）MIMD结构的外围设备要能够被多个PE分别调用，因而要通过互连网络转接3）MIMD互连网络必须满足各个PE随机访问主存储器的要求，必须有存储映射部件，满足存储空间动态分配和处理机共享数据的需要共享存储器=共享存储器+虚拟共享存储器,共享存储多处理机(Shared Memory mulptiProcessors)，也称为对称多处理机SMP(Symmetry MultiProcessors),有三种模型：,1)UMA多处理机,均匀存储器存取模型(Uniform Memory Access),存储器被所有处理机均匀共享,所有处理机对所有存储单元具有相同的存取时间,每台处理机有局部Cache,外围设备可以共享,2)NUMA多处理机,非均匀存储器存取(Nonuniform Memory Access)模型,存储器访问时间随存储单元的位置不同而变化。

共享存储器在物理上是分布在所有处理机中的本地存储器所有局部存储器地址空间的集合就组成了全局地址空间处理机访问本地存储器比较快，访问属于另一台处理机的远程存储器则比较慢，因为通过互连网络会产生附加的时间延迟共享存储多处理机,系统互连网络,NUMA多处理机模型,P,1,LM,1,P,2,LM,2,P,n,LM,n,系统互连网络,（总线、交叉开关、多级网络）,UMA多处理机模型,P,1,P,2,P,n,SM,1,SM,2,SM,2,I/O,3)COMA多处理机,只有Cache的存储器结构(Cache-Only Memory Architecture)模型，COMA是一种只用Cache的多处理机系统，实际上，COMA模型是NUMA模型的一种特例后者分布存储器换成了Cache在每个处理机结点上没有主存储器，全部Cache组成了全局虚拟地址空间远程Cache访问通过分布Cache目录进行共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输互连网络,COMA多处理机模型,目录,1,Cache,1,P,1,目录,2,Cache,2,P,2,目录,n,Cache,n,P,n,多处理机系统的特点,1）结构灵活性,SIMD从解决专用问题发展而来，其结构针对数组向量处理算法而设计，特点是：处理单元很多，但只需设置有限和固定的互连通路，即可满足并行性很高的算法需要，是以解决大型数组计算问题为主的计算机。

用库克分类标准，属于数组单执行（SEA）一类MIMD有较强的通用性，即使对数组运算，也可以同时对多个数组进行不同的处理，称为数组多执行（MEA）；它可以同时对多个标量数据进行处理，称为标量多执行（MES）要求能适应更多样的算法，更灵活的结构，实现各种复杂的互连模式，同时解决共享资源冲突问题，因此，MIMD中处理单元数量不多SIMD：专用，PE数很多（几千个），固定有限的通信MIMD：通用，PE几十个，高速灵活的通信,2）程序并行性,SIMD实现操作级的并行，其并行性存在于指令内部，由于结构固定，加上系统专用，因此并行性易于实现MIMD不限于解决数组向量问题，其并行性存在于指令外部，表现在多个任务之间，加上通用性要求，从而使程序并行性的识别难度较大，需要利用多种途径，如算法、程序语言、编译、操作系统直至指令、硬件，尽量挖掘各种潜在的并行性，而且程序并行化的主要任务不应放在程序员肩上3）并行任务派生,SIMD把同种操作集中在一起，由指令直接启动各PE同时工作MIMD用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它并行执行的另一些任务，如果任务数多于处理机数，多余的任务进入排队器等待。

4）进程同步,SIMD仅一个CU，自然是同步的,MIMD执行不同的指令，工作进度不会也不必保持相同，先做完的要停下来等待有数据相关和控制相关也要停下来等待，要采取特殊的同步措施来保持程序所要求的正确顺序一个简单的例子：,Y=A+B*C*D/E+F用两个处理机：,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,总线,共享,存储器,处理机,高速缓冲,存储器,数据分布在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，那么读取的数据将是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由于某种原因，该进程从P1迁移到P2上运行，修改的X仍在P1的C1中，P2上的进程从主存读取数据X到C2，即迁移了的进程读取的数据是“过时”了的X，而非迁移前修改过的X。

若C1、C2都有共享数据X的拷贝，P2进程修改了C2中X，使其变为X，且采用“写通过”策略，使主存中的X也修改为X由于某种原因，该进程从P2迁移到P1上运行，此时，C1中仍然是X，而不是修改过的XP1,P2,X,X,X,共享,存储器,处理机,调整缓冲,存储器,迁移之前,P1,P2,X,X,X,写通过,P1,P2,X,X,X,总线,写回,3）I/O传输引起的不一致,若C1、C2都有共享数据X的拷贝，当I/O处理机将一个新的数据X输入内存时，导致了主存与Cache之间的数据不一致若C1、C2都有共享数据X的拷贝，当P1运行过程中修改了X的值，使其变为X，P1采用“写回”策略，那么，主存的X与C1中的X不一致这时，若I/O处理机要求输出，输出的将是主存的X，而非修改后的XP1,P2,X,X,存储器,处理机,高速缓冲,存储器,P1,P2,X,X,（写通过）,P1,P2,X,X,总线,（写回）,X,I/O,存储器,X,X,（输入）,存储器,X,X,（输出）,多处理机的Cache不一致性解决办法,1）监听协议(Snoopy Protocol)：适用基于总线互连结构的系统2）基于目录的协议：适用非总线互连结构的系统。

监听协议,通过总线监听机制实现高速缓冲和共享存储器之间的数据一致性策略：,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”+“写无效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中需要注意的是：有效和无效分别表示本地处理机对应数据块状态，而非整个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）数据块状态,：读写、只读和无效只读状态表示。