《多处理机》课件.ppt

一、多处理机的特点和主要技术指标,1、定义：两个或两个以上处理机(包括PU和CU)，通过高速互连网络连接起来，在统一的操作系统管理下，实现指令以上级（任务级、作业级）并行。按照Flynn分类法，多处理机系统属于MIMD计算机。多处理机系统由多个独立的处理机组成，每个处理机都能够独立执行自己的程序。存储器操作并行并行存储系统、相联处理机 处理器操作步骤并行流水线处理机 处理器操作并行阵列处理机 任务、作业并行多处理机,2、目的：通过多个作业、任务的并行处理提高大而复杂问题的解题速度 使用冗余的多个处理机，通过重新组织来提高系统的可靠性、适用性和可用性,（1）、结构灵活性并行处理机：专用，PE数很多（几千个），固定有限的通信多处理机：通用，几十个，高速灵活的通信（2）、程序并行性并行处理机并行性存在于指令内部，识别比较容易多处理机并行性存在于指令外部，在多个任务之间，识别难度较大,3、特点,（3）、并行任务派生并行处理机把同种操作集中在一起，由指令直接启动各PE同时工作。多处理机用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它并行执行的另一些任务，如果任务数多于处理机数，多余的任务进入排队器等待。（4）、进程同步并行处理机仅一个CU，自然是同步的多处理机执行不同的指令，工作进度不会也不必保持相同,先做完的要停下来等待。有数据相关和控制相关也要停下来等待,要采取特殊的同步措施来保持程序所要求的正确顺序。,（5）、资源分配和进程调度并行处理机的PE是固定的，采用屏蔽手段改变实际参加操作的PE数目多处理机执行并发任务，需用处理机的数目不固定，各个处理机进入或退出任务的时刻不相同，所需共享资源的品种、数量又随时变化提出资源分配和进程调度问题，它对整个系统的效率有很大的影响。,多处理机为适应多种算法，要求结构能更灵活、变化要多，可以实现复杂的机间互连且避免争用共享的硬件资源 多处理机的并行性主要体现于指令的外部，使得程序并行性的识别比较困难。它必须利用算法、程序语言、编译、操作系统、指令及硬件等，从多种途径去挖掘出各种潜在的并行性。多处理机需要有专门的指令或语句来控制并行任务的派生。根据并发任务之间的数据相关或控制依赖等关系，使用专门的手段来进行并行任务（进程）的同步。,多处理机执行并发任务所需的处理机的机数是不定的。各处理机进入或退出任务所需资源的变化比较复杂，必须较好的解决动态的资源分配和任务调度，让各处理机的负荷尽可能均衡，防止死锁。多处理机中某个处理机发生故障后，应知道如何重新组织系统，使系统不至于瘫痪。多处理机机数增多后，应知道如何提供良好的编程环境。因此，多处理机的结构、机间互连、并行算法、并行语言、编译、操作系统等都将会直接影响到系统的性能和效率的提高。,二、多处理机的硬件结构,1、多处理机的构型紧耦合多处理机通过共享主存实现机间通信为了减少访问主存的冲突，主存采用模m多体交叉方式组织。如果处理机自带局部存储器或再加上Cache存储器，可以大大提高系统的性能，降低对处理机存储器互联网络的使用发生冲突的概率。松耦合多处理机的每台处理机有一个容量较大的存储器，用于存放各处理机常用的指令和数据，减少访主存的冲突。处理机之间通过通道或消息传送系统MTS来进行通信。,2、多处理机的机间互连形式 总线形式具有结构简单、成本低、可扩充性好的优点。但性能和可靠性严重受物理因素的制约。总线形式需要使用相应的总线控制机构和总线仲裁算法，来解决总线的访问冲突。令牌环网的互连形式采用点点连接，其物理参数容易得到控制，非常适合于有高通讯带宽的光纤通信。纵横交叉开关形式是多总线朝总线数增加方向发展的一种极端情况，它适影响系统性能的瓶颈不再是互联网络，而转到了共享的主存。它适合处理机机数较多的情形，但也不宜超过32台，否则将是系统造价过高。采用交叉开关互连具有可扩充性好，系统流量大的特点。,多端口存储器互连是将分布于交叉开关矩阵中的控制，转移和优先级仲裁逻辑放置到相应存储器模块的接口中来。它对机数少的多处理机场合还是很适用的，但处理机机数固定了，不能随意扩充，整个系统性能不可能很高。分布式结构的开关枢纽形式：将互连结构的开关设置在各处理机或接口内部。在这种形式中，每台处理机都经过其开关枢纽与其它多台处理机连接，适合于用在处理机机数很多的分布式多处理机的场合。可扩充性好，系统流量大。,3、存储器组织 在多处理机上，如果各个处理机活跃的进程是共享同一个集中连续的物理地址空间中的数据时，主存宜采用低位交叉编址；如果较少或基本不共享集中的数据时，主存宜用高位交叉编址。采用Cache存储器时，应解决好多个Cache存储器之间信息的一致性问题。目前，主要采用以硬件为基础的监视Cache协议法。,三、多处理机的操作系统,1、主从型：操作系统只在一个指定的主处理机上运行，采用集中控制 硬件比较简单；但系统易瘫痪，如果主处理机工作负荷重，会影响整个系统的性能。适合于工作负荷固定，异构型多处理机2、各自独立型：将控制功能分散到多台处理机上，由他们共同来完成。每台处理机都有一个独立的管理程序在运行。某个处理机发生故障，不会引起整个系统的瘫痪。但是，实现较复杂，进程调度的复杂性和开销加大，若某台处理机发生故障，则难以恢复；各处理机负荷较难均衡。适合于地理位置分散的松耦合型多处理机。,3、浮动型：操作系统的管理程序可在处理机之间浮动 它可使各种资源有较好的负荷均衡；在硬件结构和可靠性上有分布控制的优点。在操作系统的复杂性和经济性上，它接近于主从型的，但操作系统的设计最为困难，适合于紧耦合的同构型多处理机。,四、程序的并行性,1、并行算法：它取决于计算机的结构和题目，是提高多处理机并行性能的关键。研究并行算法的一种思路是将大的程序分解成可由足够多的处理机并行处理的并行过程。每个过程被看成是一个结点，将过程之间的关联关系用结点组成的树来描述。增大树中每一层的结点数，即增大各处理机可并行运行的过程数；降低树的高度，即降低多处理机的运算级数。,E=a+bx+cxx+dxxx,处理机的个数：P=3运算的级数，树高：T p=4加速比，顺序运算的级数与并行运算的级数比：S p=T1/T p=3/2效率：E p=S p/p=1/2,E=a+x(b+x(c+x(d),*,x,*,c,+,a,+,d,+,+,E=a(b+c(d+e(f+gh)E=ace(f+gh)+a(b+cd),g,h,f,e,d,c,b,a,+,*,g,h,f,e,a,c,*,+,*,*,*,*,+,a,b,c,d,处理机的个数：P=3运算的级数，树高：T p=4加速比，顺序运算的级数与并行运算的级数比：S p=T1/T p=7/4效率：E p=S p/p=7/12,2、编译：在多处理机上，程序的并行要求要设计出好的编译程序，能将高级语言源程序尽可能编译出并行度高的目标程序，而不是生成指令间有着大量相关的串行程序。,3、程序段间的相关性分析 多个程序段、进程、任务之间能否并行，依赖于程序的结构。程序段间的数据关联是限制程序并行的重要因素。若有先写后读的数据相关，可以串行，不能并行。若有先读后写的数据反相关，可以串行，不能交换串行。可以并行执行，但必须保证其写入共享主存时的先读后写的次序。若有（先）写（后）写的数据输出相关，可以串行，在保证对相关单元写入的先后次序的前提下，可以并行，但不能交换串行。,若同时有先写后读和先读后写两种相关，以交换数据为目的时，则必须是并行，并要求读与写完全同步，不允许顺序串性和交换串行。若没有任何相关，或仅有源数据相同时，可以并行，顺序串行或交换串行 交换串行的目的是：如果程序段之间不能并行，也可以让空闲的处理机提前去执行后面的程序段，这可以从宏观上增强各个程序段之间的并行度，加快作业完成的速度，改进系统的运行效率。,4、并行语言 为了增强程序并行性的识别能力，要求在程序语言中，能增设明确表示进程并发和汇合的语句。并行程序在多处理机上运行需要用控制机构管理并行任务的派生和汇合。并行任务的派生和汇合通常使用软件的手段来控制的。FORK派生 JOIN汇合 作为完整的并行语言，还要增加诸如程序分支、循环、并发进程间的通讯和同步以及数组和进程数组处理的描述。在多处理机上，处理机的机数多少是不会影响程序的编写的，其所编写的程序是可以在机数不同的多处理上通用的。,S1:U=A+B；S2:V=U/B；S3:W=A*U；S4:X=W-V；S5:Y=W*U；S6:Z=X/Y,10 U=A+B FORK 3020 V=U/B JOIN 2 GOTO 4030 W=A*U JOIN 240 FORK 60 50 X=W-VJOIN 2 GOTO 7060 Y=W*U JOIN 270 Z=X/Y,FORK 30,10+,20/,JOIN2,30*,GOTO 40,FORK 60,50-,60*,JOIN2,70/,FORK S2,S3,S4S1 A1=A1+A2 JOIN 4 GOTO*S2 A3=A3+A4 JOIN 4 GOTO*S3 A5=A5+A6 JOIN 4 GOTO*S4 A7=A7+A8 JOIN 4*FORK S6S5 A1=A1+A3 JOIN 2 GOTO S7S6 A5=A5+A7 JOIN 2S7 A1=A1+A5,CPU 1,CPU2,t,CPU 1,CPU2,t,CPU3,FORK S2,S3,S4S1 A1=A1+A2 JOIN 4 GOTO*S2 A3=A3+A4 JOIN 4 GOTO*S3 A5=A5+A6 JOIN 4 GOTO*S4 A7=A7+A8 JOIN 4,*FORK S6S5 A1=A1+A3 JOIN 2 GOTO S7S6 A5=A5+A7 JOIN 2S7 A1=A1+A5,*,*,*,